[發明專利]一種融合多粒度社區信息的網絡嵌入方法

在審

• 申請號: 202011624828.6
• 申請日: 2020-12-30
• 公開（公告）號: CN112910680A
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 胡軍;許正康;鐘福金;張清華
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 重慶輝騰律師事務所 50215
• 代理人: 盧勝斌

本發明屬于復雜網絡分析技術，特別涉及一種融合多粒度社區信息的網絡嵌入方法，包括：構建無向網絡；使用Louvain算法獲得不同粒度下的網絡以及相應的社區劃分；使用DeepWalk學習初始節點嵌入；將社區內的所有節點的嵌入進行加權平均，得到相應社區的嵌入；利用社區嵌入來調整節點嵌入，即通過最大化節點屬于所屬社區的條件概率，使得節點嵌入與節點所屬社區的社區嵌入相似，將社區信息融合進節點嵌入當中；將所有社區粒度下節點嵌入進行拼接，得到最終網絡嵌入，并應用于下游任務。本發明通過聯合多粒度社區下的節點嵌入，可以捕獲不同粒度下的社區信息，提高下游任務的準確率。

技術領域

本發明屬于復雜網絡分析技術，特別涉及一種融合多粒度社區信息的網絡嵌入方法。

背景技術

由于網絡規模的飛速增長，網絡中蘊含的信息也越來越豐富，網絡表示學習受到越來越多的關注，同時也產生了許多領域相關的方法。這些方法一般可以分為三種，分別為基于矩陣分解的網絡表示方法，基于神經網絡的網絡表示方法，以及基于Skip-Gram模型的網絡表示方法。上述方法通常只考慮了網絡的局部信息，忽視了全局信息，比如社區信息。

由于網絡中社區的重要性，近些年一些學者在網絡嵌入時開始考慮對社區信息進行保留。一般的保留社區信息的嵌入方法都是在節點嵌入上進行聚類，根據聚類結果(社區劃分)來重新調整原本的節點嵌入結果，其思想如圖1所示。但這些方法都只關注網絡最終的社區結構，沒有考慮到社區的多粒度特性。為此，本發明利用社區發現算法得到多粒度社區結構，提出可以融合多粒度社區信息的網絡嵌入方法。

發明內容

為了解決現有網絡嵌入方法無法有效利用網絡潛在的多粒度社區信息，本發明提出一種融合多粒度社區信息的網絡嵌入方法，該方法具體包括以下步驟：

S1、構建無向網絡G(V，E)，V為網絡G的節點集合，E為網絡G的邊集；

S2、使用Louvain算法獲得不同粒度下的網絡以及相應的社區劃分，表示為(G¹，C¹)，...，(G^T，C^T)；

S3、使用DeepWalk最大化通過中心節點預測上下文節點的條件概率，來學習初始節點嵌入；

S4、將社區內的所有節點的嵌入進行加權平均，得到相應的社區嵌入；

S5、利用社區嵌入來調整節點嵌入，即通過計算節點屬于所屬社區的條件概率，使得節點嵌入與節點所屬社區的社區嵌入相似，將社區信息融合進節點嵌入；

S6、將所有社區粒度下節點嵌入進行拼接，得到最終網絡嵌入，并應用于下游任務。

進一步的，使用Louvain算法獲得不同粒度下的網絡以及相應的社區劃分，過程包括：

遍歷網絡中所有節點，計算將節點劃分到其鄰居節點的所在社區的模塊度增益，并將其劃分到最大正向增益的對應社區；

重新構造網絡，將所有同一社區內的節點合并為新網絡中的節點；

將新網絡中節點內部權重更新為合并節點集合內部權重的總和、新網絡中節點之間的邊權重更新為兩個節點對應社區間連接邊上的權重總和；

重復以上步驟，直到模塊度不再發生改變，將不同粒度下構建的網絡與社區劃分輸出。

進一步的，最大化通過中心節點預測上下文節點的條件概率包括：

使用截斷隨機游走來捕獲網絡結構信息，得到游走路徑集合S＝{s₁，s₂，...，s_n}，其中s_i＝{v_i，...}表示以節點v_i為起始節點的節點序列；