基于子圖模式的反恐情報關聯圖集分析

摘 要：[目的/意義]利用子圖模式對暴恐案件中的人員關聯進行分析可以發現涉恐人員關聯圖中的規律，為反恐情報分析提供有效參考。[方法/過程]首先對涉恐基礎數據進行預處理，保證圖中各頂點的唯一性。通過計數統計出所有的頻繁1-子圖和頻繁2-子圖，然后不斷迭代生成其他候選子圖并篩選頻繁子圖，直到達到終止條件為止。[結果/結論]該方法根據反恐情報的特點進行了優化，避免了普通頻繁子圖挖掘中的大量圖同構檢測，挖掘出的頻繁子圖可以反映不同類別涉恐人員之間的聯系規律和聯系特點，發現暴恐案件線索，有效預測和打擊恐怖活動。

關鍵詞：子圖模式;反恐情報;數據挖掘;候選子圖;圖同構

DOI：10.3969/j.issn.1008-0821.2019.07.005

〔中圖分類號〕G359;D631 〔文獻標識碼〕A 〔文章編號〕1008-0821（2019）07-0037-07

Abstract：[Purpose/significance]Frequent subgraph mining could provide rules which are found from relational graphs of terrorists in the crime of terrorism for counter-terrorism intelligence analysis.[Method/process]Before subgraph mining，the paper preprocessed the data to make sure the uniqueness of every vertex，the it counted the number of subgraph to produce frequent 1-subgraph and 2-subgraph in order.After that，repeated the process of generating other candidate subgraph and mining frequent subgraph until the terminal condition was satisfied.[Result/Conclusion]The result subgraphs could provide terrorism related clues which reflect the features of relationships among terrorists and effectively fight against terrorism.

Key words：subgraph pattern;counter terrorism intelligence;data mining;candidate subgraph;graph isomorphism

美國9？11 恐怖襲擊事件發生以后，世界各地的恐怖主義活動逐漸呈現越反越恐之勢[1]。尤其近幾年，以歐洲的一些大城市為代表發生了多起大規模暴力恐怖襲擊事件。2014 年6 月，在第68 屆聯合國大會上決議通過了《聯合國全球反恐戰略》，自此嚴厲打擊暴力恐怖主義成為維護世界和平的主要任務之一。我國近年來也發生了昆明3？01、北京10？28、新疆7？5等多起暴恐案件[2]。為打擊我國境內的恐怖主義活動，2015年12 月27日第十二屆全國人民代表大會常務委員會第十八次會議正式通過《中華人民共和國反恐怖主義法》，新疆維吾爾自治區、浙江省等地也陸續出臺了相關的反恐法實施辦法。面對如此嚴峻的反恐形勢，國家反恐怖工作領導小組多次強調要加強反恐情報收集，實現反恐預警，將暴恐活動消滅在萌芽中。在大數據背景下，人們在工作、生活、學習、旅游、消費等活動中都會產生數據，形成多種來源的數據流，利用數據挖掘等技術可以對這些信息進行快速有效的分析，為實現提前預警提供有效的情報依據。

子圖模式又稱頻繁子圖，是指在圖集中出現頻率較高的子圖，即“公共子結構”。子圖模式挖掘是數據挖掘的主要方法之一，也是一種比較復雜的關聯分析。在由“頂點”和“邊”組成的數據結構“圖”的集合上挖掘子圖模式的任務稱作頻繁子圖挖掘。頻繁子圖挖掘目前主要應用于生物分子分析、化學結構分析、網絡拓撲以及文檔拓撲結構等實體的分析。在中國知網、百度學術等知名中文文獻數據庫或者學術搜索引擎中利用中文關鍵詞“頻繁子圖”或“子圖模式”與“反恐”組合搜索，沒有發現直接相關的文獻。說明在以上中文數據庫中，關于反恐情報中頻繁子圖挖掘的研究非常少。在谷歌學術搜索和必應學術搜索中，涉及這兩個概念（“Subgraph Mining”和“Counter-terrorism”）的英文文獻主要包括網頁鏈接分析[3-4]、社交網絡戰略分析[5]、社交網絡中的社區探測[6]、社交網絡的風險評估[7-8]、重要人員檢測[9]、新的頻繁子圖挖掘算法[10-11]、基于云計算的智能數據分析模型[12]等方向，也沒有發現根據涉恐人員的特點專門利用頻繁子圖分析涉恐人員關聯規律的研究。本文將研究頻繁子圖挖掘在涉恐人員關聯分析中的應用。

1 子圖模式挖掘

1.1 子圖模式挖掘簡介

