Counting and Sampling Triangles from a Graph Stream

被引：106

作者：

Pavan, A. ^{[1
]}

Tangwongsan, Kanat ^{[2
]}

Tirthapura, Srikanta ^{[3
]}

Wu, Kun-Lung ^{[2
]}

机构：

[1] Iowa State Univ, Dept Comp Sci, Ames, IA 50011 USA

[2] IBM TJ Watson Res Ctr, Yorktown Hts, NY USA

[3] Iowa State Univ, Dept Elect & Comp Engn, Ames, IA 50011 USA

来源：

PROCEEDINGS OF THE VLDB ENDOWMENT | 2013年 / 6卷 / 14期

基金：

美国国家科学基金会;

关键词：

D O I：

10.14778/2556549.2556569

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a new space-efficient algorithm for counting and sampling triangles-and more generally, constant-sized cliques-in a massive graph whose edges arrive as a stream. Compared to prior work, our algorithm yields significant improvements in the space and time complexity for these fundamental problems. Our algorithm is simple to implement and has very good practical performance on large graphs.

引用

页码：1870 / 1881

页数：12

共 23 条

[1]

Ahn K. J., 2012, P 31 ACM SIGMODSIGAC, P5

[2]

Babcock B, 2002, SIAM PROC S, P633

[3]

Bar-Yossef Z, 2002, SIAM PROC S, P623

[4]

Becchetti L., 2008, SIGKDD, P16

[5]

Buriol L. S., 2006, PODS, P253, DOI DOI 10.1145/1142351.1142388

[6]

Buriol LS, 2007, LECT NOTES COMPUT SC, V4698, P618

[7] Curvature of co-links uncovers hidden thematic layers in the World Wide Web [J].

Eckmann, JP ;

Moses, E .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (09) :5825-5829

[8]

Jha M., 2012, ABS12122264 CORR

[9]

Jowhari H, 2005, LECT NOTES COMPUT SC, V3595, P710, DOI 10.1007/11533719_72

[10]

Kane DM, 2012, LECT NOTES COMPUT SC, V7392, P598, DOI 10.1007/978-3-642-31585-5_53

← 1 2 3 →