[發明專利]一種k-核心覆蓋的社團發現方法

在審

• 申請號: 201810547801.8
• 申請日: 2018-05-31
• 公開（公告）號: CN108830307A
• 公開（公告）日: 2018-11-16
• 發明（設計）人: 王林;李陽
• 申請（專利權）人: 西安理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 寧文濤

本發明公開了一種k?核心覆蓋的社團發現方法，通過找到節點重要度最大的前k個節點形成對網絡的覆蓋，對節點相似度較高的覆蓋進行合并，對未覆蓋到的節點基于模塊度最大進行劃分。本發明的方法與NFA算法等一些其他的經典算法相比具有時間復雜度較低，準確率較高等優點。

技術領域

本發明屬于復雜網絡社團發現技術領域，涉及一種k-核心覆蓋的社團發現方法。

背景技術

21世紀是復雜性和網絡化的世紀。隨著互聯網的日益普及，人類的日常生產、生活越來越依靠網絡，這就要求人們提高對不同網絡的科學認識水平。社團結構是復雜網絡的一個重要特征，它具有同一類節點之間聯系緊密，不同類節點之間聯系稀疏的特性。發現復雜網絡中的社團結構可用來幫助人們理解復雜網絡的功能、發現復雜網絡中隱藏的規律和預測復雜網絡的行為。因此，對社團結構的深入研究具有十分重要的意義。

近年來，為了能夠準確有效地得到復雜網絡中的社團結構，研究者們提出了多種不同的社團結構劃分算法。從網絡據網絡的局部和整體之間的關系，可以將其劃分為如下兩類：

一類從網絡的整體到局部考慮來發現社團結構，其代表算法包括kernighan-Lin算法、GN算法和標簽傳播算法等。

GN算法是Girvan和Newman提出的一種分裂算法，該算法通過引入邊介數來度量網絡的通信流量，并不斷的移除網絡中邊介數較大的邊來得到復雜網絡中的社團結構。但迭代地計算所有邊介數的時間開銷較大，就導致了GN算法復雜度較高。

kernighan和Lin提出的kernighan-Lin算法是一種基于貪婪原理將網絡劃分為兩個大小已知社團的二分法。該算法要求必須事先知道該網絡的兩個社團的大小，否則就很可能不會得到正確的結果。

LPA算法通過不斷地更新鄰居節點的標簽來得到社團結構，該算法最大的優點在于其時間復雜度為線性，收斂速度非?？?，然而LPA算法缺乏高精確度。

另一類從網絡的局部到整體考慮來發現社團結構。其代表算法有NFA算法和k-means算法等。

NFA算法將每個節點看作是一個社團，每次迭代選擇產生最大Q值的兩個社團合并，直到整個網絡融合成一個社團。整個過程可表示成一個樹狀圖，從中選擇Q值最大的層次劃分得到最終的社團結構。

k-means聚類算法通過隨機的選取k個種子節點，然后計算所有節點與k個種子節點的距離，具有算法簡單且收斂速度較快的特點，但該算法過于依賴聚類的中心位置，即隨機選取種子節點可能導致不同的聚類結果，使得結果不穩定。

社團劃分是根據復雜網絡里隱含的拓撲信息來找出網絡中的社團結構，它可應用于信息標簽化、預防病毒，預測行為等，比如電子商務網絡對物品進行標簽化，以便消費者在購買時能夠快速地找到想要的物品；某網站對新聞進行分類，閱讀者在看新聞時能更加清楚地找到自己想看的專區，既為閱讀者們提供了方便，又提高了網站口碑；對網絡安全性進行檢測時，將具有同樣破壞功能的病毒進行歸類，以方便下次再遇到類似病毒時能夠快速解決；對醫療病癥進行分類，以便醫生對病患施行對癥下藥，是解決看病難的有力措施之一；對引文網絡中的各個專題進行劃分，以方便學者很容易的找到自己相關領域的論文等等。研究社團結構的性質不僅有助于分析復雜網絡的功能，在實際生活中也具有十分重要的應用意義。

發明內容

本發明的目的是提供一種k-核心覆蓋的社團發現方法，該方法降低了發現社團時的復雜度并提高了社團劃分的準確度。

本發明所采用的技術方案是，一種k-核心覆蓋的社團發現方法，通過找到網絡中節點重要度最大的前k個節點形成對網絡的覆蓋，對節點相似度較高的覆蓋進行合并，對未覆蓋到的節點基于模塊度最大進行劃分。

該方法的具體步驟如下：

步驟1、計算網絡數據集中每個節點的節點重要度，按節點重要度的降序對所有節點進行排序；