子圖模式又稱頻繁子圖，子圖模式挖掘是指給定圖集和最小支持度閾值，找出使得所有支持度大于或等于最小支持度閾值的子圖[13]。子圖模式挖掘是關聯分析方法中遠比頻繁項集挖掘[14]、頻繁靜態空間模式挖掘[15]、頻繁序列模式挖掘[16]、頻繁軌跡模式挖掘[17]更復雜的方法。一般情況下，在任何1個項集中每個單項只能出現0次或1次。但是，在圖中1個頂點可能出現多次，而且即使是對相同的頂點標號對，其邊的權值也可能不同[18]。

1.2 子圖模式挖掘中的基本概念

本文的反恐情報關聯圖集分析中需要用到的基本概念如下：

1）頂點：表示涉恐人員;

2）邊：表示兩個涉恐人員之間的聯系，邊的權值表示聯系的緊密程度，權值的大小根據涉恐人員之間的通話[19]、同住宿[20]、同上網[21]等聯系設定;

3）圖：由若干頂點和連接頂點的邊構成的數據結構體，是涉恐人員關聯的一種直觀的表示方法;

4）子圖：是指給定圖G′=（V′，E′）和G=（V，E），如果頂點集V′是V的子集，并且它的邊集E′是E的子集，則稱G′是G的子圖;

5）k-子圖：包含k個頂點的子圖，即表示k個涉恐人員的關聯;

6）支持度：表示在圖集中所有包含某子圖的圖的計數與總圖計數的比值;

7）鄰接矩陣：一種利用矩陣表示圖中頂點和邊的方法;

8）事務表：將圖中的每條邊表示成形如（頂點1，頂點2，邊的權值）形式的表格，對應表示（涉恐人員1，涉恐人員2，兩人的聯系緊密程度數值）。

1.3 子圖模式挖掘方法分析

主流的子圖模式挖掘方法主要分為基于先驗原理的方法（例如AGM和FSG等）和基于模式增長的方法（例如gSpan、CloseGraph和FFSM等）[22]。基于先驗原理的方法運算簡單，專業門檻低，更易于普及推廣。基于先驗原理的方法還可以采用直接將圖結構映射為事務集的形式，然后利用普通頻繁項集的挖掘方法進行頻繁子圖挖掘，但是這種方式會產生非連通圖，即同一個圖中包含孤立頂點或孤立子圖。如果應用這種方法，則挖掘出的涉恐人員關聯會有連接中斷，分析結果并無實際意義。在反恐情報分析中主要考慮涉恐人員之間的聯系，頻繁子圖挖掘時只需要考慮連通圖。非連通圖表示該圖中存在至少兩組涉恐人員之間沒有聯系，反恐情報分析中不考慮此類圖。AGM（Apriori-based Graph Mining）算法使用每一步增加1個節點的擴展方式來產生候選子圖，FSG算法使用每一步增加1條邊的擴展方式來產生候選子圖。這兩種方法在生成頻繁子圖的過程中都需要比較大量的圖同構，如果原始圖集較大較復雜，則剪枝后的候選子圖數量仍然很多，計算效率不高。

假設兩個頂點互換后的圖結構不變，則稱交換前以及交換后的兩個圖等價，即兩個圖同構。一般情況下，在挖掘頻繁子圖的過程中，需要判斷每個候選子圖是否與其他頻繁子圖拓撲等價。由于每個圖按照頂點次序不同，可以有多個鄰接矩陣表示方法，所以處理圖同構時要轉換為唯一的鄰接矩陣表示，將圖映射為唯一的串表達式，一般采用字典最小或字典最大串，計算開銷非常大。類似化學結構分析中的頻繁子圖挖掘，各種元素在元素周期表中的代號唯一，因此分析中一定會存在需要檢測大量圖同構的問題。

2 涉恐人員關聯圖集生成方法

本文在構建原始圖集時直接根據反恐情報的特點將圖頂點按序排列，且保證每個頂點唯一，這就避免了大量圖同構檢測中的鄰接矩陣轉換，直接對比唯一的鄰接矩陣即可，從而達到提高反恐情報分析效率的目的。

如圖1所示為生成原始圖集的方法，首先對不同來源的數據分組，然后在各分組中以人員為頂點、人員聯系為邊分別生成關聯圖，最后各分組中的數據組成圖集。

