基于雙曲空間嵌入的極小值社區(qū)劃分算法

謝 菁,羿舒文,張 毅

(武漢大學 電子信息學院,武漢 430072)

0 概述

以移動互聯(lián)網(wǎng)為代表的信息通信網(wǎng)絡(luò)已經(jīng)成為現(xiàn)代社會社交的重要媒介,逐漸滲透到人們?nèi)粘Ｉ畹母鱾€方面?；ヂ?lián)網(wǎng)的應(yīng)用日益廣泛,也使其產(chǎn)生的數(shù)據(jù)量呈爆炸性增長趨勢[1]。2019年2月,思科全球移動可視化網(wǎng)絡(luò)指數(shù)(VNI)預測全球移動用戶將達到57億,移動數(shù)據(jù)流量的年數(shù)據(jù)量將達到930 EB[2]。在此背景下,有效分析移動互聯(lián)網(wǎng)中用戶產(chǎn)生的數(shù)據(jù)具有重要的社會意義。隨著復雜網(wǎng)絡(luò)規(guī)模不斷增長,如何定量、有效地分析大規(guī)模網(wǎng)絡(luò)備受關(guān)注?，F(xiàn)實生活中的復雜網(wǎng)絡(luò)具有自組織、自相似和小世界特性[3],其中小世界特性表明網(wǎng)絡(luò)具有節(jié)點間平均距離小、聚合系數(shù)大、節(jié)點度分布服從冪律分布等特點。這些特性是復雜網(wǎng)絡(luò)為實現(xiàn)某些功能而逐漸演變成擁有特定功能集團的結(jié)果。

復雜網(wǎng)絡(luò)具有社區(qū)化特性,每個節(jié)點在不同的社區(qū)擁有不同的“角色”,其結(jié)構(gòu)的多樣性表明復雜網(wǎng)絡(luò)內(nèi)部的組織方式也具有多樣性。針對復雜網(wǎng)絡(luò)中特定社區(qū)的研究,對于理解網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)中對象的特征和對象與對象之間的相互關(guān)系具有重要價值。社區(qū)劃分是找到數(shù)據(jù)相似性并定義分組的過程,其本質(zhì)是一種使用聚類思想的方法。復雜網(wǎng)絡(luò)作為眾多領(lǐng)域信息網(wǎng)的模型,具體為表示信息資源的節(jié)點和表示信息之間關(guān)系的連邊。因此,在復雜網(wǎng)絡(luò)上進行社區(qū)劃分能發(fā)現(xiàn)信息聚集、傳播和流動關(guān)系,比單純地利用節(jié)點本身屬性聚類發(fā)現(xiàn)社區(qū)更有意義。挖掘復雜網(wǎng)絡(luò)中潛在的社區(qū)結(jié)構(gòu),對于進一步研究網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、辨識和預測社區(qū)功能起到至關(guān)重要的作用[4-5]。目前存在多種社區(qū)劃分方法,它們有各自應(yīng)用場景和不同側(cè)重,但隨著數(shù)據(jù)量的持續(xù)增長,數(shù)據(jù)處理均面臨計算能力的限制。因此,需要設(shè)計更能適應(yīng)大數(shù)據(jù)環(huán)境、保留數(shù)據(jù)精度的改進算法。

本文針對大型真實復雜網(wǎng)絡(luò)分析難以保留網(wǎng)絡(luò)特性和處理大數(shù)據(jù)量時社區(qū)劃分復雜度高的問題,提出基于雙曲空間嵌入的極小值社區(qū)劃分算法MHE。將網(wǎng)絡(luò)嵌入二維雙曲空間模型——龐加萊圓盤,以保留復雜網(wǎng)絡(luò)結(jié)構(gòu)信息。在此基礎(chǔ)上,根據(jù)節(jié)點分布與圓盤中角度的關(guān)系得到θ曲線,以雙曲角坐標差值表示兩個節(jié)點間的相似性。通過劃分θ曲線保證局部節(jié)點相似性最大,即選擇曲線極小值處劃分社區(qū),并根據(jù)最大模塊度選擇最優(yōu)社區(qū)劃分結(jié)果。在此過程中無需設(shè)定聚類中心,從而避免人為設(shè)置聚類中心導致的誤差。

1 相關(guān)研究

