基于網(wǎng)絡(luò)結(jié)構(gòu)化指標的網(wǎng)絡(luò)節(jié)點重要性評估算法

田由

（廣州杰賽科技股份有限公司，廣東 廣州 510310）

1 引言

隨著移動通信技術(shù)的發(fā)展，移動社交網(wǎng)絡(luò)的數(shù)據(jù)量呈現(xiàn)爆炸式增長?；谕ㄐ乓苿訑?shù)據(jù)的社交關(guān)系分析、社交網(wǎng)絡(luò)的鏈接關(guān)系分析的研究層出不窮。復(fù)雜網(wǎng)絡(luò)的社交關(guān)系以及鏈接關(guān)系預(yù)測都與節(jié)點的重要性具有密切關(guān)系。節(jié)點的重要性評估算法已經(jīng)發(fā)展得相當(dāng)成熟?；诠?jié)點度或者鄰居節(jié)點度的數(shù)量來評估網(wǎng)絡(luò)的節(jié)點重要性[1-3]，這類研究在蛋白質(zhì)網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)以及交通網(wǎng)絡(luò)上具有一定的實證依據(jù)，節(jié)點的度數(shù)越高，其節(jié)點表現(xiàn)越關(guān)鍵；基于介數(shù)的節(jié)點重要性評估最開始是用來個體衡量社會地位的一個指標[4]，其核心思想是經(jīng)過一個節(jié)點的最短路徑越多，則該節(jié)點的影響力越大；Kitsak認為度、介數(shù)的方法并沒有真實反應(yīng)網(wǎng)絡(luò)中節(jié)點的位置，因此提出了一種利用K-shell的方法來衡量節(jié)點的重要性，但是K-shell在一些網(wǎng)絡(luò)如Barabasi-Albert網(wǎng)絡(luò)無法區(qū)分節(jié)點的重要性。

本文考慮到移動社交網(wǎng)絡(luò)的復(fù)雜性，提出一種基于網(wǎng)絡(luò)結(jié)構(gòu)化指標評估移動用戶重要性的算法，該算法的創(chuàng)新性在于：通過劃分社團的方式對龐大、復(fù)雜的網(wǎng)絡(luò)進行分組，通過分組的方式避免了傳統(tǒng)全局性計算算法所面臨的計算時間復(fù)雜度的問題；然后對每一組的網(wǎng)絡(luò)采用聚集系數(shù)和網(wǎng)絡(luò)重要度來評價移動社交網(wǎng)絡(luò)節(jié)點的重要性，聚集系數(shù)能夠反映節(jié)點與節(jié)點之間的緊密程度；網(wǎng)絡(luò)重要度能夠反映節(jié)點對整個社團的重要性貢獻程度，反映了節(jié)點的信息在整個網(wǎng)絡(luò)中的傳播效率。

2 相關(guān)研究

2.1 移動社交網(wǎng)絡(luò)的構(gòu)建

移動用戶社交網(wǎng)絡(luò)可以描述為：存在某種社會關(guān)系或者具有相似興趣的用戶通過移動社交工具進行聯(lián)系所形成的虛擬的社交網(wǎng)絡(luò)[5]。假設(shè)移動用戶的社交網(wǎng)絡(luò)可用無向圖G=(V, E)表示，其中，圖G包含n個節(jié)點和m條邊。V={v1,v2, …, vn}E×E表示移動用戶社交網(wǎng)絡(luò)中移動用戶的集合。E={e1, e2, …, en}表示移動用戶社交網(wǎng)絡(luò)中用戶邊的集合，如果存在邊，則表示用戶之間存在聯(lián)系。

2.2 社團劃分

