通話網(wǎng)絡(luò)的分析度量方法

尹德春, 顧益軍, 張 民

(中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

通話網(wǎng)絡(luò)的分析度量方法

尹德春, 顧益軍, 張 民

(中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

論述了3種通話網(wǎng)絡(luò)分析方法：數(shù)據(jù)統(tǒng)計(jì)分析法、可視化關(guān)系圖分析等、基于PageRank算法的精確度量法。首先簡(jiǎn)要介紹最常見(jiàn)的數(shù)據(jù)統(tǒng)計(jì)分析法，并在一個(gè)簡(jiǎn)單的測(cè)試數(shù)據(jù)集上，給出了應(yīng)用實(shí)例。該方法的優(yōu)點(diǎn)是有利于對(duì)數(shù)據(jù)做精確統(tǒng)計(jì)計(jì)算，但缺點(diǎn)是不便于分析數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，并且分析結(jié)果展現(xiàn)形式也不直觀。然后采用可視化關(guān)系圖分析軟件來(lái)分析實(shí)例中的數(shù)據(jù)，以彌補(bǔ)數(shù)據(jù)統(tǒng)計(jì)分析法的不足，能夠得到更加直觀的定性觀測(cè)分析結(jié)果。最后提出采用PageRank算法對(duì)可視化關(guān)系圖做精確定量計(jì)算，得到各個(gè)節(jié)點(diǎn)的權(quán)值，從而判斷出節(jié)點(diǎn)的重要性。這對(duì)于解決可視化關(guān)系圖結(jié)果過(guò)于復(fù)雜、不利于人工觀察分析的問(wèn)題很有效。

通話網(wǎng)絡(luò); 數(shù)據(jù)統(tǒng)計(jì)分析; 可視化關(guān)系圖分析; PageRank

0 引言

通話網(wǎng)絡(luò)分析在公安業(yè)務(wù)中起著重要作用。在有組織犯罪案件的偵查過(guò)程中，首先需要解決的問(wèn)題就是還原和分析涉案人員的人際網(wǎng)絡(luò)[1]，其中最基礎(chǔ)的工作之一就是分析相關(guān)人員的通話網(wǎng)絡(luò)。

最常見(jiàn)的通話網(wǎng)絡(luò)分析方法是數(shù)據(jù)統(tǒng)計(jì)分析法。該方法的優(yōu)點(diǎn)是有利于對(duì)數(shù)據(jù)做精確統(tǒng)計(jì)計(jì)算，但缺點(diǎn)是對(duì)于節(jié)點(diǎn)關(guān)聯(lián)關(guān)系的分析過(guò)程比較復(fù)雜，并且分析結(jié)果展現(xiàn)形式不直觀。而采用可視化關(guān)系圖分析軟件的方法正好可以彌補(bǔ)這一缺點(diǎn)，能夠得到更加直觀的定性觀測(cè)結(jié)果。但是，有的時(shí)候可視化關(guān)系圖結(jié)果過(guò)于復(fù)雜，不利于人工觀察，或者有時(shí)需要對(duì)可視化關(guān)系圖做節(jié)點(diǎn)重要性的精確定量計(jì)算。因此，本文引入并結(jié)合PageRank算法來(lái)解決這些問(wèn)題，從全局角度完成節(jié)點(diǎn)重要性的分析計(jì)算。下面圍繞這3種方法展開(kāi)詳細(xì)論述。

1 數(shù)據(jù)統(tǒng)計(jì)分析法

數(shù)據(jù)統(tǒng)計(jì)分析[2]是公安信息化應(yīng)用中經(jīng)常采用的方法，是指對(duì)相關(guān)數(shù)據(jù)進(jìn)行整理、分類(lèi)、計(jì)算、分析，進(jìn)而得到統(tǒng)計(jì)結(jié)果的過(guò)程。如可以統(tǒng)計(jì)分析某轄區(qū)內(nèi)某月刑事案件的發(fā)案數(shù)量、數(shù)量的同比和環(huán)比變化、不同類(lèi)型案件的變化、發(fā)案地點(diǎn)和時(shí)間段的分布等等。這些分析結(jié)果以表格或圖表的形式來(lái)展示。常用的圖表形式有曲線圖、柱狀圖、餅圖等。這些圖形化的結(jié)果展示便于觀察和分析。

通常，可以借助Excel或Access等辦公軟件完成這些工作。對(duì)于一般性的簡(jiǎn)單統(tǒng)計(jì)分析需求，這些工具足夠勝任。但是，對(duì)于一些特定的復(fù)雜情況，如統(tǒng)計(jì)各節(jié)點(diǎn)的相關(guān)性并繪制節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系圖，這些常用的統(tǒng)計(jì)分析軟件使用起來(lái)就不太方便，操作難度也很大。如下面的分析需求：在通話話單中找出5個(gè)特定號(hào)碼之間的通話記錄，并繪制出對(duì)應(yīng)的關(guān)聯(lián)關(guān)系圖。假設(shè)已經(jīng)把5個(gè)人的通話數(shù)據(jù)抽取出來(lái)，合并后保存在Access的話單數(shù)據(jù)表T中(實(shí)驗(yàn)數(shù)據(jù)共有1 417條記錄)，T的結(jié)構(gòu)定義如圖1。

圖1 話單數(shù)據(jù)表的結(jié)構(gòu)定義

可以寫(xiě)出如下SQL語(yǔ)句來(lái)完成這個(gè)任務(wù)：

SELECT FromNumber, ToNumber FROM T

WHERE ToNumber IN

(SELECT DISTINCT FromNumber FROM T);

該SQL查詢的運(yùn)行結(jié)果如圖2所示，5個(gè)號(hào)碼之間的通話次數(shù)總計(jì)為43次。

圖2 SQL查詢的結(jié)果

因?yàn)锳ccess或Excel無(wú)法把這種關(guān)聯(lián)關(guān)系分析繪制成可視化的結(jié)果圖，所以只能人工觀察分析這些號(hào)碼之間的通話關(guān)系及其頻次。但是，當(dāng)數(shù)據(jù)量大的時(shí)候，這樣做就顯然不合適了。因此這類(lèi)分析需求更適合采用可視化關(guān)系圖的分析軟件來(lái)完成。

2 可視化關(guān)系圖分析法

可視化的關(guān)系圖分析軟件[2]有很多種，如I2、Pajek[3]、Gephi[4]等。圖3是把表T中數(shù)據(jù)導(dǎo)入到可視化分析軟件之后得到的節(jié)點(diǎn)關(guān)系圖。可以看出，當(dāng)節(jié)點(diǎn)數(shù)較少的時(shí)候，要人工觀察不同節(jié)點(diǎn)之間是否有關(guān)聯(lián)關(guān)系以及計(jì)算其關(guān)聯(lián)頻度，相對(duì)還比較容易。但是當(dāng)節(jié)點(diǎn)數(shù)量巨大的時(shí)候，這個(gè)任務(wù)就會(huì)變得困難。所以需要設(shè)定一些過(guò)濾和篩選條件，對(duì)初始關(guān)系圖進(jìn)行剪枝。圖4是經(jīng)過(guò)篩選過(guò)濾處理之后得到的我們需要的結(jié)果，其中只保留了5個(gè)節(jié)點(diǎn)之間發(fā)生的關(guān)聯(lián)關(guān)系。節(jié)點(diǎn)連線上的數(shù)字表示這兩個(gè)節(jié)點(diǎn)之間的通話頻次。

圖3 導(dǎo)入初始數(shù)據(jù)后的可視化關(guān)系圖

圖4 篩選過(guò)濾后的5個(gè)節(jié)點(diǎn)之間的關(guān)系圖

可以看到，對(duì)于數(shù)據(jù)之間的關(guān)聯(lián)分析問(wèn)題，采用可視化關(guān)系圖分析軟件是比較好的選擇。傳統(tǒng)的基于常用辦公軟件的統(tǒng)計(jì)分析及其圖表展示方法，不善于完成這樣的任務(wù)。

關(guān)系圖分析軟件的處理結(jié)果可以讓我們從直觀上觀察和推斷出一些大致結(jié)論，那么如何證明并做精確計(jì)量呢？或者當(dāng)節(jié)點(diǎn)數(shù)特別多觀測(cè)不容易、或過(guò)濾條件不容易設(shè)置的時(shí)候，除了用過(guò)濾篩選的方法，能否用其他方法計(jì)算出節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系及其權(quán)重指標(biāo)呢？為此，本文嘗試引入在搜索引擎領(lǐng)域得到成功應(yīng)用的PageRank算法[5]，來(lái)解決上述問(wèn)題。

3 基于PageRank算法的通話關(guān)系定量分析法

PageRank算法是搜索引擎對(duì)搜索結(jié)果進(jìn)行排序的理論依據(jù)，它能夠計(jì)算出互聯(lián)網(wǎng)上網(wǎng)頁(yè)節(jié)點(diǎn)的重要性并據(jù)此給出排序結(jié)果。其核心思想是：如果一個(gè)網(wǎng)頁(yè)被很多其他網(wǎng)頁(yè)所鏈接，那么說(shuō)明它受到普遍的“承認(rèn)”和“信賴”。即它的鏈入鏈接越多，它就越權(quán)威、越重要(PageRank值越高)。網(wǎng)頁(yè)權(quán)重高的網(wǎng)站貢獻(xiàn)的鏈接權(quán)重也大。網(wǎng)頁(yè)的重要程度(PageRank值)由指向它的其他網(wǎng)頁(yè)的PageRank值之和決定。

PageRank算法將整個(gè)互聯(lián)網(wǎng)的全部WEB頁(yè)面看做一個(gè)整體，即一個(gè)有向圖，每一個(gè)網(wǎng)頁(yè)是有向圖的一個(gè)節(jié)點(diǎn)，網(wǎng)頁(yè)之間的鏈接關(guān)系看作節(jié)點(diǎn)之間的有向邊。通過(guò)定義一個(gè)WEB隨機(jī)矩陣(Stochastic Matrix of the Web)來(lái)描述網(wǎng)絡(luò)中下一步訪問(wèn)的行為。假設(shè)該隨機(jī)矩陣M中的元素mij表示處在網(wǎng)頁(yè)j的訪問(wèn)者下一步訪問(wèn)網(wǎng)頁(yè)i的概率。如果網(wǎng)頁(yè)j中一共有n個(gè)鏈接，其中一個(gè)鏈向網(wǎng)頁(yè)i，那么有mij=1/n；如果網(wǎng)頁(yè)j中不包含鏈向網(wǎng)頁(yè)i的鏈接，則mij=0。如果網(wǎng)頁(yè)數(shù)目為n，則該矩陣M就是一個(gè)n行n列的方陣。M其實(shí)就是網(wǎng)頁(yè)跳轉(zhuǎn)概率矩陣。

下面為描述方便，把圖4中號(hào)碼用字母代替，如圖5所示。

圖5 可視化關(guān)系圖的簡(jiǎn)化表示

這里，我們把通話網(wǎng)絡(luò)分析問(wèn)題轉(zhuǎn)化為WEB網(wǎng)絡(luò)分析。由于通話網(wǎng)絡(luò)與WEB網(wǎng)絡(luò)不同，所以需要做一些變換處理。仍以圖4的簡(jiǎn)單通話網(wǎng)絡(luò)為例，把圖4中的各個(gè)節(jié)點(diǎn)視作網(wǎng)頁(yè)，通話關(guān)系視作雙向的網(wǎng)頁(yè)鏈接關(guān)系，也就是節(jié)點(diǎn)之間的互相訪問(wèn)關(guān)系。然后，定義一個(gè)WEB隨機(jī)矩陣M。假設(shè)M中的元素mij表示節(jié)點(diǎn)j訪問(wèn)節(jié)點(diǎn)i的概率。如果節(jié)點(diǎn)j一共有n次通話記錄，其中與節(jié)點(diǎn)i的通話次數(shù)是ni次，那么有mij=ni/n；如果節(jié)點(diǎn)j沒(méi)有與節(jié)點(diǎn)i通話，他們之間沒(méi)有鏈接關(guān)系，則mij=0。此例中，節(jié)點(diǎn)數(shù)目為5，則矩陣M就是一個(gè)維度為5的方陣。由圖4構(gòu)造出的矩陣M如下。

矩陣M的第一列表示節(jié)點(diǎn)A分別以0、1、0、0、0的概率訪問(wèn)節(jié)點(diǎn)A、B、C、D、E；第二列表示節(jié)點(diǎn)B分別以12/41、0、29/41、0、0的概率訪問(wèn)節(jié)點(diǎn)A、B、C、D、E；以此類(lèi)推。

定義n維向量V=[p1,p2,…,pj,…,pn]T為訪問(wèn)者位置的概率分布，滿足p1+p2+…+pj+…+pn=1。pj表示訪問(wèn)者處于節(jié)點(diǎn)j的概率。如果訪問(wèn)者由節(jié)點(diǎn)j進(jìn)入節(jié)點(diǎn)i，其概率為pi=mij*pj。V其實(shí)就是位置概率矩陣。假設(shè)初始的概率分布狀態(tài)為V0，隨機(jī)矩陣為M，則第一步轉(zhuǎn)移之后訪問(wèn)者的概率分布向量為V1=MV0，第二步轉(zhuǎn)移之后的概率分布向量為V2=MV1=M(MV0)，以此類(lèi)推，經(jīng)過(guò)i次左乘M，訪問(wèn)者經(jīng)過(guò)i步轉(zhuǎn)移之后的位置概率分布向量為Vi=MVi-1。

PageRank模型將網(wǎng)頁(yè)瀏覽作為一個(gè)隨機(jī)過(guò)程，將一個(gè)網(wǎng)頁(yè)瀏覽者的隨機(jī)瀏覽WEB的行為作為馬爾可夫鏈中的一個(gè)狀態(tài)轉(zhuǎn)移。每張網(wǎng)頁(yè)或者網(wǎng)絡(luò)圖中的每個(gè)節(jié)點(diǎn)都被認(rèn)為是一個(gè)狀態(tài)，一個(gè)超鏈接就是從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的帶有一定概率的轉(zhuǎn)移。根據(jù)馬爾可夫鏈的各態(tài)歷經(jīng)定理，可知隨機(jī)矩陣M定義的有限馬爾可夫鏈具有唯一的靜態(tài)概率分布。這意味著經(jīng)過(guò)一系列的狀態(tài)轉(zhuǎn)移之后，不管所選擇的初始狀態(tài)V0是什么，V都會(huì)收斂到一個(gè)穩(wěn)定的狀態(tài)概率向量V=M*V，它表示的是長(zhǎng)時(shí)間后訪問(wèn)者最可能處于的位置，也就是我們要求的各個(gè)節(jié)點(diǎn)的PageRank值。

迭代計(jì)算PageRank值的方法如下：首先根據(jù)節(jié)點(diǎn)間的鏈接關(guān)系，構(gòu)建隨機(jī)矩陣M，定義初始概率分布向量V0=[p1,p2,…,pj,…,pn]T，滿足p1+p2+…+pj+…+pn=1。比如可以初始化為V0=[1/n,1/n,…,1/n]T，此時(shí)各節(jié)點(diǎn)具有同等的概率或重要性；或者隨機(jī)分配總和為1的n個(gè)實(shí)數(shù)也可以。然后，用M不斷左乘V，讓概率(重要性)在節(jié)點(diǎn)間隨機(jī)游走，直到前后兩輪迭代產(chǎn)生的結(jié)果向量相差很小(小于給定的閾值)的時(shí)候停止。

如對(duì)圖4對(duì)應(yīng)的矩陣M進(jìn)行上述迭代運(yùn)算。初始向量設(shè)置為V0=[1/5,1/5,1/5,1/5,1/5]T，通過(guò)不斷左乘隨機(jī)矩陣M，得到以下結(jié)果(論文中小數(shù)點(diǎn)后只保留3位，做了四舍五入處理)：

當(dāng)?shù)螖?shù)i=20，V收斂到[0.112, 0.572, 0.288, 0.014, 0.014]T。也就是說(shuō)，此后無(wú)論繼續(xù)左乘M多少次，V都不再變化。V的每一行取值分別是節(jié)點(diǎn)A、B、C、D、E的PageRank值。其中，節(jié)點(diǎn)B的PageRank值最大，節(jié)點(diǎn)C次大，節(jié)點(diǎn)D和E最小。

