Triangle and Four Cycle Counting in the Data Stream Model
Triangle and Four Cycle Counting in the Data Stream Model
复制标题
数据流模型中的三角和四周期计数
DOI：
10.1145/3375395.3387652
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vorotnikova, Sofya
中科院分区：
文献类型：
--
作者：
McGregor, Andrew;Vorotnikova, Sofya
图中循环数的估计问题是数据流模型中研究最广泛的图问题之一。数据流模型的三个相关变体包括：任意顺序模型，其中流由任意顺序的图边组成；随机顺序模型，其中边随机排列；邻接表顺序模型，其中所有与同一顶点相关的边连续出现。在本文中，我们重点讨论了这些模型中的三角形和四循环计数问题。我们改进了最先进的结果如下，其中n是顶点的数量，m是边的数量，T是图中三角形的数量/四个循环（即估计的数量）：随机顺序模型：我们提出了一个单遍算法(1+ε)-使用~O（ε-2 m/√T）空间近似三角形的数量，并证明这是在T≤√m范围内的最优算法。Cormode和Jowhari在~O（ε-4.5 m/√T）空间上给出了最好的近似结果（3+ε）。第一版。Sci, 2017)。邻接表模型：我们提出了一种算法，该算法使用两次遍历和~O（ε-4 m/√T）空间返回4循环数的(1+ε)-近似值。Kallaugher等人（PODS~2019）提出了最好的先前结果，即使用~O（m/T3/8）空间的常数近似。我们还证明了如果T=Ω（n2），在a) polylog(n)空间中（1+ε)-单次逼近是可能的；如果T=Ω(n)，在b） ~O(n)空间中(1+ε)-近似是可能的。任意阶模型：当T=Ω（n2）时，我们提出了一种使用~O（ε-2 m/T1/4）空间的(1+ε)-三遍算法和使用~O（ε-2 n）空间的一遍算法。现有最好的结果是Bera和Chakrabarti （STACS~2017）提出的~O（ε-2 m2/T）空间的（1+ε）近似。我们还给出了一个多遍下界和另一种区分无四环图和多四环图的算法。
The problem of estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this paper, we focus on the problem of triangle and four-cycle counting in these models. We improve over the state-of-the-art results as follows, where n is the number of vertices, m is the number of edges and T is the number of triangles/four-cycles in the graph (i.e., the quantity being estimated): Random Order Model: We present a single-pass algorithm that (1+ε)-approximates the number of triangles using ~O(ε-2 m/√T) space and prove that this is optimal in the range T ≤ √m. The best previous result, a (3+ε)-approximation using ~O(ε-4.5 m/√T) space, was presented by Cormode and Jowhari~(Theor. Comput. Sci. 2017). Adjacency List Model: We present an algorithm that returns a (1+ε)-approximation of the number of 4-cycles using two passes and ~O(ε-4 m/√T) space. The best previous result, a constant approximation using ~O(m/T3/8) space, was presented by Kallaugher et al. (PODS~2019). We also show that (1+ε)-approximation in a single pass is possible in a) polylog(n) space if T=Ω(n2) and b) ~O(n) space if T=Ω(n). Arbitrary Order Model: We present a three-pass algorithm that (1+ε)-approximates the number of 4-cycles using ~O(ε-2 m/T1/4) space and a one-pass algorithm that uses ~O(ε-2 n) space when T=Ω(n2). The best existing result, a (1+ε)-approximation using ~O(ε-2 m2/T) space, was presented by Bera and Chakrabarti (STACS~2017). We also show a multi-pass lower bound and another algorithm for distinguishing graphs with no four cycles and graphs with many 4-cycles.
登录
查看更多内容
计算数据流中的任意子图
DOI：
--
发表时间：
2012
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
D. Kane;K. Mehlhorn;Thomas Sauerwald;He Sun
通讯作者：
He Sun
再看一下图形流中的三角形计数
DOI：
10.1016/j.tcs.2014.07.025
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Graham Cormode;H. Jowhari
通讯作者：
H. Jowhari
DOI：
10.1145/1374376.1374470
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
Amit Chakrabarti;Graham Cormode;A. Mcgregor
通讯作者：
A. Mcgregor
三角形稀疏器
DOI：
--
发表时间：
2011
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Charalampos E. Tsourakakis;M. N. Kolountzakis;G. Miller
通讯作者：
G. Miller
通过草图的绘制来宣告独立
DOI：
--
发表时间：
2008
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
P. Indyk;A. Mcgregor
通讯作者：
A. Mcgregor