# Decompositions of Triangle-Dense Graphs

arXiv: https://arxiv.org/abs/1309.7440 · HTML: https://mlsanity.com/paper/1309.7440/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2013.

## Built on by (most cited first, 2 of 2)

- [Graph is all you need? Lightweight data-agnostic neural architecture search without training](https://mlsanity.com/paper/2405.01306/) (2024)
- [Network Graph Based Neural Architecture Search](https://mlsanity.com/paper/2112.07805/) (2021)

## Abstract (arXiv)

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.