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

（例如，在第5.1节的两个玩具示例中都出现了这种情况。）为了缓解这个问题，我们在Louvain启发式中改变了合并节点的条件。我们不是将节点移动到最大程度增加模块性的社区，而是将节点移动到从增加模块性的社区中随机均匀选择的社区。我们称之为启发式LouvainRand[1]，我们在图中展示了使用它的结果。5.4（b，d）。虽然LouvainRand可以增加输出的可变性（通过增加优化过程的搜索空间），但它似乎可以缓解具有顺序对角和单向耦合的多层网络的问题。5.4. 资产关联网络中的多层社区结构。在本节中，我们展示了计算实验的结果，其中我们确定了分辨率参数γ的值，并改变了层间耦合ω的值。我们使用统一的零网络（即Pijs=hAis）并设置γ=1。我们使用LouvainRand启发式来识别多层分区，并将我们的后处理过程应用于所有输出多层分区，该过程在不改变各个层上诱导的分区的情况下提高持久性。我们在命题5.5中证明，对于2ω>2ω∞= |T|N麦克斯（英国国际航空公司）- min（Bdiag）, 全局最优解的集合Cmax（ω）不再变化，且该集合中的每个最优划分都具有最大持久性。在我们的例子中，|T |N麦克斯（英国国际航空公司）-min（Bdiag）≤ 2 | T | N，其中N=98和| T |=238。然而，为了本论文的目的，我们将连续值（总共给出501个值）之间离散步骤为0.1的集合{0，0.1，…，49.9，50}作为ω值的样本。与命题5.7和命题5.8中导出的性质一致，我们在图5.5（a）中观察到规范化持久性（由Pers（C）/[N（| T |）给出）- 1） ]）层间耦合的值越大，趋于越大，图。

5.5（b）层间耦合值越大，层内模性（我们通过p | T | s=1（1TAs1）标准化）往往越小。持久性的增加和层内模块性的降低不一定是单调的，因为我们正在为ω的每个值寻找一组局部最优值，而不是全局最优值。在图5.5（c）中，我们展示了多层分区（包含35个社区）的样本输出。（有关我们对资产类别缩写的定义，请参见第4.2节。）社区结构的一些变化对应于已知事件（例如，2008年9月雷曼破产[以股权资产类别的规模增加为标志]）。请注意，最大的两个社区是包含ZF债券资产和股权资产的社区。特别是，包含股票的社区在2006年至2007年期间变得明显更大，并在2008年底再次扩大[在图5.5（d）中2008年至2009年的粉红色条纹之后]。对于分辨率参数γ的更大值，这个群体直到2008年才变得明显更大。（通过检查相关矩阵，可以发现ω的值也可能更小。）∞这是事实；换句话说，我们没有证明ω∞是集合{w:Pers（Cωmax）=N（| T）的最小下界|-1） 对于所有的Cωmax∈Cmax（ω）}0 10 20 30 40 500.920.940.960.981标准化持久性ω（a）持久性与γ=10 10 20 30 40 500.080.0850.090.095的ω-层贡献ω（b）层内贡献与γ=1200120022003200420520062007200820092010gov的ω相对。公司Equ。Cur。遇见。福。通用域名格式。（c） （γ，ω）=（1，0.1）（d）所有层对之间的持久性的输出分区（e）所有层上所有节点对之间的平均共分类指数0.5 1Fig。5.5. 多资产分类的数值实验。

我们从区间[0,50]以0.1的离散化步骤（因此总共有501个ω值）对层间权重集进行均匀采样，并使用γ=1的均匀零网络（即Pijs=hAsi）。（a） 用N（|T|）归一化的持久性- 1） 对于每一个ω值，在20次LouvainRand上取平均值。（b） 层内模性P | T | s=1PNi，j=1Bijsδ（cis，cjs）由p |T | s=1PNi，j=1aijs归一化，达到20次LouvainRand的平均ω值。（c） 样本输出多层分区。水平轴上的每个点代表一个时间窗口，垂直轴上的每个位置都是一个资源。我们按资产类别对资产进行排序，颜色代表社区。（d）ω的所有值上平均的所有层对之间的归一化持久性值的关联矩阵∈ [0,50]在我们的样本中，每个值运行20次。一对层{s，r}isPNi=1δ（cis，cir）/N之间的归一化持久性。（e） 关联矩阵，表示每层上每个ω值和20个LouvainRand运行的平均分割集上节点的共分类。2008年股票和其他资产之间相关性的增加比2006年更大。）在图5.5（d）中，我们展示了所有层对之间持久性平均值的矩阵。（s，r）thentry是术语pni=1δ（cis，cir）/N，其中s，r∈ {1，…，|T |}不需要来自连续层，在ω的所有值上求平均值∈ [0,50]在我们的样本中，ω的每个值都有多次运行。连续层（仅为124c）而非图。

