论文标题
退化如何有助于图中的三角计数
How the Degeneracy Helps for Triangle Counting in Graph Streams
论文作者
论文摘要
我们回顾了图流中三角计数估计的充分研究问题。给定的图表示为$ m $边缘的流，我们的目的是使用小空间算法计算$（1 \ pm \ varepsilon）$ - 近似与三角形计数$ t $。对于任意顺序和恒定的通过数，已知空间复杂性本质上是$θ（\ min（m^{3/2}/t，m/\ sqrt {t}））$（McGregor等，Pods，Pods 2016，Bera等人，Bera等人，Stacs 2017）。 我们给出了一个（恒定的通过，任意的）流算法，该算法可以绕过\ emph {低退化图}的下层结合。堕落的$κ$是密度的细微量度，恒定变性图的类别非常丰富（包含平面图，次要闭合族和优先附着图）。我们设计具有空间复杂性$ \ widetilde {o}（mκ/t）$的流算法。对于恒定的退化图，此键是$ \ widetilde {o}（m/t）$，它明显小于$ m^{3/2}/t $和$ m/\ sqrt {t} $。我们通过$ω（Mκ/T）$的几乎匹配的下限匹配算法结果。
We revisit the well-studied problem of triangle count estimation in graph streams. Given a graph represented as a stream of $m$ edges, our aim is to compute a $(1\pm\varepsilon)$-approximation to the triangle count $T$, using a small space algorithm. For arbitrary order and a constant number of passes, the space complexity is known to be essentially $Θ(\min(m^{3/2}/T, m/\sqrt{T}))$ (McGregor et al., PODS 2016, Bera et al., STACS 2017). We give a (constant pass, arbitrary order) streaming algorithm that can circumvent this lower bound for \emph{low degeneracy graphs}. The degeneracy, $κ$, is a nuanced measure of density, and the class of constant degeneracy graphs is immensely rich (containing planar graphs, minor-closed families, and preferential attachment graphs). We design a streaming algorithm with space complexity $\widetilde{O}(mκ/T)$. For constant degeneracy graphs, this bound is $\widetilde{O}(m/T)$, which is significantly smaller than both $m^{3/2}/T$ and $m/\sqrt{T}$. We complement our algorithmic result with a nearly matching lower bound of $Ω(mκ/T)$.
