复杂网络关键节点组识别问题模型和算法研究*

2019-08-12江成，张军，卢山

计算机与生活 2019年8期

江成，张军，卢山

首都经济贸易大学信息学院，北京 100070

1 引言

随着科技进步和全球一体化进程加速，人们日益处于各种复杂网络中。例如，互联网网络、电力和交通网络、经济和金融网络以及社会网络等。这些网络中存在一些对结构和功能影响程度更大的特殊节点，通常被称为关键节点。这些关键节点在网络中虽然数量不多，却可以快速波及并影响网络中的大部分节点[1]。例如，TOMsInsight团队针对2014年“冰桶挑战”形成的社会网络数据分析发现：53%名人将相关视频、图片和文字发布到社交网络，被传播展示占比高达99%，而47%非名人被传播展示占比不到1%[2]。由此可见，社会网络传播中的关键节点——名人效应是非常显著的。

关键节点组识别问题是指[3]：在资源有限的情况下，从给定的网络图G=(V,E)中选择K个节点（V、E分别代表节点集和边集，K为正整数），使得移除这K个节点后，剩余网络的某种衡量指标（如离散程度或传播效应等）最优化。关键节点组识别问题作为复杂网络微观层面的重要研究内容，直接关系到信息的传播速度和影响范围，吸引了管理学、信息科和物理科学等多个领域学者的共同关注，并得到了广泛的应用。例如，流行病传播网络中，在医疗资源有限的情况下，对哪些关键个体优先接种免疫以最有效阻断病毒大规模传播的问题[4]；通信网络中，对哪些影响力重要性用户重点识别以提升网络消息传播效率的问题[5]；恐怖主义网络中，选择哪些关键恐怖分子使得其被定点清除后网络的破坏程度最大，即最小化恐怖主义袭击活动可能性的问题[6]；交通网络中，选择哪些关键基础设施重点保护，使得不致于因为意外原因而导致网络大面积瘫痪的问题[7]。此外，关键节点组识别问题在电力系统关键部件保护[8]，生物网络关键蛋白和基因的识别[9]，社会网络意见领袖挖掘[10]等领域也有着重要应用。总结国内外已有研究可见，目前关键节点组识别问题研究主要是基于仿真模拟、指标度量和数学建模三种方式开展的。

在仿真模拟方面，已有研究大多借鉴流行病学中的疾病传播模型来模拟网络中节点的影响力传播。因而，在这种类型方法下，复杂网络关键节点组识别问题经常被等同于节点影响力最大化问题[11]。如Saito等基于SIS（susceptible infected susceptible）疾病传播模型构建了一个多层的图结构，用于识别社会网络中最具影响力的节点[12]。Salamanos等通过图采样方法来识别复杂网络中最具影响力的节点，并基于SIS和SIR（susceptible infected recovered）疾病传播模型进行实验模拟[13]；王祯骏等提出了一种融合内容信息和动态时间特性的影响力传播模型，并借助该模型识别社会网络中最有影响力的用户[14]；张云飞等针对多个影响力同时传播且影响力间存在促进传播关系的情况下，对关联影响力传播最大化问题进行建模，并提出基于节点激活贡献估计的求解算法[15]。

在指标度量方面，基于图论的指标经常用来评价节点的重要性，例如，节点的中心度[16]、节点的介数[17]、节点的紧度[18]、节点的特征值[19]、K壳分解[20]等。然而这些指标只能反映网络的单一属性，忽略了整体结构和功能。为此，Borgatti从网络的整体结构出发，提出了衡量网络离散程度的专用度量指标DF，但直接优化DF因计算复杂度高而缺乏实际操作的可行性，因此其采用贪婪搜索方法对DF求解[3]。总体来看，指标度量方法反映了网络拓扑的局部特性或全局特性，设计容易，简单直观。但是，按照指标对单个节点重要性排序结果选择的前K个节点组合，往往并不是复杂网络整个最优的K个关键节点集合[21]。

