K-centralities: Local approximations of global measures based on shortest paths

Jürgen Pfeffer, Kathleen M. Carley

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

51 Scopus citations

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 boundeddistance 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 Θ(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. Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Original languageEnglish
Title of host publicationWWW'12 - Proceedings of the 21st Annual Conference on World Wide Web Companion
Pages1043-1050
Number of pages8
DOIs
StatePublished - 2012
Externally publishedYes
Event21st Annual Conference on World Wide Web, WWW'12 - Lyon, France
Duration: 16 Apr 201220 Apr 2012

Publication series

NameWWW'12 - Proceedings of the 21st Annual Conference on World Wide Web Companion

Conference

Conference21st Annual Conference on World Wide Web, WWW'12
Country/TerritoryFrance
CityLyon
Period16/04/1220/04/12

Keywords

  • Betweenness centrality
  • Centrality approximation
  • Closeness centrality
  • Large networks
  • Shortest paths

Fingerprint

Dive into the research topics of 'K-centralities: Local approximations of global measures based on shortest paths'. Together they form a unique fingerprint.

Cite this