User:Miranche/Centrality

__NOTOC__

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

Image:Graph betweenness.svg

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 + V E)$ time. On unweighted graphs, calculating betweenness centrality takes $O(V E)$ time using Brandes' algorithm {{cite document | author = Ulrik Brandes | title = A faster algorithm for betweenness centrality | url = http://www.cs.ucc.ie/~rb4/resources/Brandes.pdf }}.

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\ge 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)Newman, MEJ, 2003, Arxiv preprint [http://arxiv.org/abs/cond-mat/0309045 cond-mat/0309045]. and Sabidussi (2003)Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581--603.. In addition, Noh and Rieger (2003)J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004). discuss random-walk centrality, while Stephenson and Zelen (1989) introduce information centrality, which employs the harmonic instead of the arithmetic mean of path lengthsStephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples.

Social Networks 11, 1–37.. 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

calculateDangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).:

: $C_C(v)=\sum_{t \in V\setminus v}2^{-d_G(v,t)}.$

User:Miranche/Centrality

Degree centrality

Betweenness centrality

Closeness centrality

References

Further reading