时态多层网络中的社区检测及其应用

这就产生了最大化问题maxC∈CNXi，j=1“A+ij-k+ik+j2m+！-A.-ij-K-ik-j2m-!#δ（ci，cj），（2.13），其中k+i和2m+（分别为k-陆地2米-) A+中的强度和总优势权重（分别为A-). 这种推广背后的直觉是在无符号矩阵A+和A上使用NGnull网络-但以与正边缘权重（即（2.13）中的第一组术语）相反的方式计算负边缘权重（即（2.13）中的第二组术语）对调制度的贡献。超过其预期边缘权重的负边缘权重将受到惩罚（即，它们降低了模块性），而没有的负边缘权重将得到奖励（即，它们增加了模块性）。可以生成边权重为0、1或0的网络-1和预期边缘权重k+ik+j/（2m+）- K-ik-j/（2m）-) 通过生成一个具有预期边缘权重W+ij=k+ik+j/（2m+）的网络和一个具有预期边缘权重sw的第二个网络-ij=k-ik-j/（2m）-) 使用第2节中描述的NG null网络程序。4.1，然后定义一个网络，其边缘权重由这两个网络的边缘权重之差给出。更一般地说，根据脚注5和期望线性，集合{W]上的任何概率分布∈ 满足两个条件的有符号邻接矩阵的RN×N}NXj=1W+ij= k+i和E（W+ij）=f（k+i）f（k+j），（2.14）ENXj=1W-ij= K-土地东（西）-ij）=g（k-i） g（k）-j） ，（2.15），其中f和g是实值函数，Wij=W+ij- W-ij的预期边光为E（Wij）=k+ik+j/（2m+）- K-ik-j/（2m）-) 尽管如此，j∈ {1, . . .

，N}。[49]的作者通过建立用于推导NG空网络的随机游走方法，推导出了短时间尺度下NGS空网络的多尺度模块化公式（2.6）的变体。他们考虑了函数^r（C，t）=NXi，j=1πiδij+t∧ii（Mij- δij）- πiρi | jδ（ci，cj），（2.16），其中左侧括号中的术语是（2.12）中的指数变量M、M和πiare的线性化，如（2.12）中所定义，在邻接矩阵| a |：：=a++a的网络上-, ρi | jis是在网络结构的条件下，在平稳状态下一步从节点i跳到节点j的概率[49]。如果网络是非二部的、无符号的和无向的，那么ρi | j将减少到平稳概率πj.2.4.3。统一（U）零网络。第三个零网络，我们认为是isa统一（U）零网络，其邻接矩阵项Pij=hki/（2m），其中hki：=PNi=1ki/N表示网络中的平均强度。由此我们得到了等价的最大化问题∈CNXi，j=1Aij-hki2m！δ（ci，cj）<=> 麦克斯∈STr装货单A.-hki2mNs, （2.17）其中A是无符号邻接矩阵，1Nis是N×N矩阵，其中everyentry为1。（2.17）中的预期边缘重量是恒定的，令人满意=PNi=1kiNPNi=1ki=2mN=hAi，尤其是，他们在[71]中使用Pottsmodel方法推导了模块化的多尺度公式。这个多尺度公式产生一个分辨率参数γ，用于项（k+ik+j）/（2m+）和第二个分辨率参数γ，用于项（k）-ik-j） /（2米）-) 在（2.13）中（参见[47]了解该多尺度公式在联合国大会投票网络中的应用）。

