尹德春, 顧益軍, 張 民

(中國人民公安大學信息技術與網絡安全學院， 北京 100038)

通話網絡的分析度量方法

尹德春, 顧益軍, 張 民

(中國人民公安大學信息技術與網絡安全學院， 北京 100038)

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

通話網絡; 數(shù)據統(tǒng)計分析; 可視化關系圖分析; PageRank

0 引言

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

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

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

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

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

圖1 話單數(shù)據表的結構定義

可以寫出如下SQL語句來完成這個任務：

SELECT FromNumber, ToNumber FROM T

WHERE ToNumber IN

(SELECT DISTINCT FromNumber FROM T);

該SQL查詢的運行結果如圖2所示，5個號碼之間的通話次數(shù)總計為43次。

圖2 SQL查詢的結果

因為Access或Excel無法把這種關聯(lián)關系分析繪制成可視化的結果圖，所以只能人工觀察分析這些號碼之間的通話關系及其頻次。但是，當數(shù)據量大的時候，這樣做就顯然不合適了。因此這類分析需求更適合采用可視化關系圖的分析軟件來完成。

2 可視化關系圖分析法

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

圖3 導入初始數(shù)據后的可視化關系圖

圖4 篩選過濾后的5個節(jié)點之間的關系圖

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

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

3 基于PageRank算法的通話關系定量分析法

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

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

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

圖5 可視化關系圖的簡化表示

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

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

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

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

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

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

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

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

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

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

這樣即使WEB結構中存在終止點，由于(1-β)e/n的存在，V的分量之和永遠不會為0。WEB訪問者總會離開終止點，以一定概率跳轉至非終止點。

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

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

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

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

4 結論

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

需要指出的是，上述3種方法并沒有絕對的優(yōu)劣之分，各自都有適用場合和優(yōu)缺點。在業(yè)務實踐中，單獨只采用某一種分析方法往往是不夠的，需要綜合應用才能得到準確全面的分析結果。

[1] 顧益軍,解易,張培晶. 面向有組織犯罪分析的人際關系網絡節(jié)點重要性評價研究[J].中國人民公安大學學報(自然科學版)，2013(4):66-68.

[2] 顧益軍. 網絡情報獲取與分析[M].北京:中國人民公安大學出版社,2014.

[3] 沃特·德·諾伊，等. 蜘蛛：社會網絡分析技術[M].林楓，譯. 北京:世界圖書出版公司,2012.

[4] 劉勇,杜一.網絡數(shù)據可視化與分析利器：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.

(責任編輯 陳小明)

公安部技術研究計劃項目(2014jsya023)“基于云計算的微警務信息支撐平臺關鍵技術研究”。

尹德春(1979—)，男，吉林人，博士，講師。研究方向為自然語言處理、情報分析。

D035.39