An efficient and principled method for detecting communities in networks

Brian Ball; Brian Karrer; M. E. J. Newman

Source-linked AI summary

An efficient and principled method for detecting communities in networks

Brian Ball, Brian Karrer, M. E. J. Newman

arXiv:1104.3590v1Apr 18, 2011cs.SIcond-mat.stat-mechphysics.soc-ph

TL;DR

Community detection must identify densely connected groups that may overlap or be disjoint, including in very large networks. The paper fits a stochastic generative link-community model with a fast expectation-maximization algorithm, yielding competitive results and extensions to both overlapping and nonoverlapping detection. Its practical scope is demonstrated on real-world and synthetic networks, including a network with over 40 million edges.

Problem
Community detection requires identifying network groups that may overlap or be disjoint, but extending principled generative inference to overlapping communities is nontrivial.
Method
The method fits a stochastic generative model of edge types using maximum likelihood and expectation-maximization, then derives vertex communities from inferred link communities.
Results
The algorithm detects overlapping or nonoverlapping communities with performance similar to the best previous algorithms and can analyze networks with millions of vertices and edges.
Takeaways & Limitations
A single statistically grounded approach supports overlapping and nonoverlapping community detection at scales including a 4-million-vertex, 40-million-edge network.

Abstract

from arXiv · show

A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.

I. INTRODUCTION

The paper develops a global statistical approach to detecting overlapping communities by modeling edge types, then extends it to nonoverlapping divisions. The resulting algorithm combines competitive accuracy with scalability to networks containing millions of vertices and edges.

Community detection seeks groups with denser internal connections than external connections, allowing either disjoint or overlapping memberships.
The method’s overlap model is less restrictive than models that imply unusually dense edges in regions shared by multiple communities.
The method infers overlapping vertex communities by clustering edge types, so vertices connected by multiple edge types naturally belong to multiple communities.
The algorithm fits a generative model using maximum likelihood and expectation-maximization, with pruning that makes it practical for very large networks.
It discovers known overlapping community structure in synthetic networks and is applied to numerous real-world networks.
Nonoverlapping communities are obtained by assigning each vertex to its strongest overlapping community, justified as a relaxation of a stochastic blockmodel.

II. A GENERATIVE MODEL FOR LINK COMMUNITIES

The generative model represents communities as edge colors and assigns each vertex a propensity for edges of each color. These propensities generate dense color-specific connections among vertices sharing a community.

The model generates an undirected network with n vertices and edges divided among K edge-color communities.
Each parameter θ_iz represents vertex i’s propensity to have edges of color z.
The expected number of color-z edges between vertices i and j is θ_izθ_jz, with the actual count drawn from a Poisson distribution.
The model technically permits multiedges and self-edges because these assumptions greatly simplify mathematical treatment, although real networks often lack them.
Link communities arise implicitly because vertices with large propensities for the same color tend to form dense color-specific webs.

III. DETECTING OVERLAPPING COMMUNITIES

The paper fits the link-community model by maximizing network likelihood and reformulates the optimization so it can be solved by alternating closed-form updates. The resulting EM procedure monotonically increases likelihood, while repeated initializations address local maxima.

The model is fit by maximizing the probability, or equivalently the log-likelihood, of the observed network with respect to θ_iz.
Jensen’s inequality introduces edge-color probabilities q_ij(z), transforming difficult nonlinear equations into an alternating optimization.
Alternating updates of q_ij(z) and θ_iz form an expectation-maximization algorithm whose log-likelihood increases monotonically, though convergence to the global maximum is not guaranteed.
The algorithm uses multiple random initializations and retains the fit with the highest final log-likelihood to reduce the risk of local maxima.
q_ij(z) represents the probability that an observed edge between i and j has color z, providing the quantity needed to infer link communities.
The formulation is mathematically related to probabilistic latent semantic analysis, adapted from topic detection in text documents to link communities.

IV. IMPLEMENTATION

The implementation reduces memory use and accelerates expectation-maximization by avoiding storage of edge-assignment quantities and pruning converged parameters and edges. The resulting algorithm scales to networks with millions of vertices and edges, while a small nonzero pruning threshold trades exact equivalence for additional speed.

