基于社区划分与连边逆序放回的网络分解算法

王志晓，张磊，孙成成，芮晓彬，黄珍珍，3，张孙贤

1 引言

影响力最大化［1，2］和网络分解［3］是社交网络分析领域两个重要的研究分支，前者通过选择种子节点进行信息传播，使得最终的影响范围最大. 后者则通过删除网络中最小规模的节点或连边，将网络破坏成一系列小规模、不连通的分支. 网络分解可以应用于舆情控制［4］，蛋白质结构解析以及交通线路防护［5，6］等领域.

网络分解算法主要有两类：基于节点删除的网络分解算法［3，4，7，8］和基于连边删除的网络分解算法［9，11］. 前者利用中心性指标迭代删除网络中的重要节点，直到网络中最大连通分支［7］（Giant Connected Components，GCC）的规模小于事先设定的阈值. 大多数研究将该阈值设定为整个网络规模的0.01［7，8］. 现有基于节点删除的网络分解方法大多不考虑删除代价.Ren 等人［4］指出网络分解过程中每个节点的删除代价是不同的，节点度值越大，连边越多，其删除代价越大. 基于连边删除的网络分解方法是一类考虑删除代价的方法，该类方法迭代删除影响网络连通性的关键连边，直到网络中最大连通分支的规模小于事先设定的阈值. 大多数此类研究也将阈值设定为0.01［9，11］. 基于连边删除的网络分解可以进一步细分为基于边中心性指标的方法［9］和基于最大连通分量划分的方法［11］. 基于连边删除的网络分解方法存在以下不足：（1）基于边中心性指标的方法需要在整个网络范围内计算每条连边的中心性值，复杂性较高，不适合大规模网络；（2）基于最大连通分量划分的方法需要迭代划分网络中的最大连通分支，连边删除缺乏针对性，容易删除一些不必要的连边.

社区划分技术已经成功应用于社区结构识别［12，13］以及蛋白质复合物识别［14，15］等诸多领域. 在网络社区结构中，社区内节点间的连边稠密，不同社区间的连边稀疏. 如果先利用社区划分技术对网络进行社区划分，就可以区分出社区内的连边和社区间的连边，针对两类连边的特点分别进行处理，从而达到快速分解网路的目的. 鉴于此，本文将社区划分技术与连边逆序放回策略相结合，提出了一种基于连边删除的网络分解算法CD-IRE（Network Dismantling Based on Community Detection and Inverse Reinsertion of Edges）. 首先，利用社区划分算法挖掘网络的社区结构. 社区划分不但能将整个网络划分为多个小规模的社区，而且能有效识别影响社区间连通性的连边，删除这些连边即可将网络分解为多个独立的社区. 然后，采用逆序放回策略进行社区内的分解：先移除社区内的所有连边，接着依次放回使社区内部GCC 规模增长最小的连边，直到放回任何一条连边都会使社区内GCC 规模超过设定阈值.最后，删除那些未被放回的连边，即可完成社区分解，进而实现整个网络的分解. 逆序放回策略能准确识别并删除对社区内GCC 增长贡献最大的连边，从而有效破坏社区内部的连通性.

真实网络上的实验结果表明，相比较于其他典型网络分解算法，本文方法删除较小规模的连边就能将网络分解至设定阈值；人工网络上的实验结果表明，随着网络规模的变化、网络结构的变化以及GCC 阈值的变化，本文方法均表现出较强的稳定性.

2 算法描述

首先，挖掘网络的社区结构，删除社区之间的所有连边，使网络分解成一个个互不相连的局部区域. 然后，采用逆序放回策略分解每个社区，最终实现对整个网络的分解.

2.1 社区划分

Louvain［16］是一种基于模块度的社区划分方法，具有准确性高、复杂度低等优点. 本文借鉴Louvain 算法思想完成社区结构挖掘. 首先，将网络中的每个节点都分配到不同的社区中，对每一个节点i，计算将它加入到其邻居节点所在社区所带来的模块度变化，加入模块度增益最大的社区. 若加入所有邻居节点所在社区的模块度增益均为0，则节点i保持在原来的社区内.重复上述操作，直到网络社区结构不再变化为止. 划分社区后，连接不同社区的连边清晰地显露出来，删除这些连边即可以最小的代价快速地将整个网络分解为一个个小规模的局部区域，从而极大地破坏整个网络的连通性.

