[發明專利]一種基于路徑回溯圖嵌入的群體發現方法

在審

• 申請號: 201910533270.1
• 申請日: 2019-06-19
• 公開（公告）號: CN110347881A
• 公開（公告）日: 2019-10-18
• 發明（設計）人: 沈超;李其睿;劉曉明;劉笑子;管曉宏
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 范巍

本發明公開了一種基于路徑回溯圖嵌入的群體發現方法，包括建立用于表示網絡的拓撲圖，從拓撲圖中選取一個節點作為初始節點，進行隨機游走，得到遍歷節點序列，將遍歷節點序列按序截斷為預設長度的多個遍歷節點子序列；根據每個遍歷節點子序列中的節點，統計回溯得到節點之間每條邊出現的次數作為邊的權重值，得到邊權重矩陣，將節點采用隨機構造的圖嵌入向量表示，通過邊權重矩陣優化圖嵌入向量，得到圖嵌入表示向量并降維、聚類，聚類形成的每個類別里所包含的節點即為同一群體。具有計算復雜度低，要求數據源簡單的特點，可以有效減少群體發現中的計算資源開銷；無需任何先驗知識，完全依靠網絡拓撲結構實現，對于真實的復雜網絡適用性強。

技術領域

本發明屬于數據挖掘領域，涉及一種基于路徑回溯圖嵌入的群體發現方法。

背景技術

在數據挖掘領域中，拓撲圖網絡是一類非常重要的處理對象，這種網絡是由大量的節點以及節點之間的連接關系共同構成的。現實生活中，有許多領域的數據是以這樣的圖網絡結構進行存儲的，例如社交網絡(文字社交網絡及圖片社交網絡等)、工業網絡(電力及工業互聯設備等)、生物網絡(蛋白質結構等)。拓撲圖由于其非歐幾里得結構使得其包含的信息非常豐富，同時也使得對該類對象進行信息提出等操作較為復雜。拓撲圖網絡的一個重要特征就是網絡中所呈現出的群體結構。大量實證研究表明，許多網絡是異構的，即網絡不是大批性質相同節點的隨機連接，而是許多類型的節點的組合，其中相同類型的節點存在較多的連接，而不同類型節點的連接則相對較少。我們把同一類型節點以及這些節點之間的邊所構成的子圖稱為網絡中的群體。

對網絡中的群體進行挖掘發現是一個擁有較長歷史，也一直吸引研究者的方向。這是由于一方面網絡群體具有非常高的實用價值，可以在各個領域中起到重要的作用；另一方面是由于群體發現是處理拓撲圖方法的一個縮影，如何更有效的對圖網絡進行更有效的分析始終吸引研究者。目前，通常采用圖神經網絡算法的方法實現對網絡中的群體進行挖掘發現。

但是，通過圖神經網絡方法對網絡中的群體進行挖掘發現時，不僅計算時間復雜度高，而且需要除圖拓撲信息外的知識，例如節點名稱，性別等屬性，導致該方法難以在實際情況中應用。

發明內容

本發明的目的在于克服上述現有技術的缺點，提供一種基于路徑回溯圖嵌入的群體發現方法。

為達到上述目的，本發明采用以下技術方案予以實現：

一種基于路徑回溯圖嵌入的群體發現方法，包括以下步驟：

S1：建立用于表示網絡的拓撲圖G＝(V，E)；其中：V＝{v₁，v₂，…，v_N}為拓撲圖G中節點的集合，v₁，v₂，…，v_N為拓撲圖G中的節點；E為拓撲圖G中的邊的集合；

S2：從拓撲圖G中選取一個節點作為初始節點，從初始節點出發進行L步隨機游走，記錄初始節點和每次隨機游走的目標節點，得到遍歷節點序列；

S3：將遍歷節點序列按序劃分為H個遍歷節點子序列，對每個遍歷節點子序列內的節點進行邊權重統計，得到邊權重矩陣A*；

S4：將節點采用隨機構造的圖嵌入向量表示，構造目標函數，通過邊權重矩陣A*和目標函數優化各節點的圖嵌入向量，至節點之間的邊權重越大，對應的圖嵌入向量之間的距離越小，得到各節點的圖嵌入表示向量，將各節點的圖嵌入表示向量降維得到各節點的圖嵌入表示結果；

S5：將各節點的圖嵌入表示結果進行聚類，聚類形成的每個類別里所包含的節點為同一群體。

本發明進一步的改進在于：

S1的具體方法為：