代 翔

(中國西南電子技術(shù)研究所，成都610036)

?

復(fù)雜通信網(wǎng)絡(luò)的地理位置聚集性社團發(fā)現(xiàn)和可視化*

代 翔**

(中國西南電子技術(shù)研究所，成都610036)

針對以通信網(wǎng)絡(luò)為代表的一類復(fù)雜網(wǎng)絡(luò)地理位置信息的聚集性與網(wǎng)絡(luò)結(jié)構(gòu)一定程度上的正相關(guān)性，探討了將地理位置信息帶入特定的復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)和可視化任務(wù)中，改進(jìn)傳統(tǒng)的標(biāo)號傳播和力導(dǎo)引算法，提前進(jìn)行網(wǎng)絡(luò)的地理位置聚類分析，并對標(biāo)號傳播的和力導(dǎo)引的迭代過程引入基于地理位置的限制性條件，避免無意義的振蕩。實驗證明，提出的方法既可以加快社團發(fā)現(xiàn)和可視化算法的收斂速度，也可以通過地理位置對社團分布的影響提高快速社團發(fā)現(xiàn)算法的性能。針對存在地理位置聚集性的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)，該方法無論在收斂時間還是社團發(fā)現(xiàn)結(jié)果(Q值)上都有較大提升。

復(fù)雜通信網(wǎng)絡(luò)；社團發(fā)現(xiàn)；地理位置；標(biāo)號傳播；力導(dǎo)引

1 引 言

現(xiàn)實世界中存在著大量的網(wǎng)絡(luò)結(jié)構(gòu)，例如人際關(guān)系網(wǎng)絡(luò)、工作協(xié)作網(wǎng)絡(luò)、傳染病傳播網(wǎng)絡(luò)以及新近產(chǎn)生的通信網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等。由于這些結(jié)構(gòu)有著共同的“自組織、自相似、吸引子、小世界、無標(biāo)度”等復(fù)雜特性，所以被統(tǒng)稱為復(fù)雜網(wǎng)絡(luò)[1]。社團發(fā)現(xiàn)是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)以及可視化的重要基礎(chǔ)性工作[2]。對于大規(guī)模復(fù)雜網(wǎng)絡(luò)，通過社團發(fā)現(xiàn)，以及可視化標(biāo)記，能夠較好地幫助使用者了解復(fù)雜關(guān)系網(wǎng)絡(luò)的社團分布情況，對分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測復(fù)雜網(wǎng)絡(luò)的行為都有十分重要的意義[3]。

傳統(tǒng)的社團發(fā)現(xiàn)算法大多著眼于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)本身，僅僅拓?fù)潢P(guān)系，而忽略了節(jié)點的特征，如地理位置信息，使得傳統(tǒng)算法在不夠高效的同時，不能有效地反映節(jié)點的用戶群的地理聚集性。而在以通信網(wǎng)絡(luò)為代表的復(fù)雜網(wǎng)絡(luò)中，社團的地理聚集性顯而易見。針對這一問題，本文提出一種基于地理位置信息的可視化復(fù)雜網(wǎng)絡(luò)快速社團發(fā)現(xiàn)算法，將用戶的地理位置等用戶群信息加入社團發(fā)現(xiàn)的過程，并在可視化的網(wǎng)絡(luò)展示中進(jìn)行標(biāo)記，給使用者提供一種基于關(guān)系社團以及用戶群的社團分布展示。這種社團分布更能利用節(jié)點在地理位置和關(guān)系上的地位，輔助節(jié)點影響力分析。

2 復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)

2.1 復(fù)雜網(wǎng)絡(luò)中的社團

網(wǎng)絡(luò)是由節(jié)點(node)和邊(edge)組成的拓?fù)浣Y(jié)構(gòu)，被廣泛用于表示各種現(xiàn)實世界中的交互系統(tǒng)，例如食物鏈、人際關(guān)系等。當(dāng)所表示的系統(tǒng)節(jié)點數(shù)據(jù)巨大，節(jié)點間關(guān)系錯綜復(fù)雜時，這樣的網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)。盡管節(jié)點間關(guān)系復(fù)雜，但是大多數(shù)情況下卻并不完全隨機，而是滿足某些特定的規(guī)律，如無尺度、小世界等。

社團是指一組相互之間關(guān)系緊密，而與外界關(guān)系疏遠(yuǎn)的節(jié)點的集合。在復(fù)雜網(wǎng)絡(luò)中社團的發(fā)現(xiàn)有著十分重要的意義，例如：能夠找到一群愛好相似的用戶，或者是聯(lián)系緊密的犯罪團體。

