英语原文共 19 页

外文标题：Finding multiple core-periphery pairs in networks.

外文作者：Kojaku S. and Masuda N.

文献出处：PHYSICAL REVIEW E 96, 052313 (2017)

在网络中寻找多个核心-外围对

摘要：利用网络的核心-外围结构，核心节点密集地互连，外围节点以不同的程度连接到核心节点，并且外围节点稀疏地互连。 由单个核心和外围组成的核心-外围结构已被识别用于各种网络。 然而，与许多经验网络由密集的节点群（即社区）组成的观察结果类似，一个网络可以更好地视为多个核心和外围的集合。我们提出了一种可扩展的算法来检测网络中多个非重叠的核心-外围结构组。 我们使用综合网络和经验网络对我们的算法进行了验证。 例如，我们在一个政治博客网络中发现了不同政治倾向的核心-外围对，并且在全球机场网络的某些国家的机场的国际和国内子网之间进行分离。

1.介绍

许多复杂的系统可以表示为网络，其中一个节点表示一个对象（例如，人、网页、蛋白质），一个边缘表示两个对象之间的关系（例如，友谊、超链接、物理交互）。网络的特征可以是微尺度、中尺度和宏观尺度的结构模式，如程度（即节点的边数）、聚类系数和直径[1,2]。在网络的各种结构性质中，社区结构是网络的典型中尺度结构[3]。一个社区是一组节点，这些节点紧密相连，并且稀疏地连接到不同社区的节点上。同一社区中的节点共享一个角色[3–9]（对于例外情况，请参见参考文献[10]），因此识别社区有助于对节点的分类和网络的可视化[3]。

核心-外围结构是网络的另一种中尺度结构，我们将其视为是由两组节点组成的，称为核心和外围。尽管定义不同，核心通常被定义为一组紧密相连的节点，外围则被定义为一组与核心节点紧密相连（即相邻）但不与其他外围节点紧密相连的节点[11-23]。核心和社区都是密集互联的节点组，但有区别；一个核心密集地连接到它的边缘，而一个社区没有密集地连接到它外面的其他节点。核心-外围结构已在各种网络中发现，包括脑网络[24]，代谢网络[25]，蛋白质相互作用网络[26]，社交网络[11,16,17,22]，国际贸易网络[13,18，27]，金融网络[15,28,29]和交通网络[12,15,16]。例如，在研究者之间的合著网络中，主要研究者通常与其他主要研究者一起发表论文，形成一个核心，而其他研究者则倾向于与特定的主要研究者一起发表论文，例如那些在同一研究组中形成边缘的研究者[16]。

Borgatti和Everett介绍了核心-外围结构的第一个定量公式[11]。在核心-外围结构的离散化版本中，引入了一种理想化的核心-外围结构，即核心节点与所有其他节点相邻，外围节点与所有核心节点相邻，而不是与任何外围节点相邻。虽然假设核心-边缘连通性比核心-核心连通性更稀疏也是现实的[11]，但在本研究中，我们只关注理想化的核心-外围结构。 Borgatti和Everett寻求将给定网络中的所有节点分配给核心或外围，这样就使得网络尽可能的接近理想化的核心-外围结构。在他们的研究之后，许多核心外围检测算法得到了发展[11-13,15-18,20-22,25,27]。这些算法旨在识别嵌入在网络中的单个核心-外围对。然而，网络可以更好地被视为多个核心-外围对的集合[11,14,16,19-21]，这是本研究的重点。 例如，合著网络应该由多组研究人员组成。研究人员通常会与同一组中的主要研究人员合作，但不会与同一组中的其他研究人员合作，这可能导致组内的核心-外围结构[16]。在此方面，以往的研究并没有为此提供量身定制的可扩展算法。一项研究侧重于相关但不同类型的多核-外围结构[30]。其他算法的目标是检测多个核心，但不会假设外围节点彼此稀疏连接[17,31,32]。一个网络也可以有k个核心[33]，k个桁架[34]或密集的子图[35,36]形式的多个不相交核心。然而，相应的算法不能告诉外围节点彼此连接的密集程度或外围节点所属的核心。用于找到包含多个核心-外围对的各种网络中尺度结构的算法[19]计算成本昂贵，并且仅适用于小型网络（附录A）

我们提出了一种可扩展的算法来检测网络中的多个非重叠核心-外围对，每个核心-外围对都尽可能接近理想化的核心-外围结构。我们的算法自动确定核心-外围对的数量和大小。 用于检测网络中核心-外围结构的各种算法被分类为基于密度和基于传输的算法[15,21,25]。基于密集的算法假定核心是一组密集连接的节点，而基于传输的算法假定核心是一组可以通过短路径从其他节点到达的节点。在目前的研究中，我们主要研究基于密度的算法。

2.方法

A.算法

