代 翔

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

?

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

代 翔**

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

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

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

1 引 言

現(xiàn)實(shí)世界中存在著大量的網(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)有著共同的“自組織、自相似、吸引子、小世界、無(wú)標(biāo)度”等復(fù)雜特性，所以被統(tǒng)稱(chēng)為復(fù)雜網(wǎng)絡(luò)[1]。社團(tuán)發(fā)現(xiàn)是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)以及可視化的重要基礎(chǔ)性工作[2]。對(duì)于大規(guī)模復(fù)雜網(wǎng)絡(luò)，通過(guò)社團(tuán)發(fā)現(xiàn)，以及可視化標(biāo)記，能夠較好地幫助使用者了解復(fù)雜關(guān)系網(wǎng)絡(luò)的社團(tuán)分布情況，對(duì)分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為都有十分重要的意義[3]。

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

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

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

Step5 顏色相同的節(jié)點(diǎn)分配一個(gè)社團(tuán)號(hào)。

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

(4)

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

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

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

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

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

Fig.1 Flow chart of group detecting algorithm

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

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

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

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

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

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

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

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

(5)

(6)

(7)

(8)

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

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

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

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

Step 3 計(jì)算每個(gè)社團(tuán)的質(zhì)心位置以及重量。

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

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

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

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

4 算法測(cè)試

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

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

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

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

4.2 測(cè)試步驟

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

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

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

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

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

表2 算法時(shí)間對(duì)比Tab.2 Time consumption vs. network scale

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

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

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

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

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

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

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

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

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

圖4 社團(tuán)發(fā)現(xiàn)可視化效果對(duì)比測(cè)試

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

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

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

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

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

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

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

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

代翔.復(fù)雜通信網(wǎng)絡(luò)的地理位置聚集性社團(tuán)發(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—)，男，河南信陽(yáng)人，2012年獲博士學(xué)位，現(xiàn)為工程師，主要研究方向?yàn)樽匀徽Z(yǔ)言處理、數(shù)據(jù)挖掘等。

Email:54831015@qq.com

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