[發明專利]一種融合節點屬性的深度社團發現方法

在審

• 申請號: 202110703362.7
• 申請日: 2021-06-24
• 公開（公告）號: CN113409159A
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 潘志松;潘雨;胡谷雨;張磊;段曄鑫;張武;胡亞豪;丁鈺
• 申請（專利權）人: 中國人民解放軍陸軍工程大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 北京力量專利代理事務所(特殊普通合伙) 11504
• 代理人: 毛雨田

一種融合節點屬性的深度社團發現方法，涉及作圖分割問題的技術領域。構建模塊度矩陣：模塊度的值越大代表社團結構越清晰，社團的劃分越好，通過最大化模塊度可以得到網絡的社團結構；構建深度自編碼器捕捉網絡結構：通過重構模塊度矩陣，在隱層的最后一層輸出H中保存網絡的非線性社團結構；結合節點屬性信息；當擁有相同屬性的節點劃分到不同社團，將執行一個懲罰，同時利用融合鏈接關系數據和節點內容數據進行社團發現。本發明利用深度神經網絡挖掘非線性結構，同時結合節點屬性信息得到更準確的社團結構。

技術領域

本發明涉及作圖分割問題的技術領域，尤其是一種融合節點屬性的深度社團發現方法。

背景技術

社團結構是廣泛存在于網絡中的重要結構特征，在社團內部的節點之間連接緊密，社團之間的節點連接稀疏。社團發現是通過對網絡中節點之間的相互作用和潛在的信息進行分析，從介觀角度挖掘網絡數據中隱藏的社團結構的過程。社團發現為探索復雜網絡的潛在特征提供了有效工具，對理解網絡組織結構、分析網絡潛在特性、發現網絡隱藏規律和交互模式等具有重要的理論和現實意義。節點屬性作為網絡中重要的信息，結合網絡屬性有助于挖掘更準確的社團結構。

雖然已經提出了許多社區檢測方法并取得了合理的結果，但我們仍然面臨著以下三大挑戰:第一，隨機模型和模塊化最大化模型都是線性模型，只能捕捉網絡的線性結構。然而，已經證明現實世界中的網絡結構是復雜的，最好將其視為高度非線性。其次，眾所周知，計算特征值需要很高的計算空間。因此，可擴展性是一個主要的瓶頸。第三，如何有效地整合不同類型的信息來檢測社區還有待解決。大多數算法只利用了拓撲信息，而忽略了重要的屬性信息。日常生活中的網絡在每個節點中都有豐富的屬性信息，這些屬性可以用來提高社區檢測的效率。屬性信息的加入可以補充拓撲信息，緩解網絡稀疏問題。

發明內容

本發明的目的是提出一種融合節點屬性的深度社團發現方法，利用深度神經網絡挖掘非線性結構，同時結合節點屬性信息得到更準確的社團結構。

一種融合節點屬性的深度社團發現方法，包括如下步驟：

第一步：構建模塊度矩陣：模塊度的值越大代表社團結構越清晰，社團的劃分越好，通過最大化模塊度可以得到網絡的社團結構；

第二步：構建深度自編碼器捕捉網絡結構：通過重構模塊度矩陣，在隱層的最后一層輸出H中保存網絡的非線性社團結構；

第三步：結合節點屬性信息；當擁有相同屬性的節點劃分到不同社團，將執行一個懲罰，同時利用融合鏈接關系數據和節點內容數據進行社團發現。

優選的是，本發明構建模塊度矩陣的具體過程為：

模塊度被定義為社團內連接邊的比例減去在同樣社團結構下任意兩個節點之間連接邊的比例的期望值：

其中，是網絡中邊的總數量，代表如果網絡中的邊是隨機放置時節點v_i和v_j之間的期望邊數，w_i(w_j)代表節點v_i(v_j)的度，δ(c_i,c_j) 為克羅內克函數；引入模塊矩陣B∈R^n×n，n為網絡中節點的個數，R為實數集，模塊度矩陣的元素模塊度寫為：

Q＝tr(H^TBH) s.t.tr(H^TH)＝n (6)

矩陣H為社團指示矩陣，矩陣每行最大值所對應的社團就是節點所屬的社團，h_ij代表節點i隸屬于社團j的概率，H^T為矩陣H的轉置矩陣。

優選的是，本發明構建深度自編碼器捕捉網絡結構的具體過程為：