趙 佳，劉 玥，李 雪，王夢迪，莫升康

(阜陽師范學院 計算機與信息工程學院，安徽 阜陽 236037）

基于三度理論的節(jié)點影響力評價方法

趙 佳，劉 玥，李 雪，王夢迪，莫升康

(阜陽師范學院 計算機與信息工程學院，安徽 阜陽 236037）

“9·11”事件以來，恐怖事件已經嚴重威脅到人類的生命財產安全。本文提出基于三度理論的評價方法來對恐怖組織網絡中的各個節(jié)點的影響力進行排序；并在“9·11”數據集驗證了該方法。實驗表明對于較重要的節(jié)點，本方法和主流評價方法有相同的效果，然而對于較難分辨影響力順序的節(jié)點，本方法仍能明確節(jié)點影響力順序，主流評價方法卻無法排序；本文同時并給出恐怖組織網絡演變的過程，分析演變結果，有利于對恐怖組織網絡的有力打擊和摧毀。

恐怖組織網絡；關鍵節(jié)點；影響力；網絡演變

恐怖主義是當今世界各國面臨的一個世界性的難題，嚴重地威脅著世界的和平與安全。恐怖主義自從二十世紀六十年代，特別是冷戰(zhàn)以來，對全球政治、經濟、文化產生了深遠的影響。“9·11”恐怖襲擊給美國帶來了前所未有的損失，最大程度化地威脅美國的權威及其霸主地位，讓世界都為之震驚。

在國內，在一般社會網絡數據挖掘方面，周春光[1]等人提出了一種新的基于事件動態(tài)的社會網絡分析算法；劉威[2]等人利用恐怖份子或嫌疑恐怖份子已存在的關系建立網絡組織圖，利用已掌握的恐怖份子情報(例如：年齡、性別、種族及文化程度)以及從電子郵件通信數據中獲取的通信模式，有效地建立每一個郵件使用者的模式，生成一個可用的基于郵件用戶個性特征和情報屬性上的仿真郵件系統(tǒng)CEM。通過使用合適的通信分析工具，分析恐怖組織的社會結構和通信模式，幫助檢查異常的通信行為，預測可能的恐怖行為并鑒別潛在的嫌疑犯。在恐怖組織網絡構建方面，陳小東[3]等人使用卡內基梅隆大學的ORA工具對“東突”活動進行了分析。許晴[4]等人利用全球恐怖主義數據庫GTD2對發(fā)生在1998至2004年間世界范圍內所有公開報道的恐怖襲擊事件進行了實證研究，構建了恐怖組織的網絡模型，對全球恐怖組織的網絡特征進行了分析，發(fā)現恐怖組織網絡具有無標度網絡和小世界網絡的特征。但國內在利用社會網絡分析方法研究恐怖分子網絡方面還屬于初級階段，相對于國外來說還存在一定差距。

國外在“9·11”事件之前就已發(fā)現社會網絡分析方法在研究恐怖主義戰(zhàn)爭方面的重要性。2001年“9·11”事件之前，John Arquilla和David Ronfeldt撰寫了《網絡和網絡戰(zhàn)》[5]，Kathleen Carley和其他人描述了社會網絡分析的可能應用和破壞恐怖分子網絡的多參與者模型[6]。在2001年冬，“國際社會網絡分析網絡”（INSNA）的專門網絡期刊《Connection》對于社會網絡分析和恐怖主義的問題進行了專門的探討。Richard Rothenberg基于報紙和電臺信息推測了基地恐怖分子網絡結構[7]。自2001年冬天開始，學術界增加了對社會網絡分析在恐怖主義方面的研究。

本文在總結若干主流節(jié)點影響力評價方法的基礎上，提出基于三度理論的節(jié)點影響力評價方法。實驗表明，本方法的結果較主流方法更明確。

1 節(jié)點影響力評價相關方法

社會網絡分析（SNA）方法被用來分析、理解實體間的關系，以社會行動者之間的互動行為作為研究基礎，是對相互連接的社會實體的數學描述。常用的確定關鍵人物的SNA方法有度方法，介性法以及特征向量方法等。

1）度中心性[8](Degree Centrality)：以每個頂點的度做為衡量標準，在網絡中一個頂點的度數越大，表明該頂點也就越重要。

2）特征向量中心性[9]（Eigenvector Centrality）：一個節(jié)點的特征向量中心性與跟它相連的節(jié)點的中心性有關，利用矩陣特征向量的方法計算節(jié)點的特征向量。

3）拉普拉斯能量[10]（Laplacian Energy）：此方法通過Laplacian變換，結合Laplacian矩陣和圖的Laplacian Energy，得出節(jié)點的Laplacian影響力評價。

4）介數中心性[11](Betweenness Centrality)：是度量中介節(jié)點的影響力，也就是度量其他節(jié)點對中介節(jié)點的依賴程度。

以上方法均有各自的缺點，中心性方法會有大量節(jié)點影響力相同，難以排序；特征向量中心性僅考慮了節(jié)點的相鄰節(jié)點對其的影響；拉普拉斯能量方法對個別點的影響力估計會有嚴重的錯誤；介數中心性方法對不連通圖會有較大估計誤差，為此本文提出了基于三度理論的節(jié)點影響力評價方法。

2 基于三度理論的節(jié)點影響力評價方法

三度理論（Three Degree of Influence Rule）[12]指在社交網絡中，我們自身行為可以作用于我們的朋友、親人或同事，也可以作用于他們的朋友、親人或同事（間接關系的朋友），還可以作用于間接關系朋友的朋友、親人或同事，但彼此間的作用力是逐步削弱的。本文提出的方法基于三度理論，考慮到網絡的局部信息的同時，也考慮了網絡的全局信息，對網絡中的各個節(jié)點的重要性可以進行排序，有較大的區(qū)分度。本文把影響力分為直接影響力和間接影響力，直接影響力與定點的度相關，間接影響力基于三度理論考慮，具體描述如下。

假設G是一個無向無權圖，由n個頂點，m條邊組成。矩陣A=(aij)n*n是圖G的鄰接矩陣，其中，aij表示頂點i和頂點j是否相連，如果相連，則aij=1，否則，aij=0。我們將每個節(jié)點的影響力分為直接影響力和間接影響力，將頂點i的內在影響力記為α(i)，間接影響力記為β(i)。，d(i)是頂點i的度，n表示頂點的個數，α(i)與網絡的局部信息相關。β(i)的計算與網絡的全局信息有關，

其中Nt(i)代表頂點i頂點t步可達的頂點集合，λ代表參數，而且隨著距離越遠，這個參數的值越小。根據三步理論，影響力會隨著距離的增加而減弱，本文選取三步以內的信息作為頂點的間接影響力。個人影響力用符號p(i)表示，故p(i)=α(i)+β(i)，將每個頂點的p(i)排名。

基于三度理論的節(jié)點影響力評價方法算法：輸入：網絡G的鄰接矩陣A=()aijn*n，輸出：每個節(jié)點的影響力。Step 1：計算直接影響力，取e=1n-1( ) 1,1,1,…,1T，計算α=Ae，其中向量e中1的個數是圖G中頂點個數，設為n，則α=( )α1,α2,α,3,…,αn代表的即是圖G中每個頂點的直接影響。Step 2：找出少量較易區(qū)分影響力的點，設其集合為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中的節(jié)點調整參數λ。Step 6：計算每個頂點的影響力p()i，p()i=α()i+β()i，將p()i排名。

3 “9·11”數據集實驗分析

“9·11”劫機網絡由19人組成，他們分別在四個不同的航班。Kreb[13]通過媒體，報紙等形式搜集得到“9·11”數據集如圖1所示。圖中顯示了“9·11”恐怖分子之間的關系，有相同的顏色方塊的人同一航班，為了計算方便，我們?yōu)槊總€頂點賦予一個數字，表示該頂點的編號，圖中不同顏色的方框表示不同的飛機型號。

圖1 “9·11”劫機網絡圖

表1分別是使用第二節(jié)提出的方法（Influence Node）與其他主流方法計算得到的頂點中心性結果。從表1所得結果可以看出，這五種方法對于前幾名的排列結果是相同的，說明了該方法的有效性。從結果中可以發(fā)現，Degree方法對于很多頂點的重要程度是無法分辨的，雖然方法比較簡單，計算容易，但是效果相對較差。Betweenness方法和Eigenvector方法雖然考慮到了網絡整體的性質，能夠反映網絡中人物的重要程度，但是方法的評價指標有一定的局限性，對網絡結構的要求較為嚴格。本文提出的方法計算簡單，理論性比較強，即使網絡中有連通分支也可以評價各個連通分支中頂點的重要程度，并且對于其他方法評價出相同影響力的點（如“10”和“2”，“6”、“8”和“9”等），此方法仍有較強的分辨能力。

4 恐怖組織網絡演變

為了更加徹底地打擊恐怖組織，本論文對恐怖組織網絡的社交演變進行討論。先假設“9·11”恐怖組織網絡中最重要的一個人消失后，利用本論文提出的節(jié)點影響力方法，得出影響力最強的是序號為“10”的節(jié)點，他從網絡圖中消失后，整個網絡必然遭到強烈的打擊，那么網絡圖的連通性會下降，如圖2。排名第二第三重要的節(jié)點分別是序號為“2”和“7”的節(jié)點，當他們依次消失后，如圖3和圖4，該網絡的連通性更差。

表1 五種方法得到的中心性結果

圖2 “10”消失后的網絡圖

當網絡圖的一些重要節(jié)點消失后，可以看出，網絡中的連通性大大降低，通信能力也大幅下降。

5 結論

本論文提出一種新的方法計算恐怖組織網絡中節(jié)點的影響力，通過與其他幾種主流方法的結果進行對比，驗證了它的可靠性；并利用“9·11”數據集，得出了各個節(jié)點的影響力。并推算重要節(jié)點消失后網絡的演變情況。對打擊恐怖組織具有一定的現實意義。

圖3 “10”、“2”消失后網絡圖

圖4 “10”、“2”、“7”消失后網絡圖

[1]周春光，曲鵬程，王 曦，等.DSNE：一個新的動態(tài)社會網絡分析算法[J].吉林大學學報(工學版)，2008，38（2）：408-413.

[2]劉 威，唐常杰，喬少杰，等.基于概念郵件系統(tǒng)的犯罪數據挖掘新方法[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].合肥工業(yè)大學學報(自然科學版)，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]楊敬宗.在線社會網絡影響力節(jié)點發(fā)現方法研究[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）；安徽省大學生創(chuàng)新創(chuàng)業(yè)訓練計劃（201510371043）資助。

趙 佳（1984- ），男，博士，講師，研究方向：運籌管理、數學規(guī)劃、機器學習、數據挖掘。