[發明專利]一種基于動態同步模型的社區檢測方法

有效

• 申請號: 201410717471.4
• 申請日: 2014-11-28
• 公開（公告）號: CN104346481B
• 公開（公告）日: 2018-01-16
• 發明（設計）人: 董學文;楊超;盛立杰;王超;姚青松;李興華;曾勇;姜奇
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q50/00
• 代理公司: 西安通大專利代理有限責任公司61200
• 代理人: 徐文權

1.一種基于動態同步模型的社區檢測方法，其特征在于，應用于社交網絡，包括以下步驟：

步驟A，構造網絡圖：讀取網絡數據，構造以用戶為節點，用戶關系為邊的網絡圖；

步驟B，網絡矢量化：將步驟A所得網絡圖中各節點通過OPTICS算法進行矢量化，將網絡中各節點映射到一個一維坐標序列中，為后續的同步聚類做準備，具體步驟為：

步驟B1，首先對網絡利用節點相似性描述網絡中鏈接密度，計算各邊(x，y)的節點相似度，定義

其中τ(x)表示節點x的鄰域，包含x和x的鄰居節點,τ(y)表示節點y的鄰域，包含y和y的鄰居節點；degree(x)表示節點x的度，degree(y)表示節點y的度；

步驟B2，利用節點相似度定義和OPTICS算法，獲得節點序列；

步驟B3，根據獲得的節點序列，將網絡中的每個節點平均映射到區間[0，1)上，每個節點對應一個一維坐標，即實現整個網絡的矢量化；

步驟C，執行同步聚類：設置初始同步參數ε，確定同步范圍，每個節點在其同步范圍內進行同步聚類，直至達到全局同步，根據同步坐標位置進行社區劃分，并計算該社區劃分的模塊度；不斷增加同步半徑，執行同步聚類，直至同步半徑覆蓋所有節點；

所述同步聚類和社區劃分包括如下步驟：

步驟C1，初始化同步參數ε值為ε₀，計算各節點x的ε–鄰域集合N_ε(x)和密切節點集合Close(x)，將兩個集合進行合并組成節點x的同步范圍R_ε(x)；

N_ε(x)＝{y∈X|dist(y,x)≤ε}

Close(x)＝{y∈X|V_xy∈top 20％of V_x}

R_ε(x)＝N_ε(x)∪Close(x)

其中，dist(y,x)表示節點x，y映射的一維坐標之間的距離；

步驟C2，使用擴展kuramoto模型使得每個節點x在其同步范圍R_ε(x)內進行同步；其中，擴展的kuramoto模型為：

lx(t+1)=lx(t)+1d·Σy∈Nϵ(x)Vxy·sin(ly-lx)·degree(x)+degree(y)maxDegree,]]>

maxDegree表示網絡中最大的度；

步驟C3，計算網絡序參數其中l_x表示節點x映射后的一維坐標；若序參數r_c≥0.9999，則結束同步過程，否則繼續執行步驟C2；

步驟C4，同步過程結束后，對各節點的一維坐標位置進行排序，若一維坐標系相鄰節點間距小于1.5/N，則表示相鄰節點同屬于一個社區，否則相鄰節點屬于不同社區；

步驟C5，根據社區劃分結果，根據經典模塊度計算方法，計算模塊度；

步驟C6，不斷增加同步參數ε，執行步驟C2，直至同步半徑覆蓋所有節點。