Decompositions of Triangle-Dense Graphs
arXiv:1309.7440
Abstract
High triangle density -- the graph property stating that a constant fraction of two-hop paths belong 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.
arXiv comment20 pages. Version 1->2: Minor edits. 2->3: Strengthened §3.5, removed appendix
References in corpus (8)
- Emergence of scaling in random networks
- Community structure in social and biological networks
- Community detection in graphs
- Finding community structure in networks using the eigenvectors of matrices
- The Anatomy of the Facebook Social Graph
- Kronecker Graphs: An Approach to Modeling Networks
- Properties of highly clustered networks
- Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections