Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

References

• Abrego , [Abrego et al. 09] B. , Fernandez-Merchant , S. , Neubauer , M and Watkins , W. 2009 . Sum of Squares of Degrees in a Graph . Journal of Inequalities in Pure and Applied Mathematics , 10 ART 64
   Google Scholar
• Ahlswede , [Ahlswede and Katona 78] R. and Katona , G. O. H. 1978 . Graphs with Maximal Number of Adjacent Pairs of Edges . Acta Mathematica Academiae Scientarium Hungaricae , 32 : 97 – 120 .
   Web of Science ®Google Scholar
• Alon , [Alon et al. 96] N. , Yossi , M. and Szegedy , M. 1996 . The Space Complexity of Approximating the Frequency Moments . ACM Symposium on Theory of Computing ,
   Google Scholar
• Alon , [Alon et al. 97] N. , Yuster , R. and Zwick , U. 1997 . Finding and Counting Given Length Cycles . Algorithmica , 17 ( 3 ) : 209 – 223 .
   Web of Science ®Google Scholar
• Avron , [Avron 10] H. 2010 . Counting Triangles in Large Graphs Using Randomized Matrix Trace Estimation . Workshop on Large-Scale Data Mining: Theory and Applications ,
   Google Scholar
• Bar-Yosseff , [Bar-Yosseff et al. 10] Z. , Kumar , R. and Sivakumar , D. 2010 . Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs . ACM–SIAM Symposium on Discrete Algorithms ,
   Google Scholar
• Becchetti , [Becchetti et al. 08] L. , Boldi , P. , Castillo , C. and Gionis , A. 2008 . Efficient Semi-streaming Algorithms for Local Triangle Counting in Massive Graphs . ACM SIGKDD Conference on Knowledge Discovery and Data Mining ,
   Google Scholar
• Berry , [Berry et al. 11] J. W. , Hendrickson , B. , LaViolette , R. and Phillips , C. A. 2011 . Tolerating the Community Detection Resolution Limit with Edge Weighting . Physical Review E , 83 ( 5 ) : 056119-1 – 056119-9 .
   Web of Science ®Google Scholar
• Bhamidi , [Bhamidi et al. 08] S. , Bresler , G. and Sly , A. 2008 . Mixing Time of Exponential Random Graphs . Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science , : 803 – 812 .
   Google Scholar
• Bonato , [Bonato et al. 09] A. , Hadi , N. , Horn , P. , Pralat , P. and Wang , C. 2009 . Models of Online Social Networks . Internet Mathematics , 6 ( 3 ) : 285 – 313 .
   Google Scholar
• Broder , [Broder et al. 98] A. Z. , Charikar , M. , Frieze , A. and Mitzenmacher , M. 1998 . Min-wise Independent Permutations . ACM Symposium on Theory of Computing ,
   Google Scholar
• Buriol , [Buriol et al. 06] L. , Frahling , G. , Leonardi , S. , Marchetti-Spaccamela , A, and Sohler , C. 2006 . Counting Triangles in Data Streams . Symposium on Principles of Database Systems ,
   Google Scholar
• Chernoff , [Chernoff 81] H. 1981 . A Note on an Inequality Involving the Normal Distribution . Annals of Probability , 9 ( 3 ) : 533 – 535 .
   Web of Science ®Google Scholar
• Chiba , [Chiba and Nishizeki 85] N. and Nishizeki , T. 1985 . Arboricity and Subgraph Listing Algorithms . SIAM Journal on Computing , 14 ( 1 ) : 210 – 223 .
   Web of Science ®Google Scholar
• Graham , [Chung Graham and Lu 06] F. Chung and Lu , L. 2006 . Complex Graphs and Networks . Providence: American Mathematical Society ,
   Google Scholar
• Graham , [Chung Graham et al. 03] F. Chung , Lu , L. and Vu , V. 2003 . The Spectra of Random Graphs with Given Expected Degrees . Proceedings of the National Academy of Sciences of the United States of America , 100 ( 11 ) : 6313 – 6318 .
   Web of Science ®Google Scholar
• Coppersmith , [Coppersmith and Winograd 87] D. and Winograd , S. 1987 . Matrix multiplication via arithmetic progressions . ACM Symposium on Theory of Computing ,
   Google Scholar
• Drineas , [Drineas et al. 99] P. , Frieze , A. , Kannan , R. , Vempala , S. and Vinay , V. 1999 . Clustering in Large Graphs and Matrices . ACM Symposium on Discrete Algorithms ,
   Google Scholar
• Eckmann , [Eckmann and Moses 02] J.-P. and Moses , E. 2002 . Curvature of Co-links Uncovers Hidden Thematic Layers in the World Wide Web . Proceedings of the National Academy of Sciences , 99 ( 9 ) : 5825 – 5829 .
   Web of Science ®Google Scholar