復雜網(wǎng)絡(luò)分析最初是基于數(shù)學的方法展開的。大量交互節(jié)點的集合可以建模為圖結(jié)構(gòu),為復雜網(wǎng)絡(luò)分析提供了理論依據(jù)?；跀?shù)學的復雜網(wǎng)絡(luò)分析方法包括矩陣法、圖論法和統(tǒng)計法等。矩陣法如非負矩陣分解為深入分析網(wǎng)絡(luò)中節(jié)點和簇之間的關(guān)系提供了理論基礎(chǔ)。隨著網(wǎng)絡(luò)規(guī)模的增加,相比傳統(tǒng)圖論對網(wǎng)絡(luò)進行結(jié)構(gòu)化分析,隨機圖理論能更好地描述大型網(wǎng)絡(luò)的性質(zhì)[6]。統(tǒng)計法則側(cè)重于利用隨機圖模型和小世界網(wǎng)絡(luò),可以挖掘具有顯著統(tǒng)計特性的復雜網(wǎng)絡(luò)節(jié)點子集,得到準確的計算結(jié)果。雖然基于數(shù)學的復雜網(wǎng)絡(luò)分析方法擁有良好的理論基礎(chǔ),但因為其固有的高計算成本,所以不適合大規(guī)模網(wǎng)絡(luò)。隨機游走的網(wǎng)絡(luò)分析方法從網(wǎng)絡(luò)中的任意節(jié)點開始游走,如DeepWalk[7]用SkipGram的方法學習節(jié)點特征,當網(wǎng)絡(luò)中具有清晰的社團結(jié)構(gòu)時,節(jié)點在社團內(nèi)部游走的概率將遠高于在社團間游走。隨機游走的方法主要針對復雜網(wǎng)絡(luò)中的結(jié)構(gòu)特性,且步長選擇的不同對算法性能影響較大,步長大意味著更多的迭代,而步長取得過小又很難得到最優(yōu)解決方案。文獻[8]通過建立復雜網(wǎng)絡(luò)的雙曲幾何框架,表明復雜網(wǎng)絡(luò)在結(jié)構(gòu)上與雙曲空間有高度一致性。在大數(shù)據(jù)量的背景下,將真實復雜網(wǎng)絡(luò)嵌入到雙曲空間,可以將必須映射到高維歐式空間才能保留的較多性質(zhì),在不降低精度的情況下映射到低維的雙曲空間,這種發(fā)現(xiàn)將真實復雜網(wǎng)絡(luò)分析問題轉(zhuǎn)化為雙曲幾何問題,為復雜網(wǎng)絡(luò)分析提供了新的思路。

社區(qū)劃分在復雜網(wǎng)絡(luò)分析中具有重要的社會意義和應(yīng)用價值?，F(xiàn)有的社區(qū)劃分算法主要有基于圖論的算法、基于層次聚類的算法和基于函數(shù)優(yōu)化的算法?；趫D論的經(jīng)典算法有K-L算法[9]和基于圖拉普拉斯矩陣特征向量的譜平分算法[10],但由于K-L算法和譜平分算法均為二分算法,因此不適用于包含較多團簇的復雜網(wǎng)絡(luò)。為檢測多社區(qū)結(jié)構(gòu)網(wǎng)絡(luò),研究者提出基于圖半監(jiān)督學習的標簽傳播算法LPA[11]和基于LPA的SLPA算法[12]?；趫D論的方法涉及矩陣計算,其計算對硬件要求很高,因此,難以適用于大型網(wǎng)絡(luò)?；趯哟尉垲惖慕?jīng)典算法有GN算法[13],但因為GN算法不適用于大型復雜網(wǎng)絡(luò),研究者進而提出基于貪婪的FGN[14]算法,同時定義了重要社區(qū)劃分評價指標的模塊度?；诤瘮?shù)優(yōu)化的社區(qū)劃分算法,例如極值優(yōu)化算法[15],通過求解模塊度最優(yōu)解進行社區(qū)劃分,也有基于最優(yōu)模塊度提出通過多次迭代最大化模塊度進行社區(qū)劃分的Louvain社區(qū)發(fā)現(xiàn)算法[16]。文獻[17]在譜聚類的基礎(chǔ)上進行修正,提出了正則化譜聚類算法。

