Bounded Arboricity to Determine the Local Structure of Sparse Graphs

Gaurav Goel 1, 2 Jens Gustedt 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A known approach of detecting dense subgraphs communities in large sparse graphs involves first computing the probability~vectors for short random~walks on the graph, and then using these probability vectors to detect the communities. In this paper we focus on the first part of such an approach i.e. the computation of the probability vectors for the random walks, and propose a more efficient algorithm for computing these vectors in time complexity that is linear in the size of the output, in case the input graphs are restricted to a family of graphs of bounded arboricity. Such classes of graphs cover a large number of cases of interest, e.g all minor closed graph classes (planar graphs, graphs of bounded treewidth etc) and random graphs within the preferential attachment model. Our approach is extensible to other models of computation (PRAM, BSP or out-of-core computation) and also w.h.p. stays within the same complexity bounds for Erdös~Renyi graphs.
Type de document :
Communication dans un congrès
32 International Workshop on Graph-Theoretic Concepts in Computer Science - WG 2006, Jun 2006, Bergen, Norway. Springer Berlin / Heidelberg, 4271, pp.159-167, 2006, Lecture Notes in Computer Science. 〈10.1007/11917496_15〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00103755
Contributeur : Jens Gustedt <>
Soumis le : jeudi 5 octobre 2006 - 11:29:21
Dernière modification le : samedi 21 juillet 2018 - 13:38:01
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 11:16:03

Identifiants

Collections

Citation

Gaurav Goel, Jens Gustedt. Bounded Arboricity to Determine the Local Structure of Sparse Graphs. 32 International Workshop on Graph-Theoretic Concepts in Computer Science - WG 2006, Jun 2006, Bergen, Norway. Springer Berlin / Heidelberg, 4271, pp.159-167, 2006, Lecture Notes in Computer Science. 〈10.1007/11917496_15〉. 〈inria-00103755〉

Partager

Métriques

Consultations de la notice

323

Téléchargements de fichiers

305