由于真實(shí)的WEB結(jié)構(gòu)中PageRank計(jì)算存在“終止點(diǎn)”和“采集器陷阱”問(wèn)題[2]，所以經(jīng)常采用改進(jìn)后的PageRank算法“抽稅法”進(jìn)行計(jì)算。在該方法中，給每一個(gè)頁(yè)面增加指向所有頁(yè)面的鏈接，每個(gè)鏈接都賦予一個(gè)由參數(shù)β控制的轉(zhuǎn)移概率。這種改進(jìn)的PageRank模型中，在任何一個(gè)網(wǎng)頁(yè)上，一個(gè)隨機(jī)訪問(wèn)者將有兩種選擇：(1)隨機(jī)點(diǎn)擊一個(gè)鏈出鏈接繼續(xù)瀏覽，此時(shí)的概率為β(β取值通常在0.8到0.9之間)；(2)不點(diǎn)擊鏈接，而是直接打開(kāi)另一個(gè)隨機(jī)網(wǎng)頁(yè)，此時(shí)的概率是1-β，也就是這里所說(shuō)的“稅”。改進(jìn)的PageRank模型為：

V′=βMV+(1-β)e/n

其中，n是WEB圖中所有節(jié)點(diǎn)的數(shù)目；e是一個(gè)n維單位向量，它的所有分量都為1。

