[發明專利]一種基于社區結構的內外比度量方法及社區發現方法

有效

• 申請號: 201510526277.2
• 申請日: 2015-08-25
• 公開（公告）號: CN105337759B
• 公開（公告）日: 2018-12-25
• 發明（設計）人: 張大方;李果;謝鯤;李彥彪;黃潭龍
• 申請（專利權）人: 湖南大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 長沙正奇專利事務所有限責任公司 43113
• 代理人: 馬強;王娟

本發明公開了一種基于社區結構的內外比度量方法及社區發現方法，首先定義了內外比度量標準，用來判斷子網絡結構是否社區，以及該結構的社區緊密程度。然后提出比鄰雙向迭代算法，使用優化后的一組初始子網絡結構，通過增加鄰節點或減少內點兩個方向，基于內外比度量標準，來迭代發現社區。本發明用于快速發現網絡中緊密程度高的社區結構，能夠更快、更全面地發現更好的社區，在最早發現最好社區的時間比上平均提高39.64％，在搜索覆蓋面上平均提高12.67％，并具有計算數據依賴程度低的特點，適合分布式并行計算。

技術領域

本發明涉及社會網絡中社區發現方法,特別是一種基于社區結構的內外比度量方法及社區發現方法。

背景技術

社會網絡(Social Network)可以抽象為，由節點和線段構成的集合，節點是社會網絡中的個體，線段則是個體與個體之間的某種聯系關系。社會網絡具有一種社區特性，即網絡中的一個子網絡結構，該結構內部點與點之間的聯系緊密程度較高，而該結構與其外部鄰節點的聯系比較松散。社區發現(Community Detection)就是找出網絡中這些內部聯系緊密的子網絡結構。社區發現技術有很多重要的作用，比如能用在推薦系統中，找出具有相同興趣愛好的人，并推薦他們可能感興趣的產品。

傳統的網絡社區發現方法，需要整個網絡的全局信息，即網絡中所有的點和邊，再通過較復雜的計算公式得出該子網絡結構的社區緊密程度。而且對社區結構的判斷，要么側重于邊與邊之間的聯系程度，要么側重于點與點之間的聯系程度，沒有同時平衡考慮到邊和點兩個方面。

社會網絡的一個特點是網絡會處于動態變化中，網絡中節點和線段的數量會不停變動，即網絡的全局信息會動態變化，如果判斷社區結構時需要全局網絡信息，那就只能在某一時刻的靜態網絡結構中進行計算，而不能適用于動態社會網絡。

近年來，圖形處理單元GPU作為一種可適用于科學計算的并行處理硬件平臺，在并行計算方面得到了較多的應用。相對于CPU，GPU是一個高度并行化的多線程、多核心處理器。CPU處理器把較多的硬件資源用于控制、存儲單元，擅長有復雜控制邏輯的計算，而GPU則把更多的硬件資源用于并行計算單元，能以大量線程對大規模數據進行并行計算，適合處理計算密度高、邏輯分支簡單的計算。所以GPU更適合用來做數據規模大、數據類型統一、數據間依賴程度低的并行計算。

如果采用傳統的社區發現方法，需要先知道網絡的全局信息，再進行邏輯較復雜的計算，這樣會使得整個社區發現過程的計算數據規模很大，導致計算時間長，方法的效率不高。但是因為傳統方法中數據間依賴程度高，不適合用來在GPU并行處理平臺上進行計算。

傳統的社區度量標準，有中間度、模塊化、傳導性幾種，但是這些社區度量標準在計算時需要網絡全局信息，使得計算中的通信代價較高。而且，有些標準只是側重于對網絡中點或線一個方面的測量，因此可能導致測量不夠準確。

傳統的社區度量標準中，中間度是用來間接度量社區，先計算網絡中經過某邊的最短路徑數量，再統計子網絡結構中每個邊的中間度，如果一個子網絡結構的邊中間度較高，那么說明該子網絡結構和外界的聯系程度也比較高，因此不是社區。可以看出，該度量標準需要全局信息，主要側重于邊的計算，且計算邏輯較復雜。

模塊化、傳導性則是能直接的社區度量標準。模塊化度量標準計算過程如式2所示：

M是網絡中所有邊的數量，m_c是社區內部中邊的數量，d_c是社區中所有點的度數。可以看出，該度量標準需要全局信息，且計算量較大。

傳導性度量標準計算過程如式3所示：