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(x)={\frac {1}{\sum _{y}d(y,x)}}.}$

where ${\displaystyle d(y,x)}$ is the distance between vertices ${\displaystyle x}$ and ${\displaystyle y}$. 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. For large graphs this difference becomes inconsequential so the ${\displaystyle -1}$ is dropped resulting in:

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

Normalization allows comparisons between nodes of graphs of different sizes.

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 link, but low closeness centrality from incoming links).

In disconnected graphs

When a graph is not strongly connected, a widespread idea is that of using the sum of reciprocal of distances, instead of the reciprocal of the sum of distances, with the convention ${\displaystyle 1/\infty =0}$:

${\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}.}$

The most natural modification of Bavelas's definition of closeness is following the general principle proposed by Marchiori and Latora (2000)[3] that in graphs with infinite distances the harmonic mean behaves better than the arithmetic mean. Indeed, Bavelas's closeness can be described as the denormalized reciprocal of the arithmetic mean of distances, whereas harmonic centrality is the denormalized reciprocal of the harmonic mean of distances.

This idea was explicitly stated for undirected graphs under the name valued centrality by Dekker (2005)[4] and under the name harmonic centrality by Rochat (2009),[5] axiomatized by Garg (2009)[6] and proposed once again later by Opsahl (2010).[7] It was studied on general directed graphs by Boldi and Vigna (2014).[8] This idea is also quite similar to market potential proposed in Harris (1954)[9] which now often goes by the term market access.[10]

Variants

Dangalchev (2006),[11] in a work on network vulnerability proposes for undirected graphs a different definition:

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

This definition is used effectively for disconnected graphs and allows to create convenient formulae for graph operations. For example:

If a graph ${\displaystyle G_{1}+G_{2}}$ is created by linking node ${\displaystyle p}$ of graph ${\displaystyle G_{1}}$ to node ${\displaystyle q}$ of graph ${\displaystyle G_{2}}$ then the combined closeness is:

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));}$

if a graph ${\displaystyle G_{1}+G_{2}}$ is created by collapsing node ${\displaystyle p}$ of graph ${\displaystyle G_{1}}$ and node ${\displaystyle q}$ of graph ${\displaystyle G_{2}}$ into one node then the closeness is:[12]

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).}$

If graph ${\displaystyle T(G)}$ is the thorn graph of graph ${\displaystyle G}$, which has ${\displaystyle n}$ nodes, then ${\displaystyle T(G)}$ closeness is:[13]

${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

The natural generalization of this definition is:[14]

${\displaystyle D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},}$

where ${\displaystyle \alpha }$ belongs to (0,1). As ${\displaystyle \alpha }$ increases from 0 to 1, the generalized closeness changes from local characteristic (degree) to global (number of connected nodes).

The information centrality of Stephenson and Zelen (1989) is another closeness measure, which computes the harmonic mean of the resistance distances towards a vertex x, which is smaller if x has many paths of small resistance connecting it to other vertices.[15]

In the classic definition of the closeness centrality, the spread of information is modeled by the use of shortest paths. This model might not be the most realistic for all types of communication scenarios. Thus, related definitions have been discussed to measure closeness, like the random walk closeness centrality introduced by Noh and Rieger (2004). It measures the speed with which randomly walking messages reach a vertex from elsewhere in the graph—a sort of random-walk version of closeness centrality.[16] Hierarchical closeness of Tran and Kwon (2014)[17] is an extended closeness centrality to deal still in another way with the limitation of closeness in graphs that are not strongly connected. The hierarchical closeness explicitly includes information about the range of other nodes that can be affected by the given node.

See also

• Centrality
• Random walk closeness centrality
• Betweenness centrality

References

1. Alex Bavelas. Communication patterns in task-oriented groups. J. Acoust. Soc. Am, 22(6):725–730, 1950.
2. Sabidussi, G (1966). "The centrality index of a graph". Psychometrika. 31 (4): 581–603. doi:10.1007/bf02289527. hdl:10338.dmlcz/101401. PMID 5232444.
3. Marchiori, Massimo; Latora, Vito (2000), "Harmony in the small-world", Physica A: Statistical Mechanics and Its Applications, 285 (3–4): 539–546, arXiv:cond-mat/0008357, Bibcode:2000PhyA..285..539M, doi:10.1016/s0378-4371(00)00311-3
4. Dekker, Anthony (2005). "Conceptual Distance in Social Network Analysis". Journal of Social Structure. 6 (3).
5. Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index (PDF). Applications of Social Network Analysis, ASNA 2009.
6. Manuj Garg (2009), Axiomatic Foundations of Centrality in Networks, doi:10.2139/ssrn.1372441
7. Tore Opsahl (2010-03-20). "Closeness centrality in networks with disconnected components".
8. Boldi, Paolo; Vigna, Sebastiano (2014), "Axioms for Centrality", Internet Mathematics, 10 (3–4): 222–262, doi:10.1080/15427951.2013.865686
9. C. D. Harris. The, market as a factor in the localization of industry in the united states. Annals of the association of American geographers, 44(4):315–348, 1954
10. Gutberlet, Theresa. Cheap Coal versus Market Access: The Role of Natural Resources and Demand in Germany's Industrialization. Working Paper. 2014.
11. Ch, Dangalchev (2006). "Residual Closeness in Networks". Physica A. 365 (2): 556. doi:10.1016/j.physa.2005.12.020.
12. Ch, Dangalchev (2020). "Additional Closeness and Networks Growth". Fundamenta Informaticae. 176 (1): 1–15. doi:10.3233/FI-2020-1960.
13. Ch, Dangalchev (2018). "Residual Closeness of Generalized Thorn Graphs". Fundamenta Informaticae. 162 (1): 1–15. doi:10.3233/FI-2018-1710.
14. Ch, Dangalchev (2011). "Residual Closeness and Generalized Closeness". IJFCS. 22 (8): 1939–1948. doi:10.1142/s0129054111009136.
15. Stephenson, K. A.; Zelen, M. (1989). "Rethinking centrality: Methods and examples". Social Networks. 11: 1–37. doi:10.1016/0378-8733(89)90016-6.
16. Noh, J. D.; Rieger, H. (2004). "Random Walks on Complex Networks". Phys. Rev. Lett. 92 (11): 118701. arXiv:cond-mat/0307719. Bibcode:2004PhRvL..92k8701N. doi:10.1103/physrevlett.92.118701. PMID 15089179.
17. Tran, T.-D. and Kwon, Y.-K. Hierarchical closeness efficiently predicts disease genes in a directed signaling network, Computational biology and chemistry.