5.5给出了一些指示，说明节点是否在s层和s+1层之间改变社区，以加入一个社区，该社区包含来自另一时间层的这些节点中的一些节点的副本（即，对于某些r，PNi=1δ（cis+1，cir）6=0），还是加入一个不包含任何其他时间层中这些节点副本的社区（即，对于所有r，PNi=1δ（cis+1，cir）=0）。图5.5还提供了一些关于是否存在持续性值相对较大的连续层集的见解。这可能有助于了解多层网络中连接模式的变化。如色标上的值所示，持久性的值为inFig。5.5（d）仍然相对较高（这在一定程度上可以解释为，股票和债券在几乎所有层面上都位于同一个社区，它们约占节点样本的50%）。图5.5（d）中间最明显的对角线分隔对应于图5.5（c）在2005年和2006年之间的变化，此时各种货币、金属和燃料从债券共同体（蓝色）中分离出来，形成深绿色共同体。图5.5（d）右下角的较小对角线对应于2008年至2009年雷曼破产后图5.5（c）中的变化[图5.5（c）中的粉红色条纹之后]。在图5.5（e）中，我们展示了各层分区中节点的共分类指数，我们对各层的所有ω值进行平均∈ [0,50]和ω的每个值的多次运行（我们对节点重新排序，以强调关联矩阵中的对角块）。该图提供了关于ω值增加时，哪些节点跨层属于同一社区的见解。这可能有助于了解跨层共享的连接模式。

毫不奇怪，第一个对角线主要对应债券资产，第二个对角线主要对应股权资产。图5.5（d，e）相互补充：在给定的γ分辨率下，前者给出了社区结构何时发生变化的想法，而后者给出了社区结构如何发生变化的想法。6.结论。时间多层网络中的模块化最大化是一种产生节点时间演化分区的聚类技术。我们研究了使用这种方法时出现的两个问题：（1）零网络在模块化最大化中的作用，（2）层间边缘对多层模块化最大化问题的影响。我们证明了，在解释通过一个空网络获得的社区时必须谨慎，其中预期边权重的分布依赖于样本。此外，我们还表明，多层模块化最大化的最佳划分反映了层内静态社区结构和跨层社区结构持久性之间的权衡。人们可以尝试在实践中利用这一点，在依赖时间的网络中检测连接模式和共享连接的变化。我们的结果和观测支持层内任何单层网络的选择；我们详细讨论了CorrelationNetwork，并将其用作示例。模块化最大化的核心是预测和观察之间的比较。指定预期内容的能力是模块化最大化的一个可取（尽管未得到充分利用）特征，因为人们可以明确地将其适应不同的应用[5、6、21、66]。

通过将空模型定义为邻接矩阵空间上的概率分布，将空网络定义为指定分布下的预期邻接矩阵，我们强调了一个重要点，即相同的空网络可以对应不同的空模型；这在文学作品中并没有得到应有的重视。此外，一个人需要非常小心地选择空网络，因为它决定了什么是网络中紧密连接的：不同的选择通常会产生不同的社区。正如我们在第4节金融相关性网络中所述，这种选择可能会对结果产生很大影响，并可能导致误导性结论。在第5节中，我们证明了几个属性，这些属性描述了顺序对角和均匀层间耦合对多层模块化最大化的影响，或者更一般地说，对任何可以以形式（3.4）转换的最大化问题的影响。尽管我们的理论结果不一定适用于人们在实践中获得的局部最优解，但它们确实为如何解释最大化模块化的计算启发式结果提供了有用的指导：如果多层划分与已证明的属性之一不一致，那么它一定是启发式的产物，而不是质量函数的特征。为了进一步检验多层模块化最大化，我们定义了一个称为持久性的度量，以量化在多层分区中社区分配在时间上的变化程度。对于零层间耦合，持续性的值为0，对于足够大的层间耦合，持续性达到最大值。我们证明了在给定层间耦合ω的情况下，最优分割的持久性的最高可达值是ω中的一个非递减函数。