如图1所示，划分出的社区C1和C2内部的连边非常密集，两个社区则通过边E连接在一起. 仅仅删除边E就可以彻底破坏社区C1和C2间的连通性，边E即是具有非常强连通性的连边［9］，起连接两个连边密集社区的作用.

图1 社区间的连边示意图

2.2 社区内部连边逆序放回

破坏社区间的连通性后，需要进一步破坏每个社区内部的连通性才能完成整个网络的分解. 本文采用一种逆向策略来解决这一问题，即连边逆序放回IRE（Inverse Reinsertion of Edges），该策略依次放回对社区内连通性影响最小的连边直到GCC超过事先设定的阈值.

连边逆序放回策略的步骤如下：

步骤1：将社区i内部的连边全部删除放入集合E0（i）中，社区中仅剩下一个个互不相连的孤立节点；

步骤2：从集合E0（i）中选择一条使社区内GCC 规模增长最小的连边放回社区；

步骤3：若存在多条连边放回后都能使GCC规模增长最小，则从这些连边中选择两端所连节点度值之和最小的连边放回社区；

步骤4：若满足步骤3的连边仍然有多条，则从这些连边中选择两端所连节点度值之差绝对值最小的连边放回社区；

步骤5：重复步骤1~4，直到从E0（i）中选择任何一条连边放回原社区都会使社区内GCC 的规模大于设定阈值.

步骤6：删除E0（i）集合中的剩余连边，完成社区内的分解.

上述逆序放回策略尽可能地将位于社区边缘、连接节点度值较小，且对社区内部连通性影响小的连边保留下来，从而最大限度地删除处于中心位置、连接节点度值较大、对社区内部连通性影响较大的连边.

下面举例说明逆序放回策略的执行过程. 图2状态1是一个节点规模为400的网络划分完社区之后得到的一个社区，该社区包含6个节点和10条连边，每条连边旁边的数字表示该连边的编号.GCC的阈值设定为0.01. 采用逆序放回策略的第一步是将全部连边放入E0，此时，放回任何一条连边GCC规模的增长都相同，因此，按照步骤3选择两端所连节点的度值之和最小的连边，即编号为1的连边，将其首先放回. 以此类推，后面依次放回编号为4，7，3，8，9，10的连边. 此后，如果继续放回，则GCC的规模将大于设定的阈值0.01，放回过程结束. 此时，E0中剩余的连边为｛2，5，6｝，予以删除，从而完成对该社区的分解，见图2状态2. 算法描述如算法1所示.

图2 连边逆序放回过程示意图

2.3 算法时间复杂度分析

本文所提出的网络分解算法包含两个阶段：社区划分和连边逆序放回. 社区划分阶段采用Louvain 算法将整个网络划分为k个社区，删除社区间的所有连边，时间复杂度是O(N+N′)，N是网络的节点规模，N′是迭代节点的个数. 逆序放回阶段，完成单个社区i分解的时间复杂度是O(miNi)，mi表示社区i内的连边数量，Ni代表社区i内的节点数量. 在最坏情况下，k个社区都需要进行分解，那么，完成k个社区连边逆序放回的时间复杂度就是这样一来，整个算法的时间复杂度为

3 实验与结果分析

3.1 数据集和评价指标

实验所用数据包括真实网络和人工网络. 真实网络如表1所示，n代表网络节点规模，从几百到几万不等.m代表网络连边总数，c代表网络节点的平均连边数（平均度值）. 人工网络有两类，一类是ER（Erdös-Rényi）人工网络，节点规模分别是2000、4000、6000 和10000，对于给定规模的ER网络，平均连边数（平均度值）c的变化区间为［3，10］. 另一类是BA（Barabási-Albert）人工网络，节点规模最小是1000，最大是10000，对于给定规模的BA网络，平均连边数（平均度值）c的取值为4、6和8. 真实网络来源于http：//konect.uni-koblenz.de/，评价指标包括最大连通分支规模GCC和网络分解代价Cost.

