Counting and sampling triangles from a graph stream
Open Access
- 1 September 2013
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 6 (14) , 1870-1881
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Colorful triangle counting and a MapReduce implementationInformation Processing Letters, 2012
- Counting Arbitrary Subgraphs in Data Streams2012
- Approximate Counting of Cycles in StreamsLecture Notes in Computer Science, 2011
- Spectral counting of triangles via element-wise sparsification and triangle-based link recommendationSocial Network Analysis and Mining, 2010
- Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study2005
- New Streaming Algorithms for Counting Triangles in Graphs2005
- Approximating Clustering Coefficient and TransitivityJournal of Graph Algorithms and Applications, 2005
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Curvature of co-links uncovers hidden thematic layers in the World Wide WebProceedings of the National Academy of Sciences, 2002
- Random graph models of social networksProceedings of the National Academy of Sciences, 2002