一種基于Newman快速算法改進的社團劃分算法

付常雷

(中國科學院文獻情報中心，北京 100190)

0 引 言

隨著科研領域的不斷深入，產生科技文獻數據量的不斷增大，傳統的文獻計量方法和文獻挖掘方法所帶來的缺陷越來越明顯，因此如何從海量的科技文獻中挖掘出有效數據成了知識組織與發現領域所面臨的難題。然而隨著大數據技術的發展，文獻數據分析與數據挖掘課題已經從早期的統計學、計量學等傳統的學科拓展到圖像、WEB、空間數據等復雜和豐富數據的分析，復雜網絡分析法已經逐漸用于科技文獻數據的挖掘與分析中，極大地促進了知識組織與發現領域的發展，也為科技文獻分析深層次的數據挖掘提供了技術實現方法。因此在傳統方法上，開始關注科技文獻中存在的大量鏈接信息，如合作關系、引用關系[1]等，通過對這些關系的分析和研究，可以獲得傳統文獻分析和數據挖掘方法無法得出的分析和結論。

科技文獻中存在多種實體數據，這些實體與實體之間往往存在一些直接或者間接的聯系；科技文獻之間按照實體與實體之間的某種關系組成的網絡為科技文獻關系網[2]。目前在科技文獻關系網中，一些相似研究方向或者主題的文獻實體往往會聚集在一起形成一個社團，研究這些社團的特征往往能發現該領域內的研究熱點[3-4]，以及科研合作情況甚至研究熱點預測等重要信息[5-6]，因此對科技文獻拓撲網絡的社團劃分，是知識組織與發現的一種重要方法。

Newman快速算法[7-9]是一種比較有效的社團劃分算法,簡稱FN算法。FN算法是一種基于貪婪算法思想的凝聚算法，通過合并網絡中的節點來劃分網絡中的社團結構，算法合并過程中拒絕所有較差的候選解，只接受當前更好的候選解。因此，FN算法找到的劃分結果往往是局部最優而不是全局最優。針對FN算法的缺點，文中提出一種基于社團貢獻度的CCN算法，一定程度上提高了社團劃分結果的效率。

1 社團劃分的相關概念

社團劃分最早起源于圖分割問題，基于圖分割的方法的核心是最小化群體之間的邊數，但是一些群體間的邊并不能很好地反映圖中節點間的本質聯系。因為大多數圖分割方法必須提前得到要分析的網絡圖的節點數和分割后的群體個數，而社團劃分算法卻無法提前得到這些信息，因此圖分割方法不適用于社團劃分。

對網絡圖的社團劃分的研究很早就開始了，起先社團劃分與圖形學中的分割問題和社會科學中的聚類與分級有著相關聯系。社團劃分的問題描述很簡單，可以抽象為一個現實生活中關于人員分配的例子。假如一家公司有n個業務員，他們分布在m個城市，并不都互相認識，因此每個業務員不一定與他想要聯系的業務員有直接聯系。用節點表示業務員，每條邊表示他們之間能直接通信，因此社團劃分問題可以描述為：如何分布這n個業務員到這m個城市去，使每個城市的業務員數量近似相等，同時分布在不同城市的業務員之間的業務聯系通信的邊數相對較少。因此社團劃分問題是一個最優值問題，針對這個問題，目前存在很多試探性算法，一般情況下可以求出比較滿意的解。

網絡的社團劃分研究的三個問題是：

(1)如何定義一個社團，什么樣的社區是一個合適的社團。

(2)如何判定一種社團結構劃分是最好的，即缺乏一個普遍適用且有效的社團結構劃分衡量標準。

(3)如何把這樣一個網絡圖劃分成幾個社團或簇，每個社團由哪些頂點組成，才能使各社團內部聯系緊密，各社區間聯系稀疏。換句話說，在一個有效的社團結構劃分標準下，得到一個有效且合理的社團劃分算法。

1.1 社團的定義

