KIT | KIT-Bibliothek | Impressum | Datenschutz

Approximating Betweenness Centrality in Fully-dynamic Networks. [Preprint]

Bergamini, Elisabetta; Meyerhenke, Henning

Abstract:
Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of betweenness in networks that change over time. In this paper we propose the first betweenness centrality approximation algorithms with a provable guarantee on the maximum approximation error for dynamic networks. Several new intermediate algorithmic results contribute to the respective approximation algorithms: (i) new upper bounds on the vertex diameter, (ii) the first fully-dynamic algorithm for updating an approximation of the vertex diameter in undirected graphs, and (iii) an algorithm with lower time complexity for updating single-source shortest paths in unweighted graphs after a batch of edge actions. Using approximation, our algorithms are the first to make in-memory computation of betweenness in dynamic networks with millions of edges feasible. Our experiments show that our alg ... mehr

Open Access Logo


Seitenaufrufe: 18
seit 06.05.2018
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Buchaufsatz
Jahr 2015
Sprache Englisch
Identifikator KITopen-ID: 1000055784
Erschienen in arXiv [cs.DS] : Data Structures and Algorithms
Seiten arXiv:1510.07971
Bemerkung zur Veröffentlichung arCiv.org
Externe Relationen Siehe auch
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page