[發明專利]Spark下基于標簽傳播的并行重疊社區發現方法

在審

• 申請號: 201710121328.2
• 申請日: 2017-03-02
• 公開（公告）號: CN106991614A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 馬廷淮;岳明亮;薛羽;曹杰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 江蘇愛信律師事務所32241
• 代理人: 唐小紅

技術領域

本發明屬于數據挖掘領域，具體涉及的是一種利用標簽傳播思想挖掘網絡中社區的并行重疊社區發現方法。

背景技術

隨著Internet的高速發展使得社交網絡迅速進入人們的生活，導致了在線個人信息量的大量增加，并引起研究者對它的極大關注。簡單的來看，社會網絡所完成的就是把人們日常生活中的一部分內容轉移到了網絡平臺中。在社會網絡中，用戶可以結交新的朋友，也可以交流自己的思想，分享自己遇到的趣事等等。這些個人信息囊括了他們的活動，與個人或群體之間的聯系，他們發表的意見和想法隨著在線社交網絡的出現并快速流行開來，諸如新浪微博，微信朋友圈，Facebook，Twitter等越來越受歡迎，使得社交網絡作為一個新生的產物，吸引了眾多領域學者對其數據進行挖掘分析的廣泛關注，包括人際關系學、行為學、化學、生物學、遺傳學、計算機學等諸多領域。隨著這些用戶信息的急劇增加，人類社會快速步入的“大數據”時代，在面對海量數據的情況下，出現了“信息爆炸而知識匱乏”的現象。我們如何能在這些海量數據中挖掘出有用的信息或者模式對當今的研究者來說是一個巨大的挑戰。19世紀90年代第一次提出知識發現(Knowledge Discovery in Databases，KDD)的概念，以韓家煒《數據挖掘：概念與技術》一書中提出的概念為例：“數據挖掘是從存放在數據庫、數據倉庫或其他信息庫中的大量數據中發現有趣知識的過程”。數據挖掘技術通過分析海量數據以挖掘出潛在的有效的模式，是研究社交網絡的一件利器。

現實中的很多系統都可以抽象為節點和邊，即用節點表示實體，用邊表示各個實體之間的聯系，這樣的節點和邊就構成了一個網絡。關于社交網絡的研究已經持續了很長的時間。在很多網絡系統，如生物學，計算機科學，工程學，生態學等中都有社區的概念。例如：在生物學領域的蛋白質交互網絡中，位于同一個社區中的蛋白質通常起著相似的功能，通過把蛋白質當做節點以及他們之間的聯系當做邊來研究與生命活動，以了解生物構造和功能之間的關系。在信息領域的萬維網中,通過社區發現,可以在不知道網頁文本內容的情況下得到相關或相似主題的頁面,從而改善搜索引擎的性能。在實際應用中，一個微信用戶，當其在朋友圈中關注、發表、曬圖等有關足球方面內容相對頻繁的時候，可以會對該用戶的行為進行分析，并將其劃分為體育甚至更為準確的足球愛好者這一社區，那么以后就可以為該用戶提供一些足球方面的商品、球賽信息，減少用戶自己花時間進行搜索的同時又能實現類似于百度推廣的信息推廣，從而實現互利互贏。

標簽傳播算法基本思想是利用網絡的傳播特性，對網絡中節點的標簽信息進行傳播，從而發現潛在的社區結構。首先為每個節點分配一個標簽，隨著標簽的傳播對節點標簽進行更新，最后具有相同標簽的節點就屬于同一個社區。該算法思想簡單，易于理解和操作，并且時間復雜度很低，因此得到國內外學者的關注。很多學者雖然都針對不同的問題進行優化改進，在一定程度上提高標簽傳播的穩定性和準確率，但是大都或多或少地帶來增加計算開銷等問題，并沒有達到十分理想的效果。

本發明考慮網絡結構中存在的完全子圖中的節點在算法停止迭代的時候都會被劃分在同一個社區中，因此這些節點可以在初始化階段就劃分在同一個社區中，即標注為相同的標簽。綜合節點間標簽傳播的概率，節點間的相似度，改進標簽選擇的方法。最后，將改進后的算法在Spark平臺上實現并行化，以適應海量數據的社區發現。

發明內容

本發明所要解決的技術問題是Spark下基于標簽傳播的并行重疊社區發現問題。通過尋找完全子圖減少初始化標簽數目；綜合考慮節點間標簽傳播概率以及節點間的相似度確定節點選擇的標簽；最終將其應用于Spark并行計算框架下。本發明能提高算法的準確性以及穩定性，同時在面對海量數據時能展現出良好的可擴展性。

技術方案如下：

Spark下基于標簽傳播的并行重疊社區發現方法，包括以下步驟：

步驟1)，由網絡數據集，設計map和reduce函數，得到節點的鄰接列表，計算節點的度并降序排列。

步驟2)，由步驟1)得到的由節點的度降序排列的列表，依次選取節點，在網絡中尋找完全子圖，最終得到k個完全子圖g₁，g₂，…g_k，將每個完全子圖中的節點都分配一個相同的標簽，網絡中剩下的節點分配一個唯一的標簽。