改進PageRank算法在犯罪網(wǎng)絡(luò)分析中的應(yīng)用

余 奇

（國防科學技術(shù)大學理學院，長沙410073）

·微機軟件·

改進PageRank算法在犯罪網(wǎng)絡(luò)分析中的應(yīng)用

余 奇

（國防科學技術(shù)大學理學院，長沙410073）

通過對已知部分嫌疑人的犯罪網(wǎng)絡(luò)模型進行研究，較好解決了如何尋找潛在犯罪危險的問題。在網(wǎng)頁排名算法PageRank的基礎(chǔ)上，結(jié)合SNA（社會網(wǎng)絡(luò)分析）方法，改進了PageRank算法迭代過程，有效評價了與嫌疑人溝通人員的犯罪可能性大小，為解決此類社會網(wǎng)絡(luò)分析問題提出了一個新的思路。

PageRank算法；社會網(wǎng)絡(luò)分析（SNA）；犯罪網(wǎng)絡(luò)分析

1 引 言

Social Network Analysis（SNA）——社會網(wǎng)絡(luò)分析，是研究社會網(wǎng)絡(luò)關(guān)系的一個重要方法。在現(xiàn)今的大數(shù)據(jù)時代，尤其是與個人相關(guān)的電話、網(wǎng)絡(luò)通訊信息量持續(xù)膨脹，SNA面臨更大的挑戰(zhàn)，如何在海量數(shù)據(jù)中獲得有用的信息變得越來越困難。

傳統(tǒng)的SNA方法不能考慮由于網(wǎng)絡(luò)節(jié)點身份的特殊性帶來的對于所關(guān)心問題的影響。比如，如何對已知的一名犯罪嫌疑人的社交網(wǎng)絡(luò)進行分析找出潛在的同伙。解決問題的思路就是結(jié)合傳統(tǒng)的SNA方法與排名算法PageRank，在已知部分嫌疑人的基礎(chǔ)上評價與其溝通人員的犯罪可能性大小。

2 網(wǎng)頁級別（PageRank）算法

PageRank（網(wǎng)頁級別），這是一個經(jīng)典算法，它是Google排名運算法則（排名公式）的一部分，是Google用來標識網(wǎng)頁等級或重要性的一種方法，也是Google用來衡量一個網(wǎng)站好壞的重要標準之一。

它的基本思想就是：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的鏈接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）／C（T），其中PR（T）為T的PageRank值，C（T）為T的出鏈數(shù)，則A的PageRank值為一系列類似于T的頁面重要性得分值的累加。

設(shè)S為與A鄰接節(jié)點全體構(gòu)成的集合，則A的PageRank值可以表示為：

為了完善算法，保證迭代過程收斂，引入了阻尼因子d（d通常被設(shè)置成0.85），定義公式變?yōu)椋?/p>

利用它對初值的不依賴性質(zhì)，帶入任意一組初始數(shù)據(jù)進行迭代計算，最終收斂值便是所求網(wǎng)站A的PageRank值。

PageRank算法雖然能作為網(wǎng)頁排名的重要依據(jù)，但它還有一定的缺陷，其中最為突出的就是主題漂移現(xiàn)象：算法無法區(qū)分網(wǎng)頁中的超鏈接與網(wǎng)頁主題相關(guān)還是不相關(guān)，也就無法判斷網(wǎng)頁內(nèi)容之間的相似相關(guān)性。

3 社會網(wǎng)絡(luò)分析（SNA）方法

網(wǎng)絡(luò)指的是各種關(guān)聯(lián)，而社會網(wǎng)絡(luò)（Social Network）即可簡單地稱為社會關(guān)系所構(gòu)成的結(jié)構(gòu)。社會網(wǎng)絡(luò)分析（Social Network Analysis，SNA）問題起源于物理學中的適應(yīng)性網(wǎng)絡(luò)，通過研究網(wǎng)絡(luò)關(guān)系，有助于把個體間關(guān)系、“微觀”網(wǎng)絡(luò)與大規(guī)模的社會系統(tǒng)的“宏觀”結(jié)構(gòu)結(jié)合起來，通過數(shù)學方法、圖論等定量分析方法，對復雜的社會網(wǎng)絡(luò)進行抽象化分析，得到相應(yīng)結(jié)論。

社會網(wǎng)絡(luò)分析的角度是多方面的，主要包括：中心性分析、凝聚子群分析、核心——邊緣結(jié)構(gòu)分析等等。

3.1 中心性分析

個體中心度（Centrality）度量個體處于網(wǎng)絡(luò)中心的程度，反映該點在網(wǎng)絡(luò)中的重要性程度。因此一個網(wǎng)絡(luò)中有多少個節(jié)點，就有多少個個體中心度。除了計算網(wǎng)絡(luò)中個體的中心度外，還可以計算整個網(wǎng)絡(luò)的集中趨勢，簡稱為中心勢（Centralization）。與個體中心度刻畫的個體特性不同，網(wǎng)絡(luò)中心勢刻畫的是整個網(wǎng)絡(luò)中各個點的差異性程度，因此一個網(wǎng)絡(luò)只有一個中心勢。

3.2 凝聚子群分析

當網(wǎng)絡(luò)中某些行動者之間的關(guān)系特別緊密，以至于結(jié)合成一個次級團體時，這樣的團體在社會網(wǎng)絡(luò)分析中被稱為凝聚子群。分析網(wǎng)絡(luò)中存在多少個這樣的子群，子群內(nèi)部成員之間關(guān)系的特點，子群之間關(guān)系特點，一個子群的成員與另一個子群成員之間的關(guān)系特點等就是凝聚子群分析。由于凝聚子群成員之間的關(guān)系十分緊密，因此也將凝聚子群分析形象地稱為“小團體分析”。

