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

如果所有i和j的Aij<pij，则最优解为N个单子群。相反，如果所有i和j的Aij>pij，则最佳解决方案是单个N节点社区。为了获得具有高模性值的网络分区，人们希望在满足Aij>pijan的集合中有许多边，在满足Aij<Pij的集合中有许多边。从等式（2.3）中可以明显看出，在这种情况下，所谓的“密集连接”从根本上取决于空网络的选择。使用模块化[53]可以跟踪矩阵的最大化问题。和前面一样，我们考虑将网络的C划分为K个节点集{C，…，CK}。我们定义了划分矩阵S∈ {0，1}N×KasSij=δ（ci，j），（2.4），其中j∈ {1，…，K}和ci=j意味着节点i位于Cj中。S的列是正交的，S的JTH列和给出了Cj中的节点数。这意味着sNxi，j=1Bijδ（ci，cj）=NXi，j=1KXk=1SikBijSjk=Tr（STBS），其中STBS的（i，i）项是ci中节点之间的模块化矩阵项之和的两倍。（i，j）thoff-对角项是两个节点之间的模块化矩阵中心之和，其中一个节点位于CIAN，另一个节点位于Cj。）因此，我们可以在（2.3）asmaxS中重述模块化最大化问题∈STr（STBS），（2.5），其中S是{0，1}N×K（带K）中所有划分矩阵的集合≤ N） 。模块化最大化是众多社区检测方法之一[25]，它有许多局限性（例如，社区规模的分辨率限制[26]和大量几乎退化的局部极大值[30]）。然而，它是一种apopular方法（已成功应用于许多应用程序[25,61]），并且能够明确指定用户预期的功能，对于处理不同应用程序的用户来说是一种有用（且未充分利用）的功能。

在第四节中，我们对使用模块化质量函数时选择空网络做了一些观察。2.2. Louvain计算启发式。对于给定的模块化矩阵B，模块化最大化问题的解决方案保证存在于具有有限个节点的任何网络中。然而，N节点网络中可能的分区数（由Bell数[9]给出）至少随N呈指数增长，因此分区空间的穷举搜索是不可行的。模块化最大化在[14]中被证明是一个NP难问题（至少对于我们在本文中考虑的零网络而言），因此解决它需要使用计算启发式。在本文中，我们主要研究Louvain启发式算法，它是分区集合上的一个贪婪模块化递增抽样过程[10]。Louvain启发式由两个阶段组成，反复进行。最初，网络中的每个节点构成一个集合，该集合给出一个由N个单态组成的初始分区。在第一阶段，我们会逐个考虑节点（按一定顺序），并将每个节点放在一个集合中（可能是它已经存在的地方），这将导致模块化程度的最大提高。重复这个阶段，直到达到局部最大值（即，直到获得一个分区，其中单个节点的移动不会增加模块性）。第2阶段包括从第1阶段收敛后获得的G中的节点集构造简化网络G。在第1阶段结束时，通过{^C，…，^C^N}（其中^N≤ N） 通过^ci对这个分区中的节点i进行赋值。每个集合^Ckin G构成G中的一个节点，并且GisB的约化模性矩阵=^STB^S，其中^S是{^C，…，^C^N}的划分矩阵。

这确保GHA中的所有单音分区的模块化值与我们在第1阶段结束时确定的G分区的模块化值相同。然后，在简化的网络上重复第1阶段，并继续迭代，直到启发式收敛（即，直到第2阶段没有引起进一步的变化）。由于我们特别使用了Louvain启发式的非确定性实现，节点顺序在第一阶段的每次迭代开始时都是随机的，因此我们获得的固定模块化矩阵的网络分区可以在运行中有所不同。为了说明这一点，可以计算给定模块化矩阵B在多个启发式运行中的节点到社区的共分类频率，而不是使用单个运行的输出分区。（参见[44]了解这种方法在“共识聚类”中的应用，[65]了解suchan方法在层次聚类中的应用。）我们使用术语关联矩阵来表示amatrix，它存储了两个节点在一个启发式算法的多次运行中被放置在同一个社区中的平均次数，并且我们使用术语节点i和j的共同分类指数来指定关联矩阵的（i，j）thentry。有许多其他的启发式方法可以用来最大化模块化[25,54,61]，但Louvain启发式在实践中是一个流行的选择[43]。这是非常快的[25,43]，这是多层网络中的一个重要考虑因素，其中节点总数是每层中的节点数乘以层数。在第5节中，我们指出了Louvain启发式（独立于如何实现）在时间多层网络中面临的两个问题。我们在本文中使用的启发式实现[1,38]是[10]中实现的一个广义版本。