近年来，基于数学建模的方法逐渐得到国内外相关学者的关注。例如，Arulselvan等率先提出了整数线性规划模型，通过最小化剩余网络中连通分支的个数识别稀疏网络中的关键节点集合，奠定了关键节点组识别问题的主流模型地位[22]。由于在求解精度上较基于仿真模拟和指标度量的方法更占优势，该模型得到了学者们的关注，并且衍生出一些变体模型，例如最大化剩余网络连通分支的个数[23-24]和最小化最大连通分支中的节点个数[25]等。此外，现有研究已经证明关键节点组识别问题是NP难问题[22]，因此基于贪婪搜索[26]、遗传算法[27]、模拟退火[28]的一些启发式算法也被提出来用于求解这些识别模型。更多关于关键节点组识别的研究方法请参考文献[29-31]。

根据以上分析可见，现有的关键节点组识别方法较多，但各有侧重。其中，基于仿真模拟的方法侧重于从功能性传播角度研究节点影响力，而对网络整体结构的稳定性考虑不足；基于指标度量的方法，因其简单直观，计算复杂度较低，成为目前主要的识别方法，但其更适合于节点重要性排序问题[32-34]，对多个关键节点集合的识别问题评价不够全面。而在数学建模方面，尽管已有研究在关键节点组识别问题上已经取得了显著的成果，但是当前模型方法单一，并且现有的整数线性规划模型本身存在不能够区分连通分支内部结构的缺陷。

为此，本文从网络的整体结构和功能出发，对复杂网络关键节点组识别问题模型和算法进行研究，本文的主要贡献如下：

（1）构建基于0-1二次约束二次规划的关键节点组识别模型，通过最小化二阶路径内连通节点对的个数，实现区分连通分支内部结构的能力。

（2）提出两种模型求解方法：一种是松弛为半正定规划模型并利用内点算法求解，这种方法适用于小规模网络的近似求解；另一种是设计贪婪搜索和局部置换相结合的启发式算法，用于大规模网络中的关键节点组识别。

（3）进行了大量人工随机图和真实复杂网络数据集的实验分析，验证了所建立模型和算法的正确性和有效性。

2 相关工作

Krackhardt构建了用于计算每个连通分支内部连通节点对个数的度量指标[35]，如下所示：

式中，sk表示移除关键节点后剩余网络中第k个连通分支中的节点个数。该指标计算简单，计算复杂度较低，可以通过枚举方法求解，但其忽视了连通分支的内部结构。在此基础上，从网络的整体结构出发，文献[3]提出了衡量网络离散程度的专用指标DF，定义如下：

式中，dij表示节点对i和j之间的最短路径，DF∈[0,1]，且DF值越大，网络的离散程度越大。DF指标虽然设计比较完善，但因其计算复杂度高，导致对其直接优化缺乏实际操作的可行性。

在Krackhardt指标基础上，Arulselvan等建立了最小化剩余网络连通节点对个数的整数线性规划模型（integer linear programming，ILP）[22]，以便更好地洞察和深入理解关键节点组识别问题。然而，该模型和其衍生出的变体模型均存在不能够区分连通分支的内部结构的缺陷，这一问题直接导致了实际优化效果并不理想。

3 模型规划

为解决当前主流的整数线性规划模型对连通分支内部结构的考虑不足，本文将基于DF指标建立数学模型，并提出新的计算解决方法。

3.1 模型的建立

基于0-1二次约束二次规划（quadratically constrained quadratic programming，QCQP）建立模型，具体规划如下：

其中，A是网络的邻接矩阵，如果节点i和j是邻居节点，则aij=1，否则aij=0；vi=1表示节点i作为关键节点被移除，否则，vi=0；xij=1表示在移除关键节点后剩余网络中节点i和j是邻居节点，否则xij=0。此模型的目标函数是最小化剩余网络中二阶路径内连通节点对的个数；约束（3）重新计算了移除关键节点后剩余网络的邻接矩阵，即如果节点对i和j在原网络中是邻居节点，但节点i或j被作为关键节点移除的话，则节点i和j之间的边消失，并且这两个节点在剩余网络邻接矩阵中对应的值为0；约束（4）表示在资源有限的条件下，被移除的关键节点个数不能超过K个。约束（5）约束模型为0-1非线性规划模型。

3.2 模型与DF指标的关系

（1）当网络结构为完全图时，误差为0；

（2）当网络结构为星型网络时，目标引入的误差也为0；

4 算法求解