类似地，在给定层间耦合ω值的情况下，层内贡献对最优划分的质量函数的最高可达值是ω中的非递增函数。持久性的概念使我们有可能衡量层内的静态社区结构和层间的暂时持久性之间的这种权衡。我们在数值实验中说明了这种权衡。最后，我们证明了Louvain启发式在应用于具有顺序对角和均匀耦合的多层网络时可能会带来两个问题。这些可能会产生误导性的持久性值（或多层划分的其他量化指标），并可能导致人们对网络中的时间变化和社区结构得出错误的结论。我们提出了缓解这些问题的方法，并以实际数据为例展示了一些数值实验。为了进一步解释这些结果，我们需要更仔细地研究在“边界情况”ω和ω之间的多层划分中，持续性的增加和层内对质量函数贡献的减少实际上是如何表现的∞（请参见位置5.4和5.5）。这可能有助于确定ω值的区间，在该区间内，持久性和层内模块化之间的权衡产生了最多的见解。致谢。MB承认EPSRC颁发的案例学生奖（BK/10/41）。MB和MAP得到了欧盟委员会资助的FET前瞻性项目PLEXMATH（FP7-ICT-2011-8；grant#317614）的支持。MAP和MB也得到了詹姆斯·S·麦克唐纳基金会（220020177）的支持，MAP也得到了EPSRC（EP/J001759/1）的支持。我们感谢汇丰银行提供金融资产的时间序列数据。

我们感谢Alex Arenas、MihaiCucuringu、Sergio G\'omez、Lucas Jeub和三位匿名裁判的有益评论。参考文献[1]该代码可在http://netwiki.amath.unc.edu/GenLouvain/GenLouvain.[2] A.阿里纳斯、A.费尔南德斯和S.G\'omez。在不同分辨率水平上分析复杂网络的结构。新J.Phys。，10:5:053039, 2008.[3] T.艾纳德和J.-L.纪尧姆。进化网络的静态社区检测算法。WiOpt\'10：移动、自组织和无线网络中的建模和优化，84:508–5142010。[4] I.Barnett和J.-P.Onnela。相关网络中的变点检测。arXiv:1410.07612014。[5] D.S.巴塞特、E.T.欧文斯、M.A.波特、M.L.曼宁和K.E.丹尼尔斯。使用社区检测提取颗粒材料中的力链网络结构。SoftMatter，11（14）：2731-27442015。[6] D.S.巴塞特、M.A.波特、N.F.维姆斯、S.T.格拉夫顿、J.M.卡尔森和P.J.穆查。网络中动态社区结构的鲁棒检测。《混沌》，23:0131422013。[7] D.S.巴塞特、N.F.维姆斯、M.A.波特、P.J.穆查、J.M.卡尔森和S.T.格拉夫顿。学习过程中人脑网络的动态重构。过程。纳特尔。阿卡德。Sci。美国，108:7641–76462011。[8] S.巴蒂斯顿、J.B.格拉特菲尔德、D.加拉舍利、F.利洛和G.卡尔达雷利。金融网络的结构。斯普林格，伦敦，英国，2010年，第7章。[9] E.T.贝尔。指数数字。艾默尔。数学月刊，41:411-4191934。[10] V.D.布隆德尔、J.-L.纪尧姆、R.兰比奥特和E.莱斐伏尔。大型网络中社区的快速展开。J.统计学家。机械。，10:P100082008。[11] S.博卡莱蒂、G.比安科尼、R.克里亚多、C.I.德尔吉尼奥、J.G\'omez Gardenes、M.罗曼史、I.森蒂娜·纳达尔、Z.王和M.扎宁。多层网络的结构和动力学。菲斯。Rep.，544:1–1222014年。[12] B.Bollob\'as、S.Janson和O.Riordan。

