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

它的社区可以包含来自同一层的节点和来自不同层的节点。不同层的节点可以是不同时间的同一节点（is，ir，s 6=r）或不同时间的不同节点（is，jr，i 6=j，s 6=r）。我们说，如果δ（顺式，顺式+1）=1（分别，δ（顺式，顺式+1）=0），则在连续层s和s+1之间的相同群落中（分别，改变群落）。正有序、对角和均匀层间连接有利于节点在连续层之间保持在同一社区中。每当一个节点不改变两个连续层之间的群落（即δ（cis，cis+1）=1），多层质量函数就会增加2ω的正贡献。因此，人们倾向于不随时间变化的社区，因为社区分配是可传递的：如果δ（cis，cjs）=1和δ（cis，cis+1）=δ（cjs，cjs+1）=1，那么δ（cis+1，cjs+1）=1。我们将多层分区的持久性定义为不改变层间社区的节点总数：Pers（C）：=|T|-1Xs=1NXi=1δ（顺式，顺式+1）∈ {0，…，N（|T|- 1)} . （5.1）如等式（5.1）所示，Pers（C）是介于0和N（|T|）之间的整数，当非节点始终在同一个群体中跨越层时，会出现这种情况-1） ，当每个节点始终保持在同一个社区中时发生。（参见[7]了解一种被称为“灵活性”的密切相关测量方法，该方法已应用于功能性大脑网络。）Letters（C）| s注意在两个连续层s和s+1之间保持在同一社区中的节点数：Pers（C）| s:=NXi=1δ（cis，cis+1）∈ {0，…，N}，（5.2）所以Pers（C）=P|T|-1s=1Pers（C）| s。持久性提供了一种深刻的方法来重写多层模块化最大化问题：maxC∈C|T | Xs=1NXi，j=1Bijsδ（cis，cjs）+2ΩPers（C）.

（5.3）因此，多层最大化问题衡量了层内的静态社区结构（5.3中的第一项）和跨层的时间持久性（5.3中的第二项）之间的权衡。为了更好地理解通过非零层间耦合（即使用ω>0）获得的分区如何与通过层间耦合（即使用ω=0）获得的分区不同，我们定义了有助于将多层分区与单层分区进行比较的明确符号。设Ns:={1s，…，Ns}表示层s中的节点集 {1，…，N；1，…，N；…；1 | T |，…，N | T |}到层s是Cl | s:=Cl∩ Ns，我们定义了由多层分区C引起的分区∈ 层s上的C byC | s:={Cl | s，Cl∈ C} 。为了便于编写，我们在本节中将“全局最优分区”称为“最优分区”，并将顶层|T | s=1PNi，j=1Bijsδ（cis，cjs）（即（5.3）中的第一项）称为层内模块化。在接下来的两小节中，我们将说明由ω>0的多层分区在各个层上产生的分区集如何与ω=0.5.1的层内分区相比较。玩具的例子。5.1.1. 连接模式的变化。这个玩具示例说明了层间耦合如何使我们能够检测和区分跨层连接模式的变化。在图5.1中，我们展示了一个未加权的多层网络，其中| T |=10层，每层中N=8个节点。除第3层和第6层外，每一层都包含两个4节点团。在第3层中，节点5连接到节点{1,2}，而不是节点{6,7,8}。在第6层中，节点5连接到节点{1,2,3,4}，而不是节点{6,7,8}。我们在图5.1的面板（a）-（c）中显示了多层网络的层。我们使用一个解参数γ=1的U零网络来检验它的社区。