由于QCQP是非凸的二次规划模型，为了高效求解，本文采取两种求解途径：一种是将其松弛为半正定规划模型进行求解；另一种方法通过设计启发式算法加以求解。

4.1 半正定松弛求解方法

这里对QCQP模型写成矩阵表示形式，并松弛为半正定规划模型（semi-definite programming relaxation，SDPR）的形式如下：

这里，W为将QCQP模型写成矩阵形式的系数矩阵。y=(x11,x12,…,x1n,x21,x22,…,x2n,…,xn1,xn2,…,xnn)。利用商用软件Matlab调用Gurobi接口中的内点算法，可以快速求解SDPR模型。需要注意的是，这种快速求解的松弛方法只提供了QCQP模型问题最优解的一个下界。当然，可以在此下界的基础上，进一步设计分支定界算法求取最优解。

4.2 启发式算法求解

采用贪婪搜索和局部置换相结合的思想，设计了一种新的启发式算法。

算法1QCQP模型启发式算法

输入：网络图G和关键节点组个数K。

输出：关键节点组集合和目标函数值。

（1）初始化一个空集S。若集合的元素个数小于K值，则最大化QCQP模型目标函数值，贪婪地向集合中逐个增加节点，直到该集合元素个数等于K。

（2）每次从S集合、V-S集合中各选取一个节点尝试互换，进行2节点交换的局部搜索。如果交换能够减少目标函数值，则进行互换，否则不互换。直至遍历所有2节点交换组合。

（3）返回目标函数值最小下的节点组合S，以及相应的目标函数值。

4.3 复杂度分析

松弛求解方法的时间复杂度为O((n3.5)4)，计算成本较高，只适合小规模网络的关键节点组识别。而启发式算法的计算复杂度为O(n3)，适用于识别较大规模网络的关键节点组识别。如果需要进一步降低算法复杂度，可以结合群体智能算法加以优化。

5 实验分析

本章选取了多组不同规模的随机图和真实网络数据集进行实验，其中人工数据集可以通过图模型随机生成，而真实数据集可以从佛罗里达大学开源数据库中下载获取[36]。由于关键节点组识别问题限定在资源有限的条件下，因此本文讨论的实验结果限制在K≤|V|/2条件下。本文采用的松弛求解方法的编程语言为Matlab，调用Gurobi和CVX接口；启发式算法求解的编程语言为Java。所有编程语言的实验运行环境是1.70 GHz英特尔骁龙处理器，16 GB内存，Windows操作系统。

5.1 人工网络实验

为了验证模型的鲁棒性，本文选取了多种连接结构的网络图进行实验，包括Erdos-Renyi图[37]、Geometric图[38]、Sticky 图[39]、Range因果图[40]和 Kleinberg图[41]，并且每种类型网络都随机选取了不同的规模。虽然可以比较K≤|V|/2的结果，直至DF=1为止。但由于空间所限，此处仅针对Erdos-Renyi(|V|=14,|E|=36)列出全部结果，如表1所示。其余实验数据集仅列出K≤5的结果，如表2～表5所示。其中，K为所识别关键节点的个数，Obj为移除关键节点后的模型目标函数值，T为运算执行时间，度量时间为毫秒（ms），DF指标用来评价识别结果的好坏，上标“*”表示性能比较中占优的一方。以Erdos-Renyi图为例，从表1中可以看出，尽管本文利用松弛方法只求得QCQP问题的近似解，但在大部分情况下，求解的效果都好于传统的整数线性规划模型。例如，表1中第3行表示了一个具有14个节点和36条边的E-R随机网络，当关键节点个数为1时，ILP模型及其启发式算法得到的目标函数值均为79，相应的DF值是0.419 4和0.413 9；而本文提出的SDPR模型及QCQP启发式算法得到的目标函数值均为386，相应的DF值均为0.435 9。这说明SDPR模型和QCQP启发式所识别的关键节点，被移除后造成的网络离散程度更大，在识别效果上更为有效。当然，也存在ILP模型和启发式胜出的少数情形，这是由于本文所提出的近似求解方法只求得SDPR模型的近似解，在某些情况下会略逊于ILP模型求得的最优解。但从表1～表5的整体实验效果来看，SDPR模型和QCQP启发式算法在大部分实验情况下均取得了较好实验效果。

