DOULION: counting triangles in massive graphs with a coin

ABSTRACT

Counting the number of triangles in a graph is a beautiful algorithmic problem which has gained importance over the last years due to its significant role in complex network analysis. Metrics frequently computed such as the clustering coefficient and the transitivity ratio involve the execution of a triangle counting algorithm. Furthermore, several interesting graph mining applications rely on computing the number of triangles in the graph of interest.

In this paper, we focus on the problem of counting triangles in a graph. We propose a practical method, out of which all triangle counting algorithms can potentially benefit. Using a straightforward triangle counting algorithm as a black box, we performed 166 experiments on real-world networks and on synthetic datasets as well, where we show that our method works with high accuracy, typically more than 99% and gives significant speedups, resulting in even ≈ 130 times faster performance.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: N. Alon and S. Joel. The Probabilistic Method. Wiley Interscience, New York, second edition, 2000.
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 4: N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209--223, 1997.
• 5: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 6: Luca Becchetti , Paolo Boldi , Carlos Castillo , Aristides Gionis, Efficient semi-streaming algorithms for local triangle counting in massive graphs, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401898]
• 7: B. Bollobas. Random Graphs. Cambridge University Press, 2001.
• 8: Luciana S. Buriol , Gereon Frahling , Stefano Leonardi , Alberto Marchetti-Spaccamela , Christian Sohler, Counting triangles in data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142388]
• 9: F. Chung, L. Lu, and V. Vu. Eigenvalues of random power law graphs. Annals of Combinatorics, 7(1):21--33, June 2003.
• 10: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 11: J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. OSDI '04, pages 137--150, December 2004.
• 12: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 13: J.-P. Eckmann and E. Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS, 99(9):5825--5829, April 2002.
• 14: I. J. Farkas, I. Derenyi, A.-L. Barabasi, and T. Vicsek. Spectra of "real-world" graphs: Beyond the semi-circle law. Physical Review E, 64:1, 2001.
• 15: G. Golub and C. Van Loan. Matrix Computations. JohnsHopkinsPress, Baltimore, MD, second edition, 1989.
• 16: Alon Itai , Michael Rodeh, Finding a minimum circuit in a graph, Proceedings of the ninth annual ACM symposium on Theory of computing, p.1-10, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803390]
• 17: H. Jowhari and M. Ghodsi. New streaming algorithms for counting triangles in graphs. In COCOON, pages 710--716, 2005.
• 18: D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, second edition, 10 Jan. 1981.
• 19: Ralf Lämmel, Google's MapReduce programming model – Revisited, Science of Computer Programming, v.70 n.1, p.1-30, January, 2008 [doi>10.1016/j.scico.2007.07.001]
• 20: Matthieu Latapy, Main-memory triangle computations for very large (sparse (power-law)) graphs, Theoretical Computer Science, v.407 n.1-3, p.458-473, November, 2008 [doi>10.1016/j.tcs.2008.07.017]
• 21: J. Leskovec and E. Horvitz. Planetary-scale views on an instant-messaging network, Mar 2008.
• 22: M. Mcpherson, L. S. Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27(1):415--444, 2001.
• 23: M. Mihail and C. Papadimitriou. the eigenvalue power law, 2002.
• 24: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 25: Tamas Sarlos, Improved Approximation Algorithms for Large Matrices via Random Projections, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.143-152, October 21-24, 2006 [doi>10.1109/FOCS.2006.37]
• 26: T. Schank. Algorithmic Aspects of Triangle-Based Network Analysis. Phd in computer science, University Karlsruhe, 2007.
• 27: Charalampos E. Tsourakakis, Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.608-617, December 15-19, 2008 [doi>10.1109/ICDM.2008.72]
• 28: C. Tsourakakis, P. Drineas, E. Michelakis, I. Koutis, and C. Faloutsos. Spectral counting of triangles in power-law networks via element-wise sparsification. In SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, 2009.
• 29: Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]
• 30: Y. Wang, D. Chakrabarti, C. Faloutsos, C. Wang, and C. Wang. Epidemic spreading in real networks: An eigenvalue viewpoint. In In SRDS, pages 25--34, 2003.
• 31: S. Wasserman and K. Faust. Social network analysis. Cambridge University Press, Cambridge, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation

Keywords:
hadoop, social networks, sparsification, triangles