表1 真实网络数据集

GCC评价指标定义如式（1）.

其中，NGCC是最大连通分支GCC 中的节点数量，n是网络节点总数.

代价Cost 表示完成网络分解需要删除的连边数量占整个网络连边总数的比例：

其中，dl 是分解过程中被删除的连边数量，m是网络的连边总数.

3.2 真实网络实验结果分析

3.2.1 与基于节点删除的网络分解方法性能对比

实验中选取5种基于节点删除的网络分解算法，包括GND（Generalized Network Dismantling）算法［4］、GN‑DR（Generalized Network Dismantling with Reinsertion）算法［4］、EGP（Equal Graph Partitioning）算法［17］、Min-Sum 算法［3］和BPD（Belief Propagation-guided Decimation）算法［7］.Min-Sum和BPD是典型的基于去环的方法，相关参数均按照原文的最优值进行设置：Min-Sum 算法第一个阈值C1=0.5%，第二个阈值C2=1%.BPD权重参数x=12.

首先，分析最大连通分支规模GCC 随删除代价Cost 增大的变化情况. 图3 显示了所选算法在Crime 和Power-Grid 网络上的实验结果，横坐标代表网络分解代价Cost，纵坐标代表最大连通分支规模GCC. 从图3可以看出，随着网络分解代价Cost 的增大（删除连边的数量增多），最大连通分支规模GCC 呈现下降趋势. 相对于其他5种算法，CD-IRE算法删除较小规模的连边就能最大限度地破坏网络的连通性，性能最优. 以Crime 网络为例，CD-IRE 算法仅花费不到0.1%的代价就可以将网络分解至GCC 小于0.1，GND 算法实现这个目标需要0.2%的代价，其余4种算法的代价均超过0.5.

CD-IRE算法在Power-Grid网络上的这一优势表现得更为突出.

然后，进一步分析达到网络分解阈值（即0.01）时不同网络分解算法需要的删除代价Cost. 表2显示了上述6 种算法分解Crime、Corruption、Petster-hamster、Power-Grid、Political Blogs 和Autonomous Systems 网络所需要的代价Cost. 可以看出，本文的CD-IRE 算法只需要删除较小规模的连边就可以完成对6个网络的分解，表现出最好的性能. GNDR 算法也表现出了不错的性能，BPD 算法紧随其后. 另外，从表2 可以看出，无论何种算法，分解Corruption 网络和Political Blogs 网络的代价Cost都超过0.92，原因是这两个网络节点的平均连边数（平均度值）非常大，分别达到了21.24 和27.36（见表1），从而导致网络分解的难度较大.

表2 CD‑IRE算法与基于节点删除的网络分解方法Cost对比

3.2.2 与基于连边删除的网络分解方法性能比较

实验中选取4种基于连边删除的网络分解算法，分别是Ncut算法［11］、Bond percolation 算法［18］、Betweenness算法［10］和Bridgeness算法［9］.

首先，分析最大连通分支规模GCC 随删除代价Cost 增大的变化情况. 图4 显示了所选算法在Autono‑mous-Systems 和Petster-hamster 网络上的实验结果. 随着Cost 的增加，CD-IRE 算法的GCC 值快速下降，这一现象与图3 中的结果类似，说明删除社区间的连边可以极大地破坏整个网络的连通性.Ncut 算法采用了谱平分思想，每次迭代将网络近似分为大小相等的两部分，因此Ncut 算法也能使GCC 值快速下降.CD-IRE 算法删除当前社区的全部外部连边后才会更新GCC 的值，因此会导致GCC 值的更新略微滞后. 总体而言，CD-IRE 算法和Ncut 算法性能接近，明显优于Bond per‑colation 算法、Betweenness 算法和Bridgeness 算法.

图3 CD-IRE算法与基于节点删除的网络分解方法性能对比

图4 CD-IRE算法与基于连边删除的网络分解方法性能对比

