Parallel Triangle Counting in Massive Streaming Graphs

被引：26

作者：

Tangwongsan, Kanat ^{[1
]}

Pavan, A. ^{[2
]}

Tirthapura, Srikanta ^{[2
]}

机构：

[1] IBM Res, Yorktown Hts, NY 10598 USA

[2] Iowa State Univ, Ames, IA USA

来源：

PROCEEDINGS OF THE 22ND ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT (CIKM'13) | 2013年

基金：

美国国家科学基金会;

关键词：

triangle counting; streaming algorithm; parallel algorithm; parallel cache oblivious (PCO); massive graphs;

D O I：

10.1145/2505515.2505741

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The number of triangles in a graph is a fundamental metric widely used in social network analysis, link classification and recommendation, and more. In these applications, modern graphs of interest tend to both large and dynamic. This paper presents the design and implementation of a fast parallel algorithm for estimating the number of triangles in a massive undirected graph whose edges arrive as a stream. Our algorithm is designed for shared-memory multicore machines and can make efficient use of parallelism and the memory hierarchy. We provide theoretical guarantees on performance and accuracy, and our experiments on real-world datasets show accurate results and substantial speedups compared to an optimized sequential implementation.

引用

页码：781 / 786

页数：6

共 30 条

[1] [Anonymous], 2011, P INT C WORLD WID WE, DOI DOI 10.1145/1963405.1963491
[2] [Anonymous], 2009, KDD09 15 ACM SIGKDD
[3] Bar-Yossef Z, 2002, SIAM PROC S, P623
[4] Becchetti Luca, 2008, Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, P16
[5] Berry J., 2011, Listing triangles in expected linear time on power law graphs with exponent at least 3 7
[6] Blelloch GE, 2011, SPAA 11: PROCEEDINGS OF THE TWENTY-THIRD ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P355
[7] Blelloch GE, 2010, SPAA '10: PROCEEDINGS OF THE TWENTY-SECOND ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P189
[8] Buriol LS, 2007, LECT NOTES COMPUT SC, V4698, P618
[9] ARBORICITY AND SUBGRAPH LISTING ALGORITHMS
CHIBA, N
NISHIZEKI, T
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (01) : 210 - 223
[10] Chu Shumo, 2011, P 17 ACM SIGKDD INT, P672

← 1 2 3 →