A label-switching algorithm for fast core-periphery identification

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 (Borgatti, S. P., & Everett M. G. (2000). Models of core/periphery structures. Social Networks, 21(4), 375–395.) 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.