它独立于零网络，以模块化矩阵作为输入，允许任意选择零网络，并在启发式第一阶段每次迭代开始时随机化节点顺序，以增加启发式的搜索空间。当一个人选择[10]中假设的同一个空网络，并在第一阶段的每次迭代中使用固定为{1，…，N}的节点顺序（N的值在启发式的第二阶段的每次迭代后都会改变），那么[38]中的实现和[10]中描述的实现返回相同的输出。2.3. 多尺度社区结构。许多网络包括多尺度的社区结构[25,61]，有些系统甚至有“部分中的部分”的层级社区结构[68]。在这种情况下，虽然在一定规模的社区内存在密集的互动（例如，同一学校的学生之间的友谊纽带），但在这些社区内的节点子集中，互动甚至更密集（例如，同一学校和同一学年的学生之间的友谊纽带）。模块化函数的一些变体已被提出用于检测不同规模的社区。一个流行的选择是使用分辨率参数γ来缩放空网络≥ 0生成多尺度模块化最大化问题[64]：maxC∈CNXi，j=1（Aij- γPij）δ（ci，cj）。（2.6）在某种意义上，参数γ的值决定了相对于观测网络，零网络的重要性。在分区C处计算的相应模块化矩阵和模块化函数为B=a- γP和Q（C | A；P；γ）=PNi，j=1（Aij- γPij）δ（ci，cj）。特殊情况γ=1在模性最大化问题（2.3）中产生模性矩阵和模性函数。

这种多尺度模块化的表述有一个动态的解释[41,42]，我们将在下一小节中讨论。在大多数社区检测应用中，观测网络和空网络的邻接矩阵都有非负项。在这些情况下，当0≤ γ ≤ γ-= mini6=j，Pij6=0（Aij/Pij）是一个单一的群落，无论观察到的网络中的任何结构如何清晰，因为nBij=Aij- γ-Pij≤ 0代表我，j∈ {1，…，N}。（我们排除了对角项，因为节点总是在自己的社区中。）然而，当γ>γ+=maxi6=j，Pij6=0（Aij/Pij）时（2.6）的解是N个单子，因为ebij=Aij- 对于所有i，j，γPij<0∈ {1，…，N}。在这些边界值γ处的分区对应于网络的最粗糙和最可能的分区，并且在这些边界之间改变分辨率参数使得在中等尺度上检查网络的社区结构成为可能。对于有符号边权的观测和/或零网络，改变γin（2.6）对最优解的影响背后的直觉并不简单。对于γ的任何值，单个社区和N个单一社区不需要是最优分区≥ 0.尤其是，对于γ的大小，Bijh与Aij的符号相同，对于γ的大小，Bijh与Pij的符号相反。关于进一步的讨论，请参见第4节，在该节中，我们探讨了改变边权重为零的观测网络的最优划分的解参数的影响。我们在区间[0，γ+]而不是[γ]内改变分辨率参数-, γ+]在有符号网络的数值实验中，因为当γ∈ [0, γ-].γ≥ γ+，可以证明所有模块化贡献不再改变符号。