然后，层s具有以下单层模块化矩阵：Bijs=1.- 哈西，如果我和j有联系-哈西，不然。每层中的最佳分区是唯一的，对于s，在s层中的最佳分区是Cs={1s，2s，3s，4s}，{5s，6s，7s，8s}/∈ 在第3层和第6层中，{3,6}和is Cs={1s，2s，3s，4s，5s}，{6s，7s，8s}。当层间耦合的值为0时，最佳多层划分是| T |断开的最佳单层划分的并集。我们在图5.1的面板（d）中显示的多层划分C=Si=1Cs的持久性为pers（C）=0。对于任何ω>0的分区，任何具有与C相同的层内分区且持久性非零值的分区都会产生比C更高的多层模块化值。这直接来自多层质量函数的表达式：Q（C | B）=T | Xs=1NXi，j=1Bijsδ（cis，cjs）+2ωPers（C）。在不改变层内分区的情况下增加持久性会增加Q（C | B）的最后一项，而不改变其他项。（在第5.2节中，我们将证明ω>0对于一个最优划分具有持续性的正值是必要的和有效的。）为了获得面板（e）中的多层分区，我们将面板（d）中包含1的所有集合合并到一个集合中，并将包含n的所有集合合并到另一个集合中。这个分区的持久性等于N（|T |- 1) - 4，以及任何其他组合Cyields中集合的方法，都会降低持久性值。SSSS（a）层6=3，6（b）层3（c）层6（d）分区c（e）分区c（f）分区c（g）分区C0 0.5 1 1.5 2-20-10010ω Q（e）（f）（g）（h）多层模块化值相对于分区CFig的变化。5.1. 举例说明使用有序对角线和均匀层间耦合来检测跨层社区结构的变化。我们考虑10个层（|T |=10），每个层中有8个节点（N=8）。

我们展示了（a）层s6中的网络结构∈ {3,6}，（b）第3层和（c）第6层。图（d）-（g）展示了四种不同的多层隔板。在每个面板中，圆的STH列代表sthlayer中的节点，我们从1到8排列。Weshow使用面板（d）中的实心曲线（避免使用20种不同的颜色）和面板（e）–（g）中的颜色显示同一社区中的节点集。在图（h）中，我们展示了图（f）（细线）和图（g）（粗线）中的分区与图（e）中不同ω值的分区之间的多层模块化值的差异。我们用水平虚线表示细线与水平轴的交点。由面板（h）中两条连续垂直线之间的面积定义的区域中的面板标签表明面板（e）、（f）和（g）中的哪个多层分区具有较高的模块化值。我们现在进一步检查图5.1。我们考虑面板（e）-（g）中的多层隔板。面板（e）中的示例显示了第3层[见面板（b）]和第6层[见面板（c）]的结构变化，面板（f）中的示例仅显示了第6层的变化，面板（g）未显示任何变化。正如我们在下面的模块化成本方面所做的量化，第6层的变化是两个变化中“更强”的。我们让Cdenote表示面板（e）中的多层分区，Cdenote表示面板（f）中的多层分区，Cdenote表示面板（g）中的多层分区。另外，请注意Pers（C）<Pers（C）<Pers（C）。层间耦合的ω值决定了这三个分区中哪一个分区具有最大的多层耦合度值。为了看到这一点，我们计算了为了持久化而改变层内静态社区结构的模块化成本。

（这种计算是[30]中静态网络计算的多层版本。）Cof中的层内模块化成本将节点5sF从社区{1s，2s，3s，4s，5s}移动到层s中的社区{6s，7s，8s}∈ {3,6}是Q（s）=2Xj∈{6,7,8}B5js-Xj∈{1,2,3,4}B5js=-4+2hAi≈ -3.3，如果s=3，-8+2hAi≈ -7.2，如果s=6。这两种情况下，层间模块化成本均为+4Ω；+4ω的第一个+2ω贡献后面是B的对称性，而+4ω的第二个+2ω贡献后面是一个事实，即任何一个移动都会增加+2的持续性。因此，对于0<4ω<|Q（3）|，面板（e）中的分区比（f）和（g）中的分区产生更大的多层模块化值。什么时候|Q（3）|<4Ω<|Q（6）|，在（f）中，分区的多层模块化值大于（e）或（g）的多层模块化值。最后，当4ω>|Q（6）|，面板（g）中的分区具有三个分区中最大的多层模块化值。当4ω=|Q（3）|（分别为4Ω=|Q（6）|），面板（e）和（f）（分别是，（f）和（g））中的多层隔板具有相同的多层模块化值。我们通过绘图Q（C | B）在图5.1（h）中说明了这些结果- Q（C|B）和Q（C|B）- Q（C | B）对ω。这个例子简单地说明了层间连接如何帮助区分连接模式中的变化：更强的变化（模块化成本方面）在层间耦合的更大值上持续存在（参见[4,59]，了解时态网络中“变化点检测”的其他方法）。5.1.2。共享连接模式。在前面的玩具示例中，当ω=0时，图5.1（e，f，g）中的多层分区在每层上诱导的层内分区对于至少一层是最佳的（参见图5.1（d））。

