[發明專利]動態社交網絡中基于聯盟形成博弈的社區檢測方法

有效

• 申請號: 201710878090.8
• 申請日: 2017-09-26
• 公開（公告）號: CN107659467B
• 公開（公告）日: 2020-03-17
• 發明（設計）人: 周麗華;楊培忠;王麗珍;陳紅梅;肖清
• 申請（專利權）人: 云南大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;G06Q50/00
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

本發明公開了一種動態社交網絡中基于聯盟形成博弈的社區檢測方法，具體按照以下步驟進行：采用基于模塊度的社區檢測方法對初始社區結構進行檢測，得到初始社區結構Γ；將相鄰網絡快照上網絡社區結構的演變分解為增加節點、增加連邊、刪除節點或刪除連邊；計算t時刻的社區結構增加節點、增加連邊、刪除節點或刪除連邊后，t+1時刻所有可能形成的社區結構的收益，確定收益最大的社區結構為實際演變后t+1時刻的社區結構，如此對初始社區結構Γ進行動態局部調整，得到實際演變后的社區結構Γ'；本發明不需要在每個網絡快照上應用靜態社區檢測方法在整個網絡中檢測社區結構，從而能夠在大規模社交網絡中快速檢測社區。

技術領域

本發明屬于社交網絡技術領域，涉及一種動態社交網絡中基于聯盟形成博弈的社區檢測方法，在社交網絡中，網絡結構隨時都在動態變化，社區結構也因此發生改變。在已知原始社區結構的情況下，根據網絡中節點、邊的增刪情況，基于聯盟形成博弈理論對原社區結構進行動態調整，從而快速獲得變化的社區結構。

背景技術

隨著互聯網技術的迅速發展，各種社交應用改變了人們的生活方式。人們在虛擬的互聯網中交流合作，形成了大規模社交網絡。在社交網絡中普遍存在社區結構的特征，即網絡中的節點被劃分為多個子集，每個子集稱為一個社區，同一社區內的節點間連接緊密，而不同社區中的節點間連接比較稀疏。社區結構的挖掘能夠幫助人們了解社交網絡的內部結構和關系，從而更好地應用社交網絡。比如，論文合作網絡中社區結構的挖掘能夠發現興趣相似的研究者，進而提供專家推薦。

目前大量的社區檢測方法都是針對靜態的社交網絡，像基于模塊度的方法、基于統計推斷的方法、團過濾的方法等。除了以上方法，最近幾年博弈理論也被引入到社區檢測技術中。Chen(<Data Mining and Knowledge Discovery>,2010),Alvari(<AICI>,2011),Lung(<Plos One>,2014)運用非合作博弈理論進行社區發現，其中每一個節點被認為是一個理性的參與者，每一個參與者通過改變自己的社區歸屬最大化自己的效用。當沒有參與者能夠單方面通過改變社區歸屬來提升自己效用的時候，博弈達到均衡，所有參與者的社區歸屬形成一種社區結構。我們提出了一種基于聯盟形成博弈的社區檢測技術(<ExpertSystem with Application>,2015)，其中每一個參與者被認為是理性的個體，通過與別人合作形成聯盟使得群體的收益最大化。當沒有任何聯盟能夠通過與其他聯盟合并來提高收益時，博弈達到均衡，所有參與者的聯盟結構即為網絡的社區結構。

實際中，社交網絡是動態的，網絡結構隨時都在發生改變。動態網絡通常是用不同時間片的網絡快照序列表示，因此社區檢測在動態網絡中可以通過應用靜態社區檢測方法在網絡快照上多次執行來解決，例如，Du等(<IEEE Transaction on Knowledge and DataEngineering>,2015)提出以一種利用非負矩陣分解技術獨立地在網絡的每個快照上檢測社區，但是該方法的效率很低，不能適用于大規模的社交網絡。

發明內容

為實現上述目的，本發明提供一種動態社交網絡中基于聯盟形成博弈的社區檢測方法，在動態社交網絡中，根據網絡的演化對前一個網絡快照的社區結構進行局部調整快速獲得后一個網絡快照的社區結構，不需要在每個網絡快照上應用靜態社區檢測方法在整個網絡中檢測社區結構，從而能夠在大規模社交網絡中快速檢測社區。

本發明所采用的技術方案是，一種動態社交網絡中基于聯盟形成博弈的社區檢測方法，具體按照以下步驟進行：

步驟1，采用基于模塊度的社區檢測方法對初始社區結構進行檢測，得到初始社區結構Γ；

步驟2，將相鄰網絡快照上網絡社區結構的演變分解為增加節點、增加連邊、刪除節點或刪除連邊；