莊城山

安徽工業(yè)職業(yè)技術(shù)學(xué)院信息工程系，安徽銅陵，244000

?

經(jīng)典的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法研究與分析

莊城山

安徽工業(yè)職業(yè)技術(shù)學(xué)院信息工程系，安徽銅陵，244000

以其中最具代表性的三種經(jīng)典算法——GN算法、快速Newman算法、CNM算法為代表，研究了算法的設(shè)計(jì)思想、執(zhí)行流程。通過(guò)橫向?qū)Ρ?，?duì)三種算法的優(yōu)缺點(diǎn)進(jìn)行分析比較，明確了三種經(jīng)典算法的各自適用情況和范圍：GN算法精度較高，但時(shí)間復(fù)雜度也較高，適用于對(duì)結(jié)果要求比較精確的節(jié)點(diǎn)數(shù)較少的社團(tuán)；Newman快速算法在時(shí)間復(fù)雜度上較GN算法占優(yōu)勢(shì)，但精確度略低于GN算法；CNM算法同Newman快速算法時(shí)間復(fù)雜度相同，適用于加權(quán)的復(fù)雜網(wǎng)絡(luò)。最后以Zachary空手道俱樂(lè)部網(wǎng)絡(luò)和上證50部分股票構(gòu)建的股票網(wǎng)絡(luò)為例進(jìn)行了實(shí)證分析，得到了較為準(zhǔn)確的社團(tuán)劃分結(jié)果。

復(fù)雜網(wǎng)絡(luò)；社團(tuán)劃分；GN算法

1 復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分問(wèn)題概述

20世紀(jì)末，兩篇開(kāi)創(chuàng)性的論文：一是在《Nature》雜志上發(fā)表的《小世界網(wǎng)絡(luò)的群體動(dòng)力行為》[1]，另一是在《Science》雜志上發(fā)表的《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》[2]，標(biāo)志著復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元的到來(lái)。研究表明，社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一種重要屬性。社團(tuán)內(nèi)部的節(jié)點(diǎn)具有較強(qiáng)聯(lián)系，而社團(tuán)間節(jié)點(diǎn)之間聯(lián)系則相對(duì)較少。社團(tuán)劃分技術(shù)是近年來(lái)復(fù)雜網(wǎng)絡(luò)研究的重要方向之一，在分析研究復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、信息傳遞模式、節(jié)點(diǎn)重要性評(píng)估以及行為預(yù)測(cè)方面都具有重要的理論意義。

目前，較為成熟的社團(tuán)劃分算法通常有兩大類(lèi)：一類(lèi)是計(jì)算機(jī)科學(xué)中的圖形分割算法(Graph partitioning)，另一類(lèi)是社會(huì)學(xué)中的分級(jí)聚類(lèi)算法(Hierarchical Clustering)。圖形分割算法主要包括Kernignan-Lin算法、譜平分法、派系過(guò)濾法，分級(jí)聚類(lèi)算法又可以分為分裂算法和凝聚算法兩類(lèi)[3]。

對(duì)算法性能和有效性的分析研究離不開(kāi)特定的數(shù)據(jù)對(duì)象，也稱(chēng)數(shù)據(jù)集。對(duì)同一數(shù)據(jù)集應(yīng)用于不同的社團(tuán)劃分算法并分析實(shí)驗(yàn)結(jié)果，能夠客觀(guān)反映出算法自身的特點(diǎn)，以便進(jìn)行算法之間社團(tuán)劃分精度和效率的橫向比較研究。

2 實(shí)驗(yàn)數(shù)據(jù)集

2.1 測(cè)試數(shù)據(jù)1：Zachary空手道俱樂(lè)部網(wǎng)絡(luò)

在社團(tuán)劃分研究中，最常用的一個(gè)經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)集就是“Zachary空手道俱樂(lè)部網(wǎng)絡(luò)”。該網(wǎng)絡(luò)是社會(huì)學(xué)家Zachary于20世紀(jì)70年代初期，通過(guò)觀(guān)察美國(guó)一所大學(xué)空手道俱樂(lè)部中 34名俱樂(lè)部成員間的社會(huì)關(guān)系而形成的。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)表示俱樂(lè)部中的一位成員，聯(lián)系節(jié)點(diǎn)間的邊表示俱樂(lè)部成員之間的某種關(guān)系，如成員在俱樂(lè)部之外的地方有較多的社會(huì)活動(dòng)[5]。

圖1 Zachary空手道俱樂(lè)部成員關(guān)系網(wǎng)絡(luò)

