Community Detection

Look at any real network — friends on a social app, papers citing papers, proteins interacting in a cell — and you will see clumps. Inside a clump everyone is densely connected; between clumps the links thin out. We call these clumps communities, and finding them is one of the most useful things you can do with a network.

The catch is saying precisely what "a good split" means. The eye sees the groups instantly, but a computer needs a number to optimize. The most popular score is modularity: it rewards a grouping when there are more edges inside communities than you would expect if the same nodes were wired up at random.

Maximize modularity and you have found the network's natural communities. Simple to state — but as we will see, finding the split with the highest possible modularity is genuinely hard.

Below is a small network. Every node starts in its own community, so modularity is low. Press Greedy step and the algorithm moves each node into the neighboring community that raises modularity the most — exactly the move at the heart of the Louvain method.

<p class="hint">{{hint}}</p>
<svg id="net" viewBox="0 0 360 240" class="net"></svg>
<div class="score">{{score_label}} <span id="q">0.000</span>
  &nbsp;·&nbsp; {{communities_label}} <span id="nc">12</span></div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.net { width: 100%; height: auto; background: #f4f7fa; border: 1px solid #d6e0e8;
       border-radius: 10px; display: block; }
.net line { stroke: #b9c4ce; stroke-width: 1.3; }
.net circle { stroke: #2b3a47; stroke-width: 1.5; transition: fill .35s ease; cursor: default; }
.net text { font: 700 9px ui-monospace, monospace; fill: #16242f; pointer-events: none; }
.score { font-size: 1.05rem; font-weight: 700; margin: .6rem 0; color: #1d3557; }
.score #q { font-family: ui-monospace, monospace; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the colors coalesce and the modularity score climb with each pass. Notice what is happening: the algorithm never tries every possible grouping. It greedily merges, taking the locally best move each time. That is fast — but it has no guarantee of reaching the single best split, because finding that is the hard part.

How hard is it to find the best communities? Not eyeballing them — provably optimizing them.

• Checking a proposed split is easy: plug it into the modularity formula and read off a number.
• Brute force would try every way to partition the nodes into groups. The number of partitions of n items (the Bell number) explodes faster than $2^{n}$ — hopeless beyond a few dozen nodes.
• It's NP-hard. In 2008, Brandes and colleagues proved that modularity maximization — finding the partition with the highest possible modularity — is NP-hard. There is no known efficient algorithm that always finds the optimum, and almost certainly none exists unless P equals NP.
• So we settle for heuristics. The same year, Blondel and colleagues published the Louvain method: start with each node alone, repeatedly move nodes into the neighbor community that increases modularity the most, then collapse each community into a super-node and repeat. It is fast and usually excellent — but it is a greedy approximation, not a guarantee.

That is the trade we keep meeting: when the exact problem is NP-hard, we reach for a clever greedy rule that gets close. The communities Louvain hands you are a very good guess, not a certified best answer.

"Find the natural groups in this network" is one of the most useful questions in data science, and community detection answers it everywhere:

• Social platforms and recommendation: clustering users by who-connects-to-whom powers friend suggestions, content feeds, and ad targeting.
• Biology: groups of interacting proteins or co-expressed genes often correspond to functional modules and even disease pathways.
• Fraud and security: tight, unusual clusters of accounts or transactions can flag rings of coordinated abuse.
• Mapping knowledge: clustering citation and collaboration networks reveals research fields and how ideas flow between them.

Because the exact problem is NP-hard, every one of these uses a heuristic like Louvain or Leiden under the hood. It is the same story as graph coloring and Max-Cut: a clean partition objective whose optimum is out of reach, so we engineer fast methods that come close enough to be indispensable.

Community detection hides a familiar twist: the groups are obvious to your eye, yet finding the split with the highest modularity is NP-hard (Brandes et al., 2008). So in practice we don't search for the perfect answer — we climb toward a good one, greedily, with methods like Louvain.

The next time an app suggests a friend, a biologist names a protein module, or a fraud team flags a ring, remember the optimization underneath. It is the same intractable core behind P vs NP, quietly tamed by a greedy rule that is fast, useful, and just shy of guaranteed.