Paper Info
Title
k-Centralities: local approximations of global measures based on shortest paths
Abstract
A lot of centrality measures have been developed to analyze different aspects of importance. Some of the most popular centrality measures (e.g. betweenness centrality, closeness centrality) are based on the calculation of shortest paths. This characteristic limits the applicability of these measures for larger networks. In this article we elaborate on the idea of bounded-distance shortest paths calculations. We claim criteria for k-centrality measures and we introduce one algorithm for calculating both betweenness and closeness based centralities. We also present normalizations for these measures. We show that k-centrality measures are good approximations for the corresponding centrality measures by achieving a tremendous gain of calculation time and also having linear calculation complexity O(n) for networks with constant average degree. This allows researchers to approximate centrality measures based on shortest paths for networks with millions of nodes or with high frequency in dynamically changing networks.
Year
DOI
Venue
2012
10.1145/2187980.2188239
WWW (Companion Volume)
Keywords
Field
DocType
bounded-distance shortest paths calculation,k-centrality measure,local approximation,shortest path,popular centrality measure,closeness centrality,approximate centrality,calculation time,centrality measure,global measure,corresponding centrality measure,betweenness centrality,high frequency
Network science,Mathematical optimization,Random walk closeness centrality,Closeness,Computer science,Centrality,Network controllability,Betweenness centrality,Network theory,Katz centrality
Conference
Citations 
PageRank 
References 
24
0.90
13
Authors
2
Name
Order
Citations
PageRank
Jürgen Pfeffer134626.57
Kathleen M. Carley22507270.10