Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Jens Gustedt <>
Submitted on : Thursday, October 5, 2006 - 11:29:21 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Thursday, September 20, 2012 - 11:16:03 AM




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. pp.159-167, ⟨10.1007/11917496_15⟩. ⟨inria-00103755⟩



Record views


Files downloads