Linking the Network Centrality Measures Closeness and Degree

Abstract

Measuring the importance of nodes in a network with a centrality measure is a core task in any network application. There are many measures available and it is speculated that many encode similar information. We give an explicit non-linear relationship between two of the most popular measures of node centrality: degree and closeness. Based on a shortest-path tree approximation, we give an analytic derivation that shows the inverse of closeness is linearly dependent on the logarithm of degree. We show that our hypothesis works well for a range of networks produced from stochastic network models and for networks derived from 130 real-world data sets. We connect our results with previous results for other network distance scales such as average distance. Our results imply that measuring closeness is broadly redundant unless our relationship is used to remove the dependence on degree from closeness. The success of our relationship suggests that most networks can be approximated by shortest-path spanning trees which are all statistically similar two or more steps away from their root nodes.

arXiv commentv3 should be the same as the published version except for a couple of minor typos changed

References in corpus (13)

• Emergence of scaling in random networks
• Finding community structure in networks using the eigenvectors of matrices
• The structure of scientific collaboration networks
• Self-similar community structure in organisations
• Scale-Free Networks are Ultrasmall
• Consistency and differences between centrality measures across distinct classes of networks
• Metric structure of random networks
• Ring structures and mean first passage time in networks
• Distance distribution in random graphs and application to networks exploration
• Correlations among centrality measures in complex networks
• Scale-dependent measure of network centrality from diffusion dynamics
• Identifying time dependence in network growth
• Longest Path in the Price Model

Cited by in corpus (8)

• Local dominance unveils clusters in networks
• Ranking influential nodes in networks from partial information
• The nature and nurture of network evolution
• Scale-Free Networks beyond Power-Law Degree Distribution
• Effects of syndication network on specialisation and performance of venture capital firms
• Connectivity of random graphs after centrality-based vertex removal
• Uncovering Patterns of Participant-Invariant Influence in Networks
• Gromov Centrality: A Multi-Scale Measure of Network Centrality Using Triangle Inequality Excess