[發明專利]一種具有社團結構的網絡表示學習方法及裝置

在審

• 申請號: 202010723330.9
• 申請日: 2020-07-24
• 公開（公告）號: CN111860866A
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 何嘉林
• 申請（專利權）人: 西華師范大學
• 主分類號: G06N20/00
• 分類號: G06N20/00
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 李朝虎

本發明公開了一種具有社團結構的網絡表示學習方法，包括以下步驟：步驟1：數據收集與處理階段：使用一種密度函數，通過在網絡G上使用隨機游走策略，獲得頂點序列樣本S＝{s₁,s₂,...,s_n}；步驟2：數據表示學習階段：優化Skip?gram模型，使用Skip?gram模型來訓練頂點序列樣本S＝{s₁,s₂,...,s_n}，得到每個頂點序列的向量表示；步驟3：數據計算階段：對每個頂點序列的向量表示進行相似度計算，獲得社團劃分相似度。本發明方法不僅可以更好地捕獲網絡中的社團結構，并且可以在頂點分類任務中獲得更高的準確率。

技術領域

本發明涉及計算機技術領域，具體涉及一種具有社團結構的網絡表示學習方法及裝置。

背景技術

許多復雜系統可以抽象成網絡結構，而網絡結構通常由圖來表示，即由一組節點和一組連邊組成。對于小規模網絡，我們可以在它上面快速執行許多復雜任務，例如社團挖掘和多標簽分類。然而，對于大規模網絡(例如具有數十億個頂點的網絡)，在它上面執行這些復雜任務是一個挑戰。為了解決這個問題，我們必須找到另外一種簡潔而有效的網絡表示形式。網絡嵌入就是解決該問題的一種有效策略，即學習網絡中頂點的低維向量表示。對于每個頂點，我們將它們在網絡中的結構特征映射到低維空間向量，然后再將這些向量應用于網絡中的復雜任務。

在過去的幾年中，有人提出了許多刻畫網絡局部結構的網絡嵌入方法。DeepWalk方法通過使用截斷的隨機游走策略來刻畫網絡頂點的鄰域結構。Node2vec方法證明DeepWalk并不能捕獲網絡中連接模式的多樣性。它提出了一種偏向隨機行走策略，該策略結合了BFS和DFS思想來探索頂點鄰域信息。LINE方法主要應用于大規模網絡嵌入學習。它保留了高階的頂點鄰域結構，并可以很容易地擴展到數百萬個頂點。曹等人提出了一種深圖表示模型，該模型采用隨機沖浪策略來捕獲圖的結構信息。馮等人提出了“度懲罰”原則，該原則通過懲罰高度頂點之間的鄰近性來保留無標度屬性。王等人提出了一種半監督的深度模型，該模型能夠通過優化多層非線性函數來捕獲高度非線性的網絡結構。Yanardag等人提出了捕獲中層相似結構的通用框架。此外，他們還提出了一些用來保留全局網絡結構的方法。王等人提出了一個模塊化的非負矩陣分解模型，該模型保留了網絡中的社團結構。涂等人提出了一種啟發式的社團增強機制，該機制將社團結構信息映射到頂點向量表示中。陳等人提出了一種多層次的網絡表示學習范式，它通過重新捕獲初始網絡的全局結構，逐步將初始網絡合并為較小但結構相似的網絡。

發明內容

本發明所要解決的技術問題是現有技術中刻畫網絡局部結構的三種網絡嵌入方法不能更好地捕獲網絡中的社團結構，并且在頂點分類任務中不能獲得更高的準確率，目的在于提供一種具有社團結構的網絡表示學習方法及裝置，解決上述問題。

本發明通過下述技術方案實現：

一種具有社團結構的網絡表示學習方法，包括以下步驟：

步驟1：數據收集與處理階段：使用一種密度函數，通過在網絡G上使用隨機游走策略，獲得頂點序列樣本S＝{s₁,s₂,...,s_n}；

步驟2：數據表示學習階段：優化Skip-gram模型，使用Skip-gram模型來訓練頂點序列樣本S＝{s₁,s₂,...,s_n}，得到每個頂點序列的向量表示；

步驟3：數據計算階段：對每個頂點序列的向量表示進行相似度計算，獲得社團劃分相似度。

進一步地，一種具有社團結構的網絡表示學習方法，所述步驟1中，頂點序列樣本S＝{s₁,s₂,...,s_n}中頂點序列表示為s＝{v1,v2...,v|s|}。