Source-linked AI summary
Identification of core-periphery structure in networks
Xiao Zhang, Travis Martin, M. E. J. Newman
TL;DR
Core–periphery structure requires identifying a dense core surrounded by a sparse periphery, a task related to but distinct from community detection. The paper fits a generative stochastic block model using maximum likelihood, with expectation–maximization and belief propagation providing parameter estimation and decomposition. The method scales to networks of a million or more nodes and remains detectable even when core–periphery structure is arbitrarily weak.
Problem
Networks may contain dense cores surrounded by sparse peripheries, but detecting this large-scale structure requires a method distinct from community detection.
Method
The method fits a stochastic block model to observed networks by maximum likelihood, combining expectation–maximization for parameter estimation with belief propagation for decomposition.
Results
The algorithm successfully identifies known core–periphery structure with low error, scales to networks of a million or more nodes, and has no detectability threshold.
Takeaways & Limitations
Core–periphery structure is detectable in principle no matter how weak it is, unlike the threshold-limited community-detection case.
Abstract
from arXiv · showhide
Many networks can be usefully decomposed into a dense core plus an outlying, loosely-connected periphery. Here we propose an algorithm for performing such a decomposition on empirical network data using methods of statistical inference. Our method fits a generative model of core-periphery structure to observed data using a combination of an expectation--maximization algorithm for calculating the parameters of the model and a belief propagation algorithm for calculating the decomposition itself. We find the method to be efficient, scaling easily to networks with a million or more nodes and we test it on a range of networks, including real-world examples as well as computer-generated benchmarks, for which it successfully identifies known core-periphery structure with low error rate. We also demonstrate that the method is immune from the detectability transition observed in the related community detection problem, which prevents the detection of community structure when that structure is too weak. There is no such transition for core-periphery structure, which is detectable, albeit with some statistical error, no matter how weak it is.
I. INTRODUCTION
The paper addresses core–periphery structure as a distinct large-scale network pattern and proposes a statistically principled method to detect it. The method is presented as scalable and free of the minimum-strength barrier associated with community detection.
- Core–periphery structure divides networks into a densely interconnected core and a sparser surrounding periphery.
- Unlike rich-club structure, a core can include low-degree nodes and specifies connectivity patterns throughout the remaining network.
- Degree-assortative mixing differs because low-degree vertices preferentially connect to one another rather than to the core.
- The proposed approach fits a generative network model by maximum likelihood instead of maximizing an objective function over candidate divisions.
- Any core–periphery structure is claimed to be detectable in principle, regardless of how weak it is.
II. THE STOCHASTIC BLOCK MODEL
The stochastic block model represents core–periphery structure through group-dependent connection probabilities. Its fit can capture degree differences that are misleading for community detection but informative for core–periphery structure.
- The stochastic block model assigns nodes to groups and makes each edge probability depend only on the endpoint groups.
- Traditional community structure uses higher within-group than between-group probabilities, whereas core–periphery structure uses p11 > p12 > p22.
- In this ordering, core–core connections are most probable, periphery–periphery connections least probable, and core–periphery connections intermediate.
- Periphery vertices are therefore more likely to connect to core vertices than to one another, distinguishing this structure from assortative and disassortative mixing.
- Although broad degree distributions can cause stochastic-block-model fits to select high- and low-degree groups instead of communities, that tendency is appropriate for core–periphery structure.
III. FITTING TO EMPIRICAL DATA
The paper detects core–periphery structure by fitting the stochastic block model to an observed network. It estimates the model parameters by maximum likelihood using expectation–maximization.
- The method finds the stochastic block model parameters that best fit a given observed network.
- Maximum likelihood estimation is implemented with an expectation–maximization algorithm.
A. The EM algorithm
The EM procedure reformulates likelihood maximization using an auxiliary distribution over group assignments, then iteratively updates membership marginals and model parameters. Belief propagation is used to make the otherwise exponential assignment sum tractable.
- The likelihood is defined from the adjacency matrix and latent group assignments, then maximized over connection probabilities and group proportions.
- Jensen’s inequality introduces a normalized distribution q(g) over group assignments to convert the optimization into coupled maximizations.
- EM iterates between calculating q(g) and its one- and two-vertex marginals and updating p and γ from those marginals.
- The iterative procedure converges to a local, though not necessarily global, maximum of the log-likelihood, motivating multiple starting conditions.
- The final membership marginals classify each vertex into the core or periphery according to its highest-probability group.
B. Belief propagation
Belief propagation replaces an intractable sum over group assignments with a faster message-passing calculation of the distribution q(g). Combined with EM, it yields an iterative procedure for estimating model parameters and assigning vertices to core or periphery.
- Motivation: 2^n group assignments make the EM denominator prohibitively expensive to evaluate directly, motivating belief propagation as an alternative to Monte Carlo sampling.Belief propagation is significantly faster than Monte Carlo and supports further analysis.
- Message passing: Belief propagation finds the distribution q(g) by passing messages that represent vertex-group probabilities conditional on removing a neighboring vertex.The message equations are especially simple for sparse networks, where terms of order p_rs can be neglected relative to terms of order 1.
- Message passing: The message equations are iterated from random initial conditions to convergence, while one-vertex marginal probabilities q_i^r are recalculated at each iteration.Normalization constants ensure the resulting probabilities sum to one.
- Assumption: The belief-propagation equations are exact on trees or locally tree-like networks but approximate on many real-world networks, where they nevertheless appear comparable to Monte Carlo.The stochastic block model generates locally tree-like networks, whereas empirical networks need not satisfy that condition.
- Efficiency: O(m+n) terms are required per belief-propagation iteration, giving linear-time iterations for sparse networks with m ∝ n.Heuristic arguments suggest O(log n) iterations on a typical network, although firm convergence results are unavailable.
- Full algorithm: The complete algorithm alternates converged belief-propagation updates with improved parameter estimates until convergence, then assigns each vertex to its more probable group.The steps use one- and two-vertex marginals to update p and γ before repeating the belief-propagation stage.
IV. DETECTABILITY
Core–periphery structure remains detectable across weak and strong limits, although degree alone is optimal at the extremes. Belief propagation improves classification for intermediate-strength structure, while no sharp detectability threshold appears.
- Weak structure: Core and periphery have different average degrees, so degree-based classification performs better than chance even when structure is weak.The degree distributions overlap, causing statistical errors, but their means remain ordered.
- Evaluation: The consistency test evaluates the method on networks generated by the same stochastic block model used for fitting.Maximum-likelihood fitting is expected to be optimal on average for data generated by that model.
- Weak structure: In the weak-structure limit, posterior group probabilities depend only on vertex degree, making degree-based division optimal.Vertices above the network’s average degree favor the core; those below it favor the periphery.
- Strong structure: In the strong-structure limit, separated Poisson degree distributions again allow accurate classification by degree alone.The distributions have little overlap when their means differ substantially relative to their widths.
- Intermediate structure: For intermediate-strength structure away from the degree-only parameter plane, belief propagation uses network details and outperforms degree-only classification.This regime is presented as containing most cases of real-world interest.
- Detectability: Everywhere in the studied parameter space, the algorithm identifies core and periphery better than chance without a detectability threshold.This contrasts with the sharp threshold established for related community detection models.
A. Degree-based algorithm
The degree-based special case can be solved by iterating the model’s parameter and membership equations to convergence, without belief propagation.
- Degree-based algorithm: When degree alone governs classification, fitting the corresponding model determines the appropriate group sizes for degree-based assignment.The model is defined by a parameter family in which classification depends only on vertex degrees.
- Degree-based algorithm: The one-vertex probabilities are obtained from the model equations for this degree-based case.The supplied passage identifies these probabilities as Eq. (29).
- Degree-based algorithm: No belief propagation is necessary; iterating Eqs. (30) and (32) to convergence determines group memberships.The parameter θ is unnecessary during the iteration; γ1, γ2, and r suffice.
V. APPLICATIONS AND PERFORMANCE
The proposed method was tested on both computer-generated and real-world example networks.
- Applications and performance: The evaluation covers computer-generated networks and real-world example networks.
A. Computer-generated test networks
Computer-generated stochastic block model tests compare belief propagation with degree-based classification, showing stronger performance away from a special parameter setting and highlighting accuracy–complexity trade-offs.
- Performance comparison: For n = 1 000 000 networks, belief propagation and degree-based classification coincide at θ2 = 0, but diverge as θ2 moves away from zero.The comparison uses equally sized core and periphery groups and measures the fraction of incorrectly identified vertices.
- Performance comparison: The naive degree-based algorithm has error rates at least ten times higher than belief propagation in some parameter regimes.The error gap becomes visible as θ2 departs from zero.
- Accuracy–complexity trade-off: Degree-based classification achieves around 10 or 20 percent error for many parameter choices, while requiring less computation than belief propagation.Its lower cost can make it viable when moderate accuracy is acceptable.
- Accuracy–complexity trade-off: When group sizes are unknown, even a degree-based division requires the EM algorithm, reducing some of its computational advantage.The resulting calculations are simpler than full belief propagation but more complex than direct degree sorting.
- Experimental setup: Figure 2 averages results over 10 million-node networks, with curves restricted by nonnegative edge probabilities and c11 > c12 > c22.The plotted parameter ranges therefore differ across curves.
- Accuracy–complexity trade-off: The full maximum-likelihood method identifies anomalous low-degree core nodes and high-degree peripheral nodes that degree-based classification cannot find.These differing predictions may be especially relevant when the exceptional nodes are the objects of interest.
B. Real-world examples
Real-world applications show that the method recovers expected core–periphery organization in the Internet and nested core–periphery structure within political-blog communities.
- Internet: In the Internet network, the analysis separates well-connected backbone autonomous systems into the core and client or edge systems into the periphery.The network contains many leaves or edge nodes and fewer backbone nodes, matching the discovered decomposition.
- Political blogs: The political-blog network displays conservative and liberal communities, with a separate core and periphery identified inside each community.The result combines community-level separation with nested core–periphery divisions.
- Political blogs: The detected political-blog cores contain prominent conservative and liberal blogs, including National Review and Red State on the conservative side.The cited examination concerns the list of core nodes within each community.
VI. CONCLUSION
The paper presents a maximum-likelihood stochastic block model algorithm for core–periphery detection, combining EM with belief propagation. It reports good test-network performance, million-node scalability, and no detectability threshold for core–periphery structure.
- Method: The method fits a stochastic block model to undirected networks using maximum likelihood to identify core–periphery structure.The paper describes this as a first-principles algorithm.
- Method: Expectation–maximization calculates model parameters, while belief propagation implements the decomposition efficiently.These algorithms form the computational combination used for maximization and assignment.
- Results: The algorithm gives good results on test networks and scales efficiently to networks with a million nodes or more.This conclusion summarizes both empirical performance and computational scale.
- Results: Unlike community detection, core–periphery detection has no detectability threshold in this model, remaining detectable regardless of structure strength.The paper notes that statistical error can remain even though there is no analogous failure transition.