模塊度函數(shù)是一個定量描述網(wǎng)絡(luò)中社團的數(shù)學(xué)工具。如果網(wǎng)絡(luò)的一組社團劃分中所有內(nèi)部的連線所占的比例越大，則該社團劃分越好。但是，為了懲罰大社團的優(yōu)勢，所以需要與一個隨機網(wǎng)絡(luò)中所有社團內(nèi)部節(jié)點的連線數(shù)所占比例期望值相減，而得到的這個差值就是網(wǎng)絡(luò)社團劃分的模塊度，計算這一數(shù)值的函數(shù)稱為模塊度函數(shù)。令ci為節(jié)點i分配的社團，社團內(nèi)部節(jié)點的連線所占的比例可以表示為

(1)

式中：Aij表示i、j兩點間的連線數(shù)，有連線則為1，否則為0；δ(ci,cj)為δ函數(shù)，即ci=cj時值為1，反之為0；m表示網(wǎng)絡(luò)中連線的數(shù)量。在隨機網(wǎng)絡(luò)中，i、j兩節(jié)點相連的概率為(kikj)/2m，ki為節(jié)點i的度(degree)。所以，描述社團劃分模塊化水平的Q函數(shù)為

(2)

如果對一個復(fù)雜網(wǎng)絡(luò)進(jìn)行隨機劃分，則模塊度Q取值應(yīng)接近于0。當(dāng)社團劃分越好時，Q的取值越大，但是通常不可能達(dá)到理論上的最大值1,一般認(rèn)為現(xiàn)實世界中的社團模塊度Q值在0.3～0.7之間。

2.2 傳統(tǒng)的社團發(fā)現(xiàn)算法

由于社團的判定依賴于模塊度的計算，所以通過計算模塊度來進(jìn)行社團發(fā)現(xiàn)便成為了最顯而易見的方法?；舅悸肥歉F舉所有的可能子社團組合的方式，選擇其中模塊度最大的那一種作為下一步迭代的社團組合，反復(fù)迭代直到模塊度不再增加為止。這種方法理論上并不能得到最佳的社團劃分，而是會陷入局部最優(yōu)解。更大的問題是這一計算求解的過程是一個非決定性多項式時間完全問題，不能應(yīng)用于規(guī)模較大的網(wǎng)絡(luò)。近年來研究人員對模塊度優(yōu)化算法進(jìn)行了一系列的改進(jìn)，引入社團對層次性和重疊性的考量以及各種啟發(fā)性的近似算法，使其在計算復(fù)雜度問題上都有不小的改進(jìn)[2]。

研究人員發(fā)現(xiàn)網(wǎng)絡(luò)社團總是存在著某種層次結(jié)構(gòu)，例如一個大社團包含一系列的小社團，這種特性稱為社團的層次性，從而設(shè)計了一系列的層次性社團發(fā)現(xiàn)算法[4]。具體地，層次化的算法又分為自上而下的分裂算法和自下而上的凝聚算法兩種。較早出現(xiàn)的文獻(xiàn)中大多采用的是分裂算法，但是其并沒有根本上的解決計算復(fù)雜度，以及無法識別小社團的分辨率問題。凝聚算法由于是自下而上的，天然的能夠應(yīng)對分辨率問題。本文所改進(jìn)的標(biāo)號傳播算法[5]就是一類凝聚算法。但是真實的社團并不一定存在層次結(jié)構(gòu)，在這種情況下層次方法所產(chǎn)的偽層次反而會帶來各種問題。

傳統(tǒng)的社團發(fā)現(xiàn)算法僅僅考慮復(fù)雜網(wǎng)絡(luò)本身的結(jié)構(gòu)，在解決實際問題時，總是試圖將節(jié)點、邊的各種屬性先抽取并建模到復(fù)雜網(wǎng)絡(luò)中，再進(jìn)行結(jié)構(gòu)的分析和社團的發(fā)現(xiàn)，這種思路雖然有較好的普適性，但是無形中極大浪費了實際系統(tǒng)中已有的知識，甚至可能造成已知社團結(jié)構(gòu)的丟失等問題。

2.3 通信網(wǎng)絡(luò)中的社團與地理位置聚集性

通信網(wǎng)絡(luò)中的地理位置聚集性和社團的關(guān)系是顯而易見，無論是從實際經(jīng)驗出發(fā)(與本地親友交往的頻次遠(yuǎn)高于外地親友)，還是研究人員的定量研究成果[6-8]，都肯定了這一點。文獻(xiàn)[6]從推薦系統(tǒng)的角度出發(fā)，指出歷史行為軌跡越相近的人，其在興趣方面的相似度越高，從而越有可能建立起某種關(guān)聯(lián)關(guān)系?；谶@一點，文獻(xiàn)[7]通過地理位置的相似性，幫助用戶建立交互關(guān)系，即社群關(guān)系。其背后的邏輯與本文非常類似：都是通過地理位置信息來輔助建立線上-線下社群的映射關(guān)系。文獻(xiàn)[8]系統(tǒng)性地講述了通信網(wǎng)絡(luò)中的地理位置聚集性問題，不過是以環(huán)保節(jié)能作為出發(fā)點進(jìn)行研究。