Memory use: The algorithm can be implemented with memory usage dominated by O(nK) parameter storage rather than O(mK) edge-assignment storage.The reorganization avoids storing qij(z) and stores only old and new kiz values, totaling 2nK quantities.
Running time: Each iteration requires O(mK) operations, with total runtime primarily determined by the number of iterations needed for kiz to converge.The authors note that many cases require a rather large number of iterations, slowing the method.
Pruning: Pruning excludes kiz values that become zero and removes edges whose endpoints have converged to single communities.These strategies focus later iterations on vertices with ambiguous community assignments.
Accuracy–speed trade-off: With δ = 0, the pruned algorithm is exactly equivalent to the original EM algorithm, whereas δ = 0.001 introduces a small difference and further speed improvement.The nonzero threshold is used in the authors’ calculations as an approximation.

V. RESULTS

The paper evaluates the algorithm on synthetic and real-world networks to test recovery of known community structure and performance under practical conditions.

Evaluation design: Synthetic networks test recovery of planted community structure under controlled conditions.The generated networks allow the method’s ability to detect known structure to be measured.
Evaluation design: Real-world networks provide examples of the algorithm’s performance under practical network conditions.The evaluation includes a range of real-world examples alongside synthetic benchmarks.
Evaluation design: The evaluation combines controlled tests with empirical network examples.This pairing assesses both recovery of known structure and behavior on observed networks.

A. Synthetic networks

Synthetic benchmarks test whether the model-based algorithm recovers planted overlapping communities across degree, group-balance, and overlap conditions. It performs well across substantial parameter ranges, with accuracy approaching perfect classification when structure is sufficiently informative.

Benchmark design: The synthetic benchmarks generate networks from the same stochastic model used by the algorithm and vary parameters from strong structure to no structure.This consistency-test design measures recovery of known community divisions under controlled conditions.
Benchmark design: The test networks contain n = 10000 vertices divided between two overlapping communities, with x-only, y-only, and z shared vertices.All vertices have the same expected degree k.
Experimental conditions: The three tests vary expected degree k, the balance between x and y, and overlap size z.The first fixes z = 500 and x = y = 4750 while varying k; the second fixes k = 10 while varying group balance; the third fixes k = 10 and x = y while varying z.
Classification accuracy: For k greater than about ten, the first test identifies the known community structure essentially perfectly.When k approaches zero, the absence of edges makes community detection impossible.
Classification accuracy: Accuracy declines as group asymmetry or overlap size increases, but approaches 100% when either is small.Figure 1 reports both the fraction of correctly classified vertices and the Jaccard index for overlap recovery.

B. Real networks

The method identifies overlapping communities in real-world networks, including social and transportation systems, while representing partial membership and placing structurally bridging hubs in overlaps.

Evaluation: The real-network evaluation includes detailed results for three examples, with additional summary results reported in Appendix B.The examples cover social and transportation networks.
Karate club: The karate club network is divided into two overlapping groups that correspond well with the known split, with several vertices assigned to both groups.Each overlap vertex receives a fractional membership based on the expected fraction of incident edges associated with each community.
Les Misérables: The Les Misérables network is partitioned into six overlapping communities that roughly follow social divisions and plot subplots.Many high-degree major characters are placed in multiple communities, matching their appearances across more than one subplot.
US air transportation: In the US airline network, three detected communities correspond to the east coast, west coast, and Alaska.Overlaps include geographic boundary airports and hubs, which can connect broadly across regions.
Visualization: Figure 2 encodes edge-community assignments with edge colors and vertex-community fractions with vertex colors; overlap vertices are enlarged and shown as pie charts.Edge colors represent the highest q_ij(z) value for each edge, while pie charts show how overlap vertices divide among communities.

VI. NONOVERLAPPING COMMUNITIES

The overlapping-community algorithm can produce nonoverlapping divisions by assigning each vertex to its strongest community, with likelihood optimization improving benchmark performance. Tests cover synthetic LFR networks and real networks, including a college-football structure recovered perfectly.

