Fast Triangle Counting through Wedge Sampling
Preprint
Abstract
Graphs and networks are used to model interactions in a variety of contexts, and there is a growing need to be able to quickly assess the qualities of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle based and give a measure of the connectedness of "friends of friends." Counting the number of triangles in a graph has, therefore, received considerable attention in recent years. We propose new sampling-based methods for counting the number of triangles or the number of triangles with vertices of specified degree in an undirected graph and for counting the number of each type of directed triangle in a directed graph. The number of samples depends only on the desired relative accuracy and not on the size of the graph. We present extensive numerical results showing that our methods are often much better than the error bounds would suggest. In the undirected case, our method is generally superior to other approximation approaches; in the undirected case, ours is the first approximation method proposed.Keywords
All Related Versions
- Version 1, 2012-02-23, ArXiv
- Version 2, 2012-10-19, ArXiv
- Published version: , 10.
This publication has 21 references indexed in Scilit:
- Graph Twiddling in a MapReduce WorldComputing in Science & Engineering, 2009
- Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws2008
- Main-memory triangle computations for very large (sparse (power-law)) graphsTheoretical Computer Science, 2008
- Biological network comparison using graphlet degree distributionBioinformatics, 2007
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study2005
- Structural Holes and Good IdeasAmerican Journal of Sociology, 2004
- Curvature of co-links uncovers hidden thematic layers in the World Wide WebProceedings of the National Academy of Sciences, 2002
- Collective dynamics of ‘small-world’ networksNature, 1998
- Arboricity and Subgraph Listing AlgorithmsSIAM Journal on Computing, 1985