簡單地將線下的地理位置聚團信息映射為社團關(guān)系顯然也是不合理的。現(xiàn)代人的生活經(jīng)驗是，雖然我有大量的距離較近的親密好友，但是住在隔壁的鄰居卻大多并不認(rèn)識。即便是在社區(qū)文化更加發(fā)達(dá)的美國，與鄰居間的通信行為占比也不到5%[9]。從復(fù)雜網(wǎng)絡(luò)的層次性特性來說，地理位置聚團信息可以在某種程度上看成是社團關(guān)系的上層關(guān)系。

3 基于地理位置的社團發(fā)現(xiàn)和可視化

基于上述認(rèn)識，在對通信網(wǎng)絡(luò)這一特殊的包含有顯著地理信息聚集性的復(fù)雜網(wǎng)絡(luò)進(jìn)行分析時，可以利用其地理信息聚集性設(shè)計一個更加快速和高效的社團發(fā)現(xiàn)算法，基本思路是：先對通信網(wǎng)絡(luò)進(jìn)行地理位置聚團分析，形成群組劃分的初始信息，再通過一個帶一定限制性的算法來進(jìn)行社團發(fā)現(xiàn)，從而達(dá)到利用地理位置信息進(jìn)行快速啟動和避免算法反復(fù)迭代的目的。具體地，我們可以通過改造標(biāo)號傳播算法來實現(xiàn)這一思想。

3.1 基于地理位置聚類的快速社團發(fā)現(xiàn)

地理位置信息作為一個二維平面信息，幾乎所有的聚類算法都可以用來對其進(jìn)行聚團分析，常見的算法有K均值聚類(K-means)、凝聚型的層次聚類、模糊聚類的模糊C均值聚類(Fuzzy C-means,FCM)以及基于神經(jīng)網(wǎng)絡(luò)的聚類等。由于這部分內(nèi)容并非本文重點，我們不對上述算法進(jìn)行過多的分析和比較，只是通過經(jīng)驗以及一系列的對比實驗，選定了吸引子傳播(Affinity Propagation,AP)聚類算法作為地理位置聚團分析的聚類算法[10]。與K-means等最常見的聚類算法相比，AP算法最大的好處是不需要指定聚類的個數(shù)，而是通過優(yōu)先權(quán)(Preference)和阻尼因子(Damping factor)來控制最終聚類的大小，從而能夠很容易地對地理位置聚團的大小進(jìn)行調(diào)節(jié)。另一方面，AP算法對初始值不敏感，即使多次執(zhí)行AP聚類算法得到的結(jié)果完全一樣，這樣的好處是算法的可重復(fù)性較高。由于地理位置聚團只是本文工作的第一個步驟，所以可重復(fù)性顯得尤為重要。

接下來的社團發(fā)現(xiàn)過程，我們采用一個改進(jìn)的標(biāo)號傳播算法來進(jìn)行。標(biāo)號傳播算法時間復(fù)雜度僅為O(n)，十分適合用于大型網(wǎng)絡(luò)的社團發(fā)現(xiàn)。另一方面，標(biāo)號傳播算法的執(zhí)行過程伴隨著節(jié)點顏色的連續(xù)變化，十分適用于可視化的系統(tǒng)。但是，標(biāo)號傳播算法是一個自下而上的凝聚算法。為了利用地理位置聚團分析的結(jié)果，我們引入了色譜的概念，重新定義了標(biāo)號傳播的過程。

具體地，從一個通信網(wǎng)絡(luò)的數(shù)據(jù)集出發(fā)，進(jìn)行地理位置聚類和社團發(fā)現(xiàn)的算法流程如下：

Step 1 建立通信關(guān)系網(wǎng)絡(luò)。網(wǎng)絡(luò)中節(jié)點為每個通信活動的參與者(手機用戶)，如果節(jié)點間有通信行為，則存在一條邊，邊的權(quán)重為通信行為的次數(shù)。

Step 2 提取通信網(wǎng)絡(luò)中的位置信息。本文所針對的是移動通信網(wǎng)絡(luò)數(shù)據(jù)，所以可以根據(jù)每次呼叫的基站編號數(shù)據(jù)來判斷節(jié)點的大致位置。提取之后，對每次呼叫行為記錄節(jié)點之間的距離，如下：

distance(i,j)=mincall_distance(i,j)，

(3)

即節(jié)點間的距離定義為用戶間呼叫的最小距離。