如果没有应用程序驱动的对如何选择这些参数的调整，这将大大增加参数空间，因此我们在本文中只考虑γ=γ的情况。对于所有节点都具有相同强度的网络，uniform和Newman–Girvan-nullnetworks是等效的，因为对于所有i，j，ki=kj<=> ki=2m/N=hki代表所有i。这是[22]中针对外汇市场的应用程序指出的。其中hAi表示邻接矩阵的平均值。用邻接矩阵hAi1Nis生成无权网络的一种方法是用概率hAi生成每条边（提供hAi）≤ 1). 也就是说，边（包括自边）的存在和不存在是具有概率hAi的独立同分布（i.i.d.）伯努利随机变量。更一般地说，邻接矩阵集合上满足PNi，j=1Wij= 2m和E（Wij）=E（Wij）对于所有i，j，i，j作为期望的邻接矩阵E（W）=hAi1N。U零网络的邻接矩阵是对称的正半限定矩阵。我们可以从stabilityquality函数推导出（2.6）中U零网络的多尺度公式，其推导方法与NG零网络的推导方法完全相同，只是需要考虑每个节点的指数分布等待时间，其速率与节点强度成正比（即∧ij=δ（i，j）ki/hki）[42]。多层模块化最大化。3.1. 时间网络的多层表示。我们将注意力限制在时间网络上，在这个网络中，只有边缘随时间变化。（因此，每个节点都存在于所有层中。）我们在邻接矩阵序列T={a，…，a | T |}中使用符号ASA表示层，并用字节表示层s中的节点i。我们将术语“多层网络”用于定义在节点集{1，…，N；1，…，N；…；1 | T |。

，N | T |}[39]。到目前为止，对时间网络使用多层框架的计算几乎总是假设（1）层间连接仅存在于对应于同一实体的节点之间（即，对于某些区域，节点isand IR6=r之间）和（2）网络层是“有序的”（即，层间边在连续层之间存在）[7,39,49,50,63]。通常还假设（3）层间连接是均匀的（即层间边缘具有相同的权重）。在最近一篇关于多层网络的评论文章[39]中，条件（1）被称为“对角”耦合，条件（2）暗示网络是“层耦合”的。我们将（1）、（2）和（3）定义的耦合类型称为有序对角和均匀层间耦合，并用ω表示层间边缘权重的值∈ R.Weshow在图3.1中展示了具有顺序对角和均匀中间层耦合的多层网络的简单图示。可以考虑更一般的层间连接（例如，非均匀连接）。虽然我们在理论和计算讨论中只关注均匀耦合，但在第5节中我们给出了层间耦合的非均匀选择示例。类似于5.2小节的结果也适用于这种更一般的情况。3.2. 多层模块化函数。[49]的作者将（2.6）中的单层多尺度模块化最大化问题推广到多层网络，使用的方法与从观测网络上的随机马尔可夫过程导出NGS空网络的方法类似。为了简单起见，我们使用单个N | T | x N | T |矩阵表示N | T |节点多层网络中的层内和层间连接。

层s中的每个节点都有唯一的索引i:=i+（s- 1） N，我们用A来表示多层邻接矩阵，其条目Aij=Aijsδ（s，r）+ωδ（|s）- r |，1）当层间耦合为有序对角且均匀时。（如[39]中所讨论的，可以使用邻接张量，也可以使用无符号邻接矩阵上的一致零网络。尽管本文在无符号邻接矩阵上使用一致零网络，但对于相关矩阵，一致零网络中的预期边权始终是非负的，正半不确定性保证hAi=1TA1/（N）≥ 0.第1层第2层第3层←→0 1 1 ω 0 0 0 0 01 0 0 0 ω 0 0 0 01 0 0 0 0 ω 0 0 0ω 0 0 0 1 1 ω 0 00 ω 0 1 0 1 0 ω 00 0 ω 1 1 0 0 0 ω0 0 0 ω 0 0 0 1 00 0 0 0 ω 0 1 0 10 0 0 0 0 ω 0 1 0图3.1。（左）具有未加权层内连接（实线）和均匀加权层间连接（虚线）以及（右）其对应邻接矩阵的多层网络示例。

