KIT | KIT-Bibliothek | Impressum | Datenschutz

Computing Top-k Closeness Centrality Faster in Unweighted Graphs. (Technical Report)

Bergamini, Elisabetta; Meyerhenke, Henning

Centrality indices are widely used analytic measures for the importance of nodes in a network. Closeness centrality is very popular among these measures. For a single node v, it takes the sum of the distances of v to all other nodes into account. The currently best algorithms in practical applications for computing the closeness for all nodes exactly in unweighted graphs are based on breadth-first search (BFS) from every node. Thus, even for sparse graphs, these algorithms require quadratic running time in the worst case, which is prohibitive for large networks.
In many relevant applications, however, it is unnecessary to compute closeness values for all nodes. Instead, one requires only the k nodes with the highest closeness values in descending order. Thus, we present a new algorithm for computing this top-k ranking in unweighted graphs. Following the rationale of previous work, our algorithm significantly reduces the number of traversed edges. It does so by computing upper bounds on the closeness and stopping the current BFS search when k nodes already have higher closeness than the bounds computed for the other nodes.
In our experiments with real-world and synthetic instances of various types, one of these new bounds is good for small-world graphs with low diameter (such as social networks), while the other one excels for graphs with high diameter (such as road networks). ... mehr

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000049418
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2015
Sprache Englisch
Identifikator ISSN: 2190-4782
KITopen-ID: 1000049418
Verlag KIT, Karlsruhe
Umfang 14 S.
Serie Karlsruhe Reports in Informatics ; 2015,7
Schlagworte Closeness centrality, algorithmic network analysis, graph algorithms, algorithm engineering
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page