Zachary在調(diào)查過(guò)程中發(fā)現(xiàn)，圖1中的34號(hào)節(jié)點(diǎn)俱樂(lè)部主管John與圖1中1號(hào)節(jié)點(diǎn)俱樂(lè)部教練Hi因?yàn)槭召M(fèi)問(wèn)題發(fā)生爭(zhēng)議，最終導(dǎo)致該俱樂(lè)部分裂成兩個(gè)小俱樂(lè)部。因?yàn)閮蓚€(gè)俱樂(lè)部原來(lái)的淵源，分裂后的兩個(gè)小俱樂(lè)部中部分成員之間仍然存在一些聯(lián)系[5]。

2.2 測(cè)試數(shù)據(jù)2：“CSMAR數(shù)據(jù)庫(kù)”查詢(xún)股票數(shù)據(jù)

“國(guó)泰安數(shù)據(jù)服務(wù)中心”(CSMAR Solution)是由深圳市國(guó)泰安信息技術(shù)有限公司自主研發(fā)的網(wǎng)站系統(tǒng)。國(guó)泰安信息技術(shù)有限公司是國(guó)家科技部重點(diǎn)支持的高科技龍頭企業(yè)，致力于為教育、科研和證券機(jī)構(gòu)提供一流的中國(guó)財(cái)經(jīng)數(shù)據(jù)庫(kù)、金融工程等高端金融分析工具以及金融專(zhuān)業(yè)培訓(xùn)。

使用中國(guó)股票市場(chǎng)交易數(shù)據(jù)庫(kù)，大大節(jié)約了研究過(guò)程中處理數(shù)據(jù)的寶貴時(shí)間，提高了研究效率。中國(guó)股票市場(chǎng)交易數(shù)據(jù)庫(kù)是基礎(chǔ)庫(kù)，已廣泛地應(yīng)用于各種實(shí)證研究當(dāng)中。

3 經(jīng)典的GN社團(tuán)劃分算法

3.1 GN社團(tuán)劃分算法

3.1.1 GN社團(tuán)劃分算法概述

GN算法是Girvan和Newman在2002年提出的一種基于邊的介數(shù)的社團(tuán)劃分算法。該算法是通過(guò)刪除圖中某些邊，找出網(wǎng)絡(luò)中最自然的分割[4]。

該算法的設(shè)計(jì)思想是：依據(jù)社團(tuán)的定義，聯(lián)系社團(tuán)之間的邊相對(duì)較少，這些較少的連接，也就是邊，是社團(tuán)之間的“瓶頸”，是聯(lián)系不同社團(tuán)的必經(jīng)之路。因此，這些邊比社團(tuán)內(nèi)部的流量高。將這樣一些流量較高的邊從網(wǎng)絡(luò)中移除時(shí)，網(wǎng)絡(luò)自然會(huì)被分割為若干社團(tuán)。

Girvan和Newman用邊的介數(shù)來(lái)定義這種流量。這是Freeman節(jié)點(diǎn)的介數(shù)在邊上的推廣。圖1中一條邊的介數(shù)定義是：網(wǎng)絡(luò)中任何結(jié)點(diǎn)對(duì)之間的最短路徑中含有這條邊的最短路徑的個(gè)數(shù)。Girvan和Newman提出的GN算法就是反復(fù)計(jì)算圖中介數(shù)最高的邊，并從網(wǎng)絡(luò)中移除這條邊，不斷重復(fù)這個(gè)過(guò)程。當(dāng)兩條或多條邊的介數(shù)同時(shí)具有最高值時(shí)，就隨機(jī)地選擇一條邊將其移除。在一個(gè)具有n個(gè)節(jié)點(diǎn)、m條邊的網(wǎng)絡(luò)中計(jì)算各條邊的介數(shù)的算法時(shí)間復(fù)雜度為O(mn)[6]。

3.1.2 GN社團(tuán)劃分算法優(yōu)缺點(diǎn)與適用情況分析

優(yōu)點(diǎn)：由于GN算法從整個(gè)網(wǎng)絡(luò)的全局出發(fā)進(jìn)行社團(tuán)劃分，是每次通過(guò)移除介數(shù)最大的邊，避免了以往算法的很多缺點(diǎn)。因此，該算法精確度非常高。某種程度上GN算法已成為對(duì)后續(xù)社團(tuán)劃分算法評(píng)價(jià)的標(biāo)準(zhǔn)，被廣泛地應(yīng)用到社團(tuán)劃分及算法分析等諸多方面(圖2)。

