[發明專利]一種時變網絡中時效穩定社團的檢測方法和裝置

有效

• 申請號: 201910076701.6
• 申請日: 2019-01-26
• 公開（公告）號: CN109921921B
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 李翔;王文婧
• 申請（專利權）人: 復旦大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種時變網絡中時效穩定社團的檢測方法，其特征在于，具體步驟為：

(1)獲取一段時間內節點之間的連接隨時間變化的情況，構建時變網絡，使用鄰接矩陣的集合表示各個時刻的網絡結構；

(2)基于步驟(1)得到的時變網絡計算連邊的波動率矩陣，定量刻畫連邊的動態變化程度；

波動率表示在一段時間內連邊權重的波動程度，用于定量刻畫網絡的動態變化；節點i和j之間連邊e_ij的波動率V_ij按照如下方法計算：

其中，std(·)表示標準差運算符，Δ_ij(t)表示連邊e_ij權重在時刻t的增長率；時變網絡G_d中所有連邊的波動率組成波動率矩陣V＝[V_ij]_N×N；

(3)初始化社團結構，結合波動率計算時變網絡的動態模塊度；用于定量刻畫時變網絡中的時效穩定社團；

(4)優化所述步驟(3)的動態模塊度；動態模塊度最大值對應的社團劃分即為時變網絡中的時效穩定社團。

2.根據權利要求1所述的方法，其特征在于，所述步驟(1)中的時變網絡G_d表示N個節點之間的連邊隨時間變化的情況，具體地，G_d＝(G(t),t＝1…T)，其中G(t)＝(V,E(t))表示時刻t對應的網絡結構，共T個時間點，V是N個節點構成的集合，各個時刻均相同，E(t)是t時刻連邊構成的集合，隨時間發生變化；將每個時刻的網絡結構用鄰接矩陣表示，即A(t)＝[a_ij(t)]_N×N，如果在時刻t節點i和節點j之間不存在連邊，則a_ij(t)＝0，否則a_ij(t)等于連邊的權重，網絡G(t)為無權無向網絡，所以A(t)為對稱矩陣。

3.根據權利要求1所述的方法，其特征在于，所述步驟(3)中通過動態模塊度定量刻畫時變網絡中的時效穩定社團；時效穩定社團具體表現為：節點關于社團的隸屬關系不隨時間改變，所以不同時刻網絡中對應的時效穩定社團結構是相同的，用向量C＝[C₁,C₂,…,C_N]表示各個節點所屬的社團；在不同時刻，同一個社團內節點之間的連接比不同社團節點之間的連接密切；不同社團之間連邊的動態變化程度比同一社團內連邊的變化更劇烈；

動態模塊度的計算方法如下：

其中，s_i(t)是在時刻t網絡中與節點i相連的連邊權重之和，ω(t)為所有連邊的權重之和，C_i表示節點i所屬的社團，如果節點i和j屬于同一個社團，則δ(C_i,C_j)＝1，否則為0，m_t為t時刻網絡中的連邊數目；動態模塊度是結合波動率，將Girvan-Newman模塊度從靜態網絡向時變網絡的拓展，用社團內連邊的平均權重表示連接的密切程度，用連邊的平均波動率表示連邊的動態變化程度。

4.根據權利要求1所述的方法，其特征在于，所述步驟(4)使用優化動態模塊度的方法尋找時效穩定社團；當改變網絡中的社團劃分結構時，動態模塊度發生變化；最大動態模塊度對應的社團結構就是時變網絡的時效穩定社團。

5.一種時變網絡中時效穩定社團的檢測裝置，其特征在于，包括時變網絡構建模塊、波動率計算模塊、動態模塊度優化模塊、時效穩定社團輸出模塊，其中：

所述時變網絡構建模塊，用于獲取不同時刻節點之間的連接情況，構建包含N個節點，T個時間點的時變網絡，并以鄰接矩陣集合的形式表示網絡在各個時刻拓撲結構；

所述波動率計算模塊，用于計算連邊權重在一段時間內的波動率，并用波動率矩陣存儲所有節點對之間連邊的波動率；

所述動態模塊度優化模塊，用于優化網絡的動態模塊度，尋找動態模塊度的最大值；

所述時效穩定社團輸出模塊，用于給出最大動態模塊度對應的社團劃分，即時變網絡的時效穩定社團結構。