社團結構普遍存在于無標度網絡中[10]，但是目前對于社團還沒有一個統一明確的定義。文獻[11]提出了基于網絡圖社團的局部定義，而文獻[12]給出了基于空模型(null model)的社團全局定義。從網絡節點特征來說，社團就是一群聚集在一起的節點，社團結構的基本特征為：在同一個社團的節點之間邊的數目較多，社團與社團之間的連接數目較少[13]。

1.2 社團劃分評價系數Q

為了衡量一個網絡社團劃分的情況，Newman在文獻[1]中引入了模塊度Q值的概念。Q是衡量網絡社團劃分質量的系數，是為了表示社團劃分后，社團之間的連接數目與社團內部的連接數目的比例。Q值計算公式定義如下：

(1)

其中，ki與kj為節點的度值；Ci為節點i所屬社團；m為邊的總數。當Ci=Cj時，?(Ci,Cj)=1，否則為0。Q的取值范圍為[0,1]，Q值越大說明社團結構越明顯，一般網絡的社團劃分結果的Q值在0.3～0.7之間。

1.3 Newman快速算法

FN算法是Newman等在GN算法的基礎上提出的一種聚合算法，是一種基于局部搜索的貪心算法思想的復雜網絡社團劃分算法，其目的就是最大化Q，算法的基本步驟如下：

(1)將網絡初始化為n(n為節點數目)個社團，也就是初始階段將每一個節點看成一個獨立的社團。初始元素eij和ai滿足：

(2)

ai=ki/(2m)

(3)

其中，ki為節點i的度;m為網絡中邊的總數。

(2)根據社團之間的相似度或者歐氏距離(合并條件可自己選)合并兩個社團。模塊度增量計算公式如下:

△Q=eij+eji-2aiaj=2(eij-aiaj)

(4)

根據貪婪算法原理,每次合并應該沿著使△Q值最大的方向進行。每次合并以后,對相應的eij元素進行更新,并將與i,j社團相關的行和列相加。

(3)不斷合并社團，直到整個網絡被合并成為一個社團。

整個算法完成后可以得到一個社團結構分解的樹狀圖。再通過在不同位置斷開可以得到不同的網絡社團結構。在這些社團結構中，選擇一個對應局部最大Q值的，就得到了較好的網絡社團結構。

FN算法選取候選解采用一種局部搜索策略。從初始解開始(每個網絡社團僅包含一個節點)，在每次迭代過程中，FN算法選擇且合并兩個現有的網絡社團使ΔQ值最大化，直到網絡中只剩下一個網絡社團。FN算法的時間復雜度為O((m+n)*n)，其中m為網絡的節點數，n為網絡的邊數。

雖然某兩個社團的合并會使Q值有所減少，但仍然有可能在以后的社團合并過程中得到一個更大的Q值，而且從算法步驟可以看出，FN算法每次迭代過程都是隨機選擇兩個社團進行合并，直到所有的社團都合并后，然后比較△Q，選取使△Q最大的兩個社團歸入同一個社團，這種迭代步驟大大降低了迭代效率。

2 改進的Newman快速算法

針對Newman快速算法的缺點，文中提出一種將社團貢獻度(community contribution)作為社團合并依據的Newman快速算法(簡稱CCN算法)。

2.1 社團貢獻度

在社團劃分的Q值優化問題中，Q值是全局變量，借鑒文獻[14]中modularity的概念，定義一個社團貢獻度q的局部變量來表示該社團在網絡結構中對Q值的貢獻度大小。社團i的貢獻度的計算公式如下：

(5)

其中，Ki為社團i中的節點與其他社團內的節點相連的邊的總數；Ai為社團i內含有的邊的條數；m為整個網絡總邊數。

2.2 算法描述

CCN算法的基本步驟如下：

(1)將網絡初始化為n(n為節點數目)個社團，也就是初始階段將每一個節點看成一個獨立的社團,初始化的各個社團的貢獻度即為各個節點的度數。

(2)循環迭代：計算出各個社團的貢獻度大小，然后將貢獻度最小且相連的兩個社團合并，每次合并后，都需要對網絡中的所有社團重新計算它們的貢獻度。

