基于子圖模式的反恐情報(bào)關(guān)聯(lián)圖集分析

摘 要：[目的/意義]利用子圖模式對(duì)暴恐案件中的人員關(guān)聯(lián)進(jìn)行分析可以發(fā)現(xiàn)涉恐人員關(guān)聯(lián)圖中的規(guī)律，為反恐情報(bào)分析提供有效參考。[方法/過(guò)程]首先對(duì)涉恐基礎(chǔ)數(shù)據(jù)進(jìn)行預(yù)處理，保證圖中各頂點(diǎn)的唯一性。通過(guò)計(jì)數(shù)統(tǒng)計(jì)出所有的頻繁1-子圖和頻繁2-子圖，然后不斷迭代生成其他候選子圖并篩選頻繁子圖，直到達(dá)到終止條件為止。[結(jié)果/結(jié)論]該方法根據(jù)反恐情報(bào)的特點(diǎn)進(jìn)行了優(yōu)化，避免了普通頻繁子圖挖掘中的大量圖同構(gòu)檢測(cè)，挖掘出的頻繁子圖可以反映不同類別涉恐人員之間的聯(lián)系規(guī)律和聯(lián)系特點(diǎn)，發(fā)現(xiàn)暴恐案件線索，有效預(yù)測(cè)和打擊恐怖活動(dòng)。

關(guān)鍵詞：子圖模式;反恐情報(bào);數(shù)據(jù)挖掘;候選子圖;圖同構(gòu)

DOI：10.3969/j.issn.1008-0821.2019.07.005

〔中圖分類號(hào)〕G359;D631 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕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

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

子圖模式又稱頻繁子圖，是指在圖集中出現(xiàn)頻率較高的子圖，即“公共子結(jié)構(gòu)”。子圖模式挖掘是數(shù)據(jù)挖掘的主要方法之一，也是一種比較復(fù)雜的關(guān)聯(lián)分析。在由“頂點(diǎn)”和“邊”組成的數(shù)據(jù)結(jié)構(gòu)“圖”的集合上挖掘子圖模式的任務(wù)稱作頻繁子圖挖掘。頻繁子圖挖掘目前主要應(yīng)用于生物分子分析、化學(xué)結(jié)構(gòu)分析、網(wǎng)絡(luò)拓?fù)湟约拔臋n拓?fù)浣Y(jié)構(gòu)等實(shí)體的分析。在中國(guó)知網(wǎng)、百度學(xué)術(shù)等知名中文文獻(xiàn)數(shù)據(jù)庫(kù)或者學(xué)術(shù)搜索引擎中利用中文關(guān)鍵詞“頻繁子圖”或“子圖模式”與“反恐”組合搜索，沒(méi)有發(fā)現(xiàn)直接相關(guān)的文獻(xiàn)。說(shuō)明在以上中文數(shù)據(jù)庫(kù)中，關(guān)于反恐情報(bào)中頻繁子圖挖掘的研究非常少。在谷歌學(xué)術(shù)搜索和必應(yīng)學(xué)術(shù)搜索中，涉及這兩個(gè)概念（“Subgraph Mining”和“Counter-terrorism”）的英文文獻(xiàn)主要包括網(wǎng)頁(yè)鏈接分析[3-4]、社交網(wǎng)絡(luò)戰(zhàn)略分析[5]、社交網(wǎng)絡(luò)中的社區(qū)探測(cè)[6]、社交網(wǎng)絡(luò)的風(fēng)險(xiǎn)評(píng)估[7-8]、重要人員檢測(cè)[9]、新的頻繁子圖挖掘算法[10-11]、基于云計(jì)算的智能數(shù)據(jù)分析模型[12]等方向，也沒(méi)有發(fā)現(xiàn)根據(jù)涉恐人員的特點(diǎn)專門利用頻繁子圖分析涉恐人員關(guān)聯(lián)規(guī)律的研究。本文將研究頻繁子圖挖掘在涉恐人員關(guān)聯(lián)分析中的應(yīng)用。

1 子圖模式挖掘

1.1 子圖模式挖掘簡(jiǎn)介

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

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

本文的反恐情報(bào)關(guān)聯(lián)圖集分析中需要用到的基本概念如下：

1）頂點(diǎn)：表示涉恐人員;

