[發明專利]基于隨機優化和非均勻采樣對大規模社團網絡檢測方法

在審

• 申請號: 202011204489.6
• 申請日: 2020-11-02
• 公開（公告）號: CN112199452A
• 公開（公告）日: 2021-01-08
• 發明（設計）人: 金弟;孫繼滔;焦鵬飛
• 申請（專利權）人: 天津大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/22
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 韓帥

本發明公開了基于隨機優化和非均勻采樣對大規模社團網絡檢測方法，包括如下步驟：采集大規模社團模型節點值構建概率圖模型SBM；2)：根據概率模型變量Z建立社團模型網絡中抽象化模型表示，即P(Z|X)；3)：對抽象化模型進行社團歸屬的后驗分布建立社團檢測的目標函數模型4)：通過非均勻采樣算法對社團檢測的目標函數模型進行無偏估算L_unbiased；(5)：對社團檢測的目標函數模型變分參數進行優化求解；(6)：重復步驟3)?5)將獲得最優社團檢測的目標函數模型變分參數進行在社團網絡分別劃分，本發明是將抽象網絡結點信息進行數據計算歸類劃分進而實現網絡精準檢測。

技術領域

本發明屬于機器學習、復雜網絡檢測技術領域，尤其涉及基于隨機優化和非均勻采樣對大規模社團網絡檢測方法。

背景技術

網絡代表了復雜系統中不同個體間的關系，是用于分析復雜系統性質和功能的有力表征工具。社團結構是復雜網絡的一個重要性質，即：相同社團內節點的交互要比不同社團間節點的交互更為頻繁。探測復雜網絡中蘊含的社團結構可幫助人們更好的理解復雜系統的組織原理，探測其功能，并預測其未來趨勢。

在社團檢測領域，社團網絡模型(SBM)具有很多的應用，隨機塊模型是一種強有力的社團檢測工具，因此各種基于隨機塊模型的社團發現算法被提出。例如，第一種是基于Gibbs采樣的模型推斷方法，但是基于Gibbs采樣的算法在模型的推斷過程中效率很低，第二種是基于EM算法來推斷模型參數，EM算法通過最大化模型的一個后驗概率來獲得最優模型參數，相較于Gibbs采樣，EM算法在效率上有了一定的提高，但是EM算法也僅僅能處理幾百個結點的網絡。

現如今的網絡規模都是巨大的，之前的社團檢測算法不能很好的處理大規模網絡的結構。目前大多數基于隨機塊的社團檢測算法都是通過全部的數據點來構建社團檢測目標函數，因此在社團發現的過程中的時間復雜度是巨大的。

發明內容

本發明的目的在于克服現有技術的不足，提出一種新的基于隨機塊的社團檢測方法，來處理大規模網絡的社團結構。本發明用部分數據代替全部的數據，更好的發現大規模社團的結構。為達到上述目的，本發明采用的技術方案是基于隨機優化和非均勻采樣,主要包含以下幾個步驟：

一種基于隨機優化和非均勻采樣對大規模社團網絡檢測方法，包括如下步驟：

(1)：采集大規模社團模型節點值構建概率圖模型，其中Z_i表示結點的社團隱變量，X_ij表示結點的邊，其他的模型變量的相關描述見表1。

(2)：根據概率模型變量Z建立社團模型網絡中抽象化表示，即P(Z|X)；

(3)：對抽象化模型P(Z|X)進行社團歸屬的后驗分布建立社團檢測的目標函數模型，即：

L(q)＝E_q(logP(π,θ,Z,X))-E_q(logq(π,θ,Z))

(4)：引入隨機優化方法，通過非均勻采樣算法對社團檢測的目標函數模型進行無偏估算L_unbiased，即：

(5)：對社團檢測的目標函數模型變分參數進行優化求解；

(6)：重復3)-5)以獲得最優社團檢測的目標函數模型變分參數，根據最優變分參數進行社團網絡劃分。

進一步，所述最優變分參數進行在社團網絡劃分的過程為：

通過社團變分參數τ選擇每行最大結點作為社團歸屬P(Z|x)；

統計每個結點的社團歸屬確定網絡的預測標簽；

通過Accuracy指標衡量本發明對網絡社團檢測的準確性同時用計算收斂時間來衡量本發明的社團檢測的時間效率。