在涉恐人員分析中，在人員分類用代號表示后，每個人員的涉恐風險以及部分特征還是有差別的。產生涉恐人員關聯圖集時首先利用分類方法[23]將涉恐人員分類，然后根據風險分析方法將圖中同時出現的同一類人員進行排序，保證每個人在圖中對應頂點的唯一性，同一類別人群中的人員排序以數字表示。不同圖中的頂點標號例如A1和A2表示的是不同的人員，其標號中的字母A表示兩人都屬于A類別人員，數字1和2表示在其對應圖中所有A類人員的相對風險排序。圖中連接各“頂點”之間的“邊”的權值根據已掌握的涉恐人員之間的聯系確定。聯系的種類主要包括通信關聯、物流關聯、交易關聯、同鄉關系、親屬關系等[24]。人員關聯圖中如果以人員聯系的直接權值為邊的值，則為連續數值取值范圍過大，不宜挖掘出頻繁子圖。所以還要利用區間劃分的方法，將連續數值轉換為幾個離散的參數[25]，例如11～20設為p，21～50設為q，51～100設為r。不滿足最小權值要求的微弱關聯例如權值為1～10則視為在圖中不連通，即對應圖頂點之間沒有邊。

這種處理方式的挖掘結果會漏掉一部分模糊頻繁子圖，但是挖掘出的頻繁子圖定義人員關聯時會更精準，同時挖掘效率也會更高。這里的“模糊頻繁子圖”是指初步劃分人員類別后，不再進行各分類內的排序，同類人員的代號完全相同。

3 涉恐人員關聯圖集子圖模式挖掘方法

由于在涉恐人員關聯分析中“人”即頂點是最核心的要素，因此本文采用頂點增長的方式。在實際的反恐情報關聯圖集分析中，如果頻繁子圖中頂點和邊的數量過少則沒有太大參考價值，在反恐情報關聯圖集分析中有必要專門設置最小頂點數閾值。如圖2所示為參考頂點增長的經典方法AGM的流程[26]，本文修改了數據生成和預處理的方法，具體分析流程描述如下：

1）數據生成和數據預處理。根據樣本數據生成標準圖結構的圖集和對應事務表。將涉恐人員分類，每個類別用不同字母表示成一級編號，映射為圖中的頂點。同類人員如果在圖中多于1個，則根據涉恐風險特征排序進行二級編號用數字表示，保證其在圖中的唯一性和順序性，每個圖對應的鄰接矩陣唯一。圖中邊的權值根據不同人員之間的所有聯系綜合計算得出。

2）設定最小支持度計數、最小頂點計數的參數閾值。

3）利用統計計數依次發現頻繁1-子圖和頻繁2-子圖。

4）迭代產生頻繁k-子圖（k>2）。連接頻繁（k-1）-子圖產生候選k-子圖，按序從該k-子圖刪除1條邊，并檢查刪除該邊后的（k-1）-子圖是否連通且滿足頻繁條件。只要存在非頻繁（k-1）-子圖，則將該候選k-子圖直接刪除。對沒有被刪除的候選k-子圖計算支持度，滿足條件則保留，不滿足條件則刪除。繼續本步驟，產生頻繁（k+1）-子圖。直到沒有新的頻繁子圖或新的候選子圖產生，終止挖掘過程。

在產生頻繁k-子圖的過程中還要考慮多種不同情況，將在下文中結合示例詳細描述每一種情況。普通的頻繁子圖挖掘中，需要判定每個（k-1）-子圖是否存在圖同構問題。檢查過程中要進行對應圖鄰接矩陣的大量轉換，計算開銷非常大。前文中提出了反恐情報中一種專用的原始樣本圖集生成和預處理方法，不再需要圖同構檢測，因此下文的分析中將不再討論圖同構問題。

4 反恐情報中的子圖模式挖掘示例

4.1 涉恐人員關聯圖集樣本

反恐情報子圖模式挖掘前，除了常規的數據挖掘預處理外，還要將所有的人員關聯統計出來并生成原始樣本圖集。首先按照基礎人員的涉恐特征，將不同的人員分為幾大類。基礎涉恐人員分類時以職業、教育水平、年齡、身高、體重、性別、收入水平等屬性特征劃分。分類后將人員劃定為A、B、C、D、E、F……等不同的人群，再利用風險分析為每個分類中的人員編號排序，保證唯一性。

如圖3所示為一組涉恐人員關聯樣本圖集，圖集中共有4個子圖對應4組人員數據，分別包含5人、4人、4人、4人，即原始樣本圖集共由17名人員的數據生成，每個子圖中的人員編號表示類別和在對應子圖中的排序。圖中的數據完全隨機生成，表1所示為對應的事務表。例如圖G1中的邊（a1，b，p）前兩個元素為兩個頂點a1和b，表示兩個涉恐人員，p表示兩個人員之間的聯系權值大小。本文將以這四個虛擬的關聯圖詳細說明如何利用子圖模式挖掘發現涉恐人員的聯系規律。

