Counting Arbitrary Subgraphs in Data Streams
Counting Arbitrary Subgraphs in Data Streams
复制标题
计算数据流中的任意子图
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
He Sun
中科院分区：
文献类型：
--
作者：
D. Kane;K. Mehlhorn;Thomas Sauerwald;He Sun
研究了数据流中的子图计数问题。我们提供了第一个非平凡的估计近似计数的出现次数的任意子图H的恒定大小的（大）图G。我们的估计器在旋转栅门模型中工作，即，可以处理边插入和边删除，并且适用于分布式设置。在此之前的工作，只有少数非正则图估计已知的情况下，边插入，留下的问题，计数一般的子图在旋转栅门模型敞开。我们进一步证明了我们的估计的适用性，通过分析其浓度的几个图H和G是一个幂律图的情况下。
We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph.