A label-switching algorithm for fast core-periphery identification

2025/06/02 by Eric Yanchenko, Yanchenko, Eric, Srijan Sengupta +1
Engineering · Computer Science · #Industrial Vision Systems and Defect Detection #Digital Image Processing Techniques #Image Processing Techniques and Applications

paper · pdf · doi:10.48550/arxiv.2506.02069

Abstract

Core-periphery (CP) structure is frequently observed in networks where the nodes form two distinct groups: a small, densely interconnected core and a sparse periphery. Borgatti and Everett (2000) proposed one of the most popular methods to identify and quantify CP structure by comparing the observed network with an ``ideal'' CP structure. While this metric has been widely used, an improved algorithm is still needed. In this work, we detail a greedy, label-switching algorithm to identify CP structure that is both fast and accurate. By leveraging a mathematical reformulation of the CP metric, our proposed heuristic offers an order-of-magnitude improvement on the number of operations compared to a naive implementation. We prove that the algorithm monotonically ascends to a local maximum while consistently yielding solutions within 90% of the global optimum on small toy networks. On synthetic networks, our algorithm exhibits superior classification accuracies and run-times compared to a popular competing method, and on one-real world network, it is 340 times faster.

Citations

• Network Cross-Validation and Model Selection via Subsampling
• Scalable community detection in massive networks via predictive assignment
• Graph sub-sampling for divide-and-conquer algorithms in large networks
• Distributed Community Detection in Large Networks
• Core-periphery structure in networks: a statistical exposition
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Distributed Community Detection for Large Scale Networks Using Stochastic Block Model
• Two provably consistent divide and conquer clustering algorithms for\n large networks
• Producing a Unified Graph Representation from Multiple Social Network\n Views
• Models of core/periphery structures
• Stochastic blockmodels: First steps
• An Efficient Heuristic Procedure for Partitioning Graphs
• Revising the Borgatti-Everett core-periphery model: Inter-categorical density blocks and partially connected cores

Related

• Statistical inference for core-periphery structures
• A Nonlinear Spectral Method for Core--Periphery Detection in Networks
• Core-Periphery Structure in Networks
• An effective method for profiling core-periphery structures in complex networks
• A nonlinear spectral core-periphery detection method for multiplex networks