Bounded arboricity to determine the local structure of sparse graphs

Abstract. A known approach of detecting dense subgraphs (communities) in large sparse graphs involves first computing the probability vectors for short ran-dom walks on the graph, and then using these probability vectors to detect the communities, see Latapy and Pons [2005]. 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 vec-tors 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, see Barabási and Albert [1999]. Our approach is extensible to other models of computation (PRAM, BSP or out-of-core compu-tation) and also w.h.p. stays within the same complexity bounds for Erdős Renyi graphs.