KIT | KIT-Bibliothek | Impressum
Open Access Logo
DOI: 10.5445/IR/1000049418

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 e ... mehr

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2015
Sprache Englisch
Identifikator ISSN: 2190-4782
URN: urn:nbn:de:swb:90-494186
KITopen ID: 1000049418
Verlag 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