Step 3 將上述定義的節(jié)點間距離distance(i,j)代入到AP聚類算法中，進(jìn)行地理位置聚團分析。過程中需要通過調(diào)整優(yōu)先權(quán)和阻尼因子的取值來控制最終聚類的大小，實際的應(yīng)用場景對應(yīng)的取值我們會在實驗中具體給出。完成地理位置聚團分析后，每個節(jié)點根據(jù)結(jié)果標(biāo)記其所屬聚團號碼。

至此，完成節(jié)點的地理位置聚類，根據(jù)地理位置聚類的結(jié)果分配節(jié)點的初始著色，進(jìn)行受限制的標(biāo)號傳播。

Step 4 采用HSB(Hue,Saturation,Brightness)模型對每個節(jié)點進(jìn)行著色。

Step4-2 對聚團中的每個節(jié)點，通過一個取值在[s,100%]的隨機數(shù)作為它的S值。其中s為算法的逃逸系數(shù)，如果s取值越大，則最終的社團發(fā)現(xiàn)結(jié)果越依賴于前期的聚團結(jié)果了；如果s取值越小，則前期的聚團結(jié)果對最終結(jié)果的影響越不明顯。

Step4-3 節(jié)點初始著色的H值即為其所屬聚團的H值，節(jié)點的V值簡單設(shè)定為100%。至此完成節(jié)點初始著色。

Step5 顏色相同的節(jié)點分配一個社團號。

Step6 遍歷每個節(jié)點i，計算每個節(jié)點vi與所有相鄰社群gk之間的顏色契合度，節(jié)點和社群的顏色契合度定義如下：

(4)

式中：vj為社群gk中的節(jié)點，n為上一次迭代過程中改變了節(jié)點的社群的個數(shù)，N為復(fù)雜網(wǎng)絡(luò)中社群的總個數(shù)，n初始值設(shè)為N。

Step 7 將節(jié)點i的社團號更改為最相關(guān)社團的社團號，如果相關(guān)性最高的有多個，則保持當(dāng)前的社團號不變。

Step 8 遍歷一遍后，若此時網(wǎng)絡(luò)沒有達(dá)到穩(wěn)定(本次遍歷有足夠少的節(jié)點改變了社團號)，則重新進(jìn)行Step 5～7;否則，社團發(fā)現(xiàn)完成。

算法的總體流程非常簡單，如圖1所示，分為地理信息聚類、初始著色、標(biāo)號傳播3個步驟。其中依賴于地理信息聚類結(jié)果的初始著色是本算法的核心，通過這個在HSB空間上的初始著色算法的設(shè)計，將地理聚類的信息傳遞到了標(biāo)號傳播中。加入的逃逸系數(shù)s是控制最終算法執(zhí)行結(jié)果的一個重要手段，在具體的執(zhí)行過程中根據(jù)網(wǎng)絡(luò)的地理聚集性的強弱來對s的取值進(jìn)行設(shè)定。之所以采用HSB空間是考慮到接下來的可視化效果，色相的相似性更容易被人眼接收和感知，從而更好地理解標(biāo)號傳播的迭代過程；而明度的統(tǒng)一使得每個節(jié)點的重要性都能夠相同被可視化表示。

圖1 社團發(fā)現(xiàn)算法總體流程

Fig.1 Flow chart of group detecting algorithm

顏色契合度的加入是避免振蕩的一個重要手段，而容易陷入反復(fù)無意義的振蕩是標(biāo)號傳播算法最大的缺陷之一。標(biāo)號傳播算法雖然時間復(fù)雜度為O(n)，但是隨著網(wǎng)絡(luò)的復(fù)雜性增加，標(biāo)號傳播的振蕩次數(shù)會顯著增長，反映出來在實際應(yīng)用中的性能下降。本算法基于標(biāo)號傳播算法，時間復(fù)雜度與傳統(tǒng)的標(biāo)號傳播算法相同，都是O(n)。但是，由于通過前期的地理位置聚類以及色譜的標(biāo)注，再加上修改了標(biāo)號傳播的迭代方法，節(jié)點只會加入最“契合”的群組，而不是隨意振蕩，從而使得迭代次數(shù)相對于傳統(tǒng)的標(biāo)號傳播算法有很大的下降，很大程度上避免了標(biāo)號傳播算法中的節(jié)點振蕩問題。而與傳統(tǒng)的對標(biāo)號傳播算法的改進(jìn)不同的是，本算法不是通過限定節(jié)點的活躍度來避免振蕩，所以最終的社團發(fā)現(xiàn)結(jié)果更有說服力。