眾所周知，社交網(wǎng)絡(luò)的每一個節(jié)點代表一個移動用戶，用戶之間通過互相聯(lián)系構(gòu)成了整個移動社交網(wǎng)絡(luò)的結(jié)構(gòu)。網(wǎng)絡(luò)中有些移動用戶之間聯(lián)系較為緊密，有些移動用戶之間的聯(lián)系則較為稀疏。社團劃分把網(wǎng)絡(luò)內(nèi)部聯(lián)系較為緊密的節(jié)點劃分成為多個社團，劃分的最終結(jié)果就是社團內(nèi)部的節(jié)點之間有較為緊密的連接，社團之間的節(jié)點連接則較為稀疏。

目前，劃分社團的方法有很多，根據(jù)重疊性可分為重疊性社團劃分和非重疊性社團劃分。考慮到移動通信的網(wǎng)絡(luò)特點，本文僅研究重疊性社團劃分的算法，包括Palla等人[6]采用派系過濾算法（Clique Percolation Method，CPM）來劃分社團，使得社團劃分更加貼近現(xiàn)實；針對CPM算法效率底下的問題，Lancichinetti等人[7]從網(wǎng)絡(luò)局部結(jié)構(gòu)提出了基于局部擴展思想的重疊社團挖掘算法（Local Fitness Measure，LFM），提升了社團劃分的速度；Ahn[8]提出一種基于邊相似度的指標來衡量節(jié)點之間的緊密度，采用層次聚類算法來實現(xiàn)重疊社團的劃分。本文選取CPM算法來劃分移動社交網(wǎng)絡(luò)的社團，針對該算法的缺陷，采用詞頻-逆文件頻率（Term Frequency-Inverse Document Frequency，TF-IDF）算法對移動社交數(shù)據(jù)進行預(yù)處理，剔除大量的非緊密聯(lián)系的節(jié)點，降低算法的復(fù)雜度。

2.3 節(jié)點重要性評估算法介紹

（1）度的算法

節(jié)點的度定義為節(jié)點的鄰居數(shù)量。通過連接節(jié)點數(shù)量來衡量一個節(jié)點的重要性，在某些網(wǎng)絡(luò)中是簡單而有效的。但是，該方法僅僅考慮了節(jié)點本身的連接數(shù)量，沒有考慮節(jié)點在網(wǎng)絡(luò)中信息傳播的作用以及位置信息，也沒有描述鄰居之間的連接狀態(tài)。因此，該方法并不能很好地描述社交網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)的節(jié)點重要性。

（2）介數(shù)

介數(shù)是衡量一個個體的社會地位的指標，定義為網(wǎng)絡(luò)所有最短路徑中經(jīng)過該節(jié)點的數(shù)量。如果兩個節(jié)點之間的最短路徑經(jīng)過該節(jié)點的數(shù)量越多，那么意味著該節(jié)點擁有越多的社會資源。介數(shù)是一個全局向量，因此其計算時間復(fù)雜度較高，不適合大規(guī)模的網(wǎng)絡(luò)。

（3）聚集系數(shù)

聚集系數(shù)（也稱群聚系數(shù)、集群系數(shù)）可以反映一個節(jié)點的鄰居節(jié)點之間的緊密程度，是衡量網(wǎng)絡(luò)傳遞性的一種度量指標。

Ei表示節(jié)點i與所有相鄰節(jié)點之間相互連接邊的數(shù)量；ki表示節(jié)點i的所有相鄰節(jié)點的數(shù)量。

（4）K-shell算法

K-shell算法采用遞歸的方式剝離網(wǎng)絡(luò)中度數(shù)小于或等于k的節(jié)點，利用該方法獲得一種節(jié)點重要性排序的指標。具體的劃分過程為：

步驟1：從節(jié)點的度數(shù)角度出發(fā)，首先刪除度數(shù)為1的節(jié)點，刪除之后網(wǎng)絡(luò)會出現(xiàn)新的度數(shù)為1的節(jié)點，重復(fù)刪除步驟，直至網(wǎng)絡(luò)中沒有度數(shù)為1的節(jié)點，此時所有被刪除的節(jié)點構(gòu)成第一層，即1-shell，節(jié)點的Ks值等于1。

