摘  要： 社區(qū)挖掘算法研究是復(fù)雜網(wǎng)絡(luò)分析領(lǐng)域的熱點(diǎn)問(wèn)題。傳統(tǒng)層次聚類算法在復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘過(guò)程中，需要計(jì)算所有頂點(diǎn)對(duì)之間的相似度。針對(duì)這一缺點(diǎn)，在詳述了常見(jiàn)相似度計(jì)算方法和頂點(diǎn)重要性度量方法的基礎(chǔ)上，將ego角色的探測(cè)過(guò)程引入層次聚類算法，而后只計(jì)算其他頂點(diǎn)與ego頂點(diǎn)之間的相似度，提高了社區(qū)挖掘效率。最后在不同類型的現(xiàn)實(shí)網(wǎng)絡(luò)中驗(yàn)證了算法的有效性。
關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò)；社區(qū)挖掘；層次聚類

　復(fù)雜網(wǎng)絡(luò)表示現(xiàn)實(shí)世界中具有網(wǎng)絡(luò)結(jié)構(gòu)特性的諸多系統(tǒng),它通常具有顯著的社區(qū)結(jié)構(gòu)，同質(zhì)頂點(diǎn)聚集在同一社區(qū)，異質(zhì)頂點(diǎn)分布于不同社區(qū)，表現(xiàn)為社區(qū)內(nèi)部頂點(diǎn)之間連接邊稠密，社區(qū)之間連接邊數(shù)量相對(duì)稀疏[1]。社區(qū)挖掘是復(fù)雜網(wǎng)絡(luò)分析領(lǐng)域的熱點(diǎn)問(wèn)題，可以將現(xiàn)有的社區(qū)挖掘算法歸納為三大類[2]：基于優(yōu)化的算法、啟發(fā)式算法以及其他算法。基于相似度的層次聚類算法[3]屬于其他算法，這類算法不需要任何先驗(yàn)知識(shí)就可以有效地發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。當(dāng)前的層次聚類算法的主要缺點(diǎn)是需要計(jì)算所有頂點(diǎn)對(duì)之間的相似度，時(shí)間復(fù)雜度為O(n2)，n表示圖中頂點(diǎn)數(shù)量，不適用于大規(guī)模網(wǎng)絡(luò)分析。針對(duì)這一缺點(diǎn)，受到社交網(wǎng)絡(luò)分析相關(guān)方法的啟發(fā)，本文提出一種改進(jìn)的層次聚類算法。
    社交網(wǎng)絡(luò)分析[4]是復(fù)雜網(wǎng)絡(luò)分析的一個(gè)分支，社交網(wǎng)絡(luò)中有一類Ego Networks，表現(xiàn)為有一個(gè)中心結(jié)點(diǎn)(即ego)，圖中所有其他結(jié)點(diǎn)（稱為alters）與中心結(jié)點(diǎn)直接連接，alter之間也有邊相連。社會(huì)學(xué)理論[5]指出，關(guān)系緊密的角色之間相似度偏高，如果兩個(gè)角色之間共同點(diǎn)越多，則這兩者就越有可能是朋友或者具有緊密的聯(lián)系。當(dāng)與某確定角色比較，角色A與角色B的相似度值接近時(shí)，可以認(rèn)為角色A與B具有某種同質(zhì)性?；谶@一理論，對(duì)層次聚類算法進(jìn)行改進(jìn)，在探測(cè)出網(wǎng)絡(luò)中扮演ego角色頂點(diǎn)的前提下，計(jì)算其他頂點(diǎn)與ego的相似度，而不是計(jì)算所有頂點(diǎn)對(duì)之間的相似度，此種情況下，算法時(shí)間復(fù)雜度為O(n)，計(jì)算負(fù)荷與網(wǎng)絡(luò)規(guī)模呈線性相關(guān)。實(shí)驗(yàn)結(jié)果表明，該算法可能在準(zhǔn)確性上稍有不足，但是能有效降低網(wǎng)絡(luò)分析規(guī)模、計(jì)算復(fù)雜度和大致發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。
1 算法準(zhǔn)備
1.1 相似度計(jì)算
    相似度[3-4]是對(duì)圖中頂點(diǎn)之間的相似或者相異程度的度量，是層次聚類算法的核心概念，可以大致將現(xiàn)有的相似度計(jì)算方法分為三大類：
    第一類，可以將頂點(diǎn)嵌入到n維歐式空間中，通過(guò)給頂點(diǎn)分配合理的n維坐標(biāo)，將網(wǎng)絡(luò)聚類問(wèn)題轉(zhuǎn)化為空間點(diǎn)聚類問(wèn)題。給定兩個(gè)頂點(diǎn)，A=(a1，a2，…，an)和B=(b1，b2，…，bn)，則可以利用各種距離度量方法計(jì)算兩者的距離。例如，歐幾里得距離：
    

