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

有效

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

本發明屬于復雜網絡分析技術領域，具體為一種時變網絡中時效穩定社團的檢測方法和裝置。本發明方法包括：獲取節點之間的連接隨時間變化的情況，構建時變網絡；使用波動率定量刻畫網絡中連邊的動態變化程度；初始化社團結構，結合波動率計算時變網絡的動態模塊度；優化動態模塊度，其最大值對應的社團結構即為時變網絡的時效穩定社團。本發明使用波動率定量刻畫網絡動態變化，并將網絡動態變化特點與社團檢測方法結合起來，給出了識別時變網絡中穩定社團的方法，提高了社團檢測的準確性和可靠性，在社交網絡、生物網絡、交通網絡等不同領域具有廣泛的應用前景，同時為理解實際生活中復雜系統中社團結構的功能、動態過程提供新的視角。

技術領域

本發明屬于復雜網絡分析技術領域，具體涉及一種時變網絡中的時效穩定社團檢測方法和裝置。

背景技術

網絡是刻畫復雜系統中海量元素之間復雜關系的有效工具，實際生活中的很多系統都可以使用網絡建模分析，如社交網絡，蛋白質相互作用網絡，交通網絡等。

基于網絡科學的研究已經發現了實際系統許多重要的性質，包括小世界屬性，富人俱樂部以及社團結構等。網絡中的社團是指節點的聚類，相同社團的節點連接緊密，不同社團的節點連接稀疏。基于網絡結構將節點劃分為社團的過程被稱為社團檢測。社團結構廣泛地存在于實際系統當中，如社會學、生物學、計算機科學、經濟學、交通系統和電力系統等。網絡的拓撲結構與節點屬性、網絡功能的聯系通過社團得以體現，社團結構對網絡中的傳播過程產生影響。檢測和研究社團結構有助于我們理解網絡的結構特征和行為變化。同時，社團檢測在實際生活中有豐富的應用場景，如線上購物網站中的商品推薦，社交軟件中的廣告投放，生物學研究中蛋白質和基因功能的預測等。

由于社團結構的普遍存在和重要意義，近年來社團檢測算法已成為網絡科學的重要研究問題之一。圖割和聚類等傳統算法可以直接用于網絡的社團檢測，如層次聚類和譜聚類，其中層次聚類算法中最為著名的是Newman和Girvan提出的基于連邊介數中心性的分裂算法。Newman和Girvan提出模塊度(modularity)來衡量社團劃分的質量，模塊度值越大表明社團結構越明顯。給定網絡結構，最大化模塊度是檢測網絡中社團結構的有效手段。由于這是一個NP難問題，一系列啟發式算法被提出尋找近似解，如Blondel等人提出的Louvain算法適用于加權網絡?；谀K度最優化的方法是應用最廣泛的社團檢測算法，但是該方法存在精度限制，無法找到相對網絡而言尺寸較小的社團。除了直接分析網絡的拓撲結構，還可以基于網絡中的動態過程檢測社團，包括自旋模型，隨機游走和同步。

已有的社團檢測算法被廣泛地應用到靜態網絡中，但是多數實際系統是隨時間不斷變化的。例如，當大腦受到外界信號的刺激時，腦區的活躍程度和不同腦區之間的聯系會相應地改變；節假日期間，城市之間的交通流量會與平日不同。從網絡拓撲的角度而言，系統的動態變化體現在節點的增加和減少，連邊的出現和消失，以及連邊權重的變化三個方面。為了保留網絡結構在時間維度上的信息且模型的復雜度又不至于過高，多種關于時變網絡的建模方式被提出。

結構的動態變化和建模方式復雜度的增加為時變網絡中的社團檢測帶來一系列挑戰。關于時變網絡中社團結構的研究能夠為我們理解、控制和預測網絡結構的演化、網絡結構特征的出現和形成，網絡中的傳播過程提供更加深入和全面的視角。近年來，時變網絡中的社團檢測引起了學者的廣泛關注。使用網絡序列表示結構隨時間的變化，并用靜態網絡的方法檢測序列中每個網絡的社團是一個簡單直觀的思路，這類方法被稱為序列檢測，根據是否考慮社團結構變化的平滑性可以分為獨立檢測和演化聚類兩類方法。這類方法的關鍵問題在于排除噪聲等因素對社團結構變化的干擾，以及確定相鄰時間社團的對應關系。而基于多層網絡的檢測算法被稱為整體檢測方法，但目前層間連邊局限在相鄰網絡的同一節點之間，非相鄰網絡不同節點之間的聯系還有待研究。無論跟蹤社團結構的變化還是尋找時變網絡中不變的社團，對網絡結構時效變化的研究還不夠充分，已有的研究多數局限在對網絡整體結構在短時間內連續變化這一特點的考慮，缺乏對網絡在更長時間范圍內的時效變化特征，網絡中連邊的時效變化，以及網絡結構非連續變化的討論。

發明內容