Computing Top-k Closeness Centrality Faster in Unweighted Graphs

Abstract : Given a connected graph G = (V,E), the closeness centrality of a vertex v is defined as (n-1 / \Sigma_{w \in V} d(v,w). This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the k most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the paper, we prove that it is not solvable in time O(|E|^{2-epsilon) on directed graphs, for any constant epsilon > 0, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the k most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top k nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the 10 most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page p to a page q if p contains a link to q.
Type de document :
Communication dans un congrès
Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, 2016, Arlington, United States. 2016, 〈10.1137/1.9781611974317.6〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01390137
Contributeur : Marie-France Sagot <>
Soumis le : lundi 14 novembre 2016 - 11:08:41
Dernière modification le : mercredi 11 avril 2018 - 01:53:45
Document(s) archivé(s) le : mercredi 15 mars 2017 - 04:18:53

Fichier

closeness-JV.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke. Computing Top-k Closeness Centrality Faster in Unweighted Graphs. Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, 2016, Arlington, United States. 2016, 〈10.1137/1.9781611974317.6〉. 〈hal-01390137〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

77