Electrical and Computer Engineering, Computer Science
39th International Conference on Very Large Data Bases (VLDB 2013)
Link to Published Version
Journal or Book Title
Proceedings of the VLDB Endowment
August 26-30, 2013
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.
Pavan, A.; IBM T. J. Watson Research Center; IBM T. J. Watson Research Center; and Tirthapura, Srikanta, "Counting and Sampling Triangles from a Graph Stream" (2013). Electrical and Computer Engineering Conference Papers, Posters and Presentations. 58.