（对应于多层网络的邻接矩阵有时在网络科学文献[39]中被称为“超邻接矩阵”。）或表示多层网络的邻接矩阵。）[49]中的推广包括将（2.16）中的函数应用于N | T |节点多层网络：^r（C，T）=N | T | Xi，j=1πiδij+t∧ii（Mij- δij）- πiρi | jδ（ci，cj），（3.1），其中C现在是一个多层分区（即，一个N | T |节点多层网络的分区），∧是N | T |×N | T |对角矩阵，其对角线上每一层的每个节点的指数分布等待时间的速率，M（条目Mij:=Aij/PjAij）是N | T | T | T |网络的N | T |过渡矩阵，具有邻接矩阵，πi是相应的平稳分布（节点的强度和总边权重现在由多层邻接矩阵a计算），ρi | jis是在一步平稳时从节点i跳到节点j的概率，取决于层内和层间网络的结构。作者选择的ρi | j解释了多层邻接矩阵中层间边缘的“稀疏模式”，激发了多层模块化最大化问题maxC∈CN | T | Xi，j=1Bijδ（ci，cj），（3.2），也可以写成maxC∈CQ（C | B），其中B是多层模块化矩阵xb=Bωi0。0ωI。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。ωI0。0ωib | T|, （3.3）矩阵X的稀疏模式是矩阵Y，当Xij6=0时，条目Yij=1，当Xij=0时，条目Yij=0。BSI是在s层上计算的单层模块化矩阵。

（例如，Bs=As）- hAsi1Nif one使用U null网络并设置γ=1。）我们在[49]asmaxC中重写了多层模块最大化问题∈C“|T | Xs=1NXi，j=1Bijsδ（cis，cjs）+2Ω|T|-1Xs=1NXi=1δ（cis，cis+1）#，（3.4），其中bijs表示Bs的（i，j）。方程（3.4）明确区分了多层质量函数的层内贡献（左项）和层间贡献（右项）。在实践中，我们可以使用第2.2小节中的Louvain启发式解决这个多层模块化最大化问题，方法是使用多层模块化矩阵B代替单层模块化矩阵B作为输入（阶段1的第一次迭代中的节点数变为N | T |而不是N）。在这种情况下，initialpartition由N | T |个单例组成。首先，将每个N | T |节点放入一个集合中（可能是它已经存在的位置），从而最大程度地提高多层模块性。然后，我们在简化的网络上（如第2.2节所述）重复此过程，直到启发式收敛。从（3.4）中可以清楚地看出，将不同层的节点放在同一集合中，我们称之为层间合并，当ω<0时，多层质量函数的值会减小，因此我们只考虑ω≥ 0.与单层网络一样，我们假设n | T |节点分区集合C中的每个分区都包含在邻接矩阵B的图中没有多个连通分量的集合。在第5节中，我们试图通过证明几个属性来理解如何解释全局最优的多层分区。我们给出的结果适用于任意选择的矩阵B，B | T |，所以（例如）当在每一层上使用（2.12）中的稳定性质量函数而不是模块化质量函数时，它们仍然适用。

为了便于编写（因为模块化是我们在第5节的计算实验中使用的质量函数），我们将继续将最大化问题（3.4）称为多层模块化最大化问题。4.解释具有不同零网络的相关网络中的社区结构。从方程（3.3）中B的结构可以清楚地看出，对于给定的质量函数，层内质量函数的选择（即多层调制矩阵中的对角线块）和层间耦合的选择（即效果-对角线块）会影响（3.4）中最大化问题的解。在这一部分中，我们对使用模块化质量函数时相关网络的空网络选择进行了一些观察。为此，我们考虑了具有零层间耦合（即ω=0）的多层模块化最大化问题（3.4），这相当于在每一层上独立地执行单层模块化最大化。4.1. 玩具的例子。我们描述了两个简单的玩具网络来说明NG（2.8）和NGS（2.13）空网络的一些特征，这些特征可能会误导集合相关网络。4.1.1. NG空网络。假设网络中的节点被划分为K个不重叠的类别（例如，资产类别），这样所有类别内的边权重都有一个常量a>0，所有类别间的边权重都有一个常量20 40 60 80 100100806040201110.30.31（a）无符号邻接矩阵20 40 60 80 1002046080100（b）NG空网络的多尺度关联矩阵20 40 80 1002046080100（c）U零网络的多尺度关联矩阵0.5 120 40 60 80 1001008060402011-0.05-0.050.4（d）有符号邻接矩阵x20 40 60 80 1002046080100（e）NGS空网络的多尺度关联矩阵20 40 60 80 1002046080100（f）U空网络的多尺度关联矩阵图。4.1.

