[發明專利]一種社交網絡重疊社區發現系統及其方法

有效

• 申請號: 201410436259.0
• 申請日: 2014-08-29
• 公開（公告）號: CN104166731B
• 公開（公告）日: 2017-11-17
• 發明（設計）人: 張卓;游煌斌;張學武;范新南;李敏;付懷勇
• 申請（專利權）人: 河海大學常州校區
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京縱橫知識產權代理有限公司32224
• 代理人: 董建林,耿英

技術領域

本發明涉及數據挖掘和復雜網絡研究領域，尤其涉及一種社交網絡重疊社區發現系統及其方法。

背景技術

現實世界中存在的許多復雜系統大多可以用復雜網絡進行描述。例如：新陳代謝網，蛋白質交互網，基因網絡，科學家合著網絡，電力網，航空網以及社交網絡等等。一直以來人們對于復雜網絡的研究從未間斷，近些年來，由于互聯網的快速發展使得人們越來越關注復雜網絡，尤其是社交網絡，并進行了大量的研究工作。

一般而言，復雜網絡由于自身內部結構較為復雜，直接對整個網絡進行研究是一件十分困難的事，因此人們一般通過研究網絡的社區結構從而更好地理解整個網絡。所謂社區，是節點的集合，在社區內部節點連接很緊密，但是屬于不同社區的節點連接則比較稀疏。社區結構普遍存在于復雜網絡中，社交網絡作為復雜網絡的一類也已被證明網絡內部具有社區結構，很多用于復雜網絡的社區發現算法也可用于社交網絡。

當前，對于網絡社區結構發現的研究已經有不少成果，提出了眾多社區發現方法。早期的研究主要集中于非重疊社區發現，即認為單個節點只能屬于一個社區。典型的方法有Kernighan-Lin方法、基于Laplace矩陣的譜平分法以及Newman等人提出的FastNewman方法和CNM方法，其中CNM方法還是時間復雜度最低的算法之一。但是后來人們研究發現實際生活中社區有可能是重疊的，即一個節點有可能同時屬于多個社區。例如在社交網絡中一個人可能同時參加多個討論小組。最早的重疊社區方法是Palla等人提出的K-clique派系過濾算法，它將相鄰的K-clique進行合并，而屬于多個K-clique的節點便構成了網絡中社區的重疊部分。該方法可有效的檢測出網絡中的社區，然而該方法需提前告知網絡社區的數目，而實際網絡往往不知道最終的社區數目，這使得該方法的使用受到限制。網絡重疊社區的發現對于深入了解網絡的結構特征具有重要的意義，從而提供更有效、更具個性化的服務。社交網絡由于數據量較大，因此要求社區發現方法的時間復雜度盡可能低的同時也具有較高的劃分準確度。而現有的不少方法往往時間復雜度低卻難以保證劃分準確度，具有較高的劃分準確度的方法時間復雜度也很高。

發明內容

技術問題：本發明的目的在于提供一種社交網絡重疊社區發現系統及其方法，解決現有技術對重疊社區發現準確率和時間復雜度難以兼顧的問題。

技術方案：本發明提出一種可用于社交網絡的重疊社區發現系統，包括數據采集模塊、網絡轉換模塊、非重疊社區獲取模塊、重疊社區獲取模塊以及顯示模塊。其中數據采集模塊主要實現對實際網絡數據的采集；網絡轉換模塊實現對采集數據的轉換，以鄰接矩陣的形式存儲原始網絡信息；非重疊社區獲取模塊則采用非重疊社區發現方法對網絡進行處理，初始時認為單個節點代表一個社區，然后每次合并使模塊度增量最大的兩個社區，反復迭代直到模塊度為最大值，從而得到非重疊社區；重疊社區獲取模塊通過計算社區中節點與其他社區的隸屬度，判斷是否應將該節點加入對應社區，從而可以得到重疊節點，同時發現重疊社區；顯示模塊主要將最終獲取的重疊社區以網絡節點圖的形式直觀地展示。

本發明還提出了一種可用于社交網絡的重疊社區發現方法，首先將采集實際網絡數據，然后采用非重疊社區發現方法找出網絡中的非重疊社區，最后在非重疊社區的基礎上找出其中的重疊節點，從而得到重疊社區。

為實現上述目的，本發明技術方案包括如下步驟：

步驟一、采集實際網絡數據，以鄰接矩陣的形式存儲原始網絡信息。

步驟二、采用非重疊社區發現方法對網絡進行處理，得到非重疊社區。

(一)將單個節點視為一個社區，同時進行變量初始化設置。

(二)計算任意兩個社區合并之后的模塊度增量ΔQ。

(三)重復第二步直到模塊度Q達到最大值，此時認為社區劃分達到最優化，算法結束。

步驟三、通過計算社區中節點與其他社區的隸屬度，判斷是否應將該節點加入對應社區，從而可以得到重疊節點，也發現網絡中的重疊社區并將其展示。

一種社交網絡重疊社區發現系統，其特征在于，包括數據采集模塊、網絡轉換模塊、非重疊社區獲取模塊和重疊社區獲取模塊；

由數據采集模塊實現對實際網絡數據的采集；

網絡轉換模塊對采集的數據進行轉換，以鄰接矩陣的形式存儲原始網絡信息；

非重疊社區獲取模塊采用非重疊社區發現方法對網絡進行處理，初始時認為單個節點代表一個社區，然后每次合并使模塊度增量最大的兩個社區，反復迭代直到模塊度為最大值，從而得到非重疊社區；