3.3 核心——邊緣結(jié)構(gòu)分析

核心——邊緣（Core—Periphery）結(jié)構(gòu)分析的目的是研究社會網(wǎng)絡(luò)中哪些節(jié)點處于核心地位，哪些節(jié)點處于邊緣地位。核心邊緣結(jié)構(gòu)分析具有較廣的應(yīng)用性，可用于分析精英網(wǎng)絡(luò)、科學引文關(guān)系網(wǎng)絡(luò)以及組織關(guān)系網(wǎng)絡(luò)等多種社會現(xiàn)象中的核心——邊緣結(jié)構(gòu)。

4 改進的PageRank算法

現(xiàn)考慮基于社會網(wǎng)絡(luò)分析下的PageRank算法改進措施。由于算法對于初值并不敏感，只要在迭代過程中引入對于算法的修正即可。

對于一個已知部分犯罪嫌疑人的犯罪團伙構(gòu)成的社交網(wǎng)絡(luò)，要計算一個節(jié)點y的PR值，記與y有聯(lián)系的已知犯罪嫌疑人集合為Sy，其他聯(lián)系人員集合Uy，通訊記錄中與犯罪事實相關(guān)的通訊主題集合Ts，與犯罪事實無關(guān)的通訊主題集合Tu。設(shè)已知犯罪嫌疑人的PR值恒為1，對于其他節(jié)點的PR值，迭代計算式如下：

其中a1（x，y），a2（x，y），a3（x，y），a4（x，y）為迭代系數(shù)，且滿足

由SNA方法，確定各個系數(shù)的表達式如下：

其中，ni分別為各個集合與y之間通訊的次數(shù)，D（y）為節(jié)點y的度，ms（y）為節(jié)點y談?wù)撆c犯罪事實有關(guān)話題的總次數(shù)。

有了迭代關(guān)系式和關(guān)系式中的各項系數(shù)，就可以構(gòu)造迭代算法來計算每個節(jié)點的PageRank值作為該節(jié)點成為一名犯罪嫌疑人的可能性度量。

5 計算實例

計算實例選自2012年美國大學生數(shù)學建模競賽C題。在一家為銀行、信用卡公司開發(fā)軟件的公司中，根據(jù)可靠消息，有部分員工正在密謀盜用公款，損壞公司的利益。經(jīng)過長期跟蹤與調(diào)查，調(diào)查人員已經(jīng)確定策劃陰謀的一些成員，但是為了在逮捕嫌疑人之前找出其它犯罪成員和組織的領(lǐng)導人?，F(xiàn)有數(shù)據(jù)為：公司中83名員工的名字，400條他們之間的信息，以及他們主要談?wù)摰?5個主題。而且，在這83名員工中，已知有7個是已知的嫌疑人，8個是已知的非嫌疑人，在15個主題中，已經(jīng)確定有3個是與犯罪事實相關(guān)的。參照給定的數(shù)據(jù)建立圖論模型。83名員工就相當于一個網(wǎng)絡(luò)中83個節(jié)點，400條他們之間的信息就相當于他們之間所連接的邊，每條邊都有自己所代表的主題，其中有一些主題被認為是可疑的。所以就是要通過分析這些數(shù)據(jù)來確定這些人里面，誰最有可能是嫌疑人。

按照改進的PageRank算法進行分析，最終得到結(jié)果如圖1所示。

圖1 PR值與節(jié)點之間的對應(yīng)關(guān)系圖

最終得到PR值排在前十位的節(jié)點如表1所示。

這樣就得到了未知人員參與犯罪的可能性排名，然后可以依次做進一步的調(diào)查。

表1 PR值排在前十位的節(jié)點

6 結(jié)束語

改進的PageRank算法很好的解決了在已知部分嫌疑人的犯罪網(wǎng)絡(luò)模型中如何尋找潛在犯罪危險的問題，綜合多方面因素，為此類犯罪行為的識別與分析提供了一個新思路。但是，與此同時，作為一個現(xiàn)實問題的數(shù)學模型，其中不免有很多簡化和不足，尤其是像社會關(guān)系這樣的復雜網(wǎng)絡(luò)，在表面信息的背后很有可能隱藏著很多不容忽視的因素。所以犯罪網(wǎng)絡(luò)分析的結(jié)果只能作為一個參考標準，真正的犯罪嫌疑人的確定還依賴于更多更深入的調(diào)查。

［1］王德廣，周志剛，梁旭.PageRank算法的分析及其應(yīng)用［J］.計算機工程，2010，23（22）：291-292.

［2］林聚任.社會網(wǎng)絡(luò)分析［M］.北京：北京師范大學出版社，2009.

［3］姚文琳，劉文.一種基于本體的PageRank算法的改進策略［J］.計算機工程，2009，35（6）：50-51.

［4］姚金隆，王成良.原創(chuàng)優(yōu)先的搜索引擎排序算法［J］.計算機工程，2008，34（18）：85-86.

［5］Xu J，H Chen.Criminal network analysis and visualization［J］.Communications of the ACM，2005，48（6）：100-107.

Application of Im proved PageRank Algorithm in Crim inal Analysis

YU Qi
（College of Science，National University of Defense Technology，ChangSha 410073，China）

Through the study on criminal network model，the problem of digging potential criminal menace is solved preferably.Combining with SNA（social network analysis），the iterative process of PageRank algorithm is improved.As a result，aman who contacts the suspicious is successfully evaluated as a real criminal.

PageRank Algorithm；Social Network Analysis（SNA）；Criminal Analysis

10.3969／j.issn.1002-2279.2014.04.018

TP3

：A

：1002-2279（2014）04-0056-03

余奇（1994-），男，河南信陽人，碩士研究生在讀，主研方向：系統(tǒng)分析與集成。

2013-10-11