2 改進(jìn)的層次聚類算法
    用于表示現(xiàn)實(shí)網(wǎng)絡(luò)系統(tǒng)的復(fù)雜網(wǎng)絡(luò)通常具有的層次結(jié)構(gòu)特征，即較大的社區(qū)結(jié)構(gòu)包含較小的社區(qū)結(jié)構(gòu)。層次聚類算法能有效地發(fā)現(xiàn)這種層次結(jié)構(gòu)，被廣泛應(yīng)用于社交網(wǎng)絡(luò)分析、生物工程、市場(chǎng)分析等領(lǐng)域。層次聚類算法可以分為兩大類：
    (1)凝聚方法：采用自底向上的策略，首先將每個(gè)對(duì)象作為簇（cluster），然后合并這些原子簇成為更大的簇，直到所有對(duì)象都在一個(gè)簇中，或者滿足某終止條件。
    (2)分裂方法：采用自頂向下的策略，首先將所有對(duì)象置于一個(gè)簇中，然后逐步細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象各為一簇，或滿足某終止條件，例如達(dá)到了希望的簇?cái)?shù)或每個(gè)簇的直徑都在某個(gè)閾值內(nèi)。
    由于分裂方法很少使用，本文討論的算法采用自底向上的策略。通常可以用樹(shù)狀圖（dendrogram）表示層次聚類的過(guò)程，如圖1所示。
    層次聚類算法將網(wǎng)絡(luò)劃分為幾個(gè)社區(qū)取決于在什么位置分割樹(shù)狀圖，如圖1中橫線位置將產(chǎn)生兩個(gè)社區(qū)結(jié)構(gòu)。實(shí)際網(wǎng)絡(luò)中通常依據(jù)模塊性標(biāo)準(zhǔn)來(lái)確定最佳的劃分位置。
    傳統(tǒng)層次聚類算法在確定相似度計(jì)算方法后，計(jì)算所有頂點(diǎn)對(duì)之間的相似度。本文在傳統(tǒng)方法的基礎(chǔ)上，引入ego角色探測(cè)過(guò)程，根據(jù)復(fù)雜網(wǎng)絡(luò)具體特征，首先確定相似度計(jì)算方法，然后確定ego角色的探測(cè)方法，一旦扮演ego角色的頂點(diǎn)被確定，則只計(jì)算圖中所有其他頂點(diǎn)與ego頂點(diǎn)之間的相似度，這種情況下，時(shí)間復(fù)雜度取決于ego探測(cè)過(guò)程，例如，選定Degree Centrality作為ego探測(cè)策略，總的時(shí)間復(fù)雜度可表示為O(n)?？梢?jiàn)，在大規(guī)模網(wǎng)絡(luò)分析中，改進(jìn)的層次聚類算法具有較大優(yōu)勢(shì)。算法步驟如下。
Input:Graph G=(V,E), V include all vertexs, E include all edges
Output:Communities C1, C2, C3,……
Declare:score(v) // score of vertex v according to the ego vertex compute method
        similarity(v1,v2) //similarity between v1 and v2
Begin
//step1:basic step for detecting communities in C
;Define similarity compute method
;Define ego vertex compute method
for?坌v∈V do
    compute score(v)
endfor
v(ego)=MAX(score(v1), score(v2),……);Find ego vertex v(ego)
for ?坌v∈V\v(ego) do
    compute similarity(v, v(ego))
endfor
start to cluster vertexs based on similarities
produce C1’, C2’, C3’,……
//step2:continue to detect subgroup in groups have been found
if do not satisfy the end conditon then
    for ?坌C∈{C1’,C2’,C3’,……} do
          run step1 procedure in C
    endfor
else
    output the final result C1,C2,C3……
endif
end
    該算法可以有兩種應(yīng)用用途：在較理想的情形下，例如復(fù)雜網(wǎng)絡(luò)表示的是現(xiàn)實(shí)的EgoNetworks，則算法能有效挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)；對(duì)于準(zhǔn)確度要求很高以及復(fù)雜網(wǎng)絡(luò)規(guī)模巨大、特征不明確的情形，本文算法可作為網(wǎng)絡(luò)預(yù)處理過(guò)程，用于降低網(wǎng)絡(luò)分析規(guī)模，此時(shí)算法只產(chǎn)生規(guī)模合適的粗糙的社區(qū)，再運(yùn)用其他準(zhǔn)確度較高的算法，劃分出更精確的社區(qū)。
