Graph Community Detection

A network of 10,000 hedge funds connected by shared holdings, or 2,000 companies connected by supply-chain links, has structure a single adjacency matrix doesn't show you directly: sub-groups of nodes that connect to each other far more densely than they connect to the rest of the graph. Community detection finds those sub-groups automatically, without being told in advance how many there are or what defines them — a fundamentally different problem from k-means, because there's no coordinate space here, only who is connected to whom.

Modularity: comparing against a random baseline

Modularity $Q$ scores a proposed partition of the graph into communities by comparing observed internal edges to expected internal edges under a random-graph baseline that preserves each node's total number of connections:

$$Q = \frac{1}{2m}\sum_{ij} \left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)$$

In words: for every pair of nodes $i,j$, check whether an edge actually exists ($A_{ij}$) and subtract off how likely an edge would be there just by chance, given how many connections each node has in total ($k_i, k_j$) out of the graph's $2m$ total edge-endpoints — then only count that comparison if the pair is placed in the same community ($\delta(c_i,c_j)=1$). Sum it all up and you get a single score: positive and large when communities have far more internal edges than random chance would produce, near zero when the proposed grouping is no better than a random split.

Because checking every possible partition is computationally hopeless for large graphs, practical algorithms like Louvain and Leiden search greedily: start with every node as its own community, repeatedly merge whichever pair of communities increases modularity the most, and stop when no merge helps — an efficient, if not perfectly optimal, way to climb toward a high-modularity partition.

Worked example

Applying the Louvain algorithm to a graph of 1,200 public companies connected by shared institutional ownership (an edge if two companies share more than 5 major holders in common) finds 14 communities. One community of 60 stocks turns out, on inspection, to correspond almost exactly to companies held heavily by a specific set of large-cap growth funds; another corresponds to regional bank holdings concentrated among a handful of value-oriented funds. Neither grouping was told to the algorithm — sector labels and fund style labels were never inputs — they emerged purely from the pattern of shared ownership, and the resulting partition achieves a modularity of $Q = 0.41$, well above the near-zero score a random same-sized partition would produce.

What this means in practice

Community detection on ownership, supply-chain, or lead-lag networks surfaces groupings that aren't visible from sector classifications alone — a useful cross-check for concentration risk (do my "diversified" holdings actually sit in the same ownership community?) and for building alternative groupings for factor models that go beyond GICS sectors.