User:Miranche/Centrality

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

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

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 ${\displaystyle G:=(V,E)}$ with n vertices, the betweenness ${\displaystyle C_{B}(v)}$ for vertex ${\displaystyle v}$ is:

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

where ${\displaystyle \sigma _{st}}$ is the number of shortest geodesic paths from s to t, and ${\displaystyle \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 ${\displaystyle (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 ${\displaystyle \Theta (V^{3})}$ time with the Floyd–Warshall algorithm. On a sparse graph, Johnson's algorithm may be more efficient, taking ${\displaystyle O(V^{2}\log V+VE)}$ time. On unweighted graphs, calculating betweenness centrality takes ${\displaystyle O(VE)}$ time using Brandes' algorithm ^[1].

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

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

where ${\displaystyle n\geq 2}$ is the size of the network V. By convention, ${\displaystyle 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 ${\displaystyle 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)^[2] and Sabidussi (2003)^[3]. In addition, Noh and Rieger (2003)^[4] discuss random-walk centrality, while Stephenson and Zelen (1989) introduce information centrality, which employs the harmonic instead of the arithmetic mean of path lengths^[5]. 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^[6]:

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