[發明專利]考慮社區結構穩定度和增量相關節點進行社區發現的方法

有效

• 申請號: 201710829612.5
• 申請日: 2017-09-14
• 公開（公告）號: CN107609982B
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 郭昆;郭文忠;陳羽中;牛玉貞;李國輝
• 申請（專利權）人: 福州大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種考慮社區結構穩定度和增量相關節點進行社區發現的方法，其特征在于，包括以下步驟：

步驟1：采用SLPA算法在網絡G₁上生成初始社區集NS₁；

步驟2：對任意社區c∈NS₁，設置社區c的初始權重wc(c,t₀)＝1.0；

步驟3：初始化迭代時刻iter＝2；

步驟4：計算t時刻相較于t-1時刻的增量相關節點集合IV_t；

步驟5：并行遍歷t時刻社區集NS_t中的每個社區，解散社區權重小于閾值wc_min的社區和社區規模小于閾值cs_min的社區，將被解散的社區內的節點加入IV_t；

步驟6：采用SLPA算法對集合IV_t中的節點進行社區劃分，生成新社區；

步驟7：并行遍歷每個新社區，解散社區規模小于cs_min的新社區，將被解散的社區內的節點從集合IV_t中刪除，加入剩余相關節點集合IV_t-rm，并將剩余的社區加入t-1時刻社區集NS_t-1；

步驟8：并行遍歷集合IV_t-rm中的每個節點，計算節點與相鄰社區的相似度，將其加入到相似度最高的社區，生成t時刻社區集NS_t；

步驟9：更新社區集NS_t中每個社區的穩定度和權重；

步驟10：計算社區集NS_t的社區結構穩定度S_m，如果社區結構穩定度S_m大于等于閾值S_min，則輸出社區集NS_t；否則，調用SLPA算法輸出社區集NS_t；

步驟11：判斷是否滿足迭代停止條件，是則計算結束，否則令迭代時刻iter加1，并返回步驟4；

在步驟9中，更新社區集NS_t中每個社區的穩定度和權重的步驟如下：

步驟9.1：為每個社區設置一個社區結構穩定度st(c,t)，社區結構穩定度st(c,t)的計算公式如式(3)所示：

其中，|·|表示集合大小，|e_c,t⁺|和|e_c,t^－|分別表示t時刻社區c的增加和減少的邊數，|v_c,t⁺|和|v_c,t^－|分別表示t時刻社區c的增加和減少的節點數，|NB(v)|表示t時刻與節點v歸屬同一社區的所有鄰居節點數；|E_c,t|和|E_c,t-1|分別表示t時刻和t-1時刻社區c邊的總數，|V_c,t|和|V_c,t-1|分別表示t時刻和t-1時刻社區c節點的總數；

步驟9.2：借鑒數據流聚類中的思想，引入衰減系數，以避免長期存在的歷史社區對新社區發現的影響；有些社區可能隨著時間的推移，社區穩定結構保持較好，則適當減慢其衰減速度，而有些社區較不穩定，則適當加快其衰減速度，社區的權重wc(c,t)的更新公式如(4)如示；

其中，0＜λ≤1表示權重衰減系數，t和t₀分別表示當前時刻與初始時刻，wc(c,t)表示t時刻社區c的權重；st(c,t)表示t時刻社區c的結構穩定度，當st(c,t)大于等于給定社區結構穩定度閾值st_min時，以倍速率進行衰減，否則，以倍速率進行衰減。