在社團發(fā)現(xiàn)的效果方面，本算法加入了地理位置的影響因素，因而能夠很好地發(fā)現(xiàn)在地理位置上存在較好聚集性的社團，同時使得完全與地理位置無關(guān)的社團的劃分效果不可避免地有一定程度的降低。對特定的應(yīng)用而言(例如避免群體事件的發(fā)生，在地理位置上不具備聚集性的社團不會成為最終感興趣的結(jié)果)，這一結(jié)果不但完全可以接受，而且過濾了大量的無效社團，比一般性的社團發(fā)現(xiàn)算法更有實際應(yīng)用價值。另一方面，本算法將節(jié)點的線下關(guān)系映射到關(guān)系網(wǎng)絡(luò)中，有利于對網(wǎng)絡(luò)結(jié)構(gòu)的觀察，為下一步的可視化提供了堅實的基礎(chǔ)。

3.2 基于地理位置的社團發(fā)現(xiàn)可視化迭代

復(fù)雜網(wǎng)絡(luò)分析只是人們從大數(shù)據(jù)中獲取知識的一個步驟。由于計算機自動分析技術(shù)的不完善，人工參與不可避免，于是可視化成為了數(shù)據(jù)分析的一個重要組成部分。通過可視化能夠讓人參與到大數(shù)據(jù)分析的過程中，從而更好地結(jié)合人類和機器的分析能力[11]。社團發(fā)現(xiàn)的一個重要目的是進(jìn)行可視化展示，而標(biāo)記傳播算法由于有標(biāo)記的存在，也是最天然的適用于可視化迭代的社團發(fā)現(xiàn)算法。通過算法迭代的過程，顏色和距離上的逐漸聚集讓人更好地理解復(fù)雜網(wǎng)絡(luò)中的社團，從而進(jìn)一步學(xué)習(xí)和發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的各種知識。

為了保證復(fù)雜網(wǎng)絡(luò)中的社團可視化便于理解，一般來說會采用著色和節(jié)點聚集兩種方法進(jìn)行展示。著色方法前文已說明，此處不再贅述。節(jié)點聚集的方法是復(fù)雜網(wǎng)絡(luò)可視化的另一個比較大的基礎(chǔ)性問題，其目標(biāo)是讓同屬于一個社團的節(jié)點在空間(或者平面)位置上接近，不屬于同一個社團的節(jié)點在空間(或者平面)位置上較遠(yuǎn)。但是，由于需要計算任意兩個節(jié)點之間的關(guān)系，所以時間復(fù)雜度是O(n2)，這在一個大規(guī)模的復(fù)雜網(wǎng)絡(luò)中是一個極大的計算開銷。如果我們進(jìn)一步考慮將社團發(fā)現(xiàn)的可視化過程迭代顯示出來，則需要乘以迭代次數(shù)，時間復(fù)雜度進(jìn)一步提升。

我們提出了基于地理位置的改進(jìn)力導(dǎo)引布局算法來解決這一問題。力導(dǎo)引算法是一個經(jīng)典的復(fù)雜網(wǎng)絡(luò)布局算法，通過計算節(jié)點之間的斥力和邊上的引力來進(jìn)行復(fù)雜網(wǎng)絡(luò)的布局。其缺點在于力導(dǎo)引布局的計算本身也是一個迭代的過程，再加上一個迭代的社團發(fā)現(xiàn)過程，將會使迭代次數(shù)爆炸性增長。我們把力導(dǎo)引的迭代和標(biāo)號發(fā)現(xiàn)的迭代融合到一起，再加入地理位置的輔助信息，能夠極大地加快這一可視化的過程，降低計算復(fù)雜度。

首先定義引力和斥力。與經(jīng)典力導(dǎo)引不同，我們定義節(jié)點還會受到自身社團的引力和其他社團的斥力，具體如下：

s1(ek=(vi,vj))=-K(r-L)，

(5)

(6)

(7)

(8)

式中：s1和s2、g1和g2表示節(jié)點受到的引力和斥力，分別來自于邊、本社團質(zhì)心、其他節(jié)點和其他社團質(zhì)心；K為彈性邊的彈性系數(shù)；L表示默認(rèn)彈性邊的原長；G表示引力常量，在這里并不等同于萬有引力常量。通過調(diào)整K、L、G的值可以使布局變得更加緊湊或者松散。

在重新定義了引力和斥力后，下面給出具體的基于地理位置的改進(jìn)力導(dǎo)引布局算法步驟：

Step 1 在平面上按照地理位置放置網(wǎng)絡(luò)節(jié)點的初始位置。

Step 2 按照3.1節(jié)中基于地理位置聚類的快速社團發(fā)現(xiàn)算法Step 1～3計算節(jié)點的初始社團，并對其進(jìn)行著色標(biāo)記。

Step 3 計算每個社團的質(zhì)心位置以及重量。