Method: Nonoverlapping communities are obtained by assigning each vertex to the community with the largest θ_iz value.The procedure is justified as a relaxation of a nonoverlapping degree-corrected stochastic blockmodel.
Synthetic evaluation: The LFR benchmark evaluates performance on synthetic unweighted, undirected networks with planted community structure using the variant normalized mutual information measure.The measure is chosen to enable direct comparisons with algorithms evaluated in the same reference.
Synthetic results: Figure 4 averages results over 100 networks for each point, using ten random initializations and comparing panels without and with likelihood-optimization post-processing.The benchmark uses the small and big community-size settings from Ref. [31].
Synthetic results: After likelihood-optimization post-processing, the algorithm performs about as well as, or better than, the algorithms analyzed in Ref..Without optimization, the simple rounding method performs in the middle of the comparison; low mixing-parameter values remain less accurate and communities are sometimes split or merged.
Real-network result: In the US college football network, the algorithm extracts the known conference structure perfectly.Clusters represent detected communities, while vertex colors indicate the formal conferences; independent colleges are shown separately.

VII. CONCLUSION

The paper presents a mathematically grounded community-detection method for overlapping or nonoverlapping communities that is fast enough for networks with millions of vertices. Its main unresolved limitation is selecting the number of communities K reliably and efficiently.

The method detects overlapping or nonoverlapping communities in undirected networks using a probabilistic model of link communities.
It combines a rigorous mathematical foundation, ease of implementation, scalability to millions of vertices, and competitive results.
The method currently offers no criterion for determining K, the number of communities in a network.Bayesian information criterion and Akaike information criterion are not applicable because many model parameters lie on the boundary of parameter space.
Regularizing a large K can remove communities, but undetermined prior parameters still influence the selected number and do not completely solve the problem.
Statistical model-selection methods appear promising but are currently too computationally demanding for all but the smallest networks.Developing a reliable method that runs reasonably quickly on large networks remains open.

Appendix A: Community detection and statistical text analysis

The appendix connects network community detection to probabilistic latent semantic analysis, adapting statistical inference over word-document relationships to symmetric network link communities. The paper emphasizes that an intrinsically symmetric formulation is needed for undirected networks.

PLSA models word-document data as a bipartite network whose edges represent word occurrences in documents.The incidence matrix records word frequencies, and each edge is associated with an unobserved topic variable.
Each word-document edge is assigned a latent topic z, with its probability factorized into topic, word-given-topic, and document-given-topic probabilities.Given the topic, the word and document endpoints are placed independently.
Maximizing the PLSA likelihood yields word and document topic-association probabilities that can represent communities or divide edges into link communities.
Standard PLSA cannot be translated directly to undirected one-mode networks because its posterior edge probabilities can become asymmetric.An edge could then be assigned to different communities depending on its orientation.
The paper instead uses an intrinsically symmetric model and corresponding EM algorithm for undirected networks.This formulation differs from related NMF, LDA, and asymmetric link-community approaches.
The same model can also extract nonoverlapping communities by relaxing a nonoverlapping stochastic blockmodel.

Appendix B: Results for running time

The appendix compares naive and pruned implementations of the EM algorithm on test networks. Pruning removes unnecessary variables and substantially improves practical running time, including for a network with over 40 million edges.

The naive EM implementation is only moderately fast, whereas pruning unneeded variables achieves significantly greater speed.
The running-time comparison measures total CPU seconds, iterations, and log-likelihood across algorithm versions and network datasets.The experiments use 100 random initializations, except for LiveJournal, which uses one.
The LiveJournal network contains over 40 million edges and was evaluated with single runs using the pruned algorithm.
50 minutes with δ = 0.001 versus about 11 hours with δ = 0 shows the large running-time difference on LiveJournal.
The authors identify further possible improvements that could increase speed or improve result quality at the same speed.Suggested directions include tempered EM and alternating EM with nonnegative matrix factorization.

Appendix C: Nonoverlapping communities

The appendix derives the paper’s nonoverlapping community procedure as a relaxation of a degree-corrected stochastic blockmodel. After EM convergence, rounding each vertex to its strongest community assignment produces the final division.

The nonoverlapping procedure first finds overlapping assignments and then assigns each vertex to its strongest community.
Table I reports total running time and iterations for three algorithm versions, with directed networks symmetrized for testing.
The derivation uses a degree-corrected stochastic blockmodel, whose discrete community assignments are relaxed to nonnegative continuous membership fractions.The fractions for each vertex sum to one.
The relaxed model absorbs θ_i into θ_ir = θ_iS_ir while retaining community-specific normalization constraints.
The generalized model permits the two ends of an edge to belong to different communities, while diagonal ω_rs recovers the single-color version.
After iterating the EM equations to convergence, the algorithm assigns each vertex to the community with largest θ_ir.