Closeness centrality

In a connected graph, closeness centrality (or closeness) of a node is a measure of centrality in a network, calculated as the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph. Thus, the more central a node is, the closer it is to all other nodes.

Closeness was defined by Bavelas (1950) as the reciprocal of the farness,^[1][2] that is:

${\displaystyle C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}},}$

where ${\displaystyle d(y,x)}$ is the distance (length of the shortest path) between vertices ${\displaystyle x}$ and ${\displaystyle y}$. This unnormalised version of closeness is sometimes known as status.^[3][4][5] When speaking of closeness centrality, people usually refer to its normalized form which represents the average length of the shortest paths instead of their sum. It is generally given by the previous formula multiplied by ${\displaystyle N-1}$, where ${\displaystyle N}$ is the number of nodes in the graph resulting in:

${\displaystyle C(x)={\frac {N-1}{\sum _{y}d(y,x)}}.}$

The normalization of closeness simplifies the comparison of nodes in graphs of different sizes. For large graphs, the minus one in the normalisation becomes inconsequential and it is often dropped.

As one of the oldest centrality measures, closeness is often given in general discussions of network centrality measures in introductory texts^[6][7][8] or in articles comparing different centrality measures.^{[9][10][11][12]} The values produced by many centrality measures can be highly correlated.^[9][13][11] In particular, closeness and degree have been shown^[12] to be related in many networks through an approximate relationship

${\displaystyle {\frac {1}{C(x)}}\approx {\frac {-1}{\ln(z-1)}}\ln(k_{x})+\beta }$

where ${\textstyle k_{x}}$ is the degree of vertex ${\displaystyle x}$ while ${\displaystyle z}$ and β are parameters found by fitting closeness and degree to this formula. The z parameter represents the branching factor, the average degree of nodes (excluding the root node and leaves) of the shortest-path trees used to approximate networks when demonstrating this relationship.^[12] This is never an exact relationship but it captures a trend seen in many real-world networks.

Closeness is related to other length scales used in network science. For instance, the average shortest path length ${\textstyle \langle \ell \rangle }$, the average distance between vertices in a network, is simply the average of the inverse closeness values

${\displaystyle \langle \ell \rangle ={\frac {1}{N}}\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d(y,x)}$ .

Taking distances from or to all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in directed graphs (e.g. a website can have a high closeness centrality from outgoing links, but low closeness centrality from incoming links).