我们将Borgatti和Everett[11]引入的理想核心-边缘结构扩展到多对核心和外围的情况。 在Borgatti-Everett（BE）算法中，考虑由N个节点和M个边缘组成的图（即，网络）。设A=Aij为邻接矩阵，即，如果节点i和j相邻一条边，则A_ij=1，否则A_ij=0。我们假设一个无方向和无权重的网络没有自循环，也就是说，所有i和j的A_ij=A_ji和A_ii=0。设x=(x₁,x₂,...x_n)是长度N的向量，如果节点i是外围节点，则x_i＝0，如果i是核心节点，则x_i＝1。 我们将理想化的核心-外围结构定义为网络，其中每个核心节点与所有核心和外围节点相邻，并且每个外围节点与所有核心节点相邻但没有外围节点。 对应的相邻矩阵B(x)=[B_ij(x)]由下式给出

在本研究的基础上，本文提出了一种离散的BE算法，它寻求x，使A与B（X）之间的相似度最大化。我们将在 II C.中解释安全性的相似性度量。

我们将理想化的核心-外围结构扩展到多个核心-外围对的情况。 令C为核心-外围对的数量，并且C=(C₁,C₂,...C_n)是长度为N的向量，其中C_iisin;{1,2，...C}是节点i所属的核心-外围对的索引。 我们排除了核心-外围对之间的重叠以及核心-外围对之间核心和外围的重叠。 相应的邻接矩阵B（C，x）由下式给出

其中delta;是KroneCker delta。

我们寻求（C，x）使B（C，x）通过最大化与A最接近

=

=(-p)( -)

图1.随机块模型生成的网络的邻接矩阵的示意图。

填充块对应于概率theta;₁等于1的条目，否则为零。空块对应于概率theta;₂（theta;₂lt;theta;₁）等于1的条目，否则为零。 为了简单起见，对角线条目始终设置为零，并在图中显示为空条目。 虚线表示分隔不同块的边界。 标签（C，x）也指示在邻接矩阵的顶部和左侧。 标签R表示一个残余节点的块。 网络由（a）单核-外围对，（b）两个核-外围对，（C）单核-外围对和残余节点，以及（d）两个核-外围对和残余节点组成。 在所有情况下，我们设置N = 400。

其中P =[ M / [N（N-1）/ 2]是网络中边缘的密度。

术语表示在给定网络和理想化核心-外围结构中存在的边缘的数量。 零模型项是理想化核心-外围结构和Erd˝os-Reacute;nyi随机图[37]中存在的预期边数，其中每对节点都与概率p相邻。Q^Cp的范围在-M和M之间。一个较大的Q^Cp值表示给定的网络和理想的核心-外围结构共享更多的边缘比偶然多。

Erd˝os-Reacute;nyi随机图模型在核心-边缘结构的分析中得到广泛应用。与社区检测的模块化类似，我们的公式允许使用不同的空模型，例如配置模型。 见第二节V进一步讨论。

1. Q^Cp的最大化

图2.三种算法的真实和推断核心-外围结构之间的VI值。

行S1，S2，S3和S4对应于图1和2中所示的具有种植的核心-外围结构的网络。分别如图1（a），1（b），1（C），和1（d）所示。 每个单元格的颜色表示VI值。 白细胞是我们没有计算VI值的细胞，即我们只计算它们的theta;₁gt;theta;₂。

我们使用标签切换启发式[40,41]来最大化Q^Cp。 首先，我们通过设置（C_i,x_i）=（i，1）（1le;ile;N）将每个节点分配给不同的核心。然后，我们以随机顺序扫描所有节点。 对于每个扫描节点i，我们计算中Q^Cp的增量，当我们暂时更新（C_i,x_i）到核心-外围对的核心时，节点i的邻居（由j表示）属于，（C_i，1）。 当我们暂时更新（C_i,x_i）到（C_i，0）时，我们还计算增量Q^Cp。 请注意，无论x_i= 0还是x_i= 1，我们都会对这两种情况进行实验。我们对所有邻居执行此过程，以测量每种情况下Q^Cp的增量。 最后，weupdate，（C_i,x_i）到在Q^Cp[即，（C_i，0）或（C_i，1）为邻居j]中产生最大暂定增量的标签。 如果任何重新标记不会增加Q^Cp，我们不会更新（C_i,x_i）。当我们扫描所有节点时，如果没有节点在当前轮次中更改了其标签，我们就会停止整个过程。 否则，我们绘制一个新的节点随机顺序，并根据新的随机顺序再次扫描所有节点。

将节点i的标签从（C，x）更改为（C`，x`）时Q^Cp的增量由下式得出：

式中d_{i,（C，x）}是具有标签（C，x）的节点i的邻居数，而N_（C，x）是具有标签（C，x）的节点数。对于每个扫描节点,我们最多计算2d_i次公式（4），其中d_i是节点i的程度。 因此，扫描一轮中所有节点的时间复杂度是=，整个算法的时间复杂度是，其中r是轮数。 我们从上述相同的初始条件开始运行该算法20次，并采用产生最大Q^Cp值的模式标记。

1. 核心-边缘结构的重要性

检测到的核心-外围结构可能在统计学上是非常重要的[11,38]。 因此，我们将单核-外围对的统计检验[38]与多核-外围对的统计检验相适应。在单个核心-外围对的统计检验[38]中，我们根据Pearson相关系数[11]通过水性函数测量核心-边缘对的显著性，该系数由下式定义：

资料编号：[5418]