缺點(diǎn)：(1)該算法無(wú)法事先判斷網(wǎng)絡(luò)最終應(yīng)該被劃分為多少個(gè)社團(tuán)。(2)該算法通過(guò)不斷地計(jì)算網(wǎng)絡(luò)中各條邊的介數(shù)，并從中找出介數(shù)最大的邊。當(dāng)網(wǎng)絡(luò)中的一條邊被刪除后，一般要重新計(jì)算網(wǎng)絡(luò)每條邊的介數(shù)。因此，該算法的時(shí)間復(fù)雜度較高，最差的時(shí)間復(fù)雜度為O(m2n)(m為邊數(shù)，n為節(jié)點(diǎn)數(shù))。因效率較低，該算法只適合節(jié)點(diǎn)數(shù)較少的網(wǎng)絡(luò)。如果網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較大時(shí)，則該算法運(yùn)算耗時(shí)較長(zhǎng)。

算法適用：GN社團(tuán)劃分算法比較實(shí)用于節(jié)點(diǎn)數(shù)較少，對(duì)社團(tuán)劃分結(jié)果要求較為精準(zhǔn)的網(wǎng)絡(luò)。

圖2 GN算法對(duì)網(wǎng)球俱樂(lè)部Zachary數(shù)據(jù)集的劃分

3.2 Newman快速社團(tuán)劃分算法3.2.1 Newman快速社團(tuán)劃分算法概述

根據(jù)去邊還是加邊的判斷標(biāo)準(zhǔn)，算法執(zhí)行過(guò)程中不斷去邊的算法為分裂算法，反之則是凝聚算法。傳統(tǒng)的GN算法屬于分裂算法，而Newman快速算法屬于凝聚算法。GN算法雖然有較高的精度，但時(shí)間復(fù)雜度也較高，只適用于中小規(guī)模的網(wǎng)絡(luò)。為分析大規(guī)模復(fù)雜網(wǎng)絡(luò)，以凝聚思想為核心，Newman于2004年創(chuàng)造性地提出了一種新的高效的社團(tuán)劃分算法，稱(chēng)為Newman快速社團(tuán)劃分算法[7]。

該算法采用基于婪算法的思想，將n個(gè)節(jié)點(diǎn)獨(dú)立為n個(gè)社團(tuán)。首先通過(guò)計(jì)算得出各節(jié)點(diǎn)對(duì)之間的相似性，從相似性最高的節(jié)點(diǎn)對(duì)開(kāi)始，將其添加到n個(gè)節(jié)點(diǎn)、m條邊的空網(wǎng)絡(luò)中。以社團(tuán)模塊性增加或者減小為目標(biāo)不斷合并社團(tuán)，從而得到規(guī)模最大的網(wǎng)絡(luò)社團(tuán)，獲得社團(tuán)劃分的結(jié)果。算法的執(zhí)行流程也可以用樹(shù)狀圖來(lái)表示。這幾個(gè)聯(lián)通子圖也就對(duì)應(yīng)著一種社團(tuán)結(jié)構(gòu)的劃分。

3.2.2 對(duì)經(jīng)典網(wǎng)球俱樂(lè)部Zachary數(shù)據(jù)集劃分的結(jié)果與分析

圖3 Newman算法在Zachary網(wǎng)絡(luò)的劃分層次樹(shù)

利用Newman快速算法對(duì)Zachary網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，當(dāng)模塊度系數(shù)Q取得最大值(0.381)時(shí)，原始網(wǎng)絡(luò)被劃分為17個(gè)大小近似的小社團(tuán)。由圖3可知，只有節(jié)點(diǎn)V10劃分錯(cuò)誤。而在GN算法的分析中，V3也未被正確劃分。因此，該算法在精確度上與GN算法大體相當(dāng)。

3.2.3 Newman快速算法優(yōu)缺點(diǎn)與適用情況分析

優(yōu)點(diǎn)：對(duì)于大規(guī)模網(wǎng)絡(luò)，可以視為稀疏網(wǎng)絡(luò)，其算法時(shí)間復(fù)雜度可以簡(jiǎn)化為O(N2),因此，對(duì)于大規(guī)模網(wǎng)絡(luò)的分析，該算法具有優(yōu)良的性能。

缺點(diǎn)：該算法同GN算法相比，劃分的準(zhǔn)確度比GN算法略低，如Zarchary網(wǎng)絡(luò)中V10節(jié)點(diǎn)被劃分到了錯(cuò)誤的社團(tuán)中。

