[發明專利]網絡中重疊社團的挖掘方法

有效

• 申請號: 201710419287.5
• 申請日: 2017-06-06
• 公開（公告）號: CN107133877B
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 孫麗萍;羅永龍;劉君;鮑舒婷;鄭孝遙;陳付龍
• 申請（專利權）人: 安徽師范大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 蕪湖安匯知識產權代理有限公司 34107
• 代理人: 朱圣榮

1.網絡中重疊社團的挖掘方法，其特征在于：

對社團結構數據進行處理，根據社團整體結構動態調整社團結構數據的種子分布，包括以下步驟：

步驟1、種子選擇階段：在定義種子選擇的過程中根據社團結構自適應產生最優的種子；

步驟2、種子擴展階段：利用個性化PageRank算法，并根據社團和種子頂點間的關系進行種子擴展，覆蓋網絡多數頂點；

步驟3、社團擴展階段：將未覆蓋的頂點自適應劃分到鄰近社團中，完成社團劃分；

所述步驟1包括以下步驟：

步驟1.1、記G(V,E)為無向圖，頂點集記為V＝{v₁,v₂,...v_N}，對應N個頂點和邊集將頂點按照度從大到小排序，并對其進行1到n編號，計算頂點v_i的度degree(v_i)，初始化i＝1；

步驟1.2、記Coverage_i-1包含第i次迭代時生成的種子集及它們的鄰接點；

定義式：Coverage_i＝s_i∪neighbor(s_i)∪Coverage_i-1；其中s_i表示第i次迭代時選擇的種子，neighbor(s_i)表示s_i的鄰接點，n為迭代的次數；

如果頂點v_i不存在于第i-1次迭代時生成的種子集及它們的鄰接點集合Coverage_i-1中，則利用式Seed_i＝s_i∪Seed_i-1,i＝1,2,……n，計算第i次迭代時生成的種子集Seed_i，將頂點v_i加入種子集Seed_i中，并計算Coverage_i，將頂點v_i和它的鄰接點和上一次迭代生成的Coverage_i-1加入集合Coverage_i中；

步驟1.3、利用頂點覆蓋增長率GrowthRate_i控制種子的數量；

再通過計算頂點覆蓋增長率GrowthRate_i，其中size(Coverage_i)是Coverage_i中元素的個數；

如果GrowthRate_i＞η，表明還有頂點可以加入種子集，i＝i+1，找到序列中的下一個頂點，并循環步驟1.2和步驟1.3，若條件不滿足，則進入步驟1.4；

步驟1.4、將上一次迭代的種子集Seed_i-1復制到Seed_all，Seed_all就是選擇完畢的種子集；

所述步驟2包括以下步驟：

步驟2.1、基于種子選擇階段，已經得到初步種子集Seed_all，記α為傳送概率，ε為隨機游走的誤差，初始化count＝1，對于Seed_all中所有種子s_count按順序進行擴展；

步驟2.2、利用T←{s_count}∪{neighbor(s_count)}將s_count及它的鄰接點neighbor(s_count)加入集合T中，尋找s_count的鄰接點中是否存在可能的種子；

步驟2.3、設X_i＝{x_1i,x_2i,...,x_ni}為page-rank算法第i次隨機游走后的Page-Rank向量，向量R_i＝{r_1i,r_2i,...,r_ni}為每個頂點第i次隨機游走時的啟動向量，之后對于點集合V中的任意頂點v，頂點v在第1次隨機游走后的概率x_v1＝0，對于集合V/T中的任意頂點v，頂點v在第1次隨機游走后啟動向量的概率r_v1＝0，對于集合T中的任意頂點v，頂點v在第1次隨機游走后啟動向量的概率最后令i＝1；

步驟2.4、如果此時滿足r_vi＞degree(v)·ε；

利用計算頂點v在第i+1次隨機游走后的概率x_v(i+1)，對于邊集合E中所有與v相連的邊(v,u)；

利用r_ui＝r_u(i-1)+(1-α)r_v(i-1)/2degree(v)計算頂點u在第i+1次隨機游走后啟動向量的概率r_u(i+1)，其中α為傳送概率，ε為隨機游走的誤差，兩者取值位于(0,1]之間；

利用r_vi＝(1-α)r_v(i-1)/2計算頂點v在第i+1次隨機游走后啟動向量的概率r_v(i+1)；

之后對點集V中的下一個頂點進行計算，如果此時還滿足r_vi＞degree(v)·ε條件，則循環步驟2.4，若干不滿足，則進入步驟2.5；

步驟2.5、對于點集合V中所有頂點v，如果就將該頂點作為新種子加入C_count；

步驟2.6、將C_count加入社團集合C中，繼續從步驟2.1開始從Seed_all下一個種子進行種子擴展，直到遍歷完Seed_all中的所有種子；

所述步驟3包括以下步驟：

步驟3.1、基于種子擴展階段生成的社團集合C，將C中的每個社團C_i復制給C'_i，最終保存在社團集合C'中；

步驟3.2、對于在點集合V不在集合C中的頂點，即沒有被劃分到任何一個社團中的剩余頂點v，利用Remain←Remain∪{v}將頂點加入到剩余集合Remain中；

步驟3.3、對于剩余集合Remain中的頂點v，如果v存在至少有一個鄰接點u屬于簇類中，利用C'_i←C'_i∪{v}將v與u所在的社團合并，否則，說明v是離群點，其所有鄰接點也都未被覆蓋，利用C'_M+1←{v}∪{neighbor(v)}將頂點v與它的鄰接點合并形成一個新社團。