# Finding Cliques in Social Networks: A New Distribution-Free Model

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2018.

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

- [Explainable Graph Representation Learning via Graph Pattern Analysis](https://mlsanity.com/paper/2512.04530/) (2025)

## Abstract (arXiv)

We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure---the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a "c-closed" graph, where for every pair of vertices u,v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to "weakly c-closed graphs", which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks tend to be weakly c-closed for modest values of c.