步驟2：繼續(xù)對度數(shù)為2的節(jié)點重復(fù)上述刪除操作，被刪除的節(jié)點構(gòu)成第二層，即2-shell，得到Ks值等于2的第二層。

步驟3：依此類推，直到網(wǎng)絡(luò)中所有的節(jié)點都被賦予Ks值。

（5）網(wǎng)絡(luò)重要度貢獻

節(jié)點對的效率eij是指節(jié)點vi到vj的距離dij的倒數(shù)。當(dāng)節(jié)點vi與vj是相鄰節(jié)點時，eij的值最大，即eij=1；當(dāng)節(jié)點vi與vj是互不相鄰節(jié)點時，eij∈(0, 1)。節(jié)點對的效率表征了節(jié)點之間的相互作用，如果一個網(wǎng)絡(luò)中存在n個節(jié)點，那么網(wǎng)絡(luò)效率可以表示為：

網(wǎng)絡(luò)效率不能很好地反映某個節(jié)點與其他節(jié)點的相互作用的大小，因此，本文參考相關(guān)研究[9]，采用效率矩陣的節(jié)點重要度貢獻方法，來衡量一個節(jié)點在全網(wǎng)中的重要性。

那么，第i個節(jié)點在整個網(wǎng)絡(luò)的重要性為hi。

3 基于網(wǎng)絡(luò)結(jié)構(gòu)化指標評估移動用戶的重要性

3.1 數(shù)據(jù)預(yù)處理

如果用戶之間采用移動社交工具產(chǎn)生聯(lián)系，那么兩個用戶之間存在一條邊。這條邊的大小可由移動用戶之間的交互次數(shù)來衡量。一旦移動用戶產(chǎn)生一次交互，那么兩個移動用戶之間添加一條邊。但是，根據(jù)這種算法得出的移動用戶關(guān)系難免有點不合常理。眾所周知，一些公共電話、中介電話等一些非重要的群體可能會被納入該社交網(wǎng)絡(luò)中，導(dǎo)致算法的計算復(fù)雜度變高。因此，本文采用TF-IDF值來衡量兩個移動用戶之間的社交關(guān)系強弱。

tfuv代表用戶u和用戶v之間的交互次數(shù)，idfuv代表用戶u和用戶v之間的交互次數(shù)與用戶v和所有用戶之間的交互次數(shù)的占比。采用TF-IDF值來衡量用戶之間的關(guān)系，能夠在一定程度上剔除公共號碼等非重要群體，降低算法的復(fù)雜度。

3.2 采用CPM算法實現(xiàn)社團劃分

在衡量網(wǎng)絡(luò)節(jié)點之前，需要對網(wǎng)絡(luò)進行社團劃分。如此，不僅可以降低衡量節(jié)點重要性的計算復(fù)雜度，還能從社區(qū)內(nèi)部關(guān)系緊密、具有相似結(jié)構(gòu)的節(jié)點中挖掘具有重要位置作用的“核心點”，提高算法的精度。

基于CPM算法的步驟是：

（1）步驟一：采用迭代遞歸的方法來挖掘滿足交互次數(shù)的大小不同的派系。在第一步數(shù)據(jù)預(yù)處理的基礎(chǔ)上，提取移動社交網(wǎng)絡(luò)中交互次數(shù)大于特定值的節(jié)點集合；然后從該集合中隨機一個節(jié)點出發(fā)，找到包含該節(jié)點的大小為g-1的派系并刪除該節(jié)點以及其連接的邊；接著另選一個節(jié)點重復(fù)上述的步驟直至該集合沒有節(jié)點為止。

（2）步驟二：重復(fù)上述的步驟尋找g-2派系，…，k派系，當(dāng)g=k時，算法結(jié)束。

（3）步驟三：對上述的派系建立派系重疊矩陣C，根據(jù)用戶輸入的k值以及派系重疊矩陣構(gòu)建派系的連接矩陣，發(fā)現(xiàn)k-派系社團，實現(xiàn)重疊矩陣的挖掘。