• Frank , [Frank and Strauss 86] O. and Strauss , D. 1986 . Markov Graphs . Journal of the American Statistical Association , 81 ( 395 ) : 832 – 842 .
   Web of Science ®Google Scholar
• Feigenbaum , [Feigenbaum et al. 05] J. , Kannan , S. , McGregor , A. , Suri , S. and Zhang , J. 2005 . On Graph Problems in a Semi-streaming Model . Journal of Theoretical Computer Science , 348 ( 2 ) : 207 – 216 .
   Web of Science ®Google Scholar
• Fudos , [Fudos and Hoffman 97] I. and Hoffman , C. 1997 . A Graph-Constructive Approach to Solving Systems of Geometric Constraints . ACM Trans. Graph. , 16 : 179 – 216 .
   Web of Science ®Google Scholar
• Hajnal , [Hajnal and Szemerédi 70] A. and Szemerédi , E. 1970 . Proof of a Conjecture of Erdős . Combinatorial Theory and Its Applications , 2 : 601 – 623 .
   Google Scholar
• Heider , [Heider 46] F. 1946 . Attitudes and Cognitive Organization . Journal of Psychology , 21 : 107 – 112 .
   PubMed Web of Science ®Google Scholar
• Itai , [Itai and Rodeh 77] A. and Rodeh , M. 1977 . Finding a Minimum Circuit in a Graph . ACM Symposium on Theory of Computing ,
   Google Scholar
• Jeffrey , [Jeffrey and Ghemawat 04] D. and Ghemawat , S. 2004 . MapReduce: Simplified Data Processing on Large Clusters . Operating Systems Design and Implementation , 51 ( 3 ) : 107 – 113 .
   Google Scholar
• Johnson , [Johnson and Lindenstrauss 84] S. and Lindenstrauss , J. 1984 . Extensions of Lipschitz Mappings into a Hilbert Space . Contemporary Mathematics , 26 : 189 – 206 .
   Google Scholar
• Jowhari , [Jowhari and Ghodsi 05] H. and Ghodsi , M. 2005 . New Streaming Algorithms for Counting Triangles in Graphs . In Computing and Combinatorics, 710–716 ,
   Google Scholar
• Kang , [Kang et al. 09] U. , Tsourakakis , C. and Faloutsos , C. 2009 . PEGASUS: A Peta-scale Graph Mining System . International Conference on Data Mining ,
   Google Scholar
• Kang , [Kang et al. 10] U. , Tsourakakis , C. , Appel , A. P. , Faloutsos , C. and Leskovec , J. 2010 . Radius Plots for Mining Tera-byte Scale Graphs: Algorithms, Patterns, and Observations . SIAM Data Mining , : 548 – 558 .
   Google Scholar
• Kim , [Kim and Vu 00] J. H. and Vu , V. H. 2000 . Concentration of Multivariate Polynomials and Its Applications . Combinatorica , 20 ( 3 ) : 417 – 434 .
   Web of Science ®Google Scholar
• Kolountakis , [Kolountakis et al. 10] M. N. , Miller , G. L. , Peng , R. and Tsourakakis , C. E. 2010 . Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning . Workshop on Algorithms and Models for the Web Graph ,
   Google Scholar
• Knuth , [Knuth 97] D. 1997 . Seminumerical Algorithms, , 3rd edition , Reading , MA : Addison-Wesley Professional .
   Google Scholar
• Latapy , [Latapy 08] M. 2008 . Main-Memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs . Theoretical Computer Science , 407 : 458 – 473 .
   Web of Science ®Google Scholar
• Leskovec , [Leskovec et al. 10] J. , Huttenlocher , D. and Kleinberg , J. 2010 . Predicting Positive and Negative Links in Online Social Networks . International Conference on World Wide Web , : 641 – 650 .
   Google Scholar
• Leskovec , [Leskovec et al. 08] J. , Backstrom , L. , Kumar , R. and Tomkins , A. 2008 . Microscopic Evolution of Social Networks . ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , : 462 – 470 .
   Google Scholar
• Li , [Li et al. 04] S. , Armstrong , C. M. , Bertin , N. Ge , H. 2004 . A Map of the Interactome Network of the Metazoan C. elegans . Science , 303 : 540 – 543 .
   PubMed Web of Science ®Google Scholar
• Magen , [Magen and Zouzias 08] A. and Zouzias , A. 2008 . Near Optimal Dimensionality Reductions That Preserve Volumes . In Randomization and Approximation Techniques in Computer Science, 523–534 ,
   Google Scholar
• Mislove , [Mislove et al. 07] A. , Massimiliano , M. , Gummadi , K. , Druschel , P. and Bhattacharjee , B. 2007 . Measurement and Analysis of Online Social Networks . Internet Measurement Conference ,
   Google Scholar
• Newman , [Newman 03] M. 2003 . The Structure and Function of Complex Networks . SIAM Review , 45 ( 2 ) : 167 – 256 .
   Web of Science ®Google Scholar