2）邊：表示兩個(gè)涉恐人員之間的聯(lián)系，邊的權(quán)值表示聯(lián)系的緊密程度，權(quán)值的大小根據(jù)涉恐人員之間的通話[19]、同住宿[20]、同上網(wǎng)[21]等聯(lián)系設(shè)定;

3）圖：由若干頂點(diǎn)和連接頂點(diǎn)的邊構(gòu)成的數(shù)據(jù)結(jié)構(gòu)體，是涉恐人員關(guān)聯(lián)的一種直觀的表示方法;

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

5）k-子圖：包含k個(gè)頂點(diǎn)的子圖，即表示k個(gè)涉恐人員的關(guān)聯(lián);

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

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

8）事務(wù)表：將圖中的每條邊表示成形如（頂點(diǎn)1，頂點(diǎn)2，邊的權(quán)值）形式的表格，對(duì)應(yīng)表示（涉恐人員1，涉恐人員2，兩人的聯(lián)系緊密程度數(shù)值）。

1.3 子圖模式挖掘方法分析

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

假設(shè)兩個(gè)頂點(diǎn)互換后的圖結(jié)構(gòu)不變，則稱交換前以及交換后的兩個(gè)圖等價(jià)，即兩個(gè)圖同構(gòu)。一般情況下，在挖掘頻繁子圖的過(guò)程中，需要判斷每個(gè)候選子圖是否與其他頻繁子圖拓?fù)涞葍r(jià)。由于每個(gè)圖按照頂點(diǎn)次序不同，可以有多個(gè)鄰接矩陣表示方法，所以處理圖同構(gòu)時(shí)要轉(zhuǎn)換為唯一的鄰接矩陣表示，將圖映射為唯一的串表達(dá)式，一般采用字典最小或字典最大串，計(jì)算開(kāi)銷非常大。類似化學(xué)結(jié)構(gòu)分析中的頻繁子圖挖掘，各種元素在元素周期表中的代號(hào)唯一，因此分析中一定會(huì)存在需要檢測(cè)大量圖同構(gòu)的問(wèn)題。

2 涉恐人員關(guān)聯(lián)圖集生成方法

本文在構(gòu)建原始圖集時(shí)直接根據(jù)反恐情報(bào)的特點(diǎn)將圖頂點(diǎn)按序排列，且保證每個(gè)頂點(diǎn)唯一，這就避免了大量圖同構(gòu)檢測(cè)中的鄰接矩陣轉(zhuǎn)換，直接對(duì)比唯一的鄰接矩陣即可，從而達(dá)到提高反恐情報(bào)分析效率的目的。

如圖1所示為生成原始圖集的方法，首先對(duì)不同來(lái)源的數(shù)據(jù)分組，然后在各分組中以人員為頂點(diǎn)、人員聯(lián)系為邊分別生成關(guān)聯(lián)圖，最后各分組中的數(shù)據(jù)組成圖集。

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

這種處理方式的挖掘結(jié)果會(huì)漏掉一部分模糊頻繁子圖，但是挖掘出的頻繁子圖定義人員關(guān)聯(lián)時(shí)會(huì)更精準(zhǔn)，同時(shí)挖掘效率也會(huì)更高。這里的“模糊頻繁子圖”是指初步劃分人員類別后，不再進(jìn)行各分類內(nèi)的排序，同類人員的代號(hào)完全相同。

3 涉恐人員關(guān)聯(lián)圖集子圖模式挖掘方法

由于在涉恐人員關(guān)聯(lián)分析中“人”即頂點(diǎn)是最核心的要素，因此本文采用頂點(diǎn)增長(zhǎng)的方式。在實(shí)際的反恐情報(bào)關(guān)聯(lián)圖集分析中，如果頻繁子圖中頂點(diǎn)和邊的數(shù)量過(guò)少則沒(méi)有太大參考價(jià)值，在反恐情報(bào)關(guān)聯(lián)圖集分析中有必要專門設(shè)置最小頂點(diǎn)數(shù)閾值。如圖2所示為參考頂點(diǎn)增長(zhǎng)的經(jīng)典方法AGM的流程[26]，本文修改了數(shù)據(jù)生成和預(yù)處理的方法，具體分析流程描述如下：

