Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?

References

• W. Aiello, F. Chung, and L. Lu. “A Random Graph Model for Power Law Graphs.” Experimental Mathematics 10 (2001), 53–66.
   Web of Science ®Google Scholar
• N. Alon, R. Yuster, and U. Zwick. “Finding and Counting Given Length Cycles.” Algorithmica 17 (1997), 354–364.
   Google Scholar
• A.-L. Barabási and R. Albert. “Emergence of Scaling in Random Networks.” Science 286 (1999), 509–512.
   PubMed Web of Science ®Google Scholar
• E. A. Bender and E. R. Canfield. “The Asymptotic Number of Labeled Graphs with Given Degree Sequences.” Journal of Combinatorial Theory A 24 (1978), 296–307.
   Web of Science ®Google Scholar
• J. Berry, L. Fostvedt, D. Nordman, C. Phillips, C. Seshadhri, and A. Wilson. “Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?” In Innovations in Theoretical Computer Science (ITCS) 1407: 1116 (2014), 225–234.
   Google Scholar
• J. Berry, L. Fostvedt, D. Nordman, C. Phillips, C. Seshadhri, and A. Wilson. “Why do simple algorithms for triangle enumeration work in the real world?” Technical Report 1407.1116, arXiv, 2014. http://arxiv.org/pdf/1407.1116v1.pdf.
   Google Scholar
• J. W. Berry, B. Hendrickson, R. A. LaViolette, and C. A. Phillips. “Tolerating the Community Detection Resolution Limit with Edge Weighting.” Physical Review E 83: 5, (2011), 056119.
   Web of Science ®Google Scholar
• B. Bollobás. “A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs.” European Journal on Combinatorics 1 (1980), 311–316.
   Google Scholar
• T. Britton, M. Deijfen, and A. Martin-Löf. “Generating Simple Random Graphs with Prescribed Degree Distribution.” Journal of Statistical Physics 124: 6 (2006), 1377–1397.
   Web of Science ®Google Scholar
• A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. “Graph Structure in the Web.” Computer Networks 33 (2000), 309–320.
   Web of Science ®Google Scholar
• R. S. Burt. “Structural Holes and Good Ideas.” American Journal of Sociology 110: 2 (2004), 349–399.
   Web of Science ®Google Scholar
• R. S. Burt. “Secondhand Brokerage: Evidence on the Importance of Local Structure for Managers, Bankers, and Analysts.” Academy of Management Journal 50, (2007), 119–148.
   Web of Science ®Google Scholar
• N. Chiba and T.Takao Nishizeki. “Arboricity and Subgraph Listing Algorithms.” SIAM J. Comput. 14 (1985), 210–223.
   Web of Science ®Google Scholar
• M. Chrobak and D. Eppstein. “Planar Orientations with Low Out-Degree and Compaction of Adjacency Matrices.” Theoretical Computer Science 86 (1991), 243–266.
   Web of Science ®Google Scholar
• F. Chung and L. Lu. “The Average Distances in Random Graphs with Given Expected Degrees.” PNAS 99 (2002), 15879–15882.
   PubMed Web of Science ®Google Scholar
• F. Chung, L. Lu, and V. Vu. “Eigenvalues of Random Power Law Graphs.” Annals of Combinatorics 7 (2003), 21–33.
   Google Scholar
• J. Cohen. “Graph Twiddling in a MapReduce World.” Computing in Science & Engineering 11 (2009), 29–41.
   Web of Science ®Google Scholar
• J. S. Coleman. “Social Capital in the Creation of Human Capital.” American Journal of Sociology 94 (1988), S95–S120.
   Web of Science ®Google Scholar
• M. Faloutsos, P. Faloutsos, and C. Faloutsos. “On Power-Law Relationships of the Internet Topology.” In Proceedings of SIGCOMM, pp. 251–262. New York: ACM, 1999.
   Google Scholar
• B. Foucault Welles, A. Van Devender, and N.Noshir Contractor. “Is a Friend a Friend?: Investigating the Structure of Friendship Networks in Virtual Worlds.” In CHI-EA’10, pp. 4027–4032. New York: ACM, 2010.
   Google Scholar
• I. Fudos and C. M. Hoffmann. “A Graph-Constructive Approach to Solving Systems of Geometric Constraints.” ACM Transactions on Graphics 16: 2 (1997), 179–216.
   Web of Science ®Google Scholar
• A. Ital and M. Rodeh. “Finding a Minimum Circuit in a Graph.” SIAM Journal on Computing 7 (1978), 413–423.
   Web of Science ®Google Scholar
• M. Latapy. “Main-Memory Triangle Computations for very Large (Sparse (Power-Law)) Graphs.” Theoretical Computer Science 407 (2008), 458–473.
   Web of Science ®Google Scholar
• M. Mihail and C. Papadimitriou. “On the Eigenvalue Power Law.” In RANDOM, LNCS, 254–262. Cambridge, MA: Springer, 2002.
   Google Scholar
• M. Molloy and B. Reed. “A Critical Point for Random Graphs with a Given Degree Sequence.” Random Structures and Algorithms 6 (1995), 161–179.
   Web of Science ®Google Scholar
• M. Molloy and B. Reed. “The Size of the Giant Component of a Random Graph with a Given Degree Sequence.” Combinatorics, Probability and Computing 7 (1998), 295–305.
   Web of Science ®Google Scholar
• R. Motwani and P. Raghavan. Randomized Algorithms. New York: Cambridge University Press, 1995.
   Google Scholar
• M. E. J. Newman. “The Structure and Function of Complex Networks.” SIAM Review 45 (2003), 167–256.
   Web of Science ®Google Scholar
• M. E. J. Newman, S. Strogatz, and D. Watts. “Random Graphs with Arbitrary Degree Distributions and Their Applications.” Physical Review E 64 (2001), 026118.
   PubMed Web of Science ®Google Scholar
• K. Pearson. “Method of Moments and Method of Maximum Likelihood.” Biometrika 28 (1936), 34–59.
   Google Scholar
• A. Portes. “Social Capital: Its Origins and Applications in Modern sociology.” Annual Review of Sociology 24: 1 (1998), 1–24.
   Web of Science ®Google Scholar
• D. Sergi. “Random Graph Model with Power-Law Distributed Triangle Subgraphs.” Phys Rev E 72 (2005), 025103.
   Web of Science ®Google Scholar
• S. Suri and S. Vassilvitskii. “Counting Triangles and the Curse of the Last Reducer.” In Proceedings of WWW’11, pp. 607–614. New York: ACM, 2011.
   Google Scholar
• T. Schank and D. Wagner. “Finding, Counting and Listing all Triangles in Large Graphs, an Experimental Study.” In Experimental and Efficient Algorithms, pp. 606–609. Berlin Heidelberg; Springer, 2005.
   Google Scholar
• C. E. Tsourakakis. “Fast Counting of Triangles in Large Real Networks Without Counting: Algorithms and Laws.” In ICDM, pp. 608–617. IEEE, 2008.
   Google Scholar
• V. Vassilevska Williams and R. Williams. “Subcubic Equivalences Between Path, Matrix and Triangle Problems.” In Foundations of Computer Science (FOCS), pp. 645–654. IEEE Computer Society, 2010.
   Google Scholar
• D. Watts and S. Strogatz. “Collective Dynamics of ‘Small-World’ Networks.” Nature 393 (1998), 440–442.
   PubMed Web of Science ®Google Scholar
• N. C. Wormald. “The Asymptotic Connectivity of Labelled Regular Graphs.” Journal of Combinatorial Theory B 31 (1981), 156–167.
   Web of Science ®Google Scholar