[發(fā)明專利]一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法

在審

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

1.一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，具體包括以下步驟：

S1、構(gòu)建無向網(wǎng)絡G(V，E)，V為網(wǎng)絡G的節(jié)點集合，E為網(wǎng)絡G的邊集；

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

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

S4、將社區(qū)內(nèi)的所有節(jié)點的嵌入進行加權(quán)平均，得到相應社區(qū)的嵌入；

S5、利用社區(qū)嵌入來調(diào)整節(jié)點嵌入，即通過最大化節(jié)點屬于所屬社區(qū)的條件概率，使得節(jié)點嵌入與節(jié)點所屬社區(qū)的社區(qū)嵌入相似，將社區(qū)信息融合進節(jié)點嵌入；

S6、將所有社區(qū)粒度下節(jié)點嵌入進行拼接，得到最終網(wǎng)絡嵌入，并應用于下游任務。

2.根據(jù)權(quán)利要求1所述的一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，使用Louvain算法獲得不同粒度下的網(wǎng)絡以及相應的社區(qū)劃分，過程包括：

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

重新構(gòu)造網(wǎng)絡，將所有同一社區(qū)內(nèi)的節(jié)點合并為新網(wǎng)絡中的節(jié)點；

將新網(wǎng)絡中節(jié)點內(nèi)部權(quán)重更新為合并節(jié)點集合內(nèi)部權(quán)重的總和、新網(wǎng)絡中節(jié)點之間的邊權(quán)重更新為兩個節(jié)點對應社區(qū)間連接邊上的權(quán)重總和；

重復以上步驟，直到模塊的度不再發(fā)生改變，將不同粒度下構(gòu)造的新網(wǎng)絡與社區(qū)劃分輸出。

3.根據(jù)權(quán)利要求1所述的一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，最大化通過中心節(jié)點預測上下文節(jié)點的條件概率包括：

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

對于節(jié)點序列s_i中任意節(jié)點，根據(jù)窗口大小，生成中心-上下文節(jié)點對；

根據(jù)Skip-Gram模型，使用DeepWalk最大化通過中心節(jié)點預測上下文節(jié)點的條件概率。

4.根據(jù)權(quán)利要求3所述的一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，通過中心節(jié)點預測上下文節(jié)點的條件概率表示為：

其中，p(v_j|v_i)表示通過中心節(jié)點v_i預測上下文節(jié)點v_j的條件概率；φ_i為節(jié)點i的嵌入，φ′_j為節(jié)點j的上下文嵌入。

5.根據(jù)權(quán)利要求4所述的一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，使用負采樣策略對通過中心節(jié)點v_i預測上下文節(jié)點v_j的條件概率進行優(yōu)化，即最小化節(jié)點v_i和v_j之間的目標函數(shù)，得到初始網(wǎng)絡嵌入φ⁰，節(jié)點v_i和v_j之間的目標函數(shù)為：

其中，O₁為優(yōu)化后的節(jié)點v_i和v_j之間的目標函數(shù)；K為負采樣的個數(shù)；表示通過噪聲分布P_n(v)采樣出節(jié)點v_k所計算的期望值，d_v表示節(jié)點的度數(shù)；φ_i為節(jié)點v_i的節(jié)點嵌入；φ′_k為負采樣節(jié)點的上下文嵌入。

6.根據(jù)權(quán)利要求1所述的一種融合多粒度社區(qū)信息的網(wǎng)絡嵌入方法，其特征在于，通過對t粒度網(wǎng)絡中第i個節(jié)點的合并節(jié)點對應的社區(qū)嵌入進行加權(quán)平均，得到t-1粒度網(wǎng)絡中第i個社區(qū)的社區(qū)嵌入。