然后，进一步分析达到网络分解阈值0.01 时不同网络分解算法需要的删除代价Cost. 表3 显示了上述5种算 法分 解Crime、Corruption、Petster-hamster、Power-Grid、Political Blogs 和Autonomous Systems 网络所需要的代价Cost. CD-IRE 算法在Crime、Corruption、Political Blogs 和Autonomous Systems 等4 个网络上表现出最好的性能，在Petster-hamster 和Power-Grid 网络上的性能仅次于Ncut 算法，这一结果与图4 中对CD-IRE 算法和Ncut算法性能的分析一致.

3.2.3 GCC阈值对网络分解算法性能的影响

此处选取上述实验中性能突出的CD-IRE 算法、GNDR 算法、Min-Sum 算法、BPD 算法和Ncut 算法，分析GCC 阈值对网络分解算法性能的影响. 选取的真实网络包括PPI、Power-Grid 和Authors. GCC 的阈值分别设定为0.2、0.4、0.6和0.8.

表4~表6分别展示了所选算法在PPI、Power-Grid和Authors 网络上的Cost 值. 可以看出，随着GCC 阈值变小，网络分解标准逐渐提高，绝大多数算法的Cost 呈现增大趋势. 在PPI网络中，CD-IRE算法和Ncut算法性能相当，优于其他算法. 在Power-Grid 网络中，CD-IRE 算法最优，GNDR 算法紧随其后. Ncut 算法以0.0302 的Cost代价直接将Power-Grid网络的GCC降至0.2以下，因此0.2以上的阈值变化对该算法没有影响（见表5）. 总体而言，随着GCC阈值的变化，CD-IRE算法始终能够保持良好的性能，以较小的代价完成网络分解.

表3 CD‑IRE算法与基于连边删除的网络分解方法Cost对比

3.3 人工网络实验结果分析

3.3.1 ER网络

此处选取上述实验中性能突出的CD-IRE 算法、GND 算法、GNDR 算法和Ncut 算法，分析网络规模和结构特性对其性能的影响.ER 网络的节点规模分别取2000、4000、6000 和10000，平均连边数（平均度值）c从3 变化到10，步长为1.

GCC 阈值为0.01. 考虑到所生成人工网络的随机性，实验取48 次结果的平均值.

图5 显示了ER 网络上的相应结果. 在不同的网络规模下，随着平均连边数（平均度值）c的增大，网络分解的代价Cost逐渐增加. 很显然，节点邻居数量变多增大了网络分解的难度. 但是，无论节点规模和平均连边数（平均度值）c如何变化，CD-IRE 算法和Ncut 算法均表现出良好的性能，优于其他算法. 另外，从这两种算法曲线的位置变化可以看出，它们对网络规模不敏感.

图5 ER人工网络上的实验结果

表4 GCC阈值对网络分解算法性能的影响（PPI网络）

表5 GCC阈值对网络分解算法性能的影响（Power-Grid网络）

表6 GCC阈值对网络分解算法性能的影响（Authors网络）

3.3.2 BA网络

BA 网络的节点规模在1000 至10000 间递增，每次增加1000个节点. 平均连边数（平均度值）c分别取4、6和8. 考虑到Ncut算法和CD-IRE算法性能最接近，此处仅分析这两种算法在BA网络上的性能.

同样地，图6 显示了48 组实验的平均值. CD-IREc4中的“c4”表示平均连边数（平均度值）为4，其余曲线标识的含义类似. 可以看出，两种算法在BA 网络上的性能非常稳定. 当平均连边数（平均度值）c为6和8时，CD-IRE 算法的性能优于Ncut 算法. 当平均连边数（平均度值）c为4时，两个算法的性能相当.

图6 BA人工网络上的实验结果

4 结论

网络分解是社交网络分析中的重要问题，其研究成果在很多领域都有着广泛应用，包括控制计算机病毒在通信网络中的传播范围、干预谣言在社交网络中的扩散程度等［19，20］. 本文提出了基于社区发现与连边逆序放回的网络分解算法，该算法借助社区划分将网络分解为若干个局部社区，删除社区间的连边，破坏社区间的连通性. 然后，采用逆序放回策略，以最小的代价进一步破坏社区内部的连通性，最终完成对整个网络的分解. 实验结果表明，本文算法以删除较小规模的连边为代价，就能将网络分解至事先设定阈值. 并且，随着网络规模的变化、网络结构的变化以及设定阈值的变化表现出较强的稳定性.