Bounded Arboricity to Determine the Local Structure of Sparse Graphs
Bounded Arboricity to Determine the Local Structure of Sparse Graphs
复制标题
有界树木性确定稀疏图的局部结构
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
J. Gustedt
中科院分区：
文献类型：
--
作者：
Gaurav Goel;J. Gustedt
检测大型稀疏图中的稠密子图（社区）的已知方法涉及首先计算图上的短随机游走的概率向量，然后使用这些概率向量来检测社区，参见Latterfly和脑桥[2005]。在本文中，我们专注于这种方法的第一部分，即随机游走的概率向量的计算，并提出了一个更有效的算法，用于计算这些向量的时间复杂度是线性的输出的大小，在输入图被限制为一个家庭的有界荫度的图。这类图涵盖了大量感兴趣的情况，例如所有次要的闭图类（平面图，有界树宽的图等）和偏好连接模型中的随机图，参见Barabasi和Albert [1999]。我们的方法可扩展到其他计算模型（PRAM，BSP或核外计算），并且w.h.p.保持在Erdos Renyi图的相同复杂度范围内。
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, 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 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, see Barabasi and Albert [1999]. 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.