Source-linked AI summary
Community detection in networks: Modularity optimization and maximum likelihood are equivalent
M. E. J. Newman
TL;DR
Community detection methods need principled links between modularity optimization and statistical inference, while modularity also has resolution and modeling limitations. The paper establishes an exact equivalence between generalized modularity maximization and maximum likelihood for the planted partition model, deriving the appropriate resolution parameter and clarifying the method’s assumptions and scope.
Problem
The paper addresses the need to clarify the relationship, theoretical basis, and limitations of modularity maximization and stochastic-block-model maximum likelihood.
Method
The paper compares generalized modularity maximization with maximum likelihood for the planted partition model and its degree-corrected formulation.
Results
The two methods have maxima at the same group assignments for the appropriate γ, and the equivalence provides a rigorous derivation of modularity.
Takeaways & Limitations
The appropriate resolution parameter can be derived from the model, while conventional γ = 1 is not correct in most cases.
Takeaways & Limitations
Modularity maximization assumes that all communities are statistically similar and applies only when the correct resolution parameter γ is used.
Abstract
from arXiv · showhide
We demonstrate an exact equivalence between two widely used methods of community detection in networks, the method of modularity maximization in its generalized form which incorporates a resolution parameter controlling the size of the communities discovered, and the method of maximum likelihood applied to the special case of the stochastic block model known as the planted partition model, in which all communities in a network are assumed to have statistically similar properties. Among other things, this equivalence provides a mathematically principled derivation of the modularity function, clarifies the conditions and assumptions of its use, and gives an explicit formula for the optimal value of the resolution parameter.
I. INTRODUCTION
Community detection divides network nodes into groups with dense internal and sparse external connections. The paper studies modularity maximization and stochastic-block-model maximum likelihood, showing that they can be exactly equivalent under specified models and parameters.
- Community detection partitions network nodes into groups with dense within-group and sparse between-group connections.
- The paper examines modularity maximization and maximum likelihood applied to the stochastic block model.
- The two methods are exactly equivalent for appropriate model and parameter choices.This equivalence provides a rigorous derivation of modularity and identifies conditions under which modularity maximization is optimal.
II. COMMUNITY DETECTION
The paper introduces modularity maximization as one of the community-detection methods it analyzes.
- The study begins by describing the two community-detection methods in their widely accepted forms, starting with modularity.
A. Modularity maximization
Modularity maximization scores candidate network divisions by comparing within-community edges with a randomized expectation, then selects the highest-scoring division. Degree-preserving randomization and a resolution parameter address important practical issues, although limitations remain.
- Modularity maximization optimizes a benefit function that scores candidate divisions and selects the division with the highest score.Because possible divisions are exponentially numerous, approximate optimization is normally used.
- Modularity compares observed within-group edges with the expected number under randomized edge placement, avoiding the trivial all-nodes-in-one-group solution.
- Degree-preserving randomization uses the configuration model because uniform randomization fails to respect node degrees.
- Modularity maximization can merge communities and fail to resolve the smallest divisions when a large network contains many small communities.The cited condition is when the number of communities exceeds approximately a quantity beginning with 2m in the source passage.
- The resolution parameter γ controls detected community size: smaller γ favors larger communities, whereas larger γ favors smaller ones.γ = 1 recovers traditional modularity.
B. Statistical inference
Statistical inference fits a generative stochastic block model to observed network data and uses likelihood maximization to infer community assignments. The conventional model can mismatch empirical degree distributions, motivating degree correction.
- Statistical inference fits a generative network model to observed data, using fitted parameters to reveal network structure.
- In the stochastic block model, nodes belong to groups and edge probabilities or expected edge counts depend on the groups of each node pair.
- The Poisson block-model formulation is used because it is technically easier to handle and is virtually indistinguishable from the Bernoulli version for sparse networks.
- Community assignments are inferred by maximizing likelihood with respect to group assignments and model parameters.The parameters can be discarded after likelihood maximization when only group assignments are needed.
C. Degree-corrected block model
The degree-corrected block model addresses the ordinary stochastic block model’s poor fit to real-world networks by incorporating node degrees. Community detection then maximizes the model’s likelihood over parameters and group assignments using approximate methods when exhaustive optimization is infeasible.
- Motivation: The ordinary stochastic block model often fits empirical networks poorly because its Poisson degree distribution does not match their broad degree distributions.It fails to respect observed node degrees, so the model may be misspecified for real-world networks.
- Model: The degree-corrected block model can fit networks with any degree distribution by making expected edge counts depend on both node degrees and group affinities.For nodes i and j in groups r and s, the expected edge count is (k_i k_j/2m)ω_rs, with ω_rs measuring edge probability relative to the configuration model.
- Inference: Its log-likelihood is optimized with respect to the group assignments g and model parameters Ω to find the best fit to the observed network.The likelihood expression is obtained after neglecting constants that do not affect the location of its maximum.
- Inference: Because the number of possible group assignments is too large for exhaustive search on all but the smallest networks, approximate optimization methods are used.Examples include label-switching algorithms and Kernighan–Lin-style greedy algorithms.
III. THE PLANTED PARTITION MODEL AND MODULARITY MAXIMIZATION
The paper makes explicit an exact equivalence between modularity maximization and maximum likelihood for the planted partition model, then derives its implications for resolution, consistency, and limitations. The equivalence is specifically developed for the degree-corrected planted partition model, while the planted partition assumption treats communities as statistically similar.
- Model and setup: The planted partition model restricts the stochastic block model to two connection parameters, assuming identical within- and between-community rates.Its degree-corrected version is the model used for the main equivalence with modularity maximization.
- Exact equivalence: With known ωin and ωout, maximizing planted-partition likelihood over group assignments is equivalent to maximizing generalized modularity at the corresponding γ.The two objectives have their maxima at the same group assignments, apart from overall constants.
- Resolution parameter: The equivalence supplies an explicit correct value of γ and shows that the conventional choice γ = 1 is generally not correct.The formula depends on ωin and ωout, which are typically unknown before fitting the model.
- Implications: Modularity maximization inherits maximum-likelihood consistency under suitable conditions, correctly recovering planted group assignments in the limit of large node degrees.This follows when networks are generated from the corresponding traditional or degree-corrected block model.
- Limitations: The method is less flexible than the full stochastic block model because it assumes statistically similar communities and implicitly favors groups of uniform size.Performance may be worse when these assumptions do not hold.
A. Value of the resolution parameter
The paper estimates the resolution parameter γ iteratively by alternating modularity maximization with estimates of ωin and ωout, then recalculating γ until convergence. Synthetic and real-network results show that larger numbers of communities generally require larger γ values, while practical correctness is not formally guaranteed for real-world networks.
- Estimation procedure: An initial γ guess is used for modularity maximization, after which the resulting assignments estimate ωin and ωout.The authors note that γ = 1 usually provides a workable initial guess, even when it is not particularly accurate.
- Empirical behavior: Synthetic-network experiments compare estimated γ values with true values across networks varying in community number.The networks use equally sized groups and fixed average within-group and between-group connections, with modularity optimized by simulated annealing.
- Estimation procedure: The algorithm repeatedly recalculates γ from estimated ωin and ωout until convergence.The estimates use observed within-group and between-group edge counts, including mout, the number of edges between distinct groups.
- Scope and limitations: For sufficiently dense networks generated from the planted partition model, the procedure should converge to the correct γ and community structure; real-world networks lack formal guarantees.The paper states that this limitation applies broadly outside the model-generated setting, including practical applications.
- Empirical behavior: In most examined cases, γ is estimated within a few percent after one iteration, and no case required more than ten iterations.This empirical convergence behavior suggests the iterative procedure may be serviceable in practice.
- Resolution trend: γ generally increases as the number of communities increases, and larger q values are best treated using γ > 1.The authors relate this trend to the resolution parameter’s purpose of handling networks with many communities.
IV. CONCLUSIONS
The conclusion identifies modularity maximization as a special case of maximum-likelihood community detection.
- Modularity maximization is a special case of the maximum-likelihood method of community detection.