田由

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

1 引言

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

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

2 相關(guān)研究

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

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

2.2 社團(tuán)劃分

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

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

2.3 節(jié)點(diǎn)重要性評(píng)估算法介紹

（1）度的算法

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

（2）介數(shù)

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

（3）聚集系數(shù)

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

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

（4）K-shell算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于CPM算法的步驟是：

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

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

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

3.3 基于網(wǎng)絡(luò)結(jié)構(gòu)化指標(biāo)評(píng)估社團(tuán)中的重要節(jié)點(diǎn)

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

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

3.4 實(shí)驗(yàn)結(jié)果

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

表1 各節(jié)點(diǎn)指標(biāo)值的排序（選取前10個(gè)重要節(jié)點(diǎn)）

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

圖1 各種方法的準(zhǔn)確率對(duì)比

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

4 結(jié)束語(yǔ)

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