How to Count Triangles, without Seeing the Whole Graph
How to Count Triangles, without Seeing the Whole Graph
复制标题
DOI：
10.1145/3394486.3403073
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Suman Kalyan Bera;Seshadhri Comandur
中科院分区：
文献类型：
--
作者：
Suman Kalyan Bera;Seshadhri Comandur
三角形计数是大型图分析中的一个基本问题。在这个问题上有大量的工作，在不同的流和分布式模型，但所有这些算法都需要阅读整个输入图。在许多情况下，我们无法访问整个图，只能对图的一小部分进行采样（通常通过爬行）。在这样的设置下，我们如何准确地估计图的三角形计数？本文正式研究了Dasgupta等人（WWW '14）和Chierichetti等人（WWW '16）提出的随机游走访问模型中的三角计数问题。我们可以访问图的任意种子顶点，并且只能执行随机游走。该模型在访问方面具有限制性，并捕捉了收集真实世界图表的挑战。在这个模型中，即使对均匀随机顶点进行采样也是一项艰巨的任务。尽管有这些挑战，我们设计了一个可证明的和实用的算法，TETRIS，在这个模型中的三角形计数。TETRIS是第一个可证明的次线性算法（对于大多数自然的参数设置），它近似于随机游走模型中的三角形计数，用于具有低混合时间的图。我们的结果建立在最近的进展，在理论上的次线性算法。TETRIS构建的最后一个样本是随机游走和邻域度偏差采样的精心组合。从经验上讲，TETRIS可以准确地计算各种大型图形上的三角形，通过查看3%的边数，可以在5%的相对误差内获得估计值。
Triangle counting is a fundamental problem in the analysis of large graphs. There is a rich body of work on this problem, in varying streaming and distributed models, yet all these algorithms require reading the whole input graph. In many scenarios, we do not have access to the whole graph, and can only sample a small portion of the graph (typically through crawling). In such a setting, how can we accurately estimate the triangle count of the graph? We formally study triangle counting in the random walk access model introduced by Dasgupta et al (WWW '14) and Chierichetti et al (WWW '16). We have access to an arbitrary seed vertex of the graph, and can only perform random walks. This model is restrictive in access and captures the challenges of collecting real-world graphs. Even sampling a uniform random vertex is a hard task in this model. Despite these challenges, we design a provable and practical algorithm, TETRIS, for triangle counting in this model. TETRIS is the first provably sublinear algorithm (for most natural parameter settings) that approximates the triangle count in the random walk model, for graphs with low mixing time. Our result builds on recent advances in the theory of sublinear algorithms. The final sample built by TETRIS is a careful mix of random walks and degree-biased sampling of neighborhoods. Empirically, TETRIS accurately counts triangles on a variety of large graphs, getting estimates within 5% relative error by looking at 3% of the number of edges.