基于三度理论的节点影响力评价方法

赵 佳，刘 玥，李 雪，王梦迪，莫升康

(阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037）

基于三度理论的节点影响力评价方法

赵 佳，刘 玥，李 雪，王梦迪，莫升康

(阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037）

“9·11”事件以来，恐怖事件已经严重威胁到人类的生命财产安全。本文提出基于三度理论的评价方法来对恐怖组织网络中的各个节点的影响力进行排序；并在“9·11”数据集验证了该方法。实验表明对于较重要的节点，本方法和主流评价方法有相同的效果，然而对于较难分辨影响力顺序的节点，本方法仍能明确节点影响力顺序，主流评价方法却无法排序；本文同时并给出恐怖组织网络演变的过程，分析演变结果，有利于对恐怖组织网络的有力打击和摧毁。

恐怖组织网络；关键节点；影响力；网络演变

恐怖主义是当今世界各国面临的一个世界性的难题，严重地威胁着世界的和平与安全。恐怖主义自从二十世纪六十年代，特别是冷战以来，对全球政治、经济、文化产生了深远的影响。“9·11”恐怖袭击给美国带来了前所未有的损失，最大程度化地威胁美国的权威及其霸主地位，让世界都为之震惊。

在国内，在一般社会网络数据挖掘方面，周春光[1]等人提出了一种新的基于事件动态的社会网络分析算法；刘威[2]等人利用恐怖份子或嫌疑恐怖份子已存在的关系建立网络组织图，利用已掌握的恐怖份子情报(例如：年龄、性别、种族及文化程度)以及从电子邮件通信数据中获取的通信模式，有效地建立每一个邮件使用者的模式，生成一个可用的基于邮件用户个性特征和情报属性上的仿真邮件系统CEM。通过使用合适的通信分析工具，分析恐怖组织的社会结构和通信模式，帮助检查异常的通信行为，预测可能的恐怖行为并鉴别潜在的嫌疑犯。在恐怖组织网络构建方面，陈小东[3]等人使用卡内基梅隆大学的ORA工具对“东突”活动进行了分析。许晴[4]等人利用全球恐怖主义数据库GTD2对发生在1998至2004年间世界范围内所有公开报道的恐怖袭击事件进行了实证研究，构建了恐怖组织的网络模型，对全球恐怖组织的网络特征进行了分析，发现恐怖组织网络具有无标度网络和小世界网络的特征。但国内在利用社会网络分析方法研究恐怖分子网络方面还属于初级阶段，相对于国外来说还存在一定差距。

国外在“9·11”事件之前就已发现社会网络分析方法在研究恐怖主义战争方面的重要性。2001年“9·11”事件之前，John Arquilla和David Ronfeldt撰写了《网络和网络战》[5]，Kathleen Carley和其他人描述了社会网络分析的可能应用和破坏恐怖分子网络的多参与者模型[6]。在2001年冬，“国际社会网络分析网络”（INSNA）的专门网络期刊《Connection》对于社会网络分析和恐怖主义的问题进行了专门的探讨。Richard Rothenberg基于报纸和电台信息推测了基地恐怖分子网络结构[7]。自2001年冬天开始，学术界增加了对社会网络分析在恐怖主义方面的研究。

本文在总结若干主流节点影响力评价方法的基础上，提出基于三度理论的节点影响力评价方法。实验表明，本方法的结果较主流方法更明确。

1 节点影响力评价相关方法

社会网络分析（SNA）方法被用来分析、理解实体间的关系，以社会行动者之间的互动行为作为研究基础，是对相互连接的社会实体的数学描述。常用的确定关键人物的SNA方法有度方法，介性法以及特征向量方法等。

1）度中心性[8](Degree Centrality)：以每个顶点的度做为衡量标准，在网络中一个顶点的度数越大，表明该顶点也就越重要。

2）特征向量中心性[9]（Eigenvector Centrality）：一个节点的特征向量中心性与跟它相连的节点的中心性有关，利用矩阵特征向量的方法计算节点的特征向量。

3）拉普拉斯能量[10]（Laplacian Energy）：此方法通过Laplacian变换，结合Laplacian矩阵和图的Laplacian Energy，得出节点的Laplacian影响力评价。

4）介数中心性[11](Betweenness Centrality)：是度量中介节点的影响力，也就是度量其他节点对中介节点的依赖程度。

以上方法均有各自的缺点，中心性方法会有大量节点影响力相同，难以排序；特征向量中心性仅考虑了节点的相邻节点对其的影响；拉普拉斯能量方法对个别点的影响力估计会有严重的错误；介数中心性方法对不连通图会有较大估计误差，为此本文提出了基于三度理论的节点影响力评价方法。

2 基于三度理论的节点影响力评价方法

三度理论（Three Degree of Influence Rule）[12]指在社交网络中，我们自身行为可以作用于我们的朋友、亲人或同事，也可以作用于他们的朋友、亲人或同事（间接关系的朋友），还可以作用于间接关系朋友的朋友、亲人或同事，但彼此间的作用力是逐步削弱的。本文提出的方法基于三度理论，考虑到网络的局部信息的同时，也考虑了网络的全局信息，对网络中的各个节点的重要性可以进行排序，有较大的区分度。本文把影响力分为直接影响力和间接影响力，直接影响力与定点的度相关，间接影响力基于三度理论考虑，具体描述如下。

假设G是一个无向无权图，由n个顶点，m条边组成。矩阵A=(aij)n*n是图G的邻接矩阵，其中，aij表示顶点i和顶点j是否相连，如果相连，则aij=1，否则，aij=0。我们将每个节点的影响力分为直接影响力和间接影响力，将顶点i的内在影响力记为α(i)，间接影响力记为β(i)。，d(i)是顶点i的度，n表示顶点的个数，α(i)与网络的局部信息相关。β(i)的计算与网络的全局信息有关，

其中Nt(i)代表顶点i顶点t步可达的顶点集合，λ代表参数，而且随着距离越远，这个参数的值越小。根据三步理论，影响力会随着距离的增加而减弱，本文选取三步以内的信息作为顶点的间接影响力。个人影响力用符号p(i)表示，故p(i)=α(i)+β(i)，将每个顶点的p(i)排名。

基于三度理论的节点影响力评价方法算法：输入：网络G的邻接矩阵A=()aijn*n，输出：每个节点的影响力。Step 1：计算直接影响力，取e=1n-1( ) 1,1,1,…,1T，计算α=Ae，其中向量e中1的个数是图G中顶点个数，设为n，则α=( )α1,α2,α,3,…,αn代表的即是图G中每个顶点的直接影响。Step 2：找出少量较易区分影响力的点，设其集合为V0。Step 3：计算A2及A3。Step 4：对每个顶点i，令β()i=λ*∑i∈N1()iαi+λ2*∑i∈N2()iαi+λ3*∑i∈N3()iαi。Step 5：根据V0中的节点调整参数λ。Step 6：计算每个顶点的影响力p()i，p()i=α()i+β()i，将p()i排名。

3 “9·11”数据集实验分析

“9·11”劫机网络由19人组成，他们分别在四个不同的航班。Kreb[13]通过媒体，报纸等形式搜集得到“9·11”数据集如图1所示。图中显示了“9·11”恐怖分子之间的关系，有相同的颜色方块的人同一航班，为了计算方便，我们为每个顶点赋予一个数字，表示该顶点的编号，图中不同颜色的方框表示不同的飞机型号。

图1 “9·11”劫机网络图

表1分别是使用第二节提出的方法（Influence Node）与其他主流方法计算得到的顶点中心性结果。从表1所得结果可以看出，这五种方法对于前几名的排列结果是相同的，说明了该方法的有效性。从结果中可以发现，Degree方法对于很多顶点的重要程度是无法分辨的，虽然方法比较简单，计算容易，但是效果相对较差。Betweenness方法和Eigenvector方法虽然考虑到了网络整体的性质，能够反映网络中人物的重要程度，但是方法的评价指标有一定的局限性，对网络结构的要求较为严格。本文提出的方法计算简单，理论性比较强，即使网络中有连通分支也可以评价各个连通分支中顶点的重要程度，并且对于其他方法评价出相同影响力的点（如“10”和“2”，“6”、“8”和“9”等），此方法仍有较强的分辨能力。

4 恐怖组织网络演变

为了更加彻底地打击恐怖组织，本论文对恐怖组织网络的社交演变进行讨论。先假设“9·11”恐怖组织网络中最重要的一个人消失后，利用本论文提出的节点影响力方法，得出影响力最强的是序号为“10”的节点，他从网络图中消失后，整个网络必然遭到强烈的打击，那么网络图的连通性会下降，如图2。排名第二第三重要的节点分别是序号为“2”和“7”的节点，当他们依次消失后，如图3和图4，该网络的连通性更差。

表1 五种方法得到的中心性结果

图2 “10”消失后的网络图

当网络图的一些重要节点消失后，可以看出，网络中的连通性大大降低，通信能力也大幅下降。

5 结论

本论文提出一种新的方法计算恐怖组织网络中节点的影响力，通过与其他几种主流方法的结果进行对比，验证了它的可靠性；并利用“9·11”数据集，得出了各个节点的影响力。并推算重要节点消失后网络的演变情况。对打击恐怖组织具有一定的现实意义。

图3 “10”、“2”消失后网络图

图4 “10”、“2”、“7”消失后网络图

[1]周春光，曲鹏程，王 曦，等.DSNE：一个新的动态社会网络分析算法[J].吉林大学学报(工学版)，2008，38（2）：408-413.

[2]刘 威，唐常杰，乔少杰，等.基于概念邮件系统的犯罪数据挖掘新方法[J].计算机科学，2007，34（2）：213-215.

[3]Chen X,Li J,Huang Y.Network analysis using organizational risk analyzer[J].东南大学学报：英文版,2008 (24)：104-108.

[4]许 晴，祖正虎，郑 涛.恐怖组织网络的实证研究[J].合肥工业大学学报(自然科学版)，2010，33（2）：242-244,292.

[5]Mitliaga V N,Netwars：The Future of Terror.Crime and militancy[J].Foreign Affairs(Council on Foreign Relations),2002,10(2)：238-239.

[6]Carley K M,Reminga J,Kamneva N.Destabilizing Terrorist Networks[C].Command&Control Research Program,1998.

[7]Rothenberg R,Rothenberg R.From Whole Cloth：Making up the terrorist network[J].Connections,2001.

[8]平 亮，宗利永.基于社会网络中心性分析的微博信息传播研究--以Sina微博为例[J].图书情报知识，2010（6）：92-97.

[9]杨 明.基于特征向量中心度的程序依赖图顶点分级模型研究[D].北京：北京化工大学，2011.

[10]刘 颖，吴宝丰.关于图的拉普拉斯能量的若干结果[J].华东师范大学学报(自然科学版)，2010（1）：10-16.

[11]杨敬宗.在线社会网络影响力节点发现方法研究[D].太原：太原理工大学，2014.

[12]Wang M,Jia C,Yang D.Social friend recommendation mechanism based on three-degree influence[J]. Journal of Computer Applications,2015，35(7)：1984-1987.

[13]Valdis E K.Mapping networks of terrorist cells[J]. CONNECTIONS,2002,24(3)：43-52.

Evaluation of node influence based on three degree of influence rule

ZHAO Jia，LIU yue，LI Xue，WANG Meng-di,MO Sheng-kang
(School of Computer and Information Engineering,Fuyang Normal University,Fuyang Anhui236037,China)

After"9·11"incident,terrorist incidents have been a serious threat to human life and property.This paper presents a new approach based on three degree of influence rule to evaluate the influence of each node in the network of terrorist organizations.The experiments on the"9·11"experimental data sets demonstrate that this method is proved more explicitly than other mainstream methods for some nodes which are difficult to distinguish and have a good performance as the methods for some important nodes.Moreover the evolution of the terrorist network is presented.This method is helpful to strike and destroy the terrorist networks.

terrorist networks;vital nodes;influence;network evolution

TP181

：A

：1004-4329（2016）04-078-05

10.14096/j.cnki.cn34-1069/n/1004-4329(2016)04-078-05

2016-10-01

阜阳师范学院博士科研启动基金（FSB201501001）；安徽省大学生创新创业训练计划（201510371043）资助。

赵 佳（1984- ），男，博士，讲师，研究方向：运筹管理、数学规划、机器学习、数据挖掘。