它们在具有Pij的成对节点之间为负（分别为正）≥ 0（分别为Pij）≤ 0).区分社区检测方法[26]施加的最小社区规模的“分辨率限制”和网络中固有的多尺度社区结构[25,61,68]是很重要的。对于（2.6）中的多尺度模块化公式，[26]中描述的分辨率极限适用于γ的任何已知值。通过改变γ，可以确定小于任何特定γ值限制的群落。从这个意义上说，模块化的多尺度公式有助于“减轻”分辨率限制，尽管仍然存在问题[2,30,41]。在本文中，我们不讨论如何在不同尺度上识别社区的问题，尽管我们顺便指出，文献中包括多尺度模块化的变体（例如，见[2]）。我们在第4节中对空网络进行了观察，并使用（2.6）中的多尺度模块化公式说明了我们的观察如何在实践中得到体现。（我们的观察结果独立于人们所采用的多尺度模块化的表述，但对于多尺度模块化的不同变量，精确的表现形式可能会有所不同。）我们使用术语“多尺度社区结构”指的是一组局部最优解的克隆（γ），我们通过一组（不一定完全不同）分辨率参数值γ={γ，…，γl}的计算启发式获得，其中γ-= γ≤ . . . ≤γl=γ+。我们使用术语多尺度关联矩阵来表示关联矩阵^A∈ [0,1]N×N存储此集合中所有对节点的共分类索引：^Aij=PC∈Clocal（γ）δ（ci，cj）| Clocal（γ）|。（2.7）对于每个分区C∈ Clocal（γ），节点i和j要么是（即δ（ci，cj）=1），要么不是（即δ（ci，cj）=0）在同一个社区中。

因此，^Aijis是Clocal（γ）中节点i和j位于同一社区的平均分区数。valueof | Clocal（γ）|是我们考虑的γ的不同值的数量乘以为每个γ值执行的Louvain算法的运行次数。在第4节中，我们使用[γ]的离散化-, γ+]（分别为[0，γ+]）用于无符号（分别为有符号）网络，并对每个分辨率参数值执行一次运行。Clocal中的分区数（γ）正好是我们考虑的不同的γ值的数目（即，每个γ值一个分区）。我们在第4.2.4节的计算实验中重复使用矩阵^A。零模型和零网络。在本节中，我们将介绍三种网络。在第4.2.4.1节的计算实验中，我们使用这些空网络，对从Pearson相关矩阵中获得的群落的解释进行了几次观察。纽曼-吉尔文（NG）零网络。对于具有正边权的网络，一种常用的空网络选择是纽曼-吉凡（NG）空网络，其邻接矩阵条目为Pij=kikj/（2m），其中kiare表示观测节点的强度[52,56]。这就产生了等价的最大化问题maxC∈CNXi，j=1Aij-kikj2m！δ（ci，cj）<=> 麦克斯∈STr“STA-kkT2m！S#，（2.8），其中k=A1是节点强度的N×1向量，2m=1TA1是观测网络的总边光。这个空网络可以从各种空模型中派生出来。生成具有期望邻接矩阵xkkt/（2m）的未加权网络的一种方法是以概率kikj/（2m）（提供kikj）生成其每一条边和自边≤ 2米（我，j）。也就是说，边和自边的存在与否是一个概率为kikj/（2m）的伯努利随机变量[12,13]。