適用：該算法在時(shí)間復(fù)雜度上具有明顯的優(yōu)勢(shì)，可適用于幾百萬(wàn)個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)。因此，該算法適用于節(jié)點(diǎn)數(shù)量百萬(wàn)級(jí)，而且不要求劃分結(jié)果100%準(zhǔn)確的復(fù)雜系統(tǒng)。

3.3 CNM加權(quán)網(wǎng)絡(luò)社團(tuán)劃分算法

3.3.1 CNM算法概述

2004年，Clauset、Newman和Moore三人在Newman快速算法基礎(chǔ)上，聯(lián)名提出了一種全新的貪婪算法，稱(chēng)為CNM算法[5]。Newman快速算法和CNM算法的相同之處是兩者都用到了增量矩陣ΔQ，然后通過(guò)對(duì)它的元素進(jìn)行更新來(lái)得到一種規(guī)模性更大的社團(tuán)結(jié)構(gòu)。在算法執(zhí)行過(guò)程中，當(dāng)兩個(gè)不相連的社團(tuán)被合并時(shí)，社團(tuán)的模塊度不會(huì)增加。CNM算法只存儲(chǔ)那些相鄰社團(tuán)及合并后模塊度的增加值，達(dá)到了節(jié)約存儲(chǔ)空間的目的。該算法的一個(gè)突出優(yōu)點(diǎn)是時(shí)間復(fù)雜度為O(Nlog2N),已經(jīng)十分接近線(xiàn)性。

即使對(duì)同一種算法采用不同的數(shù)據(jù)結(jié)構(gòu)，算法的時(shí)間復(fù)雜度也會(huì)差別很大。CNM算法采用數(shù)據(jù)結(jié)構(gòu)中的“堆”進(jìn)行計(jì)算。

3.3.2 實(shí)驗(yàn)數(shù)據(jù)

3.3.2.1 數(shù)據(jù)來(lái)源和構(gòu)造方法

輸入數(shù)據(jù)：

50 47

2 9 0.077 8

2 38 0.102 0

2 42 0.060 0

…………

48 39 0.047 4

49 11 0.082 1

49 32 0.061 7

50 24 0.062 8

(1)數(shù)據(jù)的構(gòu)造方法：使用的數(shù)據(jù)由上海上證50收盤(pán)價(jià),通過(guò)處理建立的無(wú)標(biāo)度網(wǎng)絡(luò)。

(2)數(shù)據(jù)建立的方法：日對(duì)數(shù)收益率Si(t)可以用以下方法求得。

假設(shè)某支股票i(i=1,2,…,N)，該股票在第t個(gè)交易日的收盤(pán)價(jià)格為Yi(t)，則可以用公式Si(t)=lnYi(t)-lnYi(t-1)表示這只股票的日對(duì)數(shù)收益率。

(3)求相關(guān)系數(shù)rij。可用rij表示兩只股票(股票i和股票j)的相關(guān)系數(shù)，股票的同步時(shí)間進(jìn)化可以用相關(guān)系數(shù)表示。相關(guān)系數(shù)rij定義如下：

(1)

(4)求上證50股票價(jià)格相關(guān)性無(wú)標(biāo)度加權(quán)網(wǎng)絡(luò)：相關(guān)性較小的股票不是本文主要研究的對(duì)象，本文關(guān)注的是股票之間的強(qiáng)影響關(guān)系。根據(jù)相關(guān)性系數(shù)正態(tài)分布的規(guī)律，設(shè)定關(guān)系閾值為0.4，并利用相關(guān)性系數(shù)進(jìn)行相關(guān)性連接。以股票為節(jié)點(diǎn)，相關(guān)性系數(shù)為加權(quán)邊，當(dāng)rij≥0.4時(shí)，節(jié)點(diǎn)i和j連邊。當(dāng)|rij|≥0.4時(shí)，節(jié)點(diǎn)i和j不連邊，從而建立起上證50的股票價(jià)格相關(guān)性無(wú)標(biāo)度加權(quán)網(wǎng)絡(luò)模型[8]。

3.3.2.2 輸出結(jié)果

41->49ΔQ=0.012 961

8->26ΔQ=0.012 485

4->50ΔQ=0.012 345

14->49ΔQ=0.011 506

26->49ΔQ=0.010 974

6->49ΔQ=0.010 582

社團(tuán)1中的節(jié)點(diǎn)有：48,44,18,39,13,5。

社團(tuán)2中的節(jié)點(diǎn)有：49,11,34,47,27,35,32,1,23,45,7,38,2,9,42,16,40,313,20,30,43,33,46,37,36,17,29,28,21,22,15,19,41,14,26,8,6。