1）數(shù)據(jù)生成和數(shù)據(jù)預(yù)處理。根據(jù)樣本數(shù)據(jù)生成標(biāo)準(zhǔn)圖結(jié)構(gòu)的圖集和對(duì)應(yīng)事務(wù)表。將涉恐人員分類，每個(gè)類別用不同字母表示成一級(jí)編號(hào)，映射為圖中的頂點(diǎn)。同類人員如果在圖中多于1個(gè)，則根據(jù)涉恐風(fēng)險(xiǎn)特征排序進(jìn)行二級(jí)編號(hào)用數(shù)字表示，保證其在圖中的唯一性和順序性，每個(gè)圖對(duì)應(yīng)的鄰接矩陣唯一。圖中邊的權(quán)值根據(jù)不同人員之間的所有聯(lián)系綜合計(jì)算得出。

2）設(shè)定最小支持度計(jì)數(shù)、最小頂點(diǎn)計(jì)數(shù)的參數(shù)閾值。

3）利用統(tǒng)計(jì)計(jì)數(shù)依次發(fā)現(xiàn)頻繁1-子圖和頻繁2-子圖。

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

在產(chǎn)生頻繁k-子圖的過(guò)程中還要考慮多種不同情況，將在下文中結(jié)合示例詳細(xì)描述每一種情況。普通的頻繁子圖挖掘中，需要判定每個(gè)（k-1）-子圖是否存在圖同構(gòu)問(wèn)題。檢查過(guò)程中要進(jìn)行對(duì)應(yīng)圖鄰接矩陣的大量轉(zhuǎn)換，計(jì)算開(kāi)銷非常大。前文中提出了反恐情報(bào)中一種專用的原始樣本圖集生成和預(yù)處理方法，不再需要圖同構(gòu)檢測(cè)，因此下文的分析中將不再討論圖同構(gòu)問(wèn)題。

4 反恐情報(bào)中的子圖模式挖掘示例

4.1 涉恐人員關(guān)聯(lián)圖集樣本

反恐情報(bào)子圖模式挖掘前，除了常規(guī)的數(shù)據(jù)挖掘預(yù)處理外，還要將所有的人員關(guān)聯(lián)統(tǒng)計(jì)出來(lái)并生成原始樣本圖集。首先按照基礎(chǔ)人員的涉恐特征，將不同的人員分為幾大類?；A(chǔ)涉恐人員分類時(shí)以職業(yè)、教育水平、年齡、身高、體重、性別、收入水平等屬性特征劃分。分類后將人員劃定為A、B、C、D、E、F……等不同的人群，再利用風(fēng)險(xiǎn)分析為每個(gè)分類中的人員編號(hào)排序，保證唯一性。

如圖3所示為一組涉恐人員關(guān)聯(lián)樣本圖集，圖集中共有4個(gè)子圖對(duì)應(yīng)4組人員數(shù)據(jù)，分別包含5人、4人、4人、4人，即原始樣本圖集共由17名人員的數(shù)據(jù)生成，每個(gè)子圖中的人員編號(hào)表示類別和在對(duì)應(yīng)子圖中的排序。圖中的數(shù)據(jù)完全隨機(jī)生成，表1所示為對(duì)應(yīng)的事務(wù)表。例如圖G1中的邊（a1，b，p）前兩個(gè)元素為兩個(gè)頂點(diǎn)a1和b，表示兩個(gè)涉恐人員，p表示兩個(gè)人員之間的聯(lián)系權(quán)值大小。本文將以這四個(gè)虛擬的關(guān)聯(lián)圖詳細(xì)說(shuō)明如何利用子圖模式挖掘發(fā)現(xiàn)涉恐人員的聯(lián)系規(guī)律。

圖3中4個(gè)人員關(guān)聯(lián)圖對(duì)應(yīng)的鄰接矩陣分別為MG1、MG2、MG3、MG4。所有對(duì)角線數(shù)據(jù)表示每個(gè)人與自己的關(guān)聯(lián)，對(duì)應(yīng)值均為0，人員權(quán)值關(guān)聯(lián)是雙向的，所有鄰接矩陣均為對(duì)稱矩陣。矩陣中人員排序?yàn)閍1、a2、b、c、d。G1矩陣中第一行第一個(gè)p即表示兩名涉恐人員（a1，a2）的對(duì)應(yīng)聯(lián)系權(quán)值，第一行第二個(gè)p表示（a1，b）的對(duì)應(yīng)權(quán)值，同理可得矩陣其他值的意義。因?yàn)閳D集中所有頂點(diǎn)即所有人員都是唯一的，且在鄰接矩陣中的相對(duì)順序是不變的，所以對(duì)應(yīng)的鄰接矩陣一定是唯一的，對(duì)比子圖時(shí)只需要利用唯一的鄰接矩陣對(duì)比。