這樣即使WEB結(jié)構(gòu)中存在終止點(diǎn)，由于(1-β)e/n的存在，V的分量之和永遠(yuǎn)不會(huì)為0。WEB訪問(wèn)者總會(huì)離開(kāi)終止點(diǎn)，以一定概率跳轉(zhuǎn)至非終止點(diǎn)。

下面采用“抽稅法”來(lái)重新計(jì)算圖4中各節(jié)點(diǎn)的PageRank值。取β=0.85，初始向量為V0=[1/5,1/5,1/5,1/5,1/5]T，迭代過(guò)程中向量V′和V差值的閾值設(shè)置為0.000 000 000 1。在經(jīng)過(guò)134次迭代后，V′和V的差值小于設(shè)定閾值，V收斂。迭代計(jì)算過(guò)程中V的取值變化如下(論文中小數(shù)點(diǎn)后只保留3位，做了四舍五入處理)：

迭代134次后V收斂到[0.137, 0.429, 0.355, 0.040, 0.040]T。V的每一行取值分別是節(jié)點(diǎn)A、B、C、D、E的PageRank值。其中，節(jié)點(diǎn)B的PageRank值最大，節(jié)點(diǎn)C次大，節(jié)點(diǎn)D和E最小。

可以看到，無(wú)論是采用原始PageRank算法還是改進(jìn)后的“抽稅法”計(jì)算，5個(gè)節(jié)點(diǎn)PageRank值的大小順序都是不變的，重要性排序依次為B>C>A>D=E。

