Mesoscale structure: communities

Pick a candidate community \(C\). Each of its nodes has an internal degree \(k_i^{int}\) (neighbors inside \(C\)) and an external degree \(k_i^{ext}\) (neighbors outside), with \(k_i=k_i^{int}+k_i^{ext}\).

A community should have high cohesion: many internal edges, so the nodes stick together, and high separation: few edges to the rest.

The most extreme cohesive group is a clique, a complete subnetwork, but that is too strict. Popular, looser tests:

• Strong community: every node has more neighbors inside than outside, \(k_i^{int}>k_i^{ext}\) for all \(i\in C\).
• Weak community: \(\sum_{i\in C}k_i^{int}>\sum_{i\in C}k_i^{ext}\).

A community is typically a connected subnetwork. It is not a clique (some internal edges can be missing) and not a component (external edges exist). For weighted networks, replace degrees with strengths.

A partition divides the network into communities so that each node belongs to exactly one. The number of possible partitions of \(N\) nodes is the Bell number:

It grows faster than exponentially. Clustering algorithms explore only a tiny portion of the space, the region where interesting solutions are most likely to be found.

Real partitions are messier still

They can be hierarchical, with communities inside communities at different scales. They are often heterogeneous, with properties varying widely between clusters. And in many real networks, communities overlap: one person belongs to family, workplace and club at once.

Partitioning looks for well-separated subnetworks: divide the network into a given number of clusters of given sizes so that the number of edges between clusters, the cut size, is minimal.

Trivial solution: one cluster holding everything. Cut size zero!

So we must fix the number of clusters and their balance. Splitting into two clusters of equal size (or differing by one node) is graph bisection.

Kernighan–Lin algorithm

Start from an arbitrary bisection. For every pair \(i\in A, j\in B\), compute how the cut would change if they swapped. Swap the pair with the largest decrease (or smallest increase), lock both, and repeat until all nodes are locked. Keep the prefix of swaps with the best cut, then start a new pass. Stop when a pass no longer improves the cut.

It is greedy and can get stuck in local optima, so it is widely used as a post-processing step to polish partitions from other methods.

Data clustering groups elements so that those in the same cluster are more similar to each other than to elements in other clusters. On a network we need a similarity between nodes. A classic one is structural equivalence:

Two nodes need not be neighbors to be similar. To compare groups \(G_1,G_2\), choose a linkage: single (maximum pairwise similarity), complete (minimum) or average.

Agglomerative clustering starts from singletons and repeatedly merges the most similar pair of groups until one group remains. The record of merges is a dendrogram; cutting it at a threshold gives a partition.

Limits: it delivers as many partitions as there are nodes with no criterion to choose one, results depend on the similarity and linkage, and it is slow on big networks.

Edges between communities act as bridges: many shortest paths must squeeze through them. The edge betweenness counts that traffic:

\(\sigma_{hj}\) is the number of shortest paths from \(h\) to \(j\), and \(\sigma_{hj}(e)\) the number passing through edge \(e\).

• Calculate the betweenness of all links.
• Remove the link with the largest betweenness (ties broken at random).
• Recalculate the betweenness of the remaining links, and repeat until none remain.

The result is again a hierarchy of partitions. Recalculation makes it slow, \(O(m^2 n)\), impractical beyond roughly 10,000 nodes.

So which level do we keep? We need a score. Hence modularity, next.

“Dense internal, sparse external edges” is locally different density, but with respect to what? Modularity compares each community with a random baseline: the same network after degree-preserving randomization.

\(k_ik_j/2m\) is the Newman–Girvan null-model term, the expected number of edges between \(i\) and \(j\) if links were rewired at random keeping degrees. \(g_i\) is the community of node \(i\), \(\delta\) the Kronecker delta, and \(\gamma\) the resolution parameter (1 by default). Counting per community instead of per pair gives the equivalent form

Directed and weighted versions follow by modifying the adjacency matrix suitably, e.g. \(Q_w=\frac1W\sum_C\left(W_C-\frac{s_C^2}{4W}\right)\).

Greedy modularity optimization starts from singletons and keeps merging the pair of communities that raises \(Q\) the most, stopping at the peak.

Start again from singletons. Each iteration has two steps:

• Modularity optimization. Visit nodes one by one and move each into the neighboring community with the largest increase \(\Delta Q\). Keep sweeping until no single move raises \(Q\).
• Community aggregation. Replace each community by a supernode. Links between supernodes carry the summed weight of links between their groups; links inside a group become a weighted self-loop.

Repeat on the supernetwork until \(Q\) stops increasing. The random order of node visits makes the result stochastic: reshuffle to see different answers.

Variants such as GenLouvain (generalized Louvain) extend the idea, e.g. to multilayer networks.

Modularity's null model depends on the total number of links. Communities whose degree is smaller than about \(\sqrt{2L}\) are virtually invisible to the method and may be merged with other clusters.

The classic example: a ring of cliques joined by single links. Every clique is obviously a community, yet once the ring is long enough, merging neighboring cliques in pairs scores a higher \(Q\).

The resolution parameter \(\gamma\) is one remedy: \(\gamma>1\) favors smaller communities, \(\gamma<1\) larger ones. But there is rarely an obvious right value.

Divide the \(N\) nodes into \(q\) groups. The probability that nodes \(i\) and \(j\) are connected depends only on their groups: \(P(i\leftrightarrow j)=p_{g_ig_j}\). The \(q\times q\) matrix of these probabilities is the stochastic block matrix.

The model can generate many kinds of group structure:

• \(p_{rr}>p_{rs}\): community structure
• \(p_{rr}<p_{rs}\): disassortative structure; with \(p_{rr}=0\), multipartite networks
• \(p_{11}\gg p_{12}\gg p_{22}\): core–periphery
• all equal: the classic random graph, no group structure at all

To detect communities, fit the model: for a given partition, maximize the likelihood that an SBM reproduces the observed links. The degree-corrected version (DCSBM) maximizes

Newman (2016) showed that modularity maximization with resolution \(\gamma=\frac{\omega_{in}-\omega_{out}}{\log\omega_{in}-\log\omega_{out}}\) is equivalent to maximum-likelihood fitting of a planted-partition DCSBM.

Artificial benchmarks plant a known answer. In the planted partition model, an SBM with \(p_{rr}=p_{in}\) and \(p_{rs}=p_{out}\), all \(q\) groups have size \(N/q\) and

The GN benchmark fixes \(N=128\), \(q=4\), \(\langle k\rangle=16\), so \(31p_{in}+96p_{out}=16\). As \(\langle k^{ext}\rangle\) grows, the groups dissolve; at \(\langle k^{ext}\rangle=12\) every node has as many links to each other group as to its own.

Its nodes all have about the same degree and its communities the same size, unlike real networks. The LFR benchmark adds heavy-tailed distributions of degree and community size and is now the standard test.

Real benchmarks come with known groups: Zachary's karate club (rather too famous by now), power grids, the Star Wars character network, and so on.

Comparing partitions

NMI is 1 when two partitions are identical and about 0 when they are independent.