[發明專利]一種基于最大生成樹的圖嵌入方法

在審

• 申請號: 202210297523.1
• 申請日: 2022-03-24
• 公開（公告）號: CN114726738A
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 閔勇;江婷君;龍杰;傅晨波;宣琦
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心
• 主分類號: H04L41/12
• 分類號: H04L41/12;H04L41/14;G06Q50/00
• 代理公司: 北京東方盛凡知識產權代理事務所(普通合伙) 11562
• 代理人: 李娜

本發明公開了一種基于最大生成樹的圖嵌入方法，包括：在原始網絡社區基于隨機游走算法對節點路徑進行采樣，獲得節點序列；基于采樣的節點路徑構造加權網絡，基于加權網絡生成最大生成樹；計算最大生成樹的中介中心性，獲得若干組分布于原始網絡社區之間的邊作為割集；基于割集對原始序列進行分割，獲得細粒度序列；將原始序列作為細粒度序列的初始嵌入，通過迭代獲得更細粒度的嵌入值，直到獲得最終嵌入結果。本發明在原網絡的最大生成樹上進行社區劃分，與在原網絡上計算邊介數相比，計算最大生成樹的邊介數計算量較小，時間復雜度更低。

技術領域

本發明屬于大規模復雜網絡社區發現技術領域，特別是涉及一種基于最大生成樹的圖嵌入方法。

背景技術

現實生活中，許多復雜關系信息通常可以通過復雜網絡的形式呈現，如生物領域的基因網絡、蛋白質網絡和流行病傳播網絡，科技領域的電力網絡、電子郵件網絡和萬維網絡，以及Facebook、Twitter、微博、朋友圈等社交網絡。網絡中最顯著的特征是社區結構，社區內部節點的連接較為緊密，而社區之間的節點連接相對稀疏。

發現網絡中的社區結構有助于分析社交網絡的拓撲結構、發現隱藏在復雜網絡中的規律，和預測復雜網絡的演化趨勢。社區發現在網絡輿情監控、廣告傳播、流行病預測等領域有著巨大的應用價值，已經成為網絡科學研究中的經典和熱點問題之一。

目前已經有許多具有代表性的社區發現方法被提出，如經典的GN算法，FastNewman(FN)算法，CNM算法，標簽傳播方法等。然而這些方法都存在一些不足，如標簽傳播方法每次迭代的結果不穩定，準確率不高；GN算法必須在原圖上求解邊介數，時間復雜度較高。針對上述研究中所存在的問題，本發明提出一種基于最大生成樹的社區發現方法，先利用隨機游走方法將原無權網絡轉化為加權網絡，并構造最大生成樹MST，然后根據最大生成樹的邊介數、邊權值劃分社區，并使用模塊度值Q來尋找最優的劃分結果。

發明內容

本發明的目的是提供一種基于最大生成樹的圖嵌入方法，以解決上述現有技術存在的問題。

為實現上述目的，本發明提供了一種基于最大生成樹的圖嵌入方法，包括：

在原始網絡社區基于隨機游走算法對節點路徑進行采樣，獲得節點序列；

基于采樣的節點路徑構造加權網絡，基于所述加權網絡生成最大生成樹；

計算所述最大生成樹的中介中心性，獲得若干組分布于所述原始網絡社區之間的邊作為割集；

基于所述割集對所述原始序列進行分割，獲得細粒度序列；

將所述原始序列作為所述細粒度序列的初始嵌入，通過迭代獲得更細粒度的嵌入值，直到獲得最終嵌入結果。

可選的，在原始網絡社區基于隨機游走算法對節點路徑進行采樣，獲得節點序列的過程中包括：

在原始網絡社區中構建無權無向網絡模型，所述無權無向網絡模型包括若干個節點和若干條邊；

設定每個節點隨機游走步數和重復游走次數；

以每個節點為初始節點，基于設定好的所述隨機游走步數和所述重復游走次數進行隨機游走并進行節點路徑采樣，獲得所述節點序列。

可選的，基于采樣的節點路徑構造加權網絡，基于所述加權網絡生成最大生成樹；

統計所述隨機游走經過每一條邊的次數，將邊被遍歷的次數作為邊的權重，基于權重獲得權重集合；

基于權重集合構建加權無向網絡，基于所述加權無向網絡生成最大生成樹。

可選的，計算所述最大生成樹的中介中心性，獲得若干組分布于所述原始網絡社區之間的邊作為割集；