2 復雜網(wǎng)絡(luò)與雙曲空間

2.1 復雜網(wǎng)絡(luò)和社區(qū)

現(xiàn)實生活中許多領(lǐng)域的網(wǎng)絡(luò),如信息網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等,均可建模為復雜網(wǎng)絡(luò)的形式。復雜網(wǎng)絡(luò)具有自組織、自相似和小世界效應(yīng)[18]。小世界效應(yīng)指網(wǎng)絡(luò)擁有無標度性,節(jié)點擁有高聚合系數(shù),網(wǎng)絡(luò)直徑不大于O(logan))[6],其中,無標度特性指網(wǎng)絡(luò)中節(jié)點的度分布服從冪律分布,節(jié)點的聚合系數(shù)是指節(jié)點相鄰的所有節(jié)點之間連邊數(shù)與這些相鄰節(jié)點之間最大可能連邊數(shù)的比值,物理含義為相同節(jié)點的兩個相鄰節(jié)點仍然是相鄰節(jié)點的概率。聚合系數(shù)描述了網(wǎng)絡(luò)的局部聚集特性,可證明復雜網(wǎng)絡(luò)有明顯的社區(qū)化特征。

社區(qū)一詞由德國社會學家T?NNIES于1887年在《共同體與社會》中提出。T?NNIES認為,社區(qū)是由具有共同習俗和價值觀的同質(zhì)人口所形成的社會集合狀態(tài)[19]。社區(qū)可以看作網(wǎng)絡(luò)中具有相同偏好節(jié)點的集合,是社會關(guān)系和社會活動的特定具體方式。由于復雜網(wǎng)絡(luò)擁有明顯的集團化特征,因此區(qū)分復雜網(wǎng)絡(luò)中的社區(qū)具有重要的應(yīng)用價值。

2.2 雙曲空間

雙曲空間是指曲率為恒定復常數(shù)K=-ζ2,ζ>0的非歐空間。二維雙曲空間節(jié)點坐標用極坐標的方法表示為徑坐標和角坐標的形式:(ρ,θ)。假設(shè)雙曲空間上存在兩個點(ρt,θt)和(ρs,θs),兩點間的雙曲距離為兩點間的測地線長度,計算公式為[8]:

sinh(ζρs)sinh(ζρt)cosθst)

(1)

其中,θst表示兩個點間角坐標的差值。

負曲率導致雙曲空間很難在平面上可視化,但雙曲空間上的定理可以通過幾何關(guān)聯(lián)性質(zhì)轉(zhuǎn)換到歐式空間上證明,由此出現(xiàn)了雙曲空間的等價分析模型,例如二維雙曲空間模型——龐加萊圓盤[20]。該模型將二維雙曲空間在平面上可視化為半徑為R的平面圓盤,圓盤邊界處表示無窮遠,雙曲直線為兩端均垂直于圓盤邊界的弧線。

雙曲幾何與歐式幾何的主要不同點為雙曲幾何不遵循歐幾里得第五公設(shè)。在雙曲空間中,過直線外一點存在至少兩條不重合的直線與已知直線平行,如圖1(a)所示,并且雙曲空間中三角形ABC內(nèi)角之和小于180°,如圖1(b)所示。

圖1 二維雙曲圓盤幾何性質(zhì)

2.3 問題描述

信息時代網(wǎng)絡(luò)數(shù)據(jù)量迅速增長,如何完整保留復雜網(wǎng)絡(luò)的信息非常重要。復雜網(wǎng)絡(luò)節(jié)點間的相似性不是單純依靠節(jié)點間的直接連接評判,而更與其樹形結(jié)構(gòu)相關(guān),同一子樹上的節(jié)點相互之間具有一定程度上的相似性,具有相同父節(jié)點的子節(jié)點具有高度相似性。因此,文獻[5]提出了復雜網(wǎng)絡(luò)的雙曲幾何框架,用幾何的方法研究復雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能,證實了雙曲幾何不會破環(huán)網(wǎng)絡(luò)結(jié)構(gòu)的性質(zhì)并論證了復雜網(wǎng)絡(luò)嵌入雙曲空間的合理性。復雜網(wǎng)絡(luò)的冪律分布是雙曲幾何作為潛在幾何結(jié)構(gòu)的自然反映,在二維雙曲空間中,圓的周長C(r)和面積A(r)計算公式[8]分別如下:

(2)

(3)

可以看出,圓的周長和面積對于雙曲圓中的半徑r均呈指數(shù)增長關(guān)系,該特性表明雙曲空間能夠完整地表現(xiàn)復雜網(wǎng)絡(luò)的冪律分布特性。雙曲隨機圖模型[21]定義了大小為n所有圖的概率分布,當雙曲平面中節(jié)點距離較小時節(jié)點相連,得到的模型具有冪律分布和高聚集性,為真實網(wǎng)絡(luò)嵌入雙曲空間提供了理論依據(jù)。

復雜網(wǎng)絡(luò)與雙曲空間的相關(guān)研究包括網(wǎng)絡(luò)生成方法和網(wǎng)絡(luò)嵌入方法。文獻[22]構(gòu)建了基于二維雙曲空間的經(jīng)典網(wǎng)絡(luò)生成模型PSO模型,提出了節(jié)點流行度和相似度的概念,其中節(jié)點徑坐標與節(jié)點的流行度成反比,節(jié)點間的角坐標差值與節(jié)點屬性相似度成反比。文獻[23]提出基于拉普拉斯矩陣的雙曲嵌入方法,該算法以龐加萊圓盤模型為保角模型,利用節(jié)點度拉普拉斯矩陣的最小兩個非零特征值得到雙曲角坐標,由于該方法涉及矩陣運算,因此在大型數(shù)據(jù)下難以適用。文獻[24]在雙曲隨機圖模型的基礎(chǔ)上提出快速嵌入算法,該算法適用于計算大規(guī)模網(wǎng)絡(luò)基于極大似然估計的雙曲嵌入,不依賴昂貴的數(shù)值計算及嵌入迅速的優(yōu)點,使其在真實的大規(guī)模網(wǎng)絡(luò)嵌入中具有較高的應(yīng)用價值。

本文在快速嵌入算法的基礎(chǔ)上提出基于雙曲空間嵌入的極小值聚類算法用于社區(qū)劃分。龐加萊圓盤定義為一組范數(shù)小于圓盤半徑的復數(shù)集合[25],本文將復雜網(wǎng)絡(luò)嵌入到二維龐加萊圓盤上,保留了網(wǎng)絡(luò)樹形結(jié)構(gòu),又因為雙曲角坐標差值表示節(jié)點間的相似度,所以對節(jié)點對應(yīng)角坐標的分布曲線進行極小值劃分,得到相鄰極小值之間的節(jié)點角坐標差值,其物理含義為一個社區(qū),并通過最大模塊度值選擇最優(yōu)社區(qū)劃分。

3 基于雙曲嵌入的極小值社區(qū)劃分

本文將已知連接關(guān)系無權(quán)無向的真實復雜網(wǎng)絡(luò)嵌入到二維雙曲空間模型——龐加萊圓盤[20]中。二維龐加萊圓盤擁有3個基本參數(shù):徑坐標r,角坐標θ和溫度T。溫度參數(shù)用來調(diào)整圓盤潛在幾何分布,當T→0時,雙曲空間越穩(wěn)定,相應(yīng)的T越高,雙曲空間的隨機性越高,一般根據(jù)經(jīng)驗將T設(shè)置為0.1。根據(jù)龐加萊圓盤的雙曲幾何性質(zhì)掃描嵌入復雜網(wǎng)絡(luò)的圓盤,得到節(jié)點對應(yīng)角坐標的分布曲線,并對曲線按極小值劃分,得到社區(qū)劃分結(jié)果。

3.1 復雜網(wǎng)絡(luò)建模

已知網(wǎng)絡(luò)的節(jié)點屬性信息,根據(jù)節(jié)點間的相似度構(gòu)建節(jié)點間的連邊,因為本文方法針對的是真實復雜網(wǎng)絡(luò),所以要求建模后節(jié)點度分布符合冪律分布。將復雜網(wǎng)絡(luò)的節(jié)點和連邊作為算法的輸入,建模無權(quán)無向圖得到節(jié)點的鄰接矩陣,并且根據(jù)節(jié)點間的連接信息計算節(jié)點度。

3.2 雙曲嵌入