4.2 量化分析過(guò)程

設(shè)最小支持度閾值為40%，則頻繁子圖支持度計(jì)數(shù)至少為2（大于等于4*40%，數(shù)值4表示圖集中共有4個(gè)關(guān)聯(lián)圖），最小頂點(diǎn)數(shù)閾值為4。如圖4所示為樣本人員關(guān)聯(lián)圖的子圖模式挖掘過(guò)程，圖中圓括號(hào)內(nèi)數(shù)字表示支持度計(jì)數(shù)。當(dāng)子圖中只有1個(gè)節(jié)點(diǎn)（k=1）時(shí)，只需對(duì)圖集中每個(gè)頂點(diǎn)計(jì)數(shù)，如果候選1-子圖（只有1個(gè)單獨(dú)頂點(diǎn)）計(jì)數(shù)大于或等于2時(shí)，則滿足支持度條件，樣本圖集中有5個(gè)頂點(diǎn)滿足條件。接著在表1中利用頻繁1-子圖兩兩組合，通過(guò)計(jì)數(shù)挖掘出頻繁2-子圖（k=2），每個(gè)子圖中包含2個(gè)頂點(diǎn)和1條邊，共有5個(gè)頻繁2-子圖滿足條件。

從挖掘頻繁k-子圖（k>2）開(kāi)始，基于每?jī)蓚€(gè)頻繁（k-1）-子圖共享“核”（相同的頻繁（k-2）-子圖，對(duì)應(yīng)鄰接矩陣除了最后一行和最后一列完全相同）生成候選k-子圖，然后利用先驗(yàn)原理和支持度計(jì)數(shù)統(tǒng)計(jì)選擇滿足條件的頻繁k-子圖。產(chǎn)生候選k-子圖和頻繁k-子圖的過(guò)程有以下幾種不同的情況。

查閱表1，對(duì)應(yīng)事務(wù)表中（b，c，？）兩個(gè)涉恐人員的邊只有q一種值。當(dāng)取值為q時(shí)，對(duì)應(yīng)所有的3-子圖均為頻繁3-子圖，且滿足支持度計(jì)數(shù)條件，所以g41為頻繁4-子圖。假設(shè)b和c兩個(gè)涉恐人員還有其他的聯(lián)系權(quán)值也滿足頻繁條件，則只取權(quán)值更大的邊。例如（b，c，Q）也滿足條件且Q>q，則b和c之間的邊取Q值。

情況3：存在新增頂點(diǎn)生成邊且不滿足頻繁條件（圖7中的“問(wèn)號(hào)”可取非0值但對(duì)應(yīng)子圖不滿足條件），這時(shí)考慮邊的權(quán)值取0的情況?？紤]合并頻繁3-子圖g31和g33的情況，候選4-子圖如圖7所示。查詢表1發(fā)現(xiàn)（b，d）之間存在邊，取值為p。當(dāng)邊的權(quán)值為p時(shí)，存在非頻繁子圖，不滿足條件，這時(shí)只考慮二者之間沒(méi)有邊的情況，即權(quán)值取0。當(dāng)取0時(shí)，所有3-子圖頻繁，且支持度計(jì)數(shù)滿足條件，所以對(duì)應(yīng)頻繁4-子圖為g42。

最后生成的頻繁子圖即為g41和g42，滿足最小頂點(diǎn)數(shù)要求。本文中的虛擬涉恐人員關(guān)聯(lián)樣本圖集較小，圖中“頂點(diǎn)”和“邊”數(shù)量也較少，所以頻繁子圖結(jié)構(gòu)非常簡(jiǎn)單。實(shí)際反恐情報(bào)關(guān)聯(lián)圖集分析中挖掘出的人員關(guān)聯(lián)會(huì)非常復(fù)雜。同時(shí)，在實(shí)際應(yīng)用中，“邊”的權(quán)值不一定用數(shù)值區(qū)間離散化簡(jiǎn)單表示，還可以根據(jù)不同的聯(lián)系類型標(biāo)記，挖掘出更精細(xì)化、更有參考價(jià)值的涉恐人員關(guān)聯(lián)規(guī)律。

