Identification of core-periphery structure in networks

Abstract

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.

References in corpus (25)

• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Functional cartography of complex metabolic networks
• Mixing patterns in networks
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Dynamical and correlation properties of the Internet
• Detecting rich-club ordering in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• k-core organization of complex networks
• The Rich-Club Phenomenon In The Internet Topology
• Mixture models and exploratory analysis in networks
• Phase transition in the detection of modules in sparse networks
• Structure and dynamics of core-periphery networks
• Core-periphery organization of complex networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Friendship networks and social status
• Model Selection for Degree-corrected Block Models
• (Un)detectable cluster structure in sparse networks
• Density-based and transport-based core-periphery structures in networks
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives

Cited by in corpus (47)

• Community detection in networks: A user guide
• Modern temporal network theory: A colloquium
• Nestedness in complex networks: Observation, emergence, and implications
• Multicores-periphery structure in networks
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• A Clarified Typology of Core-Periphery Structure in Networks
• Finding multiple core-periphery pairs in networks
• Statistical inference of assortative community structures
• Core-periphery structure requires something else in the network
• Structural inference for uncertain networks
• Multiplex core-periphery organization of the human connectome
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Disentangling bipartite and core-periphery structure in financial networks
• Community detection in networks with unequal groups
• Core-Periphery Structure in Directed Networks
• Reconstructing networks
• Detecting Core-Periphery Structures by Surprise
• The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market
• Efficient Network Structures with Separable Heterogeneous Connection Costs
• Centrality metrics and localization in core-periphery networks
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• The impact of inter-city mobility on urban welfare
• Random Spatial Network Models with Core-Periphery Structure
• Algorithmic detectability threshold of the stochastic block model
• Detecting mesoscale structures by surprise
• Hierarchical core-periphery structure in networks
• Comparative analysis on the selection of number of clusters in community detection
• Detection of core-periphery structure in networks by 3-tuple motifs
• Convexity in complex networks
• Assortative and preferential attachment lead to core-periphery networks
• Double phase transition of the Ising model in core-periphery networks
• Link Prediction in Networks with Core-Fringe Data
• Core-periphery Models for Hypergraphs
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Detectability thresholds of general modular graphs
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Core-periphery Detection Based on Masked Bayesian Non-negative Matrix Factorization
• AOC; Assembling Overlapping Communities
• Informative core identification in complex networks
• Spectral density of equitable core-periphery graphs
• The Atlas for the Aspiring Network Scientist
• Multiscale modeling of brain network organization
• Unifying Modular and Core-Periphery Structure in Functional Brain Networks over Development
• A generative model for community types in directed networks
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• Node Dominance: Revealing Community and Core-Periphery Structure in Social Networks