• Newman , [Newman et al. 02] M. E. J. , Watts , D. J. and Strogatz , S. 2002 . Random Graph Models of Social Networks . Proceedings of the National Academy of Sciences of the United States of America , 99 : 2566 – 2572 .
   PubMed Web of Science ®Google Scholar
• Pagh , [Pagh and Tsourakakis 12] C. and Tsourakakis , C. E. 2012 . Colorful Triangle Counting and a MapReduce Implementation . Information Processing Letters , 112 ( 7 ) : 227 – 281 .
   Google Scholar
• Papadimitriou , [Papadimitriou and Yannakakis 81] C. and Yannakakis , M. 1981 . The Clique Problem for Planar Graphs . Information Processing Letters , 13 : 131 – 133 .
   Web of Science ®Google Scholar
• Robins , [Robins et al. 07] G. , Pattison , P. , Kalish , Y. and Lusher , D. 2007 . An Introduction to Exponential Random Graph (p*) Models for Social Networks . Social Networks Journal, Special Section: Advances in Exponential Random Graph (p*) Models , 29 : 173 – 191 .
   Google Scholar
• Rougemont , [Rougemont and Hingamp 03] J. and Hingamp , P. 2003 . DNA Microarray Data and Contextual Analysis of Correlation Graphs . BMC Bioinformatics , 4 : 4 – 15 .
   Web of Science ®Google Scholar
• Schank , [Schank and Wagner 05a] T. and Wagner , D. 2005 . Finding, Counting and Listing All Triangles in Large Graphs: An Experimental Study . Workshop on Experimental and Efficient Algorithms ,
   Google Scholar
• Schank , [Schank and Wagner 05b] T. and Wagner , D. 2005 . Approximating Clustering Coefficient and Transitivity . Journal of Graph Algorithms and Applications , 9 : 265 – 275 .
   Google Scholar
• Tsourakakis , [Tsourakakis 08] C. E. 2008 . Fast Counting of Triangles in Large Real Networks, without Counting: Algorithms and Laws . International Conference on Data Mining ,
   Google Scholar
• Tsourakakis , [Tsourakakis 11] C. E. 2011 . Counting Triangles Using Projections . Knowledge and Information Systems , 26 ( 3 ) : 501 – 520 .
   Web of Science ®Google Scholar
• Tsourakakis , [Tsourakakis et al. 09] C. E. , Kang , U. , Miller , G. L. and Faloutsos , C. 2009 . Doulion: Counting Triangles in Massive Graphs with a Coin . ACM SIGKDD Conference on Knowledge Discovery and Data Mining ,
   Google Scholar
• Tsourakakis , [Tsourakakis et al. 10] C. E. , Drineas , P. , Michelakis , E. , Koutis , I. and Faloutsos , C. 2010 . Spectral Counting of Triangles via Element-wise Sparsification and Triangle-Based Link Recommendation . Advances in Social Networks Analysis and Mining ,
   Google Scholar
• Tsourakakis , [Tsourakakis et al. 11] C. E. , Kolountzakis , M. and Miller , G. L. 2011 . Triangle Sparsifiers . Journal of Graph Algorithms and Applications , 15 ( 6 ) : 703 – 726 .
   Google Scholar
• Vu , [Vu 00] V. H. 2000 . On the Concentration of Multivariate Polynomials with Small Expectation . Random Structures and Algorithms , 16 : 344 – 363 .
   Web of Science ®Google Scholar
• Wasserman , [Wasserman and Faust 94] S. and Faust , K. 1994 . Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences) . Cambridge UK: Cambridge University Press ,
   Google Scholar
• Wasserman , [Wasserman and Pattison 96] S. and Pattison , P. 1996 . Logit Models and Logistic Regressions for Social Networks: I. An Introduction to Markov Graphs and p* . Psychometrika , 61 : 401 – 425 .
   Web of Science ®Google Scholar
• Watts , [Watts and Strogatz 98] D. and Strogatz , S. 1998 . Collective Dynamics of Small-World Networks . Nature , 393 : 440 – 442 .
   PubMed Web of Science ®Google Scholar
• Wesler , [Wesler et al. 07] H. , Gleave , E. , Fisher , D. and Smith , M. 2007 . Visualizing the Signatures of Social Roles in Online Discussion Groups . Journal of Social Structure , 8
   Google Scholar
• Wimmer , [Wimmer and Lewis 10] A. and Lewis , K. 2010 . Beyond and Below Racial Homophily: ERG Models of a Friendship Network Documented on Facebook . American Journal of Sociology , 2 : 583 – 642 .
   Web of Science ®Google Scholar
• Yook , [Yook et al. 04] S. , Oltvai , Z. and Barabasi , A. L. 2004 . Functional and Topological Characterization of Protein Interaction Networks . Proteomics , 4 : 928 – 942 .
   PubMed Web of Science ®Google Scholar