Step 4 根據(jù)上文所定義的引力和斥力公式，對每個節(jié)點計算受力大小和方向，并根據(jù)受力計算節(jié)點位移δ=f·d，其中f為總的受力大小，d為位移常量。

Step 5 按照3.1節(jié)中基于地理位置聚類的快速社團發(fā)現(xiàn)算法Step 5～8進(jìn)行一次受限制的標(biāo)號傳播過程。

Step 6 重復(fù)Step 3～5，直到社團穩(wěn)定不發(fā)生變化，則算法終止。

本算法將力導(dǎo)引的迭代過程和標(biāo)號傳播的迭代過程整合到一起，引入了社團對節(jié)點的作用力，一方面加強社團的可視化效果，另一方面幫助節(jié)點快速進(jìn)行定位。本算法的核心在于這一全新的引力和斥力的定義和計算的方式。傳統(tǒng)的力導(dǎo)引算法只是對自然界中的引力和斥力進(jìn)行機械地模仿，缺乏合理的物理學(xué)基礎(chǔ)理論的支撐，實際表現(xiàn)上也有相當(dāng)多的缺陷。我們跳出其簡陋的物理模型，從實際效果出發(fā)來進(jìn)行力的設(shè)計，使得社團結(jié)構(gòu)能夠快速地被顯現(xiàn)，社團越早被發(fā)現(xiàn)，則社團的結(jié)構(gòu)越容易被可視化表示；并且使用節(jié)點的地理位置進(jìn)行輔助，一方面降低了迭代過程的計算復(fù)雜性，另一方面減少了節(jié)點的無謂振蕩，無論迭代性能還是可視化效果都有較大的提升。

4 算法測試

4.1 實驗環(huán)境及算法測試數(shù)據(jù)

實際的測試采用某地的真實通信網(wǎng)絡(luò)數(shù)據(jù)集，該數(shù)據(jù)集包含了251 231個節(jié)點以及1 031 449條連線(僅考慮數(shù)據(jù)集節(jié)點間的通信行為)，每次通信行為都包含了通信參與者雙方的地理位置信息(基站信息)。

表1代表了用戶之間的消息記錄，每條記錄代表兩個數(shù)字節(jié)點具有關(guān)系。同時，表中標(biāo)記了每次通信的LAC和CELLID信息，通過這些信息很容易查詢到具體的位置信息,因數(shù)據(jù)敏感，表中用“*”代替。由于節(jié)點不可避免地處于運動中，我們把節(jié)點最后一次通信行為的位置作為節(jié)點的位置。

表1 消息記錄示例Tab.1 Example of message record

4.2 測試步驟

本文的測試分兩個步驟進(jìn)行，分別是針對算法的收斂時間和算法的最終結(jié)果的測試。我們選用經(jīng)典的標(biāo)號傳播算法進(jìn)行對比測試，以驗證本文算法改進(jìn)的有效性。

分析算法的執(zhí)行步驟可以很容易理解，標(biāo)號傳播類算法都是通過多次遍歷網(wǎng)絡(luò)的邊集以進(jìn)行社團發(fā)現(xiàn)，因此，隨著數(shù)據(jù)量的增加，算法從達(dá)到收斂狀態(tài)的時間是等比增加的，也就是說，算法都具備線性的時間復(fù)雜度。我們通過刪除數(shù)據(jù)集中的部分節(jié)點來修改數(shù)據(jù)集節(jié)點數(shù)的大小，對比測試兩個算法計算時間的同時，驗證其算法的時間是否隨著節(jié)點個數(shù)的變化呈現(xiàn)線性關(guān)系。所有測試結(jié)果均重復(fù)10次取平均值。

我們在測試中使用模塊化函數(shù)定量分析社團劃分結(jié)果的模塊化水平，從而對算法的執(zhí)行結(jié)果進(jìn)行定量分析。模塊度Q值取值在0～1之間，社團劃分效果越好Q值越大，但是會受到實際社團的影響，很難對其進(jìn)行評價，例如：網(wǎng)絡(luò)中如果不存在明顯社團，則無論算法如何優(yōu)秀，都不可能得到較好的Q值。所以，只能過通過對比試驗來判斷算法的有效性。與算法收斂時間測試相同，社團劃分效果測試同樣采用相同的多組數(shù)據(jù)集，比較在不同數(shù)據(jù)規(guī)模下兩個算法的執(zhí)行效果。

4.3 測試結(jié)果與分析

使用帶有地理位置的通信網(wǎng)絡(luò)真實數(shù)據(jù)集，進(jìn)行社團發(fā)現(xiàn)算法度對比分析測試。首先測試算法的執(zhí)行速度，使用傳統(tǒng)的標(biāo)號傳播社團發(fā)現(xiàn)算法和基于地理位置聚類的快速社團發(fā)現(xiàn)算法，分別對大小不相同的幾個數(shù)據(jù)集進(jìn)行社團發(fā)現(xiàn)測試后，其執(zhí)行時間對比如表2所示。

