User:Miranche/Centrality

Within graph theory and network analysis, there are various measures of centrality of a vertex within a graph, used to indicate the relative importance of the vertex.

Degree centrality

For a graph $G:=(V,E)$ with n vertices, the degree centrality $C_{D}(v)$ for vertex $v$ is the fraction of the total number vertices that are the node's neighbors:

$C_{D}(v)={\frac {{\text{deg}}(v)}{n-1}}$

Betweenness centrality

Hue (from red=0 to blue=max) shows the node betweenness.

Betweenness is a centrality measure of a vertex within a graph (there is also an analogous betweenness measure for edges). Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.

For a graph $G:=(V,E)$ with n vertices, the betweenness $C_{B}(v)$ for vertex $v$ is:

$C_{B}(v)=\sum _{s\neq v\neq t\in V \atop s\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}$

where $\sigma _{st}$ is the number of shortest geodesic paths from s to t, and $\sigma _{st}(v)$ is the number of shortest geodesic paths from s to t that pass through a vertex v. This may be normalised by dividing through the number of pairs of vertices not including v, which is $(n-1)(n-2)$.

Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph. This takes $\Theta (V^{3})$ time with the Floyd–Warshall algorithm. On a sparse graph, Johnson's algorithm may be more efficient, taking $O(V^{2}\log V+VE)$ time. On unweighted graphs, calculating betweenness centrality takes $O(VE)$ time using Brandes' algorithm .

Closeness centrality

Closeness centrality $C_{C}(v)$ of a vertex $v$ can be defined as the reciprocal of the average geodesic distances to all other vertices of V :

$C_{C}(v)={\frac {n-1}{\sum _{t\in V\setminus v}d_{G}(v,t)}}.$

where $n\geq 2$ is the size of the network V. By convention, $d_{G}(v,t)\equiv n$ if there is no path between v and t, so that the lowest centrality value, that of an isolate, is $C_{C}=n^{-1}$.

Egonet software reports this value multiplied by 100.

Different methods and algorithms have been introduced to measure closeness. Two measures similar to the one above are described in Newman (2003) and Sabidussi (2003). In addition, Noh and Rieger (2003) discuss random-walk centrality, while Stephenson and Zelen (1989) introduce information centrality, which employs the harmonic instead of the arithmetic mean of path lengths. Dangalchev (2006), in order to measure the network vulnerability, modifies the definition for closeness so it can be used for disconnected graphs and the total closeness is easier to calculate:

$C_{C}(v)=\sum _{t\in V\setminus v}2^{-d_{G}(v,t)}.$

Further reading

• Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.
• Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31, 581-603.
• Freeman, L. C. (1977) A set of measures of centrality based on betweenness. Sociometry 40, 35--41.
• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16-61, LNCS 3418, Springer-Verlag.