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

謝 菁,羿舒文,張 毅

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

0 概述

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

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

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

1 相關研究

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

社區劃分在復雜網絡分析中具有重要的社會意義和應用價值。現有的社區劃分算法主要有基于圖論的算法、基于層次聚類的算法和基于函數優化的算法。基于圖論的經典算法有K-L算法[9]和基于圖拉普拉斯矩陣特征向量的譜平分算法[10],但由于K-L算法和譜平分算法均為二分算法,因此不適用于包含較多團簇的復雜網絡。為檢測多社區結構網絡,研究者提出基于圖半監督學習的標簽傳播算法LPA[11]和基于LPA的SLPA算法[12]。基于圖論的方法涉及矩陣計算,其計算對硬件要求很高,因此,難以適用于大型網絡。基于層次聚類的經典算法有GN算法[13],但因為GN算法不適用于大型復雜網絡,研究者進而提出基于貪婪的FGN[14]算法,同時定義了重要社區劃分評價指標的模塊度。基于函數優化的社區劃分算法,例如極值優化算法[15],通過求解模塊度最優解進行社區劃分,也有基于最優模塊度提出通過多次迭代最大化模塊度進行社區劃分的Louvain社區發現算法[16]。文獻[17]在譜聚類的基礎上進行修正,提出了正則化譜聚類算法。

2 復雜網絡與雙曲空間

2.1 復雜網絡和社區

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

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

2.2 雙曲空間

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

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

(1)

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

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

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

圖1 二維雙曲圓盤幾何性質

2.3 問題描述

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

(2)

(3)

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

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

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

3 基于雙曲嵌入的極小值社區劃分

本文將已知連接關系無權無向的真實復雜網絡嵌入到二維雙曲空間模型——龐加萊圓盤[20]中。二維龐加萊圓盤擁有3個基本參數:徑坐標r,角坐標θ和溫度T。溫度參數用來調整圓盤潛在幾何分布,當T→0時,雙曲空間越穩定,相應的T越高,雙曲空間的隨機性越高,一般根據經驗將T設置為0.1。根據龐加萊圓盤的雙曲幾何性質掃描嵌入復雜網絡的圓盤,得到節點對應角坐標的分布曲線,并對曲線按極小值劃分,得到社區劃分結果。

3.1 復雜網絡建模

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

3.2 雙曲嵌入

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

圖2 復雜網絡嵌入龐加萊圓盤示意圖

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

(4)

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

(5)

其中,deg(i)表示節點i在復雜網絡中的度,R表示龐加萊圓盤半徑。

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

(6)

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

3.3 極小值劃分

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

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

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

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

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

3.4 最優劃分條件

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

(7)

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

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

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

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

(8)

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

L=max(QK)

(9)

3.5 基于雙曲嵌入的極小值社區劃分

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

輸入節點id,節點id對應節點屬性,節點個數n

輸出社區劃分結果

//步驟1:根據節點屬性建模復雜網絡

for i in range(n):

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

if節點i和節點j相似

連接節點i和節點j

根據節點的連接信息得到網絡中每個節點的度

for i in range(n):

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

if節點i和節點j相似

連接節點i和節點j

根據節點的連接信息得到網絡中每個節點的度

//步驟2:雙曲嵌入

降序排列節點度,生成新的節點順序

while i

按節點新順序根據雙曲坐標計算公式計算每個節點的ri和θi

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

//步驟3:社區發現

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

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

保存θi為極小值

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

優化目標L=max(QK)得到相應極小值序列

return劃分社區和社區個數

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

4 實驗與結果分析

4.1 數據集描述

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

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

表1 基站用戶數據

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

表2 基站經緯度數據

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

4.2 冪律擬合

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

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

圖5 復雜網絡節點度冪律擬合結果

4.3 社區劃分結果

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

圖6 建模后復雜網絡嵌入龐加萊圓盤的結果

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

圖7 極小值劃分結果

4.4 實驗結果對比

針對真實復雜網絡,將本文算法MHE與3種類型的社區發現算法進行對比,分別為在LPA上改進的SLPA算法[12]、基于函數優化的Louvain算法[16]和基于譜聚類的正則化譜聚類社區發現算法[17]。

使用模塊度評估社區劃分的優劣,計算MHE、Louvain、SLPA和正則化譜聚類算法對合作網絡社區劃分后的模塊度,如圖8所示。

圖8 4種算法的模塊度

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

圖9 4種算法的社區劃分可視化結果

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

5 結束語

在復雜網絡數據迅速增長的背景下,現有社區劃分算法難以在保留數據精度的基礎上準確選擇社區中心。針對該問題,本文提出一種基于雙曲空間嵌入的極小值社區劃分算法。將大型復雜網絡建模為圖的形式嵌入到二維雙曲空間模型——龐加萊圓盤中,利用圓盤上幾何對應的物理意義對其中節點對應角坐標的分布曲線進行極小值劃分,每兩個相鄰極小值之間為一個社區。本文算法應用復雜網絡的雙曲模型理論,保留復雜網絡結構特性,無需設定聚類中心,可根據優化目標選擇最優社區劃分結果。基于中國移動用戶訪問記錄的真實數據對算法進行有效性評估,結果表明,該算法在真實復雜網絡中能夠取得較好的社區劃分效果。下一步將探究復雜網絡與雙曲幾何的映射關系,利用幾何方法簡化復雜網絡分析過程。