表2 算法時間對比Tab.2 Time consumption vs. network scale

為了有一個更直觀的認(rèn)識，將表中各種數(shù)據(jù)繪制為折線圖，以對比兩種算法執(zhí)行社團發(fā)現(xiàn)的收斂時間隨節(jié)點規(guī)模的變化關(guān)系，如圖2所示。

特別需要說明的是，由于基于地理位置聚類的快速社團發(fā)現(xiàn)算法包含了兩步走的處理過程，所以在社團較小的極端情況下耗時稍高。

從圖2中可以看出，兩種算法在時間消耗上基本符合線性增長的特征，這與前文對其時間復(fù)雜度的分析對應(yīng)。在進(jìn)行大規(guī)模網(wǎng)絡(luò)社團發(fā)現(xiàn)時，傳統(tǒng)的標(biāo)號傳播算法由于存在節(jié)點的振蕩，算法時間與線性擬合的曲線有較大的偏離，表現(xiàn)為網(wǎng)絡(luò)越大，振蕩越嚴(yán)重，同時節(jié)點振蕩的程度也與網(wǎng)絡(luò)的模塊度有一定關(guān)系。本文中的限制性標(biāo)號傳播算法由于采用兩步走的策略，通過一個快速的地理位置聚類度步驟減少了標(biāo)號傳播度迭代次數(shù)，避免了節(jié)點振蕩，從而可以消耗更少的時間達(dá)到收斂。

兩個算法的社團發(fā)現(xiàn)效果測試結(jié)果如表3所示。

表3 算法Q值比較Tab.3 Q value vs. network scale

將測試數(shù)據(jù)繪制為折線圖，對比兩種社團發(fā)現(xiàn)算法的模塊度，如圖3所示。

基于地理位置聚類的限制性標(biāo)號傳播算法較標(biāo)號傳播社團發(fā)現(xiàn)的模塊度值明顯有所提升，可以得出結(jié)論：算法的其社團發(fā)現(xiàn)效果要好于傳統(tǒng)的標(biāo)號傳播社團發(fā)現(xiàn)。

可視化是本文算法的另一個組成部分，但是，對可視化復(fù)雜網(wǎng)絡(luò)缺乏客觀的評價標(biāo)準(zhǔn)，使得較難以用過數(shù)值對其進(jìn)行可視化的評價。這里還是給出一個直觀的例子，試圖通過這個示例來解釋本文中所述的方法和傳統(tǒng)方法的區(qū)別。

我們抽取除了一個包含76個節(jié)點的圖進(jìn)行了可視化對比展示(見圖4)，并以顏色區(qū)分不同的社團。在圖4(a)中用普通的力導(dǎo)引算法將網(wǎng)絡(luò)中的節(jié)點在平面上進(jìn)行了可視化布局展示，圖4(b)中加入了地理位置的影響。表面上看，圖4(a)的節(jié)點布局更合理，每個社團的可視化聚集性更好，更能反映網(wǎng)絡(luò)中的社團結(jié)構(gòu)。但是，由于圖4(b)中考慮了節(jié)點的實際位置，使得圖4(b)雖然看起來不漂亮，但是卻包含了更多的可視化信息。從知識表達(dá)的角度來說，我們認(rèn)為圖4(b)的結(jié)果會更好一些。

圖4 社團發(fā)現(xiàn)可視化效果對比測試

從上述測試結(jié)果可以發(fā)現(xiàn)，加入地理位置信息之后的社團發(fā)現(xiàn)和可視化算法在收斂時間、Q值以及可視化效果方面均優(yōu)于傳統(tǒng)算法，并且在社團發(fā)現(xiàn)的結(jié)果中體現(xiàn)了地理位置的聚團性。因此，我們可以得出結(jié)論：該算法可以適用于實際通信數(shù)據(jù)的可視化分析。

5 結(jié)束語

本文討論了參考節(jié)點地理位置信息的情況下對復(fù)雜通信網(wǎng)絡(luò)的社群劃分和可視化兩個基本問題進(jìn)行優(yōu)化的方法，主要貢獻(xiàn)在于：

(1)提出一種基于地理位置信息的限制性標(biāo)號傳播算法，通過地理位置信息幫助初始化編號傳播網(wǎng)絡(luò)，并且限制節(jié)點的無目的性振蕩，提高了標(biāo)號傳播社群發(fā)現(xiàn)的性能;