第二个示例说明了层间耦合如何识别层内分区，当ω=0时，这些分区对于任何单独的层都不是最优的，但反映了跨层共享的连接模式。在图5.2中，我们考虑了一个未加权的多层网络，其中| T |=3层，每层中N=13个节点。每个sthlayer包含四个3节点的cliques和一个连接到sthclique中三个节点中的每个节点的节点，以及4thlique中的tonodes 10和12。我们在平面图（a）-（c）中展示了多层网络的各层。我们使用一个resolutionparameter值为γ=1的U空网络来检查它的社区。每一层中的最优划分是唯一的，对于第1层，{1,2,3,13}，{4,5,6}，{7,8,9}，{10,11,12}，{1,2,3}，{4,5,6,13}，{7,8,9}，{10,11,12}，对于第2层，{1,2,3}，{4,5,6,3}，{7,8,9,13}，13}，{12}，对于第3层。我们通过组合这些集合来获得多层分区Cinpanel（d），使得当ω=0且层间持久性最大时，诱导的层内分区对于每一层都是最优的。多层分区Cin面板（e）反映了所有层共享的连接模式（即节点13Si与第四个3节点组而不是sth3节点组）；但当ω=0时，它的层内分区对于任何层都不是最优的。通过进行与前一个玩具示例类似的计算，我们可以证明，当ω>3/2时，面板（e）中的多层划分会产生更大的模块化。e、 ，当4ω+6[2（1-（海斯）-海斯-3(1-hAis）]>0，其中hAi=hAi=hAiby施工（a）第1层（b）第2层（c）第3层（d）分区c（e）分区C0 0.5 1 1.5 2-10-505ω Q（d）（e）（f）关于分区CFig的多层模块化值的变化。5.2.

玩具示例演示了如何使用有序对角线和均匀层间耦合来检测跨层的共享连接模式。我们考虑三层（|T |=3），每层有13个节点（N=13）。我们展示了（a）第1层，（b）第2层和（c）第3层中的网络结构。实线表示所有三层中存在的边，虚线表示仅在其中一层中存在的边。面板（d）和（e）展示了两个不同的多层分区。在每个面板中，圆的STH列表示sthlayer中的节点，我们将其排序为1到13。我们使用面板（d）和（e）中的颜色显示同一社区中的节点集。在图（f）中，我们展示了不同ω值的图（e）中的分区和图（d）中的分区之间的多层模块化值的差异。我们用水平虚线来表示直线与水平轴的交点。由面板（f）中两条连续垂直线之间的面积定义的区域中的面板标签表明面板（d）和（e）中的哪一个多层隔墙具有更大的多层模块化值。值大于面板（d）中的多层分区。我们在图5.2（f）中通过绘制Q（C | B）来说明这一结果-Q（C | B）对ω。本例简单说明了层间连接如何帮助识别跨层共享的连接模式。5.2. 多层隔板的一些性质。我们现在要问的是，引入正序对角和均匀耦合（即ω>0）如何改变静态网络（即ω=0的情况）的最大模划分集。为了明确区分层内和层间模块化贡献，我们用q（C | B。

，B | T |；ω） ：=|T | Xs=1NXi，j=1Bijsδ（cis，cjs）+2ΩPers（C）。而不是Q（C | B），其中C∈ C是一个多层分区。在本节中，我们假设| T |≥ 2.设Cmax（ω）表示多层模块最大化问题（5.3）的最优划分集，并设Cωmax为Cmax（ω）中的任意划分。在接下来的讨论中，回忆一下我们的假设是，集合C中的每个分区都包含集合，这些集合在邻接矩阵B的加权图中没有多个连通分量。这尤其适用于分区Cωmax∈ Cmax（ω）。我们证明了对于任意选择的矩阵Bs（例如，如果使用具有U零网络和分辨率参数值为1的modularityquality函数，则Bs=As）的几个命题- 哈西恩）。提议5.1。Pers（Cωmax）>0<=> ω > 0 .命题5.1确保只要ω的值严格为正，最优解的持久性也为正。为了证明这一点，有必要观察到，如果一个人通过将一些集合合并到同一个集合中来重新排列多层分区中的集合，而不改变各个层上的分区，那么他只会改变多层模块性表达式中持久性的值。例如，当从面板（d）中的隔板转到面板（e）中的隔板时，这种现象出现在图5.1中。证据=>: 我们证明了相反的结果。假设ω=0，考虑多层分区C，使得Pers（C）>0。

分区C至少包含一个具有多个连接组件的集合（因为Pers（C）>0且不同层中的节点未连接），并且C不是最优的，因为我们假设全局最优解不包含具有多个连接组件的集合。<=: 假设ω>0，考虑多层分区C，使得Pers（C）=0。我们将证明C不是最优的。设ir是{1，…，N；…；1 |T |，…，N |T |}中的任意节点，并设Cir表示C中包含ir的集合。让Cbe通过将包含is的所有集合（对于某些s）组合成一个集合，从而从C获得分区：C=C\\|T |[s=1{Cis}∪|T |[s=1Cis,其中CIS表示C中包含is的集合。因此，Q（C | B，…，B | T |ω）≥ Q（C | B，…，B | T |ω）+2ω（|T |- 1） ，所以C不是最优的。（注意2ω（|T |- 1） 对于ω>0是严格正的，因为我们假设|T |≥ 2.）提案5.2。如果Cl | r= 为了一些人∈ {1，…，T |- 1} ，则Cl | s= 对于所有s>r，其中Cl∈ Cωmax和Cωmax∈ Cmax（ω）。命题5.2确保如果一个社区在给定的层中变为空，那么它在所有后续层中保持为空。我们省略了这个证明，因为这个结果直接来自于B的稀疏模式，以及我们的假设，即在邻接矩阵B的图中，最优分割不包含具有多个连通分量的集。命题5.3。Cωmax | s=Cωmax | s+1<=> Pers（Cωmax）|s=N.命题5.3将两层之间的持久性概念与层内群落结构的变化联系起来。通过有序对角和均匀层间耦合进行的各种数值实验包括改变ω的值，并使用节点何时在层间改变群落的信息作为这些层内群落结构变化的指示[6,7,49]。

命题5.3中的等价关系促使使用pers（C）| s（或其变体）作为社区结构层内变化的指示。证据<=: 社区分配的传递性直接遵循了这一点：如果δ（cjs，cjs+1）=δ（cis，cis+1）=1表示所有i，j，那么δ（cis，cjs）=1当且仅当δ（cis+1，cjs+1）=1表示所有i，j（这个方向适用于任何多层分区；它不需要是最优的）=>: 让C∈ C是一个多层分区，使得C | s=C | s+1和Pers（C）| s<s∈ {1，…，T}。我们证明了C不是最优的。考虑一组Cl∈ 节点的C，使得Cl | s6=. 如果δ（cis，cis+1）=1（分别为δ（cis，cis+1）=0），则∈ Cl | s，则δ（cjs，cjs+1）=1（分别为δ（cjs，cjs+1）=0）∈ Cl | sby社区分配的及时性，因为C | s=C | s+1是由假设决定的。因为Pers（C）| s<N是假设的，所以至少存在一组Ck | sof节点（其中Ck∈ C） 使得δ（cis，cis+1）=0表示所有∈ Ck | s.设Cm | s+1，带Cm∈ C、 表示层s+1中包含is+1或所有is的节点集∈ Ck | s.考虑场景∪R≤CKK中位于{1，…，s}层和集合中的sCk | rof节点∪r> CM中的sCm | rof节点位于{s+1，…，|T |}层中。因为对于allis，δ（cis，cis+1）=0∈ Ck | s，根据命题5.2，Ck=∪R≤sCk |兰特厘米=∪r> sCm | r.定义分区CbyC=C\\{Ck}∪ {Cm}[{Ck∪ Cm}.该分区满足所有r的C | r=C | r∈ 因此，Q（C | B，…，B | T |ω）>Q（C | B，…，B | T |ω）和C不是最优的。命题5.1、5.2和5.3适用于以ω的任何正值获得的最优划分。接下来的两个命题涉及ω的“边界”值的存在性。提议5.4。