復雜網(wǎng)絡(luò)一般表示為鄰接矩陣。由于矩陣計算的復雜性,因此本文考慮對復雜網(wǎng)絡(luò)進行二維雙曲空間嵌入,在此過程中會保留網(wǎng)絡(luò)局部的結(jié)構(gòu)信息,即每個節(jié)點的度連接信息,并計算復雜網(wǎng)絡(luò)每個節(jié)點對應(yīng)在雙曲空間二維龐加萊圓盤模型上的雙曲坐標,如圖2所示。

圖2 復雜網(wǎng)絡(luò)嵌入龐加萊圓盤示意圖

本文使用快速嵌入算法[24]進行雙曲嵌入。在快速嵌入算法中,節(jié)點擁有嵌入順序。根據(jù)已知的網(wǎng)絡(luò)節(jié)點與連邊信息,確定唯一的龐加萊圓盤。按照節(jié)點在網(wǎng)絡(luò)中的度降序排列得到節(jié)點順序,按照節(jié)點順序從第一個節(jié)點開始依次計算雙曲坐標。計算龐加萊圓盤半徑和雙曲嵌入坐標公式的過程如下,詳細推導和證明過程請參考文獻[24]。

(4)

將節(jié)點按度降序排列的順序依次嵌入,節(jié)點i的徑坐標計算公式如下:

(5)

其中,deg(i)表示節(jié)點i在復雜網(wǎng)絡(luò)中的度,R表示龐加萊圓盤半徑。

同理,按上述節(jié)點順序得到節(jié)點i的角坐標,計算公式如下:

(6)

其中,k表示復雜網(wǎng)絡(luò)中節(jié)點i的所有鄰居中有k個節(jié)點已經(jīng)嵌入,rj為節(jié)點i已經(jīng)嵌入到雙曲空間中的鄰居的徑坐標,θj為節(jié)點i已經(jīng)嵌入到雙曲空間的鄰居的角坐標,第一個節(jié)點的角坐標在[0,2π]區(qū)間中隨機生成。

3.3 極小值劃分

利用快速嵌入算法[24]將真實復雜網(wǎng)絡(luò)嵌入到雙曲空間二維龐加萊圓盤后,每個節(jié)點擁有徑坐標和角坐標。由于雙曲嵌入考慮了網(wǎng)絡(luò)性質(zhì),因此節(jié)點在圓盤上不是均勻分布的。根據(jù)PSO模型可知節(jié)點徑坐標與節(jié)點度成反比,節(jié)點間角坐標差值與節(jié)點的相似程度成反比,而雙曲距離可以綜合考量節(jié)點度和相似度。所以,首先考慮圓盤上角坐標和徑坐標分別對雙曲距離的影響,固定角度差為45°,固定半徑長度為3,分別作徑坐標和角坐標對距離的影響曲線,如圖3和圖4所示。

圖3 徑坐標對雙曲距離的影響

圖4 角坐標對雙曲距離的影響

可以看出:在徑坐標不變的情況下,除了角度趨近于零的情況,角度差對雙曲距離變化的影響很小;在角度差不變的情況下,徑坐標與雙曲距離成正比。復雜網(wǎng)絡(luò)的集團特性導致節(jié)點嵌入后在圓盤上分布不均勻,所以,在雙曲圓盤上按照角度劃分區(qū)域,使角度區(qū)域內(nèi)節(jié)點密度大,而在角度區(qū)域間節(jié)點密度小。因此,本文考慮在節(jié)點的雙曲角度分布曲線上使用曲線極小值劃分實現(xiàn)聚類。

綜上,按角度掃描已嵌入的龐加萊圓盤,得到嵌入的節(jié)點對應(yīng)角坐標的分布曲線,稱為θ曲線,記為γ(θ)。在θ曲線上尋找局部極小值劃分角度區(qū)域,使兩個局部最小值之間包含一個最大值。

3.4 最優(yōu)劃分條件

本文使用模塊度作為選擇極小值最優(yōu)社區(qū)劃分的條件。模塊度是2004年NEWMAN提出的一種衡量社區(qū)結(jié)構(gòu)的概念[14],用來描述網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)內(nèi)部連邊的比例和隨機網(wǎng)絡(luò)中社區(qū)內(nèi)部連邊所占比例差值,反映了社區(qū)內(nèi)真實連邊數(shù)與期望連邊數(shù)的差異,其值越大,表明節(jié)點聚集趨勢越大。模塊度是社區(qū)中的邊緣數(shù)量減去隨機生成圖中的期望邊緣數(shù)量[20],計算公式如下:

(7)

因為θ曲線上的極大值表示圓盤上節(jié)點分布稠密處,極小值表示節(jié)點分布稀疏處,所以θ曲線相鄰極大極小值的縱坐標之差越小,表示節(jié)點分布變化越小。因此,定義極值刪除規(guī)則如下:

定義1(極值刪除規(guī)則) 尋找曲線上相鄰兩個極大極小值,使它們的縱坐標值之差最小,將該極大值和極小值刪去。

假設(shè)當前已經(jīng)存在θ曲線上k個極小值,根據(jù)極值刪除規(guī)則依次刪去極大值極小值,得到極小值點序列集合K={mk,mk-1,…,m2},其中,mk表示該極小值序列包含k個極小值。每個極小值序列對應(yīng)一種社區(qū)劃分。對集合K中每個極小值序列計算每個社區(qū)劃分的模塊度,得到模塊度集合:

QK={Qk,Qk-1,…,Q2}

(8)

當社區(qū)模塊度最大時,極小值序列中的極小值為社區(qū)劃分界限,相鄰極小值間的節(jié)點屬于一個社區(qū),從而得到最優(yōu)劃分社區(qū)。最優(yōu)社區(qū)劃分目標為:

L=max(QK)

(9)

3.5 基于雙曲嵌入的極小值社區(qū)劃分

綜上所述,利用快速嵌入算法,基于雙曲嵌入的極小值社區(qū)劃分算法偽代碼如下:

輸入節(jié)點id,節(jié)點id對應(yīng)節(jié)點屬性,節(jié)點個數(shù)n

輸出社區(qū)劃分結(jié)果

//步驟1:根據(jù)節(jié)點屬性建模復雜網(wǎng)絡(luò)

for i in range(n):

for j in range(i+1,n):

if節(jié)點i和節(jié)點j相似

連接節(jié)點i和節(jié)點j

根據(jù)節(jié)點的連接信息得到網(wǎng)絡(luò)中每個節(jié)點的度

for i in range(n):

for j in range(i+1,n):

if節(jié)點i和節(jié)點j相似

連接節(jié)點i和節(jié)點j

根據(jù)節(jié)點的連接信息得到網(wǎng)絡(luò)中每個節(jié)點的度

//步驟2:雙曲嵌入

降序排列節(jié)點度,生成新的節(jié)點順序

while i

按節(jié)點新順序根據(jù)雙曲坐標計算公式計算每個節(jié)點的ri和θi

計算所有節(jié)點的雙曲坐標并可視化到二維圓盤上

//步驟3:社區(qū)發(fā)現(xiàn)

按角度掃描雙曲圓盤,得到θ曲線γ(θ),對γ(θ)求導記為γ′(θ)

if γ′(θi-1)<0 and γ′(θi+1)>0

保存θi為極小值

根據(jù)極值刪除規(guī)則,計算模塊度集合QK={Qk,Qk-1,…,Q2}

優(yōu)化目標L=max(QK)得到相應(yīng)極小值序列

return劃分社區(qū)和社區(qū)個數(shù)

步驟1中所述相似性度量可以根據(jù)實際情況選擇。

4 實驗與結(jié)果分析

4.1 數(shù)據(jù)集描述

本文對浙江省某市中國移動的基站真實記錄進行復雜網(wǎng)絡(luò)建模,該市包括8個主要行政區(qū),數(shù)據(jù)集時間范圍是2014年11月21日——2014年12月13日,共計23 d,記錄條數(shù)超過450萬。

每條用戶訪問記錄數(shù)據(jù)信息包括用戶ID、訪問基站LAC ID、訪問基站CEL ID、訪問URL、訪問開始時間、訪問終止時間等。因為訪問記錄數(shù)據(jù)量巨大且本文建模基站合作網(wǎng)絡(luò)有大量數(shù)據(jù)信息是不需要的,所以首先對原始數(shù)據(jù)進行“清洗”。本文建?；竞献骶W(wǎng)絡(luò),假設(shè)基站為復雜網(wǎng)絡(luò)節(jié)點,因此,算法中節(jié)點間相似性度量方法為兩個基站只要服務(wù)于共同用戶則節(jié)點間擁有連邊。數(shù)據(jù)預處理時僅保留數(shù)據(jù)中基站的LAC ID、基站的CEL ID、基站服務(wù)的用戶ID,去除基站下的錯誤用戶ID,最后得到每個基站下的用戶數(shù)據(jù)格式如表1所示。

