  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.

Data Structures and Algorithms;Social and Information Networks;Combinatorics