更一般地说，邻接矩阵集合上满足以下条件的任何概率分布PNj=1Wij= ki（即，预期强度等于观测强度，见上文[16]），对于某些实值函数f，e（Wij）=f（ki）f（kj）的预期邻接矩阵为e（W）=kkT/（2m）。网络的邻接矩阵是对称的正半限定矩阵。我们简要描述了一种从timeseries数据模型（与网络模型相比）中推导NG空网络的方法。给定c的a和b之间的偏相关corr（a，b | c）是a与c和b与c的线性回归产生的残差之间的皮尔逊相关，由corr（a，b | c）=corr（a，b）给出- corr（a，c）corr（b，c）p1- corr（a，c）p1- corr（b，c）。（2.9）假设用于构建观测网络的数据是一组时间序列{zi|i∈ {1，…，N}，其中zi={zi（t）|t∈ T}和T是一组离散的时间点。[46]的作者指出，Aij=corr（zi，zj）意味着ki=cov（^zi，^ztot），因此kikj2m=corr（^zi，^ztot）corr（^zj，^ztot），（2.10）其中^zi（t）=（zi t）-hzii）/σ（zi）是标准化时间序列，^ztot（t）=PNi=1^zi（t）是标准化时间序列的总和。取a=^zi，b=^zj，c=^ztot，方程（2.9）意味着如果corr（^zi，^zj |^ztot）=0，那么corr（^zi，^zj）=kikj/（2m）。也就是说，满足CORR（^zi，^zj |^ztot）=0的时间序列对之间的皮尔逊相关系数正是NG空网络的邻接矩阵项。

生成一组时间序列的一种方法是，假设每个标准化时间序列几乎依赖于平均时间序列，并且残差是相互不相关的（即^zi=αi^ztot/N+βi+对于某些αi，βi∈ R和corr(我j） =0表示I6=j）。（2.6）中的多尺度模块化最大化问题最初是在[64]中使用特殊方法引入的。有趣的是，我们可以通过考虑基于观测网络上连续时间马尔可夫过程X（t）的质量函数，推导出足够大的γ值的最大化问题的公式[41,42]。由λ（i）saties˙p=p∧M参数化的每个节点上具有指数分布等待时间的连续时间马尔可夫过程的概率密度- p∧，（2.11），其中向量p（t）∈ [0,1]1×Nis是每个节点上随机行走者的概率密度[即，pi（t）：=P（X（t）=i），对于每个i]，λ是一个对角矩阵，其速率λ（i）位于其对角项上，M是随机行走者的转移矩阵期望和假设的线性度ePNj=1Wij= kiand E（Wij）=f（ki）f（kj）意味着f（ki）=ki/PNj=1f（kj）和PNj=1f（kj）=√200万。把这些方程结合起来就得到了理想的结果。等式（2.10）适用于使用时间序列之间的皮尔逊相关性构建的网络[46]。这类网络是具有边权值的有符号网络的例子[-1, 1]. 节点i的强度由相关矩阵的第i列（有符号）或行和给出。（即Mij:=Aij/ki）。

方程（2.11）的解是p（t）=pe∧（M-一） 其平稳分布是唯一的（假设网络连接），由π=ckT∧给出-1/（2m），其中归一化常数c确保pni=1πi=1。分区的稳定性是由[18,41,42]r（S，t）=TrhST定义的质量函数πe∧（M）-一） t- πTπSi，其中∏ij=δ（i，j）πi。等价地，稳定性isr（C，t）=NXi，j=1πie∧（M）-一） tij- πiπjδ（ci，cj）。（2.12）取p=π，（2.12）左侧括号中的术语为p（X（0）=i∩X（t）=j），右侧括号中的术语是P（X（0）=i∩X（t）→ ∞) =j） （前提是系统是遍历的）。稳定性质量函数背后的直觉是，在达到平稳性之前的给定时间，一个好的分区对应于一个随机步行者在社区内花费的时间比在社区之间花费的时间要长。换句话说，一个从社区开始的随机游走者在随机游走的早期阶段，在平稳性之前很久，又在那里结束了。由此产生的最大化问题是maxS∈Sr（S，t），或等效的maxC∈Cr（C，t）。通过线性化e∧（M）-一） tat t=0，取∧=I，在γ=1/t和Pij=kikj/（2m）的短时间尺度下，得到（2.6）中的多尺度模性最大化问题。这种方法提供了分辨率参数γ的动力学解释，它是随机行走者探索网络所用时间的倒数（后线性化）。2.4.2. 将Newman-Girvan空网络推广到有符号网络（NGS）。在[28]中，G\'omez等人提出了将NG网络推广到有符号网络的方法。他们把A分为正面和负面两种：A=A+- A.-,其中A+表示A的正部分，且-A.-表示它的负部分。将NG空网络泛化为有符号网络（NGS）是Pij=k+ik+j/（2m+）-K-ik-j/（2m）-).