表1 基站用戶數(shù)據(jù)

每個基站節(jié)點以LAC ID和CEL ID共同表示,利用LAC ID和CEL ID能夠得到基站在地理空間上的真實經(jīng)緯度,所以,將基站的LAC ID與CEL ID組合作為基站ID,與基站經(jīng)緯度相對應(yīng),去除經(jīng)緯度缺失基站,得到的數(shù)據(jù)格式如表2所示。

表2 基站經(jīng)緯度數(shù)據(jù)

本文建模基站合作網(wǎng)絡(luò),基站間擁有共同用戶時表現(xiàn)為兩個基站相似,節(jié)點間擁有連邊,其物理意義為兩個基站服務(wù)于共同用戶,同時可以刻畫用戶的活動軌跡,所以,對合作網(wǎng)絡(luò)進行社區(qū)劃分可以表現(xiàn)基站在真實地理空間上的分布。

4.2 冪律擬合

建模后的基站合作網(wǎng)絡(luò)為無標度網(wǎng)絡(luò)。許多學者通過對人類大量行為的動力學研究,發(fā)現(xiàn)人類日常行為常有潛在的冪律分布特性[26-27],會表現(xiàn)出冪律分布間隔特性[28-29]。本文建模的基站合作網(wǎng),其物理含義表現(xiàn)為人的活動方式,由于數(shù)據(jù)采樣時間不包括法定節(jié)假日,因此假設(shè)在數(shù)據(jù)采樣時間范圍內(nèi)人類行為不會出現(xiàn)較大的地理跨越異常,可使用清洗后的用戶訪問基站記錄數(shù)據(jù)進行合作復雜網(wǎng)絡(luò)建模。因此,網(wǎng)絡(luò)節(jié)點度分布應(yīng)符合冪律分布。

冪律分布表現(xiàn)了真實復雜網(wǎng)絡(luò)的一種自然形成的節(jié)點“排序”性質(zhì),由于本文主要研究的網(wǎng)絡(luò)類型為真實復雜網(wǎng)絡(luò),因此首先需要保證實驗過程中的數(shù)據(jù)節(jié)點度服從冪律分布。本文使用Python環(huán)境下的Powerlaw冪律擬合包[30]擬合建模后的復雜網(wǎng)絡(luò)節(jié)點度分布,擬合結(jié)果如圖5所示。可以看出,基站合作網(wǎng)絡(luò)建模得到的網(wǎng)絡(luò)節(jié)點度符合冪律分布特性。

圖5 復雜網(wǎng)絡(luò)節(jié)點度冪律擬合結(jié)果

4.3 社區(qū)劃分結(jié)果

將建模后的真實復雜網(wǎng)絡(luò)嵌入龐加萊圓盤,如圖6所示,可以看出,圓盤上出現(xiàn)明顯的密度分布不均的現(xiàn)象。

圖6 建模后復雜網(wǎng)絡(luò)嵌入龐加萊圓盤的結(jié)果

復雜網(wǎng)絡(luò)嵌入圓盤后,以角坐標為參考得到節(jié)點在圓盤上按角度分布的θ曲線。根據(jù)θ曲線求導,保證每兩個局部極小值中間存在一個局部極大值,并根據(jù)極值刪除規(guī)則選擇最優(yōu)模塊度下的極小值。θ曲線的最優(yōu)劃分結(jié)果如圖7所示,其中,橫坐標表示雙曲角度,縱坐標表示當前角度節(jié)點個數(shù)。

圖7 極小值劃分結(jié)果

4.4 實驗結(jié)果對比

針對真實復雜網(wǎng)絡(luò),將本文算法MHE與3種類型的社區(qū)發(fā)現(xiàn)算法進行對比,分別為在LPA上改進的SLPA算法[12]、基于函數(shù)優(yōu)化的Louvain算法[16]和基于譜聚類的正則化譜聚類社區(qū)發(fā)現(xiàn)算法[17]。