(2)提出了一種基于地理位置信息的改進(jìn)力導(dǎo)引布局算法，將力導(dǎo)引算法和標(biāo)號傳播社群發(fā)現(xiàn)在地理位置為基礎(chǔ)的信息上進(jìn)行融合迭代，使得一方面社群發(fā)現(xiàn)的過程可視化，另一方面可視化效果也得到了提升。

本文的直接結(jié)論只有益于通信網(wǎng)絡(luò)，在其他結(jié)構(gòu)特征下的復(fù)雜網(wǎng)絡(luò)中也許并不適用，但是所提出的采用節(jié)點信息輔助社群劃分和可視化的思路是普適的，可以作為復(fù)雜網(wǎng)絡(luò)分析的一項基本手段。進(jìn)一步的研究可著眼于不同業(yè)務(wù)網(wǎng)絡(luò)的結(jié)構(gòu)特征與節(jié)點屬性的關(guān)聯(lián)分析，以及深度融合節(jié)點特征的網(wǎng)絡(luò)結(jié)構(gòu)分析算法。

[1] 何大韌,劉宗華,汪秉宏. 復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)[M].北京：高等教育出版社,2009.

[2] HARENBERG S,BELLO,G,GJELTEMA L,et al.Community detection in large-scale networks: a survey and empirical evaluation[J].Wiley Interdisciplinary Reviews: Computational Statistics，2014(6): 426-439.

[3] CORREAC D. History and evolution of social network visualization[M].New York：Springer,2014: 677-695.

[4] TRUSINA A,MASLOV S,MINNHAGENP,et al.Hierarchy measures in complex networks[J].Physical Review Letters,2004,92(17): 178702-1-178702-4.

[5] 張俊麗,常艷麗,師文. 標(biāo)簽傳播算法理論及其應(yīng)用研究綜述[J].計算機應(yīng)用研究,2013,30(1): 21-25. ZHANG Junli,CHANG Yanli,SHI Wen. Overview on label propagation algorithm and applications[J].Application Research of Computers,2013,30(1): 21-25.(in Chinese)

[6] LI Q,ZHENG Y,XIE X,et al.Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Irvine,CA,USA:ACM,2008:1-10.

[7] ZHENG Y,XIE X,MA W Y. GeoLife: a collaborative social networking service among user,location and trajectory[J].IEEE Data Engineering Bulletin,2010,33(2):32-39.

[8] WANG X,VASILAKOSA V,CHEN M,et al.A survey of green mobile networks: opportunities and challenges[J].Mobile Networks and Applications,2012,17(1):4-20.

[9] KASSEN M. A promising phenomenon of open data: a case study of the Chicago open data project[J].Government Information Quarterly,2013,30(4): 508-513.

[10] PAVLOPOULOS G A,MOSCHOPOULOSC N,HOOPER S D,et al.Clust: a clustering and visualization toolbox[J].Bioinformatics,2009,25(15): 1994-1996.

[11] BECK F,BURCH M,DIEHLS,et al.A taxonomy and survey of dynamic graph visualization[J].Computer Graphics Forum,2016,36(1): 133-159.

Complex Communication Network Geolocation BasedCommunity Detection and Visualization

DAI Xiang

(Southwest China Institute of Electronic Technology,Chengdu 610036，China)

The geolocation is believed to have certain positive correlation with network structure in the communication networks,shopping network and other complex networks.The geolocation information is introduced into the task of complex network group detecting and visualization to improve the traditional label propagation algorithm and force-directed graph drawing algorithm. By performing the geolocation based clustering in advance,and then adding the geolocation based restriction in the iterative process,meaningless oscillations can be greatly minimized. The experiment proves that this scheme can speed up the discovery of community and the convergence speed of the algorithm can also be added to the influence of geographical location on the distribution of the community,and the performance of the fast community discovery algorithm can be improved both in convergence time and community discovery(Qvalue).

complex communication network;community detection;label propagation;force-directed graph

2017-03-09；

2017-05-03 Received date:2017-03-09；Revised date：2017-05-03

“十三五”國防預(yù)研基金

10.3969/j.issn.1001-893x.2017.06.001

代翔.復(fù)雜通信網(wǎng)絡(luò)的地理位置聚集性社團發(fā)現(xiàn)和可視化[J].電訊技術(shù)，2017,57(6):615-621.[DAI Xiang.Complex communication network geolocation based community detection and visualization[J].Telecommunication Engineering,2017,57(6):615-621.]

TN921

A

1001-893X(2017)06-0615-07

代 翔(1983—)，男，河南信陽人，2012年獲博士學(xué)位，現(xiàn)為工程師，主要研究方向為自然語言處理、數(shù)據(jù)挖掘等。

Email:54831015@qq.com

**通信作者：54831015@qq.com Corresponding author：54831015@qq.com