Answered: Consider a complete graph with n nodes.…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Consider a complete graph with n nodes.
1. Compute normalized degree centrality for each node as a function of n.
2. Compute normalized closeness centrality for each node as a function of n.
3. Compute normalized betweenness centrality for each node as a function of n.

Expert Solution

Step 1

Degree
In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.[1] The degree of a vertex $v$ is denoted $\deg(v)$ or $\deg v$ . The maximum degree of a graph G, denoted by $\Delta$ (G), and the minimum degree of a graph, denoted by $\delta$ (G), are the maximum and minimum degree of its vertices. In the graph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph.

Degree Centrality
Historically first and conceptually simplest is degree centrality, which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree. Accordingly, indegree is a count of the number of ties directed to the node and outdegree is the number of ties that the node directs to others. When ties are associated to some positive aspects such as friendship or collaboration, indegree is often interpreted as a form of popularity, and outdegree as gregariousness.

The degree centrality of a vertex $v$ , for a given graph $G:=(V,E)$ with $|V|$ vertices and $|E|$ edges, is defined as

$C_{D}(v)=\deg(v)$
Calculating degree centrality for all the nodes in a graph takes $\Theta(V^2)$ in a dense adjacency matrix representation of the graph, and for edges takes $\Theta(E)$ in a sparse matrix representation.

The definition of centrality on the node level can be extended to the whole graph, in which case we are speaking of graph centralization. Let $v*$ be the node with highest degree centrality in $G$ . Let $X:=(Y,Z)$ be the $|Y|$ node connected graph that maximizes the following quantity (with $y*$ being the node with highest degree centrality in $X$ ):

$H=\sum _{{j=1}}^{{|Y|}}[C_{D}(y*)-C_{D}(y_{j})]$
Correspondingly, the degree centralization of the graph $G$ is as follows:

$C_D(G)= \frac{\displaystyle{\sum^{|V|}_{i=1}{[C_D(v*)-C_D(v_i)]}}}{H}$
The value of $H$ is maximized when the graph $X$ contains one central node to which all other nodes are connected (a star graph), and in this case