Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

Abstract : In this paper, we propose a new algorithm that computes the radius and the diameter of a weakly connected digraph G=(V,E), by finding bounds through heuristics and improving them until they are validated. Although the worst-case running time is O(|V||E|), we will experimentally show that it performs much better in the case of real-world networks, finding the radius and diameter values after 10–100 BFSs instead of |V| BFSs (independently of the value of |V|), and thus having running time O(|E|) in practice. As far as we know, this is the first algorithm able to compute the diameter of weakly connected digraphs, apart from the naive algorithm, which runs in time Ω(|V||E|) performing a BFS from each node. In the particular cases of strongly connected directed or connected undirected graphs, we will compare our algorithm with known approaches by performing experiments on a dataset composed by several real-world networks of different kinds. These experiments will show that, despite its generality, the new algorithm outperforms all previous methods, both in the radius and in the diameter computation, both in the directed and in the undirected case, both in average running time and in robustness. Finally, as an application example, we will use the new algorithm to determine the solvability over time of the “Six Degrees of Kevin Bacon” game, and of the “Six Degrees of Wikipedia” game. As a consequence, we will compute for the first time the exact value of the radius and the diameter of the whole Wikipedia digraph.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 586, pp.59-80. 〈10.1016/j.tcs.2015.02.033〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248555
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 16 juin 2017 - 15:34:39
Dernière modification le : jeudi 15 novembre 2018 - 20:26:57
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 14:38:17

Fichier

Fast diameter and radius BFS-b...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A. Kosters, Andrea Marino, et al.. Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs. Theoretical Computer Science, Elsevier, 2015, 586, pp.59-80. 〈10.1016/j.tcs.2015.02.033〉. 〈hal-01248555〉

Partager

Métriques

Consultations de la notice

280

Téléchargements de fichiers

240