Counting triangles in data streams
Authors:
Open Access
- 26 June 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 253-262
Abstract
We present two space bounded random sampling algorithms that compute an approximation of the number of triangles in an undirected graph given as a stream of edges. Our first algorithm does not make any assumptions on the order of edges in the stream. It uses space that is inversely related to the ratio between the number of triangles and the number of triples with at least one edge in the induced subgraph, and constant expected update time per edge. Our second algorithm is designed for incidence streams (all edges incident to the same vertex appear consecutively). It uses space that is inversely related to the ratio between the number of triangles and length 2 paths in the graph and expected update time O(log |V |·(1+s ·|V |/|E|)), where s is the space requirement of the algorithm. These results significantly improve over previous work [20, 8]. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size and so they provide a basic tool to analyze the structure of large graphs. They have many applications, for example, in the discovery of Web communities, the computation of clustering and transitivity coefficient, and discovery of frequent patterns in large graphs. We have implemented both algorithms and evaluated their performance on networks from different application domains. The sizes of the considered graphs varied from about 8, 000 nodes and 40, 000 edges to 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with parameter s = 1, 000, 10, 000, 100, 000, 1, 000, 000 to evaluate running time and approximation guarantee. Both algorithms appear to be time efficient for these sample sizes. The approximation quality of the first algorithm was varying significantly and even for s = 1, 000, 000 we had more than 10% deviation for more than half of the instances. The second algorithm performed much better and even for s = 10, 000 we had an average deviation of less than 6% (taken over all but the largest instance for which we could not compute the number of triangles exactly). Copyright 2006 ACMKeywords
This publication has 11 references indexed in Scilit:
- Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study2005
- Graph indexing2004
- Uniform hashing in constant time and linear space2003
- Algorithmics and applications of tree and graph searching2002
- Data-streams and histograms2001
- Trawling the Web for emerging cyber-communitiesComputer Networks, 1999
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985
- Matrix measures for transitivity and balance*The Journal of Mathematical Sociology, 1979