圖3中4個人員關聯圖對應的鄰接矩陣分別為MG1、MG2、MG3、MG4。所有對角線數據表示每個人與自己的關聯，對應值均為0，人員權值關聯是雙向的，所有鄰接矩陣均為對稱矩陣。矩陣中人員排序為a1、a2、b、c、d。G1矩陣中第一行第一個p即表示兩名涉恐人員（a1，a2）的對應聯系權值，第一行第二個p表示（a1，b）的對應權值，同理可得矩陣其他值的意義。因為圖集中所有頂點即所有人員都是唯一的，且在鄰接矩陣中的相對順序是不變的，所以對應的鄰接矩陣一定是唯一的，對比子圖時只需要利用唯一的鄰接矩陣對比。

4.2 量化分析過程

設最小支持度閾值為40%，則頻繁子圖支持度計數至少為2（大于等于4*40%，數值4表示圖集中共有4個關聯圖），最小頂點數閾值為4。如圖4所示為樣本人員關聯圖的子圖模式挖掘過程，圖中圓括號內數字表示支持度計數。當子圖中只有1個節點（k=1）時，只需對圖集中每個頂點計數，如果候選1-子圖（只有1個單獨頂點）計數大于或等于2時，則滿足支持度條件，樣本圖集中有5個頂點滿足條件。接著在表1中利用頻繁1-子圖兩兩組合，通過計數挖掘出頻繁2-子圖（k=2），每個子圖中包含2個頂點和1條邊，共有5個頻繁2-子圖滿足條件。

從挖掘頻繁k-子圖（k>2）開始，基于每兩個頻繁（k-1）-子圖共享“核”（相同的頻繁（k-2）-子圖，對應鄰接矩陣除了最后一行和最后一列完全相同）生成候選k-子圖，然后利用先驗原理和支持度計數統計選擇滿足條件的頻繁k-子圖。產生候選k-子圖和頻繁k-子圖的過程有以下幾種不同的情況。

查閱表1，對應事務表中（b，c，？）兩個涉恐人員的邊只有q一種值。當取值為q時，對應所有的3-子圖均為頻繁3-子圖，且滿足支持度計數條件，所以g41為頻繁4-子圖。假設b和c兩個涉恐人員還有其他的聯系權值也滿足頻繁條件，則只取權值更大的邊。例如（b，c，Q）也滿足條件且Q>q，則b和c之間的邊取Q值。

情況3：存在新增頂點生成邊且不滿足頻繁條件（圖7中的“問號”可取非0值但對應子圖不滿足條件），這時考慮邊的權值取0的情況。考慮合并頻繁3-子圖g31和g33的情況，候選4-子圖如圖7所示。查詢表1發現（b，d）之間存在邊，取值為p。當邊的權值為p時，存在非頻繁子圖，不滿足條件，這時只考慮二者之間沒有邊的情況，即權值取0。當取0時，所有3-子圖頻繁，且支持度計數滿足條件，所以對應頻繁4-子圖為g42。

最后生成的頻繁子圖即為g41和g42，滿足最小頂點數要求。本文中的虛擬涉恐人員關聯樣本圖集較小，圖中“頂點”和“邊”數量也較少，所以頻繁子圖結構非常簡單。實際反恐情報關聯圖集分析中挖掘出的人員關聯會非常復雜。同時，在實際應用中，“邊”的權值不一定用數值區間離散化簡單表示，還可以根據不同的聯系類型標記，挖掘出更精細化、更有參考價值的涉恐人員關聯規律。

5 結 語

本文提出了如何利用子圖模式挖掘發現暴恐案件中恐怖分子的聯系規律。經典的子圖模式挖掘方法中大多基于頂點增長或者邊增長的方式迭代的擴展子圖，通過生成候選子圖然后篩選頻繁子圖的方式實現。也有一部分方法基于類似頻繁模式樹的方式采用模式增長的思路。這些方法中一般要利用一些專門設計的算法來進行大量的圖同構檢測，盡量減少這部分計算的開銷。本文從反恐情報關聯圖集分析的目標出發，結合反恐情報的特點，在數據預處理時不但將涉恐人員按照涉恐特征分類，還在每個分類中對涉恐人員進行風險評估排序，保證圖集中所有圖頂點唯一且按序排列，進而保證每個圖的鄰接矩陣唯一，避免大量的圖同構檢測。文中涉恐人員之間的關聯需要按照各種不同聯系綜合計算出數值權重，再利用區間劃分將連續數值轉換為權重類別。