（a） 玩具无符号块矩阵，带有常数对角线和带块中指示值的反对角线块。（b） （a）的多尺度关联矩阵，给出了使用NG空网络跨分辨率参数值对节点进行共分类的频率。（c） （a）的多尺度关联矩阵，使用U空网络。（d） 玩具符号块矩阵，具有常数对角线和负对角线块，取块中指示的值。（e） 使用NGS空网络的（d）的多尺度关联矩阵。（f） （d）的多尺度关联矩阵，使用U空网络。对于NG和U（分别为NGS）空网络，我们的解参数值样本是{γ集-, . . . , γ+}（分别为，{0，…，γ+}），离散化步骤为10-3在每对连续值之间。值b，带0≤ b<a.让κi注意节点i的类别，并重写节点i的强度aski=|κi | a+（N- |κi |）b=|κi |（a）- b） +Nb。该网络中节点的强度与其类别中节点的数量成正比。假设我们有两类κ，κ不包含相同的节点。取|κ|>|κ|在不失去一般性的情况下，得出pi，j∈κ=2m“|κ|（a）- b） +Nb#>2m“|κ|（a）- b） +Nb#=Pi，j∈κ、 （4.1）式中Pi，j∈κiI NGnull网络中κiI中节点对之间的预期边权重。也就是说，NG空网络中属于较大类别的节点对比属于较小类别的节点对具有更大的预期边权重。为了了解等式（4.1）如何导致误导性结果，我们进行了一个简单的实验。考虑图4.1（a）中的玩具网络，它包含100个节点，分为大小为40、30、20和10的四类。我们将类别内边缘权重设置为1，类别间边缘权重设置为0.3（即方程式（4.1）中的a=1和b=0.3）。在图4.1（b）中（分别为。

4.1（c）），我们使用NG空网络（分别为U空网络）展示了（2.7）中定义的多尺度关联矩阵。颜色随分辨率参数值将成对节点共同分类为同一社区的频率而变化。由于节点是按类别排序的，图4.1（b，c）中的对角块表示同一类别中节点的共分类指数，对角块表示不同类别中节点的共分类指数。我们在图4.1（b）中观察到，当使用NG空网络时，在较小的分辨率参数值范围内，较大的类别被识别为一个群体，而不是较小的类别。特别是，当γ<a/Pi，j时，κ类被确定为单一群落∈κ（带a/Pi，j∈κ<a/Pi，j∈当|κ|>时|κ|通过等式（4.1））。当γ≥ a/Pi，j∈κ、 κ类被定义为|κ|单身社区。然而，我们在图4.1（c）中观察到，当使用U空网络时，所有四个类别都被识别为同一分辨率参数值范围内的单个群体。特别是，当γ<a/hAi时，κ类被确定为一个单一社区，当γ<a/hAi时，κ类被确定为|κ|单一社区≥ a/海。多尺度模块化最大化的标准解释是，当γ值较大时，所获得的共同体显示出观测网络中“更小”且“更密集”的连接节点[41,64]。尽管图4.1（a）中的所有对角线块具有相同的内部连通性，但当使用NG空网络时，不同的对角线块被识别为不同的γ值社区，随着γ的增加，最大类别中的节点首先分裂为单态，其次是第二大类别中的节点，等等。在本例中，在使用多尺度社区结构来获取有关被观测网络中连接模式的信息时，需要谨慎。4.1.2. 网络。