[發明專利]基于隨機游走的網絡表示學習方法

在審

• 申請號: 201911178785.0
• 申請日: 2019-11-27
• 公開（公告）號: CN111126443A
• 公開（公告）日: 2020-05-08
• 發明（設計）人: 吳蓉暉;陳湘濤;朱寧波;孫穎;劉桃億
• 申請（專利權）人: 湖南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳市中原力和專利商標事務所(普通合伙) 44289
• 代理人: 胡國良

本發明提供了一種基于隨機游走的網絡表示學習方法，包括如下步驟：建立NSRW模型，所述NSRW模型表示為函數G＝(V,E)，其中V＝{v₁,v₂,…v_n}代表節點，用于表示網絡中的實體；E＝{e₁,e₂,…e_n}代表邊，用于表示網絡中實體之間的關系；計算網絡中相鄰兩個節點的相似度，相鄰兩個節點的相似度計算公式為：其中n_ab表示節點v_a和節點v_b之間共同鄰居的數量，k_a和k_b分別代表節點v_a和節點v_b的節點度；根據所述相似度計算相鄰節點之間的游走概率；根據所述游走概率進行隨機游走生成節點序列；根據所述節點序列，進行節點的表示學習，得到節點的低維表示。本發明提供的網絡表示學習方法分類更加精確。

【技術領域】

本發明涉及網絡表示學習領域，尤其涉及一種基于隨機游走的網絡表示學習方法。

【背景技術】

網絡節點分類是網絡分析領域的一項主要任務，并且已經有很多研究成果，例如支持向量機(Support Vector Machine，SVM)與基于規則的分類器(Rule-basedclassifier，RBC)的結合、決策樹和CRFs聯合優化模型以及基于隨機圖的半監督網絡分類方法等。但是，其中大多數方法著重于使用近似推斷改善分類結果，難以處理網絡稀疏性問題。

網絡表示學習(Network representation learning，NRL)提供了解決上述問題的有效方法。NRL將網絡節點轉換為低維實值向量并最大程度地保留網絡拓撲結構，在得到低維向量后，應用現有的機器學習方法簡單高效的執行網絡分類任務。

相關技術中，DeepWalk算法是NRL算法中較為常用的算法，其使用隨機游走生成節點序列并通過Skip-Gram模型得到網絡中每個頂點的向量表示；但是，該種算法忽略了不同節點鏈接的相似度，在采樣過程中，任何節點的游走概率相同，使得分類的精確性不高。

因此，有必要提供一種新的基于隨機游走的網絡表示學習方法來解決上述問題。

【發明內容】

為解決上述技術問題，本發明提供了一種依據節點相似度進行采樣，提高分類精確度的基于隨機游走的網絡表示學習方法。

本發明的技術方案在于：一種基于隨機游走的網絡表示學習方法，包括如下步驟：

建立NSRW模型，所述NSRW模型表示為函數G＝(V,E)，其中V＝{v₁,v₂,…v_n}代表節點，用于表示網絡中的實體；E＝{e₁,e₂,…e_n}代表邊，用于表示網絡中實體之間的關系；

計算網絡中相鄰兩個節點的相似度，相鄰兩個節點的相似度計算公式為：其中n_ab表示節點v_a和節點v_b之間共同鄰居的數量，k_a和k_b分別代表節點v_a和節點v_b的節點度；

根據所述相似度計算相鄰節點之間的游走概率；

根據所述游走概率進行隨機游走生成節點序列；

根據所述節點序列，進行節點的表示學習，得到節點的低維表示。

優選的，根據所述節點序列，進行節點的表示學習，得到節點的低維表示步驟具體為：所述節點序列代入到Skip-Gram模型中獲得節點的向量表示。