Decompositions of triangle-dense graphs. (English) Zbl 1332.05114
Summary: High triangle density – the graph property stating that a constant fraction of two-hop paths belongs to a triangle – is a common signature of social networks. This paper studies triangle-dense graphs from a structural perspective. We prove constructively that significant portions of a triangle-dense graph are contained in a disjoint union of dense, radius 2 subgraphs. This result quantifies the extent to which triangle-dense graphs resemble unions of cliques. We also show that our algorithm recovers planted clusterings in approximation-stable \(k\)-median instances.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C42 | Density (toughness, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 91D30 | Social networks; opinion dynamics |
Software:
KronFitReferences:
| [1] | R. Albert, H. Jeong, and A.-L. Barabási, {\it Error and attack tolerance of complex networks}, Nature, 406 (2000), pp. 378-382. |
| [2] | A.-L. Barabasi and R. Albert, {\it Emergence of scaling in random networks}, Science, 286 (1999), pp. 509-512. · Zbl 1226.05223 |
| [3] | M.-F. Balcan, A. Blum, and A. Gupta, {\it Clustering under approximation stability}, J. ACM, 60 (2013), pp. 1068-1077. · Zbl 1422.68287 |
| [4] | A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, {\it Graph structure in the web}, Computer Networks, 33 (2000), pp. 309-320. |
| [5] | R. S. Burt, {\it Structural holes and good ideas}, Amer. J. Sociology, 110 (2004), pp. 349-399. |
| [6] | D. Chakrabarti and C. Faloutsos, {\it Graph mining: Laws, generators, and algorithms}, ACM Comput. Surv., 38 (2006). |
| [7] | F. Chung and L. Lu, {\it The average distances in random graphs with given expected degrees}, Proc. Nat. Acad. Sci. USA, 99 (2002), pp. 15879-15882. · Zbl 1064.05137 |
| [8] | F. Chung and L. Lu, {\it Connected components in random graphs with given degree sequences}, Ann. Combin., 6 (2002), pp. 125-145. · Zbl 1009.05124 |
| [9] | J. S. Coleman, {\it Social capital in the creation of human capital}, Amer. J. Sociology, 94 (1988), pp. 95-120. |
| [10] | D. Chakrabarti, Y. Zhan, and C. Faloutsos, {\it R-MAT: A recursive model for graph mining}, in Proceedings of the 2004 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2004, pp. 442-446. |
| [11] | K. Faust, {\it Comparing social networks: Size, density, and local structure}, Metodoloski zvezki, 3 (2006), pp. 185-216. |
| [12] | M. Faloutsos, P. Faloutsos, and C. Faloutsos, {\it On power-law relationships of the internet topology}, in Proceedings of SIGCOMM, 1999, pp. 251-262. · Zbl 0889.68050 |
| [13] | S. Fortunato, {\it Community detection in graphs}, Phys. Rep., 486 (2010), pp. 75-174. |
| [14] | A. Ferrante, G. Pandurangan, and K. Park, {\it On the hardness of optimization in power law graphs}, in Proceedings of Conference on Computing and Combinatorics, 2006, pp. 417-427. · Zbl 1206.05096 |
| [15] | B. Foucault Welles, A. Van Devender, and N. Contractor, {\it Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds}, in Extended Abstracts on Human Factors in Computing Systems, ACM, 2010, pp. 4027-4032. |
| [16] | M. Girvan and M. Newman, {\it Community structure in social and biological networks}, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 7821-7826. · Zbl 1032.91716 |
| [17] | R. Gupta, T. Roughgarden, and C. Seshadhri, {\it Decompositions of triangle-dense graphs}, in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ACM, 2014, pp. 471-482. · Zbl 1365.05245 |
| [18] | P. W. Holland and S. Leinhardt, {\it A method for detecting structure in sociometric data}, Amer. J. Sociology, 76 (1970), pp. 492-513. |
| [19] | J. J. Pfeiffer III, T. La Fond, S. Moreno, and J. Neville, {\it Fast generation of large scale social networks while incorporating transitive closures}, in Proceedings of the International Conference on Privacy, Security, Risk, and Trust (PASSAT), 2012, pp. 154-165. |
| [20] | J. M. Kleinberg, {\it Navigation in a small world}, Nature, 406 (2000), 845. · Zbl 1296.05181 |
| [21] | J. M. Kleinberg, {\it The small-world phenomenon: An algorithmic perspective}, in Proceedings of the Symposium on Theory of Computing, 2000, pp. 163-170. · Zbl 1296.05181 |
| [22] | J. M. Kleinberg, {\it Small-world phenomena and the dynamics of information}, in Advances in Neural Information Processing Systems, Vol. 1, MIT Press, Cambridge, MA, 2002, pp. 431-438. |
| [23] | R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal, {\it Stochastic models for the web graph}, in Proceedings of Foundations of Computer Science, 2000, pp. 57-65. |
| [24] | H. Lin, C. Amanatidis, M. Sideri, R. M. Karp, and C. H. Papadimitriou, {\it Linked decompositions of networks and the power of choice in Polya urns}, in Proceedings of the Symposium on Discrete Algorithms, 2008, pp. 993-1002. · Zbl 1192.90027 |
| [25] | J. Leskovec, D. Chakrabarti, J. M. Kleinberg, C. Faloutsos, and Z. Ghahramani, {\it Kronecker graphs: An approach to modeling networks}, J. Mach. Learn. Res., 11 (2010), pp. 985-1042. · Zbl 1242.05256 |
| [26] | J. Leskovec, J. Kleinberg, and C. Faloutsos, {\it Graph evolution: Densification and shrinking diameters}, ACM Trans. Knowledge Discovery Data, 1 (2007). |
| [27] | J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney, {\it Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters}, Internet Math., 6 (2008), pp. 29-123. · Zbl 1205.91144 |
| [28] | R. J. Lipton and R. E. Tarjan, {\it A separator theorem for planar graphs}, SIAM J. Appl. Math., 36 (1979), pp. 177-189. · Zbl 0432.05022 |
| [29] | A. Montanari and A. Saberi, {\it The spread of innovations in social networks}, Proc. Natl. Acad. Sci. USA, 107 (2010), pp. 20196-20201. |
| [30] | M. E. J. Newman, {\it The structure of scientific collaboration networks}, Proc. Natl. Acad. Sci. USA, 98 (2001), pp. 404-409. · Zbl 1065.00518 |
| [31] | M. E. J. Newman, {\it Properties of highly clustered networks}, Phys. Rev. E, 68 (2003), 026121. |
| [32] | M. E. J. Newman, {\it Finding community structure in networks using the eigenvectors of matrices}, Phys. Rev. E, 74 (2006), 036104. |
| [33] | A. Pinar, C. Seshadhri, and T. G. Kolda, {\it The similarity between Stochastic Kronecker and Chung-Lu graph models}, in Proceedings of the 2012 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2012. |
| [34] | N. Robertson and P. D. Seymour, {\it Graph minors III: Planar tree-width}, J. Combin. Theory Ser. B, 36 (1986), pp. 49-64. · Zbl 0548.05025 |
| [35] | A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, and B. Y. Zhao, {\it Measurement-calibrated graph models for social network experiments}, in Proceedings of the World Wide Web Conference, ACM, 2010, pp. 861-870. |
| [36] | C. Seshadhri, T. G. Kolda, and A. Pinar, {\it Community structure and scale-free collections of Erdös-Rényi graphs}, Phys. Rev. E, 85 (2012), 056109. |
| [37] | C. Seshadhri, A. Pinar, and T. G. Kolda, {\it Fast triangle counting through wedge sampling}, in Proceedings of the 2013 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2013. · Zbl 07260400 |
| [38] | V. Satuluri, S. Parthasarathy, and Y. Ruan, {\it Local graph sparsification for scalable clustering}, in Proceedings of ACM SIGMOD, 2011, pp. 721-732. |
| [39] | E. Szemerédi, {\it Regular partitions of graphs}, Problèmes Combinatoires théorie Graphes, 260 (1978), pp. 399-401. · Zbl 0413.05055 |
| [40] | J. Ugander, L. Backstrom, and J. Kleinberg, {\it Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections}, in Proceedings of World Wide Web Conference, 2013, pp. 1307-1318. |
| [41] | J. Ugander, B. Karrer, L. Backstrom, and C. Marlow, {\it The Anatomy of the Facebook Social Graph}, arXiv:1111.4503, 2011. |
| [42] | J. Vivar and D. Banks, {\it Models for networks: A cross-disciplinary science}, Wiley Interdiscip. Rev. Comput. Statist., 4 (2012), pp. 13-27. |
| [43] | S. Wasserman and K. Faust, {\it Social Network Analysis: Methods and Applications}, Cambridge University Press, Cambridge, UK, 1994. · Zbl 0926.91066 |
| [44] | D. Watts and S. Strogatz, {\it Collective dynamics of “small-world” networks}, Nature, 393 (1998), pp. 440-442. · Zbl 1368.05139 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
