改進PageRank算法在犯罪網絡分析中的應用

余 奇

（國防科學技術大學理學院，長沙410073）

·微機軟件·

改進PageRank算法在犯罪網絡分析中的應用

余 奇

（國防科學技術大學理學院，長沙410073）

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

PageRank算法；社會網絡分析（SNA）；犯罪網絡分析

1 引 言

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

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

2 網頁級別（PageRank）算法

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

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

設S為與A鄰接節點全體構成的集合，則A的PageRank值可以表示為：

為了完善算法，保證迭代過程收斂，引入了阻尼因子d（d通常被設置成0.85），定義公式變為：

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

PageRank算法雖然能作為網頁排名的重要依據，但它還有一定的缺陷，其中最為突出的就是主題漂移現象：算法無法區分網頁中的超鏈接與網頁主題相關還是不相關，也就無法判斷網頁內容之間的相似相關性。

3 社會網絡分析（SNA）方法

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

社會網絡分析的角度是多方面的，主要包括：中心性分析、凝聚子群分析、核心——邊緣結構分析等等。

3.1 中心性分析

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

3.2 凝聚子群分析

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

3.3 核心——邊緣結構分析

核心——邊緣（Core—Periphery）結構分析的目的是研究社會網絡中哪些節點處于核心地位，哪些節點處于邊緣地位。核心邊緣結構分析具有較廣的應用性，可用于分析精英網絡、科學引文關系網絡以及組織關系網絡等多種社會現象中的核心——邊緣結構。

4 改進的PageRank算法

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

對于一個已知部分犯罪嫌疑人的犯罪團伙構成的社交網絡，要計算一個節點y的PR值，記與y有聯系的已知犯罪嫌疑人集合為Sy，其他聯系人員集合Uy，通訊記錄中與犯罪事實相關的通訊主題集合Ts，與犯罪事實無關的通訊主題集合Tu。設已知犯罪嫌疑人的PR值恒為1，對于其他節點的PR值，迭代計算式如下：

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

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

其中，ni分別為各個集合與y之間通訊的次數，D（y）為節點y的度，ms（y）為節點y談論與犯罪事實有關話題的總次數。

有了迭代關系式和關系式中的各項系數，就可以構造迭代算法來計算每個節點的PageRank值作為該節點成為一名犯罪嫌疑人的可能性度量。

5 計算實例

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

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

圖1 PR值與節點之間的對應關系圖

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

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

表1 PR值排在前十位的節點

6 結束語

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

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

［2］林聚任.社會網絡分析［M］.北京：北京師范大學出版社，2009.

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

［4］姚金隆，王成良.原創優先的搜索引擎排序算法［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-），男，河南信陽人，碩士研究生在讀，主研方向：系統分析與集成。

2013-10-11