付常雷

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

0 引 言

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

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

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

1 社團劃分的相關(guān)概念

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

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

網(wǎng)絡的社團劃分研究的三個問題是：

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

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

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

1.1 社團的定義

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

1.2 社團劃分評價系數(shù)Q

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

(1)

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

1.3 Newman快速算法

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

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

(2)

ai=ki/(2m)

(3)

其中，ki為節(jié)點i的度;m為網(wǎng)絡中邊的總數(shù)。

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

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

(4)

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

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

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

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

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

2 改進的Newman快速算法

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

2.1 社團貢獻度

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

(5)

其中，Ki為社團i中的節(jié)點與其他社團內(nèi)的節(jié)點相連的邊的總數(shù)；Ai為社團i內(nèi)含有的邊的條數(shù)；m為整個網(wǎng)絡總邊數(shù)。

2.2 算法描述

CCN算法的基本步驟如下：

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

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

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

3 實 驗

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)基本信息

3.2 實驗結(jié)果與分析

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

圖1 運算時間對比

圖2 社團劃分結(jié)果Q值對比

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

4 結(jié)束語

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

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

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

[2] 王 苑,徐德智,陳建二.復雜中文文本的實體關(guān)系抽取研究[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] 辛娟娟,曹 佳.基于復雜網(wǎng)絡的文獻熱點挖掘及可視化[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] 汪小帆,李 翔,陳關(guān)榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006:

[10] 譚 瑩,張 然,朱東生.社區(qū)發(fā)現(xiàn)在復雜網(wǎng)絡劃分中的應用[J].計算機技術(shù)與發(fā)展,2014，24(11):234-237.

[11] 汪小帆,劉亞冰.復雜網(wǎng)絡中的社團結(jié)構(gòu)算法綜述[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] 朱小虎,宋文軍,王崇駿,等.用于社團發(fā)現(xiàn)的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.