Source-linked AI summary
Parsimonious module inference in large networks
Tiago P. Peixoto
TL;DR
The paper addresses module inference when the number of blocks is not known, using minimum description length and Monte Carlo inference. It reports detectability bounds, a √N scaling for the maximum number of detectable blocks at fixed average degree, and an application to a large bipartite actor–film network.
Problem
The paper investigates how modules can be detected in large networks when the number of modules is unknown in advance.
Method
The method combines minimum description length with Metropolis-Hastings Monte Carlo inference and one-dimensional golden search over the number of blocks.
Results
The method identifies a minimum-description-length partition with B = 332 in the IMDB network, yielding a predominantly bipartite actor–film block structure.
Takeaways & Limitations
The inferred IMDB structure is fully dissortative and cannot be obtained by community-detection methods focused on assortative connections.
Takeaways & Limitations
For large degree correlations, the equations used may become approximate and can produce spurious blocks; a more satisfactory general methodology is still lacking.
Abstract
from arXiv · showhide
We investigate the detectability of modules in large networks when the number of modules is not known in advance. We employ the minimum description length (MDL) principle which seeks to minimize the total amount of information required to describe the network, and avoid overfitting. According to this criterion, we obtain general bounds on the detectability of any prescribed block structure, given the number of nodes and edges in the sampled network. We also obtain that the maximum number of detectable blocks scales as $\sqrt{N}$, where $N$ is the number of nodes in the network, for a fixed average degree $<k>$. We also show that the simplicity of the MDL approach yields an efficient multilevel Monte Carlo inference algorithm with a complexity of $O(τN\log N)$, if the number of blocks is unknown, and $O(τN)$ if it is known, where $τ$ is the mixing time of the Markov chain. We illustrate the application of the method on a large network of actors and films with over $10^6$ edges, and a dissortative, bipartite block structure.
Supplemental Material: Parsimonious Module Inference in Large Networks
The supplemental material is affiliated with the Institut für Theoretische Physik at Universität Bremen. The listed institutional address is Hochschulring 18, D-28359 Bremen, Germany.
- The supplemental material lists the Institut für Theoretische Physik.
- The listed university is Universität Bremen.
- The address is Hochschulring 18, D-28359 Bremen, Germany.
I. BLOCKMODEL ENTROPY
This section presents entropy expressions for traditional and degree-corrected blockmodel variants, including directed cases and sparse-limit approximations. It also explains computational trade-offs and approximation caveats.
- The traditional blockmodel entropy is given for undirected and directed cases, with the binary entropy function defined explicitly.
- Sparse-limit expressions simplify entropy calculations and make single-node membership changes cheaper to evaluate.Changing a node of degree k requires modifying at most 4k terms in one sum and 2 terms in another.
- The degree-corrected variant has corresponding expressions, but their validity depends on sparse-network conditions and degree-distribution details.
- Outside the sparse limit, degree-corrected entropy lacks a closed-form expression and higher-order corrections may fail for broad degree distributions without a structural cutoff.
- Approximate entropy formulas can detect spurious blocks reflecting intrinsic dissortative degree-degree correlations when relevant block quantities are large.The MDL approach may reject some such blocks, but a more satisfactory general methodology is still lacking.
II. MONTE CARLO INFERENCE
The inference algorithm uses Metropolis-Hastings moves whose proposals exploit local block neighborhoods, while entropy and acceptance calculations remain local enough for efficient network sweeps.
- The MCMC procedure proposes moving each node from its current block r to a candidate block s and accepts or rejects the move using the entropy difference.
- Candidate blocks are proposed using a random neighbor’s block label and probabilities proportional to ets + 1, preserving nonzero probability for every block.
- The proposal can be sampled through uniform selection, an acceptance probability Rt, and a fallback edge-based selection from the sampled neighbor’s block.
- The proposed move still requires a Metropolis-Hastings acceptance probability to enforce detailed balance.
- A full Monte Carlo sweep takes O(E) time because the entropy change and remaining acceptance terms can be computed in O(ki) time for a moved node.
A. Minimizing the description length Σt/c
The description length is minimized over block counts by combining Monte Carlo optimization with a one-dimensional golden-search procedure. The resulting method reuses solutions across block counts and scales efficiently for sparse networks.
- The minimum description length over B is obtained by independently minimizing St/c for candidate block counts and then applying golden search to Σt/c or Σb.
- Golden search contributes O(ln Bmax) to the overall complexity by progressively narrowing an interval that brackets a minimum.
- The search guarantees a global minimum when the objective is convex, but generally guarantees only a local minimum because Σb need not be convex.
- For each new B, the algorithm initializes from a solution at a larger block count and coalesces nodes in the same blocks to avoid discarding previous work.
- O(τE ln Bmax) is the overall complexity, becoming O(τE ln E) without prior Bmax information and O(τN ln N) for sparse graphs.
- An implementation is freely available through the graph-tool Python library.
III. THE INTERNET MOVIE DATABASE (IMDB) NETWORK
The IMDB actor-film network yields a data-driven, fully bipartite block structure, with blocks reflecting recognizable film and actor patterns. The inferred structure demonstrates the method’s ability to recover dissortative organization that conventional community-detection methods generally cannot represent.
- Network construction: The pruned IMDB network contains films and actors connected when a film includes an actor in its cast.The database was filtered to retain entries with the stated metadata before interpreting the large-scale structure.
- Inferred structure: B = 332 was the block count of the partition with the minimum description length found across multiple algorithm runs.The typical minimization trajectory is illustrated in Fig. 1.
- Inferred structure: The inferred block structure was also bipartite, with blocks composed predominantly of either actors or films rather than both.A small minority of mixed blocks could occur for very low-degree films and actors, but the best partitions were fully bipartite.
- Methodological implication: This fully dissortative structure is unavailable to methods focused exclusively on assortative connections, including modularity optimization.The result therefore illustrates a structural capability of the model beyond conventional community formulations.
- Block interpretation: Film blocks align with production year, country, and genre, including recognizable historical and geographical groupings.The graphical representation shows a rough time ordering and proximity between culturally or geographically related film groups.
- Block interpretation: Actor blocks can group performers with shared national and temporal characteristics, such as British actors active mainly during the 1970s and 1980s.The cited example places the Monty Python members in a block with approximately 1,500 other actors, including Sean Connery and Roger Moore.