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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于三度理論的節(jié)點影響力評價方法算法：輸入：網(wǎng)絡G的鄰接矩陣A=()aijn*n，輸出：每個節(jié)點的影響力。Step 1：計算直接影響力，取e=1n-1( ) 1,1,1,…,1T，計算α=Ae，其中向量e中1的個數(shù)是圖G中頂點個數(shù)，設為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：根據(jù)V0中的節(jié)點調(diào)整參數(shù)λ。Step 6：計算每個頂點的影響力p()i，p()i=α()i+β()i，將p()i排名。

3 “9·11”數(shù)據(jù)集實驗分析

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

圖1 “9·11”劫機網(wǎng)絡圖

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

4 恐怖組織網(wǎng)絡演變

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

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

圖2 “10”消失后的網(wǎng)絡圖

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

5 結論

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

圖3 “10”、“2”消失后網(wǎng)絡圖

圖4 “10”、“2”、“7”消失后網(wǎng)絡圖

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

[2]劉 威，唐常杰，喬少杰，等.基于概念郵件系統(tǒng)的犯罪數(shù)據(jù)挖掘新方法[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]許 晴，祖正虎，鄭 濤.恐怖組織網(wǎng)絡的實證研究[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]平 亮，宗利永.基于社會網(wǎng)絡中心性分析的微博信息傳播研究--以Sina微博為例[J].圖書情報知識，2010（6）：92-97.

[9]楊 明.基于特征向量中心度的程序依賴圖頂點分級模型研究[D].北京：北京化工大學，2011.

[10]劉 穎，吳寶豐.關于圖的拉普拉斯能量的若干結果[J].華東師范大學學報(自然科學版)，2010（1）：10-16.

[11]楊敬宗.在線社會網(wǎng)絡影響力節(jié)點發(fā)現(xiàn)方法研究[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- ），男，博士，講師，研究方向：運籌管理、數(shù)學規(guī)劃、機器學習、數(shù)據(jù)挖掘。