一種基於層次聚類的複雜網絡社區劃分方法
2023-11-11 22:34:07
一種基於層次聚類的複雜網絡社區劃分方法
【專利摘要】一種基於層次聚類的複雜網絡社區劃分方法，從全局中心節點建立初始社區，再根據聯繫緊密程度一層一層地擴展社區，最後把一些過小的社區融合到大社區中。初始化社區過程為：選取度數最大的k個節點，按照節點的相似度合成若干個社區。擴展社區過程首先標記所有節點的層數，然後根據節點與社區的連結強度把節點分到相應的社區中。融合小社區過程首先要確定小社區的大小，計算小社區中的每個節點v的相鄰節點與每個大社區C的公共節點個數，將v重新劃分到公共節點數最大的社區中。選取最優結果過程要做10次試驗，根據擴展模塊度選出最終結果。本發明不需要預先知道社區數目，時間複雜度為O(m)，可以處理大型複雜網絡，提高了社區劃分的準確度。
【專利說明】一種基於層次聚類的複雜網絡社區劃分方法
【技術領域】
[0001] 本發明涉及一種複雜網絡社區劃分方法，特別涉及一種基於層次聚類的社區劃分 方法。
【背景技術】
[0002] 複雜網絡一般指節點眾多、連接關係複雜的網絡，如全球資訊網、論文引用網絡、在線 社交網絡、人際交往關係網絡以及新陳代謝網絡等。近年來，隨著網際網路的發展和普及，對 複雜網絡的研究越來越多。對複雜網絡的研究表明，複雜網絡中存在社區結構,社區內部的 聯繫很緊密，而不同社區之間的聯繫則相對較少。社區是具有共同愛好或相似屬性的群體， 因此找出社區有助於我們挖掘複雜網絡中一些有用的信息，如複雜網絡中哪些人群具有相 同的愛好以及具有不同愛好的人群之間的聯繫情況等。如何將一個複雜網絡劃分成若干個 社區是近年來的一個研究熱點。
[0003] 目前已經有很多社區劃分方法，各有優劣。常見的社區劃分方法主要有基於圖論 的方法和基於層次聚類的方法。基於圖論的方法是比較早期的方法，其主要思想是將網絡 劃分成k個大致相同大小的部分，使得每一部分內部聯繫緊密，而不同部分之間的聯繫較 少。該類方法的代表方法有Kernighan-Lin方法、基於拉普拉斯圖特徵值的譜平分法等。基 於層次聚類的方法是目前比較常見的方法。該類方法屬於社會學的方法，主要是分析社會 網絡之間的相似性或邊之間連接的強度。基於層次聚類的方法又可以分為凝聚方法和分裂 方法兩種類型，劃分的依據是在網絡中加邊還是去邊，加邊的是凝聚方法，而去邊的則是分 裂方法。該類方法的代表方法有GN方法、CNM方法、Newman快速方法等。
[0004] 通常來說，網絡中有多少個社區是很難預先知道的，但是有些方法，如 Kernighan-Lin方法、基於拉普拉斯圖特徵值的譜平分法，卻需要先確定社區的數目。有些 方法的時間複雜度非常高，難以處理大型的網絡，比如GN方法的時間複雜度為0(m2n)、CNM 方法的時間複雜度為〇(mdInn)、Newman快速方法的時間複雜度為0((m+n)n)。也有一些 方法的時間複雜度達到〇(m)。
[0005] 綜上，現有技術存在的缺點有：需要預先知道社區的數目，而實際上很難預先知道 社區的數目；方法的時間複雜度和空間複雜度較高，難以處理大型複雜網絡；劃分出的社 區結果與真實社區偏差較大。
【發明內容】
[0006] 本發明要解決的技術問題是：本發明提出了一種基於層次聚類的社區劃分方法， 從全局中心節點建立初始社區，再根據聯繫緊密程度一層一層地擴展社區，最後把一些過 小的社區融合到大社區中，不需要預先知道社區數目，時間複雜度為〇(m)，可以方便地處理 大型複雜網絡。
[0007] 本發明解決其技術問題所採用的技術方案：一種基於層次聚類的複雜網絡社區劃 分方法，包括初始化社區、擴展社區、融合小社區以及選取最優結果四部分。一座城市會有 一個或多個中心地區，圍繞著中心一環一環向外擴展。類比城市的結構，社區應該由一個或 多個中心節點，圍繞中心節點一層一層向外擴展。中心節點在該社區中的度數最大，中心節 點作為第一層，第n層的節點主要與第n層和第n-1層的節點相連。
[0008] 初始化社區過程首先要選取全局中心節點，即度數最大的k個節點。然後將這k 個節點按照節點的相似度合成若干個社區。節點V和社區C的中心節點w的相似度計算方 法如下：
[0009；
【權利要求】
1. 一種基於層次聚類的複雜網絡社區劃分方法，其特徵在於：包括初始化社區、擴展 社區、融合小社區以及選取最優結果四個過程，從全局中心節點建立初始社區，再根據聯繫 緊密程度一層一層地擴展社區，最後把一些過小的社區融合到大社區中； 所述初始化社區過程為： 在複雜網絡中，與節點相連的所有節點的個數稱為該節點的度數，將複雜網絡中的所 有節點按照節點的度數降序排列，選取度數最大的k個節點，再將度數最大的節點劃分到 第一個社區，並作為第一個社區的中心節點，計算剩下k-1個節點中的每個節點V與每個社 區c的中心節點W的相似度，當相似度大於某個閾值n時，將節點V劃分到社區c中，否則 將節點V作為新社區的中心節點； 所述擴展社區過程為： 初始化社區後，標記所有節點的層數，初始化社區過程中選中的節點作為第1層，將所 有與第n層節點相連的未標記層數的節點標記為第n+1層節點，n為大於O的自然數，直到 所有節點被標記，擴展初始社區的第n層，對標記為第n層的每個節點V，計算節點V與每個 社區C的連結強度，若節點V與社區C的連結強度最大，將節點V劃分到社區C中，直到所 有節點都分到某個社區中； 所述融合小社區過程為： 若一個社區包含的節點數目小於t = max {5, HiaxtlCi I}/10}，則稱其為小社區，其中 max表示最大值，max {I Ci I}表示複雜網絡中所有社區的節點數目的最大值；擴展社區後，需 要把小社區融合到大社區中；計算小社區中的每個節點V的相鄰節點與每個不是小社區的 社區C的公共節點個數，若節點V的相鄰節點與社區C的公共節點個數達到最大，將節點V 重新劃分到社區C中； 所述選取最優結果過程為： 對初始化社區過程中的相似度閾值n從〇. 1到1，以〇. 05-0. 1作為步長，重複上述三 個過程做10-20次試驗，對每一次試驗的劃分結果計算擴展模塊度eQ，選取使得eQ最大的 劃分結果作為最終劃分結果。
2. 根據權利要求1所述的基於層次聚類的複雜網絡社區劃分方法，其特徵在於：所述 初始化社區過程中選取度數最大的k個節點的具體過程為： k = max {k1； k2} k: = n/10+2 k2 = I {v I d (v) > max {d (v)} /2} 其中，max表示最大值，n為網絡中的節點個數，d(v)表示節點v的度數。
3. 根據權利要求1所述的基於層次聚類的複雜網絡社區劃分方法，其特徵在於：所述 初始化社區過程中計算剩下k-1個節點中的每個節點V與每個社區C的中心節點w的相似 度的公式為：
其中L(V) = Adj (V) U {v}，Adj (V)表示與節點V相連的節點的集合。
4. 根據權利要求1所述的基於層次聚類的複雜網絡社區劃分方法，其特徵在於：所述 擴展社區過程中計算節點V與每個社區C的連結強度的公式是：
其中，d[v] [C]表示節點V和社區C之間的邊的數目。
5.根據權利要求1所述的基於層次聚類的複雜網絡社區劃分方法，其特徵在於：所述 擴展模塊度eQ的計算方法如下：
其中，Ci為網絡中的社區，Clin(Ci)表示社區Ci中邊的數目，Cl ext(Ci)表示社區Ci和其他 社區之間邊的數目，m表示網絡中邊的數目，en表示社區Ci中邊的數目佔網絡中邊的數目 的比例，ai表示與社區Ci中的節點相連的邊的數目佔網絡中邊的數目的比例。
【文檔編號】G06F19/00GK104361235SQ201410650818
【公開日】2015年2月18日 申請日期:2014年11月15日 優先權日:2014年11月15日
【發明者】殷傳濤, 朱帥兵, 張笑顏, 吳念念, 管明輝 申請人:北京航空航天大學