[發明專利]重疊社區并行發現的方法及系統

在審

• 申請號: 201410302016.8
• 申請日: 2014-06-27
• 公開（公告）號: CN105302823A
• 公開（公告）日: 2016-02-03
• 發明（設計）人: 徐敏;周修莊;劉卉;吳敏華;周麗娟
• 申請（專利權）人: 首都師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司 11139
• 代理人: 孫皓晨;朱世定

技術領域

本發明涉及復雜網絡領域，具體而言，涉及一種基于MapReduce(Map，映射；Reduce，化簡；MapReduce是Google提出的一個軟件架構，用于大規模數據集的并行運算)的重疊社區并行快速發現的方法及系統。

背景技術

虛擬社區是指基于互聯網的社會群聚現象，它構成了一定規模的個體關系網絡，在虛擬的網絡中聚合了相同興趣的用戶，使他們能夠相互提出，表達，交換自己的觀點，不同社區的用戶也可能交互。社區可以為用戶提供及時的、可靠的、有價值的信息，同時還也有利于商家準確地找到客戶。然而社區一般都是隱藏在眾多繁雜的關系和連接背后，并不是顯性存在的，這就需要研究人員使用相關方法和技術把隱藏的社區發現和挖掘出來，繼而可以利用發現的社區關系為所有個體提供個性化的應用和服務。

近年來隨著網絡技術的高速發展和普及應用，社區發現已經發展成為一個跨學科的研究熱點問題，社會學、教育學、心理學等多個學科的研究人員從不同角度對它展開了系列研究。從更廣義的角度來看，現實世界的大部分系統都可以通過網絡來描述，網絡是由節點的集合和這些節點的關系，也就是連接節點的邊集合所組成。大量實際數據都表明復雜網絡通常都是異構的，也就是說它是由各種不同類型的節點所構成，其中同一類型的節點之間關聯較多，而屬于不同類型的節點之間連接相對較少。

對于大型復雜網絡，常規社區發現方法的設計原理和工作模式無法快速實時完成。

發明內容

本發明提供一種基于MapReduce的重疊社區并行發現方法及系統，用以快速檢索大型復雜網絡中的社區。

為達到上述目的，本發明提供了一種重疊社區并行快速發現方法，包括以下步驟：

S1：從數據集文件中讀取節點分布網絡圖；創建社區集合；將所述節點分布網絡圖與所述社區集合相關聯；

S2：設定初始社區的個數為n；計算所述節點分布網絡圖中每個節點的度數，并獲取前n個節點度數最高的節點分別作為n個初始社區的中心節點；此時每個初始社區的聚集度為0；n個初始社區儲存于所述社區集合；其中n為大于或等于1的自然數；

S3：對上述n個初始社區的每一個同時執行以下程序：將所述中心節點的直接相鄰節點選為該社區的候選成員節點，并將所述候選成員節點加入該社區的候選成員集合；依次判斷所述候選成員集合中的所述候選成員節點是否屬于該社區，將屬于該社區的節點并入該社區，對屬于該社區的節點的直接相鄰節點選為該社區的候選成員節點，重復該步驟；對不屬于該社區的節點移出所述候選成員集合并不作處理；將該社區數據存入所述社區集合；

S4：判斷所述節點分布網絡圖中是否有節點未并入任何社區，若是，則對未并入任何社區的節點重復執行步驟S2、S3、S4，直至所述節點分布網絡圖中的所有節點都屬于一個社區；

S5：對所述社區集合中的所有社區兩兩計算其社區重疊度，若兩個社區的所述社區重疊度大于設定閾值，則將該所述社區重疊度大于設定閾值的兩個社區合并為一個社區，并更新所述社區集合的相應數據；

S6：對所述社區集合中任意兩個具有公共節點的社區，計算將其合并為一個新社區的新社區聚集度，將該新社區聚集度分別與合并前該兩個具有公共節點的社區的所述社區聚集度進行對比，若該新社區聚集度分別大于合并前該兩個具有公共節點的社區的所述社區聚集度，則將該兩個具有公共節點的社區合并為一個新社區，該新社區聚集度為該兩個具有公共節點的社區合并后的新社區的社區聚集度，并更新所述社區集合的相應數據。

其中，步驟S3中，對上述n個初始社區的每一個同時執行的程序以多線程并行方式實現，判斷所述候選成員集合中的節點是否屬于該社區的方法是：計算每個所述候選成員節點的節點貢獻度；將所述節點貢獻度為1的節點并入該社區，并計算該社區的初始社區聚集度；對于所述節點貢獻度不為1的節點，根據其所述節點貢獻度由高到底進行排序，并從其中所述節點貢獻度最高的節點開始，依次假設所述候選成員集合中的節點屬于該社區并計算該社區的第一中間社區聚集度，假設不將所述候選成員集合中的節點并入時該社區的聚集度為初始聚集度，該社區若該第一中間社區聚集度大于該初始社區聚集度，則將相應節點并入該社區；若該第一中間社區聚集度小于該初始社區聚集度，則相應節點及其后面的節點不并入該社區，當沒有所述第一中間社區聚集度大于該初始社區聚集度時判斷為該社區發現完畢，該初始社區聚集度即為該社區的社區聚集度。

其中，步驟S3中，對上述n個初始社區的每一個同時執行的程序在MapReduce框架下實現，判斷所述候選成員集合中的節點是否屬于該社區的方法是：