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 converges to a local minimum 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 is 340 times faster.

翻译：核心-外围（CP）结构在网络中频繁出现，其中节点形成两个不同的组：一个规模较小、内部连接紧密的核心和一个稀疏的外围。Borgatti和Everett（2000）提出了一种最流行的识别和量化CP结构的方法，通过将观测网络与一个“理想”的CP结构进行比较。尽管该度量已被广泛使用，但仍需改进算法。在本工作中，我们详细阐述了一种贪婪的标签交换算法来识别CP结构，该算法既快速又准确。通过利用CP度量的数学重构，我们提出的启发式方法相比朴素实现，在操作数量上实现了数量级的改进。我们证明了该算法收敛于局部最小值，同时在小型玩具网络上始终能获得接近全局最优解90%的解决方案。在合成网络上，与一种流行的竞争方法相比，我们的算法展现出更优的分类精度和运行时间；在一个真实世界网络上，其速度提升了340倍。