[發明專利]一種基于邊圖隨機游走的重疊社區發現方法

有效

• 申請號: 201510046401.5
• 申請日: 2015-01-29
• 公開（公告）號: CN104537126B
• 公開（公告）日: 2017-12-01
• 發明（設計）人: 鄧曉衡;李更好;桂勁松;劉安豐;沈海瀾;李登
• 申請（專利權）人: 中南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中南大學專利中心43200
• 代理人: 胡燕瑜

1.一種基于邊圖隨機游走的重疊社區發現方法，其特征在于包括以下步驟：

步驟1)，計算有權邊圖LG的權值矩陣H，具體步驟如下：

步驟1-1)根據復雜網絡中成員與成員之間的關系構建一個相互連接的無向圖G＝(V，E)，V代表成員節點的集合，E代表成員間的邊集合；假定網絡圖中總的節點數為N,邊數為M，A＝[a_ij]為無向圖G的鄰接矩陣，若節點i與節點j相連，則a_ij＝1，反之a_ij＝0；W＝[w_ij]則為無向圖G的權值矩陣，其中w_ij表示無向邊(i，j)的權值；節點i的強度s_i等于與節點i相連的所有邊的權值之和，即s_i＝∑_jw_ij；若網絡為無向無權圖，則W＝A，每條邊的權值為1；

步驟1-2)對無向圖G中的邊進行編號，并記錄連接關系及權值，建立無向圖G的關聯矩陣B；關聯矩陣B＝[b_iα]是一個N×M的矩陣，元素b_iα表示邊α占節點i強度的大小，計算公式為：

步驟1-3)構建有權邊圖LG，計算其權值矩陣H：有權邊圖LG中M個節點代表無向圖G的M條邊,兩點之間的邊表示無向圖G中相應的兩條邊有公共頂點；其權值矩陣H＝[h_αβ]是一個M×M的矩陣，通過關聯矩陣B計算得到，計算公式為：

其中，節點的強度s_i＝∑_jw_ij＝∑_αb_iα；權值矩陣H是一個對稱矩陣且含有自環，表明隨機游走者不僅僅可以進行邊到邊的游走，還可以在一條邊的兩個端點間游走，更符合實際情況；

步驟2)，在有權邊圖LG上進行隨機游走，計算有權邊圖LG中節點之間的距離D，聚類獲得邊社區C_L，具體步驟如下：

步驟2-1)在有權邊圖LG上進行長度為T的隨機游走，計算并記錄每一步t的轉移概率，1≤t≤T；其中，一步轉移概率矩陣P＝[p_αβ]由權值矩陣H計算而得，計算公式為：

步驟2-2)對T步內的轉移概率進行累加,得到無向圖G中任意兩邊的相似度σ_αβ，

其中，[P^t]_αβ表示從邊α出發經過t步到達邊β的轉移概率；

步驟2-3)對相似度進行歸一化處理，得到無向圖G中任意兩邊的距離d_αβ，

其中，maxσ_αβ，minσ_αβ分別表示最大和最小的距離；

步驟2-4)根據average-linkage聚類方法對距離進行處理，生成一個有層次的樹狀圖；設定社區數目為q，將網絡的邊劃分成q個子集，即邊社區C_L＝{P₁，...，P_q}；

隨機游走的長度T是一個經驗值，當取T＝1時，則邊圖LG中只有相鄰節點對之間的相似度非零；當T增大時，節點之間的相似度發生相應的變化；不同的T值會產生不同的聚類樹，利用最大化共表型相關系數來得到合適的T，的定義如下，

其中，d_ij為D中i到j的距離，z_ij為聚類方法產生的i到j的cophenetic距離，分別為它們的平均值；

步驟3)，將邊社區轉化為節點社區；

C_L＝{P₁，...，P_q}表示網絡的邊被劃分成的q個邊社區，定義網絡中的節點u受到來自邊社區P_C的吸引度為：

其中，(u，v)表示初始無向圖G的一條邊，u，v是該邊的兩個端點，s_u＝∑_vw_uv為節點u的強度，表示邊社區P_c內含有端點u的邊的權值之和；吸引度表示邊社區P_c內含有端點u的邊的權值之和占節點u的強度的比例，若吸引度越大，則表示節點u被邊社區P_c吸引的程度越強烈；根據定義可知當時代表u與P_c沒有吸引，即u與P_c之間不存在連接；當時代表u完全被P_c吸引，即u在P_c內部；只要考慮處于邊社區之間的邊緣節點受到的吸引度，就能將邊社區轉化成節點社區，方法如下：

步驟3-1)找出邊社區之間的邊緣節點，邊緣節點的表達式如下：

edge-node＝{u|(u，v)∈P_c，(u，w)∈P_d，l≤c＜d≤q}

其中，(u，v)和(u，w)分別代表屬于不同邊社區的邊，u，v，w代表不同的節點；

步驟3-2)為了避免重疊節點數目過多，利用邊緣節點受到的吸引度來調節重疊節點的數目；

若邊緣節點u受到的最大吸引度I_max來自于邊社區P_m，1≤m≤q，它滿足條件

且P_m唯一，

則將邊緣節點u納入邊社區P_m，反之，邊緣節點u仍為重疊節點；

閾值δ的范圍為[0，1]，δ越小，條件越容易滿足，重疊節點數目減少的越多；相反δ越大，條件越難滿足，重疊節點數目減少的越少；通常取δ＝1/2，即邊緣節點受到的唯一最大吸引度大于0.5，則邊緣節點可納入對應的社區；若為無向無權圖，則表示與邊緣節點u相連的邊有一半都在這個邊社區里；

大部分節點都被納入邊社區C_L，小部分不能納入的成為重疊節點，最終發現的社區是允許節點重疊的。