使用模塊度評估社區(qū)劃分的優(yōu)劣,計算MHE、Louvain、SLPA和正則化譜聚類算法對合作網(wǎng)絡(luò)社區(qū)劃分后的模塊度,如圖8所示。

圖8 4種算法的模塊度

由于本文合作網(wǎng)絡(luò)的物理含義體現(xiàn)了基站的相對地理位置,因此利用基站的真實經(jīng)緯度將MHE、Louvain、SLPA和正則化譜聚類算法將真實數(shù)據(jù)集的社區(qū)劃分結(jié)果投影在地圖上,如圖9所示。其中,Louvain為最優(yōu)化模塊度的方法,正則化譜聚類和Louvain的值類似,與本文算法模塊度的值都僅相差僅為0.04。模塊度評價僅考慮到網(wǎng)絡(luò)拓撲結(jié)構(gòu),可以看出:在實際應(yīng)用場景下,本文算法對社區(qū)進行了更細致的劃分,在地理位置上呈現(xiàn)出明顯的區(qū)域性,在區(qū)域劃分與地理位置上與該市的行政劃分基本吻合;Louvain和正則化譜聚類只是劃分出了大的區(qū)域,缺少細節(jié)劃分;MHE相較于Louvain和正則化譜聚類有更高的實際應(yīng)用價值;SLPA結(jié)果的模塊度相對較低,在合作網(wǎng)絡(luò)中有一部分節(jié)點未找到其歸屬社區(qū)。

圖9 4種算法的社區(qū)劃分可視化結(jié)果

Louvain首先將網(wǎng)絡(luò)中每個節(jié)點作為一個獨立的社區(qū),依次將每個節(jié)點分配到每個鄰居節(jié)點所在的社區(qū),計算分配前后的模塊度,取模塊度最優(yōu),該迭代過程與網(wǎng)絡(luò)節(jié)點個數(shù)相關(guān);SLPA是先對網(wǎng)絡(luò)中每個節(jié)點給定一個標簽,遍歷每個節(jié)點的鄰居確定當前鄰居,其計算過程和效果與迭代次數(shù)和網(wǎng)絡(luò)節(jié)點個數(shù)相關(guān),而迭代次數(shù)又明顯地影響了計算復雜度;正則化譜聚類基于矩陣運算,而矩陣運算與網(wǎng)絡(luò)規(guī)模關(guān)系緊密,本身對計算復雜度和空間復雜度要求都很高;雖然MHE的優(yōu)化目標也是最優(yōu)模塊度,但其優(yōu)化過程僅與θ曲線極小值點個數(shù)相關(guān),其復雜度主要體現(xiàn)在雙曲嵌入,而嵌入過程無需迭代,僅與節(jié)點個數(shù)線性相關(guān)。

5 結(jié)束語

在復雜網(wǎng)絡(luò)數(shù)據(jù)迅速增長的背景下,現(xiàn)有社區(qū)劃分算法難以在保留數(shù)據(jù)精度的基礎(chǔ)上準確選擇社區(qū)中心。針對該問題,本文提出一種基于雙曲空間嵌入的極小值社區(qū)劃分算法。將大型復雜網(wǎng)絡(luò)建模為圖的形式嵌入到二維雙曲空間模型——龐加萊圓盤中,利用圓盤上幾何對應(yīng)的物理意義對其中節(jié)點對應(yīng)角坐標的分布曲線進行極小值劃分,每兩個相鄰極小值之間為一個社區(qū)。本文算法應(yīng)用復雜網(wǎng)絡(luò)的雙曲模型理論,保留復雜網(wǎng)絡(luò)結(jié)構(gòu)特性,無需設(shè)定聚類中心,可根據(jù)優(yōu)化目標選擇最優(yōu)社區(qū)劃分結(jié)果?；谥袊苿佑脩粼L問記錄的真實數(shù)據(jù)對算法進行有效性評估,結(jié)果表明,該算法在真實復雜網(wǎng)絡(luò)中能夠取得較好的社區(qū)劃分效果。下一步將探究復雜網(wǎng)絡(luò)與雙曲幾何的映射關(guān)系,利用幾何方法簡化復雜網(wǎng)絡(luò)分析過程。