余 奇

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

·微機(jī)軟件·

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

余 奇

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

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

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

1 引 言

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

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

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

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

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

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

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

利用它對(duì)初值的不依賴性質(zhì)，帶入任意一組初始數(shù)據(jù)進(jìn)行迭代計(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 社會(huì)網(wǎng)絡(luò)分析（SNA）方法

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

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

3.1 中心性分析

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

3.2 凝聚子群分析

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

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

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

4 改進(jìn)的PageRank算法

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

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

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

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

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

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

5 計(jì)算實(shí)例

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

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

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

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

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

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

6 結(jié)束語

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

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

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

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

［4］姚金隆，王成良.原創(chuàng)優(yōu)先的搜索引擎排序算法［J］.計(jì)算機(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