社團(tuán)3中的節(jié)點(diǎn)有：50,24,10,25,12,4。

其中節(jié)點(diǎn)數(shù)較多的社團(tuán)中的節(jié)點(diǎn)大多數(shù)為金融業(yè)方面的股票，而節(jié)點(diǎn)數(shù)較少的社團(tuán)中的節(jié)點(diǎn)多為農(nóng)、林、牧、漁及文化產(chǎn)業(yè)方面的股票。因此，可以得出，保持好中心位置社團(tuán)就顯得十分重要。這樣，便可避免它給其他社團(tuán)帶來(lái)的風(fēng)險(xiǎn)和不良影響，從容地對(duì)國(guó)民經(jīng)濟(jì)進(jìn)行宏觀(guān)調(diào)控。該算法不僅揭示了哪些股票所在的社團(tuán)更具影響力，而且顯示了不同節(jié)點(diǎn)在社團(tuán)中的影響力。

3.3.4 算法性能分析

優(yōu)點(diǎn)：CNM算法同Newman快速算法一樣具有極高的運(yùn)行效率。因?yàn)樗峭ㄟ^(guò)對(duì)Newman快速算法中模塊度進(jìn)行加權(quán)，從而選出在加權(quán)網(wǎng)絡(luò)中最相似的兩個(gè)節(jié)點(diǎn)合并為一個(gè)社團(tuán)。因?yàn)椴捎枚呀Y(jié)構(gòu)更新網(wǎng)絡(luò)的模塊度，該算法的時(shí)間復(fù)雜度只有O(Nlog2N),這樣的時(shí)間復(fù)雜度已經(jīng)十分接近線(xiàn)性。

4 結(jié)束語(yǔ)

社團(tuán)劃分技術(shù)是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究中的重要課題之一，它在各個(gè)領(lǐng)域的應(yīng)用有重要的理論價(jià)值和現(xiàn)實(shí)意義。三種經(jīng)典社團(tuán)劃分算法中，GN算法精度較高，但時(shí)間復(fù)雜度也較高，適用于對(duì)結(jié)果要求比較精確的節(jié)點(diǎn)數(shù)較少的社團(tuán)。Newman快速算法在時(shí)間復(fù)雜度上較GN算法占優(yōu)勢(shì)，但精確度略低于GN算法。CNM算法同Newman快速算法時(shí)間復(fù)雜度相同，適用于加權(quán)的復(fù)雜網(wǎng)絡(luò)。

因?yàn)閷?duì)社團(tuán)概念本身還缺乏嚴(yán)格的數(shù)學(xué)定義，各種社團(tuán)劃分算法還缺乏統(tǒng)一嚴(yán)格的衡量標(biāo)準(zhǔn)。多數(shù)算法雖然具有較高的社團(tuán)識(shí)別精度，但執(zhí)行效率往往不高。進(jìn)一步提高社團(tuán)識(shí)別精度和較高的執(zhí)行效率是以后社團(tuán)劃分算法的一個(gè)重要研究方向。

[1]Watts DJ,Strogatz SH.Collective dynamics of small-world networks[J].Nature，1998，393(4):440-442

[2]Bráabasi A L,Albert R.Emergence of scaling in random networks[J]. Science，1999，286(15):509-512

[3]郭世澤，陸哲明.復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京：科學(xué)出版社，2012:265-289

[4]丁連紅，時(shí)鵬.網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[M].北京：化學(xué)工業(yè)出版社，2008:18-33

[5]汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京：高等教育出版社，2013:119-153

[6]薄輝.社區(qū)發(fā)現(xiàn)技術(shù)的研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，2009:13-25

[7]鐘芬芬.復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究[D].西安：西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，2012:5-17

[8]王浩，李國(guó)歡，姚洪亮，等.基于影響力計(jì)算模型的股票網(wǎng)絡(luò)社團(tuán)劃分算法[J].計(jì)算機(jī)研究與發(fā)展，2014，51(10):2137-2147

[9]羅明偉，姚洪亮，李俊照，等.一種基于節(jié)點(diǎn)相異度的社團(tuán)層次劃分算法[J].計(jì)算機(jī)工程，2014，40(1):275-279

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2015.06.024

2015-03-20

安徽省教育廳質(zhì)量工程項(xiàng)目“《網(wǎng)絡(luò)互聯(lián)技術(shù)》精品資源共享課程”(2013gxk159)。

莊城山(1975-)，江蘇南京人，碩士，高級(jí)工程師，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與虛擬化技術(shù)。

O157.5

A

1673-2006(2015)06-0090-04