[發明專利]一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法

在審

• 申請號: 202010436501.X
• 申請日: 2020-05-21
• 公開（公告）號: CN111611381A
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 鄭軍;鄭藝;吳可心
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06F16/31;G06F16/953
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 王民盛

本發明涉及一種基于蝴碟模型的主題?文檔二分圖網絡聚類切割方法，屬于譜圖理論中的圖數據挖掘技術領域。包括：步驟1：計算出圖G的主題鄰接矩陣、主題度矩陣和拉普拉斯矩陣；步驟2：根據主題鄰接矩陣構造出無向加權圖；步驟3：計算主題拉普拉斯矩陣第二小特征值對應的特征向量及該特征向量的索引值，具體為：計算主題拉普拉斯矩陣第二小特征值對應的特征向量并輸出從大到小排序的索引值；建立r個索引值集合；步驟4：分別計算索引值集合的電導率，其最小值對應的類即為所求聚類。針對二分圖網絡進行聚類切割；使用拉普拉斯矩陣特征向量，有較高的稠密度和可分離度；適用于加權、未加權、有向和無向的二分圖，均有較好的效果，具有普適性。

技術領域

本發明涉及一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，屬于譜圖理論中的圖數據挖掘技術領域。

背景技術

隨著人工智能應用的發展，知識圖譜已廣泛應用于智能搜索，智能問答，個性化推薦，智能分析等領域。在實際應用中，二分圖是知識圖譜的一種常見表示形式。例如，研究論文主題topic和論文paper之間的關系可以用圖1中的二分圖表示，其中研究主題形成一個頂點分區，論文集形成另一個頂點分區。每篇論文都與所涉及的主題通過邊相連。此外，產品與制造商，論文與作者，演員和電影之間的關系都可以通過二分圖網絡來表示。由此可見，二部圖是能表示實體之間的一對一，一對多和多對多關系的圖，并且在網絡分析中起著不可替代的作用。

在網絡中找到密集的交互結構可以揭示不同實體之間的功能和關聯。聚類切割是一個熱門的研究主題，它是根據通用結構(例如網絡主題motif)來對網絡進行切割，得到一個由密集網絡主題組成的網絡子圖。其中，網絡主題是復雜網絡的基本構建塊。

先前的聚類研究集中于在普通圖中基于邊和主題的聚類切割方法。例如Hao Yin等人研究了復雜網絡的邊緣如何聚類的更全面。但由于邊的內聚性不足以顯示整個網絡的構建結構，因此越來越多的研究通過網絡主題圖案來切割聚類。例如Jaewon Yang等人提出了一個新的范式來揭示復雜網絡中不同模塊的聚類；Alex Rodriguez等人提出了一種新的基于密度的聚類方法；Suraj Jain等人提出了SGC的聚類切割方法。這些研究都是應用于普通圖中的聚類切割方法，卻沒有專門針對二分圖的聚類切割。普通圖中最常見的圖案是小尺寸的團，比如三角形，但在圖1的二分圖中，我們看到并沒有兩個以上頂點的團，更沒有三角形，因此在二分圖中我們無法應用常用的三角形來進行聚類。在二分圖中取而代之的是完整的2×2的雙斜線結構，也稱為butterfly蝴蝶。它是二分圖中最小的子圖，是內聚力的最小單位，并已用于定義基本度量，如二分圖中的聚類系數。可以認為它在二分網絡中起的作用與三角形在普通網絡中起著相同的作用，都是復雜網絡的基本構建塊。因此在本發明中，我們選擇蝴蝶作為二分圖的基本主題。本發明以知識圖譜中文章-主題的二分圖網絡為例，提出了一種基于蝴碟主題的二分圖聚類方法，針對二分圖網絡的特點，切割出具有密集蝴碟圖案的聚類。

發明內容

本發明的目的是針對二分圖網絡中沒有聚類分割的技術現狀，提出了一種基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，借助于電導率計算公式和拉普拉斯矩陣特征向量，從輸入的無向、不加權二分圖G和主題-蝴碟M中，計算出最緊密的目標聚類S。

本發明的技術方案如下：

所述基于蝴碟模型的主題-文檔二分圖網絡聚類切割方法，包括以下步驟：

步驟1：計算出圖G的主題鄰接矩陣W_M、主題度矩陣D_M和主題拉普拉斯矩陣L_M；

其中，圖G為主題-文檔二分圖；

步驟1.1：計算出圖G的主題鄰接矩陣W_M；