以上是使用PageRank及其改進(jìn)算法分析簡(jiǎn)單通話數(shù)據(jù)的過(guò)程。通常，在通話網(wǎng)絡(luò)分析中，要面對(duì)和解決的更一般問(wèn)題是：在大數(shù)據(jù)量環(huán)境下，節(jié)點(diǎn)數(shù)非常多的時(shí)候，要求分析所有通話數(shù)據(jù)，判斷出各個(gè)節(jié)點(diǎn)的重要等級(jí)，找出相對(duì)重要的節(jié)點(diǎn)。對(duì)于此類(lèi)問(wèn)題可以直接用PageRank算法或其改進(jìn)后的“抽稅法”計(jì)算全部節(jié)點(diǎn)的重要性指標(biāo)值，然后由大到小排序輸出即可。

4 結(jié)論

本文初步總結(jié)和探討了通話網(wǎng)絡(luò)的分析度量方法，并重點(diǎn)研究了如何將原本用于WEB網(wǎng)頁(yè)搜索排序的PageRank算法應(yīng)用于通話網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的計(jì)算，給出了推理和計(jì)算過(guò)程，得到的實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的正確性和有效性。

需要指出的是，上述3種方法并沒(méi)有絕對(duì)的優(yōu)劣之分，各自都有適用場(chǎng)合和優(yōu)缺點(diǎn)。在業(yè)務(wù)實(shí)踐中，單獨(dú)只采用某一種分析方法往往是不夠的，需要綜合應(yīng)用才能得到準(zhǔn)確全面的分析結(jié)果。

[1] 顧益軍,解易,張培晶. 面向有組織犯罪分析的人際關(guān)系網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)價(jià)研究[J].中國(guó)人民公安大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013(4):66-68.

[2] 顧益軍. 網(wǎng)絡(luò)情報(bào)獲取與分析[M].北京:中國(guó)人民公安大學(xué)出版社,2014.

[3] 沃特·德·諾伊，等. 蜘蛛：社會(huì)網(wǎng)絡(luò)分析技術(shù)[M].林楓，譯. 北京:世界圖書(shū)出版公司,2012.

[4] 劉勇,杜一.網(wǎng)絡(luò)數(shù)據(jù)可視化與分析利器：Gephi 中文教程[M].北京:電子工業(yè)出版社,2017.

[5] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[C]∥International Conference on World Wide Web, 1998: 107-117.

(責(zé)任編輯 陳小明)

公安部技術(shù)研究計(jì)劃項(xiàng)目(2014jsya023)“基于云計(jì)算的微警務(wù)信息支撐平臺(tái)關(guān)鍵技術(shù)研究”。

尹德春(1979—)，男，吉林人，博士，講師。研究方向?yàn)樽匀徽Z(yǔ)言處理、情報(bào)分析。

D035.39