Table 1 Results on Erdos-Renyi(|V|=14,|E|=36)networks表1 Erdos-Renyi(|V|=14,|E|=36)网络实验结果

Table 2 Results on geometric(|V|=10,|E|=15)networks表2 Geometric(|V|=10,|E|=15)网络实验结果

Table 3 Results on Sticky(|V|=12,|E|=9)networks表3 Sticky(|V|=12,|E|=9)网络实验结果

Table 4 Results on Range dependent(|V|=14,|E|=15)networks表4 Range因果 (|V|=14,|E|=15)网络实验结果

Table 5 Results on Kleinberg(|V|=16,|E|=47)networks表5 Kleinberg(|V|=16,|E|=47)网络实验结果

Fig.1 Statistical results on Erdos-Renyi networks图1 Erdos-Renyi随机网络实验统计结果

Fig.2 Statistical results on Range dependent networks图2 Range因果网络实验统计结果

Fig.3 Statistical results on small world networks图3 小世界网络实验统计结果

此外，针对Erdos-Renyi随机图、Range因果图和小世界网络图，本文又分别随机生成不同规模下（节点8、节点10和节点12）的网络数据集进行实验，统计分析本文所提出方法与传统ILP方法比较情况下，胜出、平局和败出各自所占的比例。图1～图3分别展示了在100组Erdos-Renyi随机图、Range因果图和小世界网络图在节点规模为8、10和12规模下实验的统计情况分布图。从图中可以看出，本文提出的方法在大多数情况下占优。

5.2 真实网络实验

为了验证本文所提出算法的有效性，本文进一步选取了Can73通信网络、Football115合作网络、Jazz198音乐家社交网络和Celegans453网络标准数据集进行实验。由于空间所限，此处仅列出K≤10的结果，从表6～表9可见，本文所提出的QCQP启发式算法在大多数情况下识别的DF效果好于ILP启发式算法的DF值，并且在计算时间上占优，QCQP启发式算法的运行效率大约是ILP启发式算法的102～103倍。

从表6～表9中可见，本文所提出的QCQP启发式算法在大部分情况下效果占优。但由于QCQP启发式求解的是QCQP模型的近似解，因此在个别点也存在不如ILP模型启发式的情况，后续可以进一步设计精确求解算法。为了能够进一步从“实际角度”解释关键节点，本文又基于“9⋅11”恐怖袭击网络进行实验。将本文方法识别出关键恐怖分子群组，与“9⋅11”恐怖袭击事件调查报告[42]所公布的恐怖分子地位进行比较验证。实验结果表明：本文方法所识别出关键恐怖分子头目群组，与“9⋅11”恐怖袭击事件调查中利用社交网络度、介性和紧度分析得到的恐怖分子头目吻合度较好，具体实验的结果如表10所示。

Table 6 Results on Can(|V|=73,|E|=47)networks表6 Can(|V|=73,|E|=47)通信网络实验结果

Table 7 Results on Football(|V|=115,|E|=47)social networks表7 Football(|V|=115,|E|=47)社交网络实验结果

Table 8 Results on Jazz(|V|=198,|E|=47)social networks表8 Jazz(|V|=198,|E|=47)社交网络实验结果

Table 9 Results on Celegans(|V|=453,|E|=2 025)networks表9 Celegans(|V|=453,|E|=2 025)网络实验结果

为了展示移除关键节点后网络的变化情况，图4～图6以Can73通信网络为例，分别可视化展示了ILP启发式方法和QCQP启发式算法在K=1、K=5和K=10的识别结果。

6 总结与展望

本文从网络整体结构出发，提出了一种非凸的0-1二次约束二次规划模型，模型的目标是最小化移除关键节点后剩余网络中二阶路径内的连通节点对的个数，通过这样的建模方法，实现了区分连通分支内部结构的能力。在此基础上，本文又设计了两种模型求解方法：一种是通过半正定松弛的方法识别小规模网络中的关键节点组；另一种是设计了结合贪婪搜索和局部置换的启发式算法，以适应大规模网络的关键节点组识别。通过在多组不同规模的随机网络和真实网络实验，验证了模型和算法的正确性和有效性。在未来的研究中，本文将扩展模型到大规模网络、有向有权网络以及动态网络中进行识别应用。