5 結(jié) 語(yǔ)

本文提出了如何利用子圖模式挖掘發(fā)現(xiàn)暴恐案件中恐怖分子的聯(lián)系規(guī)律。經(jīng)典的子圖模式挖掘方法中大多基于頂點(diǎn)增長(zhǎng)或者邊增長(zhǎng)的方式迭代的擴(kuò)展子圖，通過(guò)生成候選子圖然后篩選頻繁子圖的方式實(shí)現(xiàn)。也有一部分方法基于類似頻繁模式樹(shù)的方式采用模式增長(zhǎng)的思路。這些方法中一般要利用一些專門設(shè)計(jì)的算法來(lái)進(jìn)行大量的圖同構(gòu)檢測(cè)，盡量減少這部分計(jì)算的開(kāi)銷。本文從反恐情報(bào)關(guān)聯(lián)圖集分析的目標(biāo)出發(fā)，結(jié)合反恐情報(bào)的特點(diǎn)，在數(shù)據(jù)預(yù)處理時(shí)不但將涉恐人員按照涉恐特征分類，還在每個(gè)分類中對(duì)涉恐人員進(jìn)行風(fēng)險(xiǎn)評(píng)估排序，保證圖集中所有圖頂點(diǎn)唯一且按序排列，進(jìn)而保證每個(gè)圖的鄰接矩陣唯一，避免大量的圖同構(gòu)檢測(cè)。文中涉恐人員之間的關(guān)聯(lián)需要按照各種不同聯(lián)系綜合計(jì)算出數(shù)值權(quán)重，再利用區(qū)間劃分將連續(xù)數(shù)值轉(zhuǎn)換為權(quán)重類別。

參考文獻(xiàn)

[1]王震.“9？11”以來(lái)全球反恐戰(zhàn)略困境探析[J].社會(huì)科學(xué)，2017，（9）：16-28.

[2]騰訊網(wǎng).近年來(lái)新疆分裂勢(shì)力制造的暴恐事件不完全匯總[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]張仲妹，王桂玲，張賽，等.基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦[J].電子科技大學(xué)學(xué)報(bào)， 2016，45（2）：263-269.

[14]李勇男，梅建明.基于頻繁模式樹(shù)的涉恐情報(bào)關(guān)聯(lián)分析[J].情報(bào)科學(xué)，2017，35（9）：141-145，152.

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

[16]李勇男.基于頻繁序列模式挖掘的反恐情報(bào)關(guān)聯(lián)分析[J].情報(bào)理論與實(shí)踐，2018，41（10）：100-104，46.

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

[18]劉振.頻繁子圖挖掘算法的研究與應(yīng)用[D].長(zhǎng)沙：中南大學(xué)，2009：13-14.

[19]侯麗波，王冠.交互式話單數(shù)據(jù)的社會(huì)關(guān)系權(quán)值分析[J].中國(guó)刑警學(xué)院學(xué)報(bào)，2017，（5）：106-112.

[20]付璇.旅店同住分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京大學(xué)，2011.

[21]陳剛，李松巖.對(duì)以異常行為信息為基礎(chǔ)科學(xué)構(gòu)建積分預(yù)警系統(tǒng)的思考[J].北京警察學(xué)院學(xué)報(bào)，2013，（1）：44-47.

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

[23]李勇男.貝葉斯理論在反恐情報(bào)分類分析中的應(yīng)用研究[J].數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn)，2018，2（10）：9-14.

[24]陳鵬，瞿珂，陳剛，等.反恐背景下的個(gè)人特征數(shù)據(jù)構(gòu)成與涉恐個(gè)體的挖掘分析[J].情報(bào)雜志，2018，（4）：38-41，68.

[25]李勇男，梅建明，秦廣軍.反恐情報(bào)分析中的數(shù)據(jù)預(yù)處理研究[J].情報(bào)科學(xué)，2017，35（11）：103-107，113.

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

（責(zé)任編輯：孫國(guó)雷）