3.3 基于網(wǎng)絡(luò)結(jié)構(gòu)化指標評估社團中的重要節(jié)點

社交網(wǎng)絡(luò)具有傳播信息實效性強、重要節(jié)點影響力深遠的特點[10]，為了充分突出社交網(wǎng)絡(luò)的結(jié)構(gòu)化、層次化，本文對網(wǎng)絡(luò)節(jié)點重要性評估的指標選取聚集系數(shù)以及網(wǎng)絡(luò)重要度兩個指標。結(jié)合節(jié)點的聚集系數(shù)和網(wǎng)絡(luò)重要度考慮，得出一種新的參數(shù)來評估某個節(jié)點在社團中的重要性：

其中，g(Ci)表示聚類系數(shù)的標準化計算，Ci為節(jié)點i的聚類系數(shù)；g(hi)表述網(wǎng)絡(luò)重要度的標準化計算，hi為節(jié)點i的重要度。

3.4 實驗結(jié)果

本文選取某地市的500名移動用戶進行實驗，實驗的目的是通過多種方法對比，來證明本文提出方法的準確率是滿足工程應(yīng)用的。經(jīng)過TF-IDF進行數(shù)據(jù)預(yù)處理后，將剩下的397名移動用戶放進模型中，經(jīng)過一系列的操作，包括社團劃分、重要節(jié)點提取后，得出的實驗結(jié)果如表1所示：

表1 各節(jié)點指標值的排序（選取前10個重要節(jié)點）

從表1可知，針對500名移動用戶的信息發(fā)布、傳播以及節(jié)點的交互次數(shù)進行評分后，得到的Top10的排名是：215-623-599-753-452-750-532-612-933，影響力最高的是代號為215的移動用戶，其次為代號為623的移動用戶，以此類推。本文把各種算法得出的500名移動用戶的影響力進行排名，并把排序分成50個區(qū)間，把各個區(qū)間集合與真實排序?qū)?yīng)區(qū)間集合求交集，形成區(qū)間的準確率。在此基礎(chǔ)上，對每一個區(qū)間的準確率進行加權(quán)平均達到綜合準確率。例如：上表Top10排名顯示第一個區(qū)間的劃分情況，本文方法的區(qū)間內(nèi)的代號與真實排序的區(qū)間代號求交集為{215, 623,599, 753, 452, 750, 532}，那么第一區(qū)間的準確率為7/10=70%。同理，遍歷所有的區(qū)間并求出各區(qū)間的準確率后進行加權(quán)平均得到綜合準確率。各種方法影響力排名的準確率如圖1所示：

圖1 各種方法的準確率對比

從圖1可知，本文提出的方法的準確率比傳統(tǒng)方法的準確率略高。經(jīng)過社團劃分后再進行重要節(jié)點提取的方法在理論上應(yīng)該比介數(shù)、聚類系數(shù)和K-shell的方法計算復(fù)雜度低，但是由于本文樣本數(shù)量的限制，無法從不同數(shù)量級別上進行對比，樣本量過少無法凸顯本文算法的速度優(yōu)越性，這個問題將會在樣本數(shù)量滿足條件的基礎(chǔ)上進一步進行證明。

4 結(jié)束語

本文利用移動通信用戶的社交數(shù)據(jù)構(gòu)建移動社交網(wǎng)絡(luò)，采用一種基于網(wǎng)絡(luò)結(jié)構(gòu)化指標評估移動用戶重要性。實驗證明，結(jié)合節(jié)點的聚集系數(shù)和網(wǎng)絡(luò)重要度考慮的方法比傳統(tǒng)的方法準確率高。由于樣本數(shù)量的條件限制，無法進一步對比本文提出的先劃分社團再提取重要節(jié)點的方法在速度上的優(yōu)越性，這將會在樣本數(shù)量滿足條件的基礎(chǔ)上進一步進行證明。