參考文獻

[1]王震.“9？11”以來全球反恐戰略困境探析[J].社會科學，2017，（9）：16-28.

[2]騰訊網.近年來新疆分裂勢力制造的暴恐事件不完全匯總[EB/OL].http：//news.qq.com/a/ 20140302/005359.htm，2018-10-15.

[3]Badia A，Kantardzic M.Link Analysis Tools for Intelligence and Counterterrorism[C]//International Conference on Intelligence and Security Informatics.Springer Berlin Heidelberg，2005：49-59.

[4]Akhtar Z，Singh M K，Begam N.Challenges and Usage of Link Mining to Semantic Web[J].Intemational Journal of Electronics and Computer Science Engineering，2012，（1）：775-780.

[5]Michalak T P，Rahwan T，Wooldridge M.Strategic Social Network Analysis[C]//The Thirty-First AAAI Conference on Artificial Intelligence（AAAI），2017：4841-4845.

[6]Muslim N.A Combination Approach to Community Detection in Social Networks by Utilizing Structural and Attribute Data[J].Social Networking，2015，5（1）：11-15.

[7]Camacho D，Gilpérez-López I，Gonzalez-Pardo A，et al.RiskTrack：A New Approach for Risk Assessment of Radicalisation Based on Social Media Data[C]//CEUR Workshop Proceedings，2016：1-10.

[8]Lara-Cabrera R，Pardo A G，Benouaret K，et al.Measuring the Radicalisation Risk in Social Networks[J].IEEE Access，2017，（5）：10892-10900.

[9]Farooq E，Khan S A，Butt W H.Covert Network Analysis to Detect Key Players Using Correlation and Social Network Analysis[C]//International Conference Internet of Things and Cloud Computing.ACM，2017：1-6.

[10]Rao B，Mishra S.An Approach to Detect Patterns（Sub-graphs）with Edge Weight in Graph Using Graph Mining Techniques[M]//Computational Intelligence in Data Mining.Springer，Singapore，2019：807-817.

[11]Shelokar P，Quirin A，Cordon O.MOEP-SO：A Multiobjective Evolutionary Programming Algorithm for Graph Mining[C]//Intelligent Systems Design and Applications（ISDA），2011 11th International Conference on.IEEE，2011：219-224.

[12]Goteng G L，Tao X.Cloud Computing Intelligent Data-Driven Model：Connecting the Dots to Combat Global Terrorism[C]//Big Data（BigData Congress），2016 IEEE International Congress on.IEEE，2016：446-453.

[13]張仲妹，王桂玲，張賽，等.基于頻繁子圖挖掘的數據服務Mashup推薦[J].電子科技大學學報， 2016，45（2）：263-269.

[14]李勇男，梅建明.基于頻繁模式樹的涉恐情報關聯分析[J].情報科學，2017，35（9）：141-145，152.

[15]李勇男.空間模式挖掘在反恐情報分析中的應用研究[J].情報雜志，2018，37（4）：33-37.

[16]李勇男.基于頻繁序列模式挖掘的反恐情報關聯分析[J].情報理論與實踐，2018，41（10）：100-104，46.

[17]李勇男.時空軌跡頻繁模式在反恐情報分析中的應用研究[J].情報雜志，2018，37（8）：51-55.

[18]劉振.頻繁子圖挖掘算法的研究與應用[D].長沙：中南大學，2009：13-14.

[19]侯麗波，王冠.交互式話單數據的社會關系權值分析[J].中國刑警學院學報，2017，（5）：106-112.

[20]付璇.旅店同住分析系統的設計與實現[D].北京：北京大學，2011.

[21]陳剛，李松巖.對以異常行為信息為基礎科學構建積分預警系統的思考[J].北京警察學院學報，2013，（1）：44-47.

[22]張煥生，崔炳德，王政峰，等.基于圖的頻繁子結構挖掘算法綜述[J].微型機與應用，2009，28（10）：5-9.

[23]李勇男.貝葉斯理論在反恐情報分類分析中的應用研究[J].數據分析與知識發現，2018，2（10）：9-14.

[24]陳鵬，瞿珂，陳剛，等.反恐背景下的個人特征數據構成與涉恐個體的挖掘分析[J].情報雜志，2018，（4）：38-41，68.

[25]李勇男，梅建明，秦廣軍.反恐情報分析中的數據預處理研究[J].情報科學，2017，35（11）：103-107，113.

[26]張偉.頻繁子圖挖掘算法的研究[D].秦皇島：燕山大學，2011：13-14.

（責任編輯：孫國雷）