非齐次随机图中的相变。随机结构。Alg。，31:3–122, 2007.[13] B.博洛巴斯和O.里奥丹。随机图和分支过程，在：大规模随机网络手册。Bolyai Soc。数学《螺柱》，2009年18:15–115。[14] U.Brandes、D.Delling、M.Gaertler、R.G–Worker、M.Hoefer、Z.Nikoloski和D.Wagner。无模聚类。IEEE Trans。知识数据工程。，20:172–188, 2008.[15] 卡坦扎罗先生和布坎南先生。网络机遇。《自然物理学》，2013年9:121–123。[16] 钟福林和吕立军。给定期望度数的随机图中的平均距离。过程。纳特尔。阿卡德。Sci。美国，99:15879–158822002。[17] R.Cont.资产回报的经验性质：程式化事实和统计问题。定量。《金融》，1（2）：223–236，2001年。[18] J-C.德尔文内、S.N.亚利拉基和M.巴拉霍纳。图社区跨时间尺度的稳定性。过程。纳特尔。阿卡德。Sci。美国，107（29）：12755-127602010。[19] 多梅尼科先生，A。兰基奇内蒂、A.阿里纳斯和M.罗斯瓦尔。识别多层网络上的模块化流动揭示了互联系统中高度重叠的组织。菲斯。牧师。十、 2015年5:011027。[20] J·爱德蒙和R·M·卡普。网络流量问题算法效率的理论改进。ACM杂志，19（2），1972年。[21]P.Expert、T.S.Evans、V.D.Blondel和R.Lambiotte。在空间网络中发现独立于空间的社区。过程。纳特尔。阿卡德。Sci。美国，108:7663–76682011。[22]D·J·芬、M·A·波特、M·麦当劳、S·威廉姆斯、N·F·约翰逊和N·S·琼斯。多渠道数据中的动态社区：2007-2008年信贷危机期间外汇市场的应用。混乱，19:033119，2009。[23]D.J.Fenn、M.A.Porter、P.J.Mucha、M.McDonald、S.Williams、N.F.Johnson和N.S.Jones。汇率的动态聚类。定量。《金融》，12（10）：1493-15201212。[24]D.J.Fenn，M.A.Porter，S。

威廉姆斯、M.麦克唐纳、N.F.约翰逊和N.S.琼斯。金融市场相关性的时间演化。菲斯。牧师。E、 84:0261092011。[25]S.Fortunato。图中的社区检测。菲斯。代表，486:75–174，2010年。[26]S.Fortunato和M.Barthel\'emy。社区检测中的分辨率限制。过程。纳特尔。阿卡德。Sci。美国，104:36-412006。[27]N.吉尔文和M.E.J.纽曼。社会和生物网络中的社区结构。过程。纳特尔。阿卡德。Sci。美国，99:7821–78262002。[28]S.GAomez、P.Jensen和A.Arenas。相关数据网络中的社区结构分析。菲斯。牧师。E、 80:0161142009。[29]S.Gonz\'alez Bail\'on、J.Borge Holthoefer、A.Rivero和Y.Moreno。通过在线网络进行招聘的动态。Sci。2011年第1期，第197页。[30]B.H.很好，Y.-A.德蒙乔伊和A.克劳塞特。模块化最大化在实际环境中的性能。菲斯。牧师。E、 81:4:0461062010。[31]A.A.格罗佩利和E.尼克特。巴伦的财务部。巴伦教育系列，第四版，纽约，2000年。[32]R.Guimer`a、M.Sales Pardo和L.a.N.Amaral。复杂代谢网络的功能制图。《自然》，443:895-9002005。[33]T.Ho Off mann、M.A.Porter和R.Lambiotte。网络上非泊松动力学的广义主方程。菲斯。牧师。E、 86（4）：0461022012年。[34]P.福尔摩斯。现代时间网络理论：学术讨论会。arXiv:1508.01303，2015年。[35]P.霍尔姆和J.萨拉姆-阿基。时间网络。菲斯。众议员，519:97-1252012。[36]J.霍普克罗夫特、O.汗、B.库利和B.塞尔曼。跟踪大型LinkedNet中不断发展的社区。过程。纳特尔。阿卡德。Sci。美国，101:5250–5253，2004年。[37]L.G.S.朱布、P.巴拉昌德兰、M.A.波特、P.J.穆查和M.W.马奥尼。本地思考，本地行动：在大型网络中检测小型、中型和大型社区。菲斯。牧师。E、 91:0128212015。[38]I.S.朱特拉、L.G.S.朱布和P.J.穆查。