3 實(shí)驗(yàn)分析
3.1 EgoNetworks中的算法應(yīng)用
    該EgoNetworks數(shù)據(jù)采集自社交網(wǎng)站人人網(wǎng)，包含了一個(gè)Ego角色和49個(gè)alter角色。圖中頂點(diǎn)代表一個(gè)個(gè)體，邊表示個(gè)體之間的好友關(guān)系。由調(diào)查得知，該網(wǎng)絡(luò)包含三個(gè)同學(xué)群體，一個(gè)陌生人群體，一個(gè)親密好友群體。運(yùn)用改進(jìn)的層次聚類算法，成功地挖掘出了網(wǎng)絡(luò)中包含的五個(gè)社區(qū)，算法采用的相似度計(jì)算方法是頂點(diǎn)間海明距離，ego角色在初始狀態(tài)是已知的，第一次迭代后利用Degree Centrality探測(cè)新的ego角色。圖2描述了模塊度Q值隨社區(qū)個(gè)數(shù)變化的分布圖，x軸表示社區(qū)數(shù)量，y軸表示對(duì)應(yīng)的Q值。
    由圖2可見(jiàn)，當(dāng)Q值取最大0.363時(shí)，對(duì)應(yīng)的社區(qū)個(gè)數(shù)為5，此時(shí)劃分質(zhì)量最高，網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)圖如圖3所示。

3.2 “Zachary空手道俱樂(lè)部網(wǎng)絡(luò)”中的算法應(yīng)用
    Zachary空手道俱樂(lè)部網(wǎng)絡(luò)[8]是測(cè)試社區(qū)挖掘算法的經(jīng)典網(wǎng)絡(luò)，該網(wǎng)絡(luò)描述了美國(guó)一所大學(xué)空手道俱樂(lè)部的34名成員之間的關(guān)系，其中包含了兩個(gè)已知的社區(qū)結(jié)構(gòu)。圖4的劃分結(jié)果來(lái)自Girvan-Newman算法，不同社區(qū)用不同顏色頂點(diǎn)區(qū)分。

    本文算法在選定Degree Centrality和海明距離分別作為ego角色探測(cè)和相似度計(jì)算策略后，劃分結(jié)果如表1所示。

    表1中，除了10,12,32,28四個(gè)頂點(diǎn)劃分有誤，其他都正確。在這種非EgoNetworks中，根據(jù)網(wǎng)絡(luò)特征選取恰當(dāng)?shù)南嗨贫扔?jì)算和ego角色探測(cè)方法很重要，實(shí)驗(yàn)中選擇了較簡(jiǎn)單的方法，雖然在準(zhǔn)確性上有不足，但是時(shí)間復(fù)雜度只有O(n)，較傳統(tǒng)方法的O(n2)，在大規(guī)模網(wǎng)絡(luò)中，改進(jìn)的層次聚類算法優(yōu)勢(shì)明顯。
    社區(qū)挖掘是復(fù)雜網(wǎng)絡(luò)分析的重要手段之一。本文總結(jié)了復(fù)雜網(wǎng)絡(luò)中常用的頂點(diǎn)間相似度計(jì)算方法和頂點(diǎn)重要性度量方法，在此基礎(chǔ)上，對(duì)傳統(tǒng)的層次聚類算法進(jìn)行改進(jìn)，引入網(wǎng)絡(luò)中“ego”角色的探測(cè)過(guò)程，并在現(xiàn)實(shí)的EgoNetworks以及經(jīng)典實(shí)際網(wǎng)絡(luò)中驗(yàn)證了算法的有效性。雖然改進(jìn)的層次聚類算法能很好地提高社區(qū)挖掘效率，但是在準(zhǔn)確性上仍有不足之處。如何提高算法準(zhǔn)確度以及如何根據(jù)具體的網(wǎng)絡(luò)特征，制定合適的相似度計(jì)算和“ego”角色探測(cè)方法是以后研究的主要工作。
參考文獻(xiàn)
[1] GIRVAN M，NEWMAN M E J.Community structure in  social and biological networks[C].Proc.Natl.Acad.Sci.USA  99，2002：7821-7826.
[2] Yang Bo, Liu Dayou, Liu Jiming, et al.Complex network clustering algorithms[J]. Journal of Software, 2009,20(1)：54-66.
[3] FORTUNATO S.Community detection in graphs[C].arXiv：0906.0612，2010.
[4] HANNEMAN R A，RIDDLE M.Introduction to social network methods[M/OL].Riverside，CA：Universityof California，Riverside,2005.http://faculty.ucr.edu/~hanneman/.
[5] ADAMIC L A，ADAR E.Friends and neighbors on the web[J].Social Networks, 2007,25(2): 211-230.
[6] NEWMAN M E J.Mathematics of networks[M].In The New Palgrave Encyclopedia of Economics, 2nd edition.Palgrave  Macmillan, Basingstoke, 2007.
[7] NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E, 69,2004.
[8] ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research, 1977, 33(2):452-473.