[發明專利]基于社區緊密度的快速社區發現方法

無效

• 申請號: 201110177772.9
• 申請日: 2011-06-28
• 公開（公告）號: CN102779142A
• 公開（公告）日: 2012-11-14
• 發明（設計）人: 藺智挺;吳秀龍;陳軍寧;孟堅;徐超;李正平;譚守標
• 申請（專利權）人: 安徽大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及復雜網絡領域，尤其涉及一種復雜網絡中社區結構的發現技術及其實現方法。

背景技術

社區發現技術即發現網絡中的社區結構是復雜網絡中的一個基礎研究，也是近年來復雜網絡中的一個研究熱點。

關于網絡社區結構的研究，它不僅與計算機科學中的圖形分割(GP：graph?partition)技術密切相關，還與社會學中的層次聚類(HC：hierarchicalclustering)技術也有著不容忽視的關系。

基于圖分割的著名算法主要有K-L算法、譜平分法、派系過濾算法和W-H快速譜分割法等。其中，K-L算法在稀疏圖中的時間復雜度O(n³)。并且其最大缺陷是必須為算法預先指定兩個社區的大小，否則算法會得到錯誤的劃分結果，這就使該算法的應用非常的有限，在大多數的真實網絡中根本無法得到應用。此外，即便克服了K-L算法的這一缺點，我們仍然不能解決K-L算法作為圖分割方法的先天性不足。至于譜平分法，人們在使用這類方法時，預先不能確定究竟將圖分成多少個子圖才合適，因為該方法只能將圖分成2個子圖即偶數個子圖，且不知何時停止。

而層次聚類算法可分為兩大類算法：凝聚算法和分裂算法。凝聚算法的典型代表是Newman快速算法，該算法可以用于分析含有高達100萬節點的復雜網絡。此后，Clauset、Newman和Moore等人又提出了一種新的貪婪算法。該算法是基于Newman快速算法，并采用了數據結構“堆”來對網絡的模塊化度進行計算和更新，其復雜度只有O(nlog²n)。在很多不同的現實網絡中，凝聚算法的確已經得到了廣泛應用，但這并不能掩飾這類算法所存在的問題。首先，在一些應用中，即使已經知道了社區數目，卻并沒有得到正確的社區結構。其次，凝聚算法傾向于找到社區的核心，而忽略社區的周邊。

而GN算法屬于層次聚類中的分裂算法。盡管該算法彌補了一些傳統算法的不足，但是仍然存在一個缺陷：不能直接根據網絡的拓撲結構來判斷它所求的社區是否有意義。另外，GN算法在對社區數目不清楚的情況下，也不知道算法該在哪一次迭代后結束。

由以上描述可以看出，現有的社區發現技術性能雖然優越，也可以較為準確地發現復雜網絡中的社區結構，但是它們的計算量卻依然十分龐大，嚴重限制了它們在大型復雜網絡中的應用。

發明內容

有鑒于此，本發明的主要目的在于提供一種新的社區發現技術——基于社區緊密度的快速社區發現方法，在不影響社區發現性能的情況下，降低方法所需的時間復雜度，使其可以更好地應用在大型的復雜網絡中。

為了達到上述目的，本發明引入了邊稠密度、相鄰社區的概念，并設計了一種緊密度矩陣。

其中邊稠密度的定義如下：給定一個含有n個頂點，m條邊的圖G，該圖的邊稠密度是邊數目與頂點數目的比率，數學描述為λ_G＝m/n。

其中相鄰社區的定義如下：給定一個當前具有k個社區的圖G和相應的緊密度矩陣M，我們稱滿足如下條件的社區i和社區j是相鄰的，它們互為相鄰社區：m_ij≥[λ_G/2]，i∈[1，k]，j∈[1，k]。

其中我們設計的緊密度矩陣如下：給定一個含有n個節點、m條邊的圖G，該緊密度矩陣的公式描述為M＝(m_ij)_k×k，其中M代表緊密度矩陣，m_ij代表社區i和社區j之間的緊密度值，k是當前網絡中的社區個數，其值小于等于n。

其中緊密度矩陣中的元素記錄的是任意兩個社區之間的緊密度值。并且緊密度矩陣M在初始化時，其每個元素的緊密度值均置為0，這緊密度值會隨著算法的運行逐漸增大。

實現本發明所提供的社區發現技術包含三部分的工作：

A、計算緊密度矩陣；

B、合并社區；

C、更新緊密度矩陣。

其中步驟A是我們最先需要完成的工作，即我們需要首先計算出網絡中的緊密度矩陣。然后才能開始步驟B合并社區的工作，步驟B完成后，需要對步驟A中計算出的緊密度矩陣按照步驟B的結果進行更新，然后再進行下一輪的迭代。

其中步驟A的工作包括兩種情況：

A1、計算無權網中的緊密度矩陣；

A2、計算加權網中的緊密度矩陣。

其中步驟B，緊密度矩陣M的維數k初始值等于所研究的圖中頂點的個數(初始時，每個頂點形成該圖中的一個獨立社區，即此時每個社區內只有一個節點)。并且步驟B中，合并社區的工作有兩種特殊情況：