(3)不斷合并社團，直到整個網絡被合并成一個社團。

3 實 驗

3.1 實驗數據

為了驗證改進算法的有效性，在MATLAB上對其進行驗證。實驗數據為五個關系網絡圖，分別為Dolphins、Test-real、Article2008、Article2009和Article2010。Dolphins網絡數據來自D. Lusseau對新西蘭海豚之間的接觸頻繁程度構造出的海豚關系網[15]；Test-real來自經典的復雜網絡可視化軟件Pajek實例網絡；Article2008、Article2009和Article2010分別是從林業科技文獻信息中按年份抽取的關鍵詞共現網絡。這五個網絡的規模信息如表1所示。

表1 實驗數據基本信息

3.2 實驗結果與分析

實驗從運行時間和社團劃分結果Q值兩方面進行比較，結果如圖1和圖2所示。

圖1 運算時間對比

圖2 社團劃分結果Q值對比

從圖1看可以，CCN算法在運算時間上均小于FN算法，而且隨著網絡節點的增多，算法的運行時間差越來越大；圖2中，CCN算法的社員劃分結果Q值都大于FN算法。綜上，改進的CCN算法在運算效率和社團劃分結果Q值上較FN算法都有所改善。

4 結束語

基于Newman快速算法，提出了一種基于社團貢獻度為合并條件的社團劃分CCN算法，在算法中提出了社團貢獻度的概念，并給出了其計算方法。CCN算法的合并步驟直接根據各個社團的貢獻度大小，然后選擇貢獻度最小且相連的兩個社團合并,而不像FN算法需計算所有的社團對Q值的影響，然后通過比較，選擇對Q值增量最大的兩個社團進行合并,因此在時間性能上較FN算法有較大程度的提高。在社團

劃分效果方面，CCN算法以社團貢獻度為選擇的迭代過程，在某種程度上解決了FN算法具有的局部搜索的缺陷，因而社團劃分結果Q值有所提高。

[1] 肖 雪,陳云偉,鄧 勇.引文網絡的社團劃分研究進展綜述[J].情報雜志,2016,35(4):125-130.

[2] 王 苑,徐德智,陳建二.復雜中文文本的實體關系抽取研究[J].計算機科學,2009,36(8):208-211.

[3] NEWMAN M E J.Detecting community structure in networks[J].European Physical Journal B,2004,38(2):321-330.

[4] 辛娟娟,曹 佳.基于復雜網絡的文獻熱點挖掘及可視化[J].計算機工程與應用,2016,52(12):261-264.

[5] ECK N J,WALTMAN L.How to normalize cooccurrence data? An analysis of some well-known similarity measures[J].Journal of the American Society for Information Science and Technology，2009，60(8):1635-1651.

[6] KLAVANS R,BOYACK K W.Identifying a better measure of relatedness for mapping science[J].Journal of the American Society for Information Science and Technology,2006,57(2):251-263.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[8] COHEN J.Graph twiddling in a MapReduce world[J].Computing in Science & Engineering,2009,11(4):29-41.

[9] 汪小帆,李 翔,陳關榮.復雜網絡理論及其應用[M].北京:清華大學出版社,2006:

[10] 譚 瑩,張 然,朱東生.社區發現在復雜網絡劃分中的應用[J].計算機技術與發展,2014，24(11):234-237.

[11] 汪小帆,劉亞冰.復雜網絡中的社團結構算法綜述[J].電子科技大學學報,2009,38(5):537-543.

[12] WASSERMAN S,FAUST K.Social network analysis:methods and applications[M].[s.l.]:Cambridge University Press,1994.

[13] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[14] 朱小虎,宋文軍,王崇駿,等.用于社團發現的Girvan-Newman 改進算法[J].計算機科學與探索,2010(12):1101-1108.

[15] LUSSEAU D.The emergent properties of a dolphin social network[J].Proceedings of the Royal Society of London B:Biological Sciences,2003,270(2):186-188.