Which null model should a bipartite network use?

Modularity rewards edges inside communities relative to what a null model expects. The standard Newman–Girvan (NG) term expects edges between any pair of nodes, including same-type pairs that a bipartite network can never contain. Barber’s (BB) term only expects edges across the two node types. This demo runs a stochastic Louvain search many times at each resolution γ, on bipartite networks with planted communities and on a real network of languages and the countries where they are spoken, and measures how consistently each null model finds communities.

Reproduces the model-network experiments and the language–country example in S. H. Lee, “Refinement for community structures of bipartite networks,” J. Korean Phys. Soc. 79, 1190 (2021). The bipartite null model is from M. J. Barber, “Modularity and community detection in bipartite networks,” Phys. Rev. E 76, 066102 (2007). Language data from the KONECT Unicode languages network.

Model network Real network

Newman–Girvan null model

Pij = kikj / 2m for every pair

Barber (bipartite) null model [2]

Pij = kikj / m across types, 0 within a type
Partition inconsistency Ω (left axis) Average number of communities (right axis) γ window where ≥ 90% of runs find the planted 2 communities Node size grows with how often a node switches community across runs

What the experiment measures

Each network has two node types (circles and squares) split into vertically stacked groups. The top and bottom groups of opposite types are densely linked, forming the two planted communities. A middle group links evenly to everything, so its nodes have no true home and should look unstable.

At every γ the Louvain search runs repeatedly from a random node order. Identical runs give Ω = 1; C equally likely, unrelated partitions give Ω = C. Similarity between partitions uses element-centric similarity, whose personalised-PageRank form has a closed form for clique-induced graphs, so it is computed exactly here.

In the language–country network there is no ground truth, so the shaded band marks the longest stretch of γ with Ω ≤ 1.02. Look near γ ≈ 4: with the bipartite null model the community count jumps from about 90 to about 130 and then holds steady at low inconsistency, while Newman–Girvan climbs gradually, as in Fig. 5 of the paper.

Both null models can find the planted split if you pick γ carefully. The paper’s point is that the bipartite-aware term holds that split over a wider range of γ, so the result depends less on a knob you would have to guess on real data. Try raising pmid or lowering pin to see where each model breaks.

Notes: the BB term uses Barber’s normalisation, kikj/m on cross-type pairs, so both null models expect the same total number of edges and their γ axes line up, as in the paper’s figures. Louvain here is a plain JavaScript implementation, not GenLouvain, so exact γ positions differ slightly from the published figures. The language–country network is weighted by the share of each country’s population using each language; its 149 zero-weight edges carry no weight, so they are left out, which does not change modularity. The paper’s disease–gene and ecological networks are not included.

NG expects ○–○ ○–□ □–○ □–□ BB expects 0 ○–□ □–○ 0 Purple: expected edges that cannot exist in a bipartite network
The NG term spends part of its “expected edges” budget on same-type pairs. Those phantom edges subtract from modularity everywhere and blur the penalty that separates real communities. BB puts the whole budget on the cross-type blocks, equivalent to Fig. 1d of the paper.