Reducibility
Glossary Contents
← Ch XII
Chapter XIII Clique Cover
Ch XIV →
  1. 37 — Cliques as colors
  2. 38 — Reducing in Kotlin
  3. 39 — Community detection
39

Community detection

When LinkedIn's "people you may know" partitions the social graph into clusters, it is doing a relaxed clique cover.

Real social-graph clustering doesn't insist each cluster be a perfect clique — it asks for dense subgraphs that nearly cover the vertex set. The Louvain method, label propagation, and Leiden algorithm (used by LinkedIn, Facebook, Twitter for community detection) are clique-cover relatives that optimize modularity rather than exact cover count. Same ancestry: minimize the number of groups while keeping each group internally well-connected. The exact clique cover problem itself shows up in data compression — a clique in a feature co-occurrence graph is a set of always-together features, mergeable into one — and in chip layout, where clique cover the standard-cell library helps macro selection.

In plain terms

If you want to put every member of a social network into a friend group where everyone in each group knows everyone else, and you want as few groups as possible, you're doing clique cover. Real apps relax "everyone knows everyone" to "most people know most people," which makes the problem tractable.

Scan to come back to page 39

End of Chapter XIII
Chapter XIV Exact Cover →
← 38 Reducing in Kotlin
3/3 · 39/63
40 Exactly once →