基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法

孟凡榮，張可為，朱 牧

（中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116）

0 引 言

目前，復(fù)雜網(wǎng)絡(luò)聚類算法得到了廣泛的研究［1－3］，算法主要包括模塊度優(yōu)化算法［4，5］、 啟發(fā)式算法［6，7］、 基 于 模 型的算法［8，9］等，文獻(xiàn) ［10］給出了詳細(xì)的綜述。然而，大多數(shù)已有的算法都是無(wú)監(jiān)督的學(xué)習(xí)方式，不能夠利用少量的先驗(yàn)知識(shí)對(duì)復(fù)雜網(wǎng)絡(luò)的聚類進(jìn)行有效指導(dǎo)。而往往在很多實(shí)際應(yīng)用中，可以獲取少量有關(guān)社區(qū)結(jié)構(gòu)的先驗(yàn)知識(shí)，例如類標(biāo)簽或者成對(duì)約束信息等，如何利用這些知識(shí)指導(dǎo)復(fù)雜網(wǎng)絡(luò)的聚類，并提高社區(qū)發(fā)現(xiàn)的性能，具有非常重要的意義［11］。

針對(duì)上述問(wèn)題，本文提出一種基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法，以利用少量的先驗(yàn)知識(shí)來(lái)有效提高復(fù)雜網(wǎng)絡(luò)的聚類性能。本文算法首先采用must－link和cannot－link兩種常用的約束對(duì)信息來(lái)表示先驗(yàn)知識(shí)，并根據(jù)must－link的傳遞性質(zhì)計(jì)算并記錄所有相互之間滿足must－link約束的節(jié)點(diǎn)集合；然后，在基于密度的復(fù)雜網(wǎng)絡(luò)聚類算法［12］的基礎(chǔ)上，根據(jù)所獲取的所有的約束關(guān)系，在對(duì)節(jié)點(diǎn)集進(jìn)行遍歷過(guò)程中識(shí)別并記錄節(jié)點(diǎn)之間相互連通的關(guān)系，并在先驗(yàn)知識(shí)的指導(dǎo)下發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的連接信息并進(jìn)一步修改節(jié)點(diǎn)的原有遍歷方式，從而發(fā)現(xiàn)滿足連通性和最大性的社區(qū)結(jié)構(gòu)。在若干真實(shí)復(fù)雜網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，新算法相對(duì)于其它幾種代表性的半監(jiān)督算法，能夠更加有效地提高無(wú)監(jiān)督聚類的性能。

1 密度聚類算法

給定復(fù)雜網(wǎng)絡(luò)G＝ （V，E），V表示節(jié)點(diǎn)的集合，E表示邊的集合，基于密度的復(fù)雜網(wǎng)絡(luò)聚類算法［12］主要包含如下若干定義：

定義1 節(jié)點(diǎn)v的節(jié)點(diǎn)結(jié)構(gòu)定義為節(jié)點(diǎn)v和其所有鄰居節(jié)點(diǎn)組成的節(jié)點(diǎn)集，記為N（v），如下所示

定義2 節(jié)點(diǎn)v和節(jié)點(diǎn)w的結(jié)構(gòu)相似度為將兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)結(jié)構(gòu)進(jìn)行余弦相似度計(jì)算得到的結(jié)果，記為Sim（v，w），如下所示

定義3 節(jié)點(diǎn)v的近鄰節(jié)點(diǎn)為節(jié)點(diǎn)v的節(jié)點(diǎn)結(jié)構(gòu)中所有與v的結(jié)構(gòu)相似度不小于參數(shù)ε的節(jié)點(diǎn)構(gòu)成的集合，記為Nε（v），如下所示

定義4 若節(jié)點(diǎn)v的近鄰節(jié)點(diǎn)數(shù)目不小于設(shè)定的參數(shù)μ，則稱節(jié)點(diǎn)v為核節(jié)點(diǎn)，表示為Cε，μ（v），如下所示

定義5 如果節(jié)點(diǎn)w屬于節(jié)點(diǎn)v的近鄰節(jié)點(diǎn)，而且節(jié)點(diǎn)v是核節(jié)點(diǎn)，那么v到w是直接結(jié)構(gòu)聯(lián)通，記為Dirrε，μ（v，w），如下所示

定義6 節(jié)點(diǎn)v到節(jié)點(diǎn)w結(jié)構(gòu)聯(lián)通即存在一個(gè)節(jié)點(diǎn)集，使得節(jié)點(diǎn)v與這些節(jié)點(diǎn)通過(guò)直接結(jié)構(gòu)聯(lián)通的傳遞性可以到達(dá)節(jié)點(diǎn)w。

定義7 結(jié)構(gòu)社區(qū)表示算法對(duì)網(wǎng)絡(luò)進(jìn)行聚類得到的一個(gè)社區(qū)，這個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)之間是結(jié)構(gòu)聯(lián)通的，并且這個(gè)社區(qū)包含了所有內(nèi)部節(jié)點(diǎn)的結(jié)構(gòu)聯(lián)通節(jié)點(diǎn)集，即節(jié)點(diǎn)數(shù)目達(dá)到最大。

密度聚類算法遍歷樣本節(jié)點(diǎn)集，通過(guò)直接結(jié)構(gòu)聯(lián)通的傳遞關(guān)系將所有與核節(jié)點(diǎn)聯(lián)系密切的節(jié)點(diǎn)都聚到同一個(gè)社區(qū)中，保證了社區(qū)的聯(lián)通性和最大性，遍歷過(guò)程中如果節(jié)點(diǎn)不是核節(jié)點(diǎn)則標(biāo)記為特殊節(jié)點(diǎn)。遍歷結(jié)束后即完成了對(duì)網(wǎng)絡(luò)的社區(qū)劃分。

2 半監(jiān)督密度算法

在實(shí)際聚類研究中，往往可以獲取少量先驗(yàn)知識(shí)，例如類標(biāo)簽或者成對(duì)約束信息等，本文選擇以約束對(duì)信息作為先驗(yàn)知識(shí)。其中，must－link和cannot－link是兩種常用的約束對(duì)信息：must－link表示兩者必須隸屬于同一個(gè)社區(qū)，cannot－link表示兩者必須隸屬于不同的社區(qū)［13］。針對(duì)普通密度聚類算法無(wú)法有效利用先驗(yàn)知識(shí)的問(wèn)題，本文提出了基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法。

2.1 先驗(yàn)知識(shí)的表示

定義8 Cm表示所有已知的滿足must－link約束的節(jié)點(diǎn)對(duì)組成的集合，即

定義9 Cc表示所有已知的滿足cannot－link約束的節(jié)點(diǎn)對(duì)組成的集合，即

定義10 TMS表示一個(gè)由若干自成集合的元素組成并且每個(gè)元素內(nèi)部的任意兩個(gè)節(jié)點(diǎn)之間滿足mustlink約束的集合，即

定義11 TCS表示在已知TMS集合的情況下對(duì)Cc集合進(jìn)行拓展得到的所有滿足cannot－link約束的節(jié)點(diǎn)對(duì)組成的集合。

must－link約束具有對(duì)稱性和傳遞性。利用這些性質(zhì)對(duì)Cm集合進(jìn)行計(jì)算，可以發(fā)現(xiàn)隱含的must－link約束，整合即可知道所有已知的和隱含的must－link約束對(duì)，最后將所有相互之間滿足must－link約束的節(jié)點(diǎn)集都保存在TMS中。TMS的具體計(jì)算步驟見(jiàn)算法1：

算法1：CALTMS（G＝ （V，E），Cm ）輸入：V，E，Cm輸出：TMS 01 M＝formMustLinkMatrix（）；02for each vertex vinot in TMSdo 03 generate a new set S’；04 if（vj∈V） ＆ ＆ （M（i，j）＝＝1）then 05 add vjnot in TMSto S’；06 add vinot in TMSto S’；07 if（vx∈V） ＆ ＆ （M（x，j）＝＝1）then 08 add vxnot in TMSto S’；09 end if；10 end if；11 add S’to TMS；12end for；

CALTMS用于根據(jù)Cm集合計(jì)算TMS集合，為聚類過(guò)程提供輸入。其中，算法第1行用于生成一個(gè)n×n維矩陣M，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j滿足 （i，j）∈Cm，則矩陣對(duì)應(yīng)位置的元素為1，否則為0。算法第3－10行用于生成一個(gè)集合S’，里面的元素為所有與節(jié)點(diǎn)i之間滿足must－link約束的節(jié)點(diǎn)。所有的子集S’共同構(gòu)成了TMS集合。

隨后，我們根據(jù)計(jì)算得到的TMS集合來(lái)對(duì)Cc集合進(jìn)行拓展，可以得到TCS集合。內(nèi)部元素為所有已知的和計(jì)算得到的滿足cannot－link約束的節(jié)點(diǎn)對(duì)。

2.2 算法描述

算法根據(jù)前面獲取的所有約束關(guān)系，識(shí)別并影響節(jié)點(diǎn)之間相互連通的關(guān)系，從而發(fā)現(xiàn)滿足連通性和最大性的社區(qū)結(jié)構(gòu)，見(jiàn)算法2，這部分是算法的核心部分。

算法2：TMSSCAN （G＝ （V，E），ε，μ，Cc，TMS）輸入：V，E，ε，μ，Cc，TMS輸出：聚類結(jié)果01for each unmarked vertex v∈Vdo 02if Cε，μ（v）then 03generate new cluster U ，U.id＝newid； Q.add（v）；04 while（Q.size＞0）do 05 y＝Q.poll（）；／／取出Q的第一個(gè)元素，并刪除06 if（y∈cj） ＆ ＆ （cj∈TMS）then 07 for each unmarked or special vertex oin cjdo 08 o.type＝newid； Q.add（o）；09 end for；10 end if；11 R＝ ｛x∈V｜ Dirrε，μ（y，x）｝12 for each x∈Rdo 13 if each vertex pin Q （x，p）（TCSthen 14 x.type＝newid； Q.add（x）；15 end if；16 end for；17 end while；18else 19 v.type＝special；20 end if；21end for；

TMSSCAN開(kāi)始時(shí)默認(rèn)所有的節(jié)點(diǎn)都是未標(biāo)記的。算法從第1行開(kāi)始遍歷所有的樣本節(jié)點(diǎn)，第2行用于判斷當(dāng)前節(jié)點(diǎn)v是否為核節(jié)點(diǎn)，如果是則檢索與節(jié)點(diǎn)v連接緊密的所有節(jié)點(diǎn)，即TMS集合中節(jié)點(diǎn)v所在子集的其它節(jié)點(diǎn)（6－10行）和節(jié)點(diǎn)v的直接結(jié)構(gòu)聯(lián)通節(jié)點(diǎn) （11行），分析這些節(jié)點(diǎn)與當(dāng)前劃分跟TCS集合是否存在矛盾，不矛盾時(shí)將節(jié)點(diǎn)v和這些節(jié)點(diǎn)分配到同一個(gè)社區(qū)中，存在矛盾則分析下一個(gè)與節(jié)點(diǎn)v連接緊密的節(jié)點(diǎn)，檢索結(jié)束即得到一個(gè)由節(jié)點(diǎn)v拓展得到的社區(qū) （3－17行）；如果節(jié)點(diǎn)v不是核節(jié)點(diǎn)，則將其標(biāo)記為特殊節(jié)點(diǎn) （19行）。如此將樣本節(jié)點(diǎn)全部遍歷一遍，即可得到最終的聚類結(jié)果。

聚類過(guò)程中先驗(yàn)知識(shí)的指導(dǎo)作用主要體現(xiàn)在如下部分：TMSSCAN的第6－10行用于將所有與當(dāng)前節(jié)點(diǎn)滿足mustlink約束的節(jié)點(diǎn)都加入到隊(duì)列中，保證最后能聚到同一個(gè)社區(qū)；第13行檢測(cè)能否將當(dāng)前節(jié)點(diǎn)加入隊(duì)列，使得不將滿足cannot－link約束的兩個(gè)節(jié)點(diǎn)聚到同一個(gè)社區(qū)。如此，算法在對(duì)節(jié)點(diǎn)集進(jìn)行遍歷時(shí)充分考慮了TMS集合和TCS集合，保證了先驗(yàn)知識(shí)的有效性。

2.3 復(fù)雜度分析

CALTMS用于計(jì)算TMS集合，其時(shí)間復(fù)雜度跟Cm集合有關(guān)?？紤]最壞的情況，即所有的節(jié)點(diǎn)標(biāo)簽信息已知，在構(gòu)造子集S1’時(shí)，將遍歷標(biāo)簽信息為第一類的節(jié)點(diǎn)，設(shè)其時(shí)間復(fù)雜度為O（a1），設(shè)構(gòu)造子集數(shù)為b，則總共時(shí)間復(fù)雜度為O（a1＋a2＋a3＋…＋ab），其中a1＋a2＋a3＋…＋ab＝n，因此在最壞情況下CALTMS的時(shí)間復(fù)雜度為O（n）。

TMSSCAN在聚類過(guò)程中，需遍歷網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)。對(duì)每個(gè)節(jié)點(diǎn)v，必須檢索其所有鄰居節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O（deg（v））。所以最終的時(shí)間復(fù)雜度為O（（deg（v1）＋deg（v2）＋deg（v3）＋…＋deg（vn））／2），其中deg（v1）＋deg（v2）＋…＋deg（vn）＝2 m，因此TMSSCAN聚類過(guò)程的時(shí)間復(fù)雜度為O（m）。

綜上所述，基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法的時(shí)間復(fù)雜度為O（m＋n）。在對(duì)實(shí)際網(wǎng)絡(luò)進(jìn)行分析時(shí)，網(wǎng)絡(luò)中的邊數(shù)和節(jié)點(diǎn)數(shù)大致相當(dāng)，即m≈n，所以算法時(shí)間復(fù)雜度可以記為O（m）?？芍?，本文所提算法的時(shí)間復(fù)雜度較低，能應(yīng)用于對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類研究。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)環(huán)境為：處理器Inter（R）Core（TM）2Duo 2.8GHz PC，內(nèi)存2G，操作系統(tǒng)為 Windows 7，編程環(huán)境為Visual Studio 2008C＋＋.Net。

3.1 數(shù) 據(jù)

為了驗(yàn)證算法的聚類性能，我們?cè)贜ewman數(shù)據(jù)中的真實(shí)網(wǎng)絡(luò)上進(jìn)行了聚類分析，網(wǎng)絡(luò)的具體信息見(jiàn)表1。

表1 Newman真實(shí)網(wǎng)絡(luò)數(shù)據(jù)

3.2 方 法

我們用基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法 （SSSCAN）對(duì)表1中的數(shù)據(jù)進(jìn)行聚類分析，將結(jié)果與半監(jiān)督譜聚類算法 （SS－SP）［13］、基于 Ncut的半監(jiān)督核K－means算法 （SS－KK）［13］的聚類結(jié)果進(jìn)行了對(duì)比。

實(shí)驗(yàn)中，我們選擇被廣為使用的NMI［14］作為算法聚類精度的評(píng)價(jià)標(biāo)準(zhǔn)，其計(jì)算公式如下

式中：N——一個(gè)矩陣，Nij——既在類Xi中又在簇Yj中的節(jié)點(diǎn)的個(gè)數(shù)，Ni.——矩陣第i行求和的結(jié)果，N.j——矩陣第j列求和的結(jié)果。

3.3 結(jié) 果

我們分別用SS－SCAN、SS－SP和SS－KK 算法在4個(gè)數(shù)據(jù)集上進(jìn)行聚類分析，實(shí)驗(yàn)結(jié)果如圖1、圖2、圖3、圖4所示。其中橫坐標(biāo)表示數(shù)據(jù)中已知標(biāo)簽節(jié)點(diǎn)的比例，考慮實(shí)際情況中已知比例不會(huì)太多的問(wèn)題，其取值范圍為［0，50%］；縱坐標(biāo)表示聚類結(jié)果的NMI值，NMI值越高表示聚類精度越高。

實(shí)驗(yàn)表明在使用半監(jiān)督學(xué)習(xí)之前 （對(duì)應(yīng)圖中已知比例為0的聚類結(jié)果），SS－SCAN算法在football數(shù)據(jù)和karate數(shù)據(jù)上的聚類精度相比其它兩個(gè)算法更高，但在其它兩個(gè)數(shù)據(jù)上的聚類結(jié)果就沒(méi)有這個(gè)現(xiàn)象，說(shuō)明在使用半監(jiān)督學(xué)習(xí)之前，SS－SCAN相比其它兩個(gè)算法在聚類精度上并沒(méi)有絕對(duì)優(yōu)勢(shì)。

使用半監(jiān)督學(xué)習(xí)后 （對(duì)應(yīng)圖中已知比例不為0的聚類結(jié)果），可以發(fā)現(xiàn)，SS－SP算法在前3個(gè)數(shù)據(jù)集上的聚類精度比較高，但其波動(dòng)現(xiàn)象相對(duì)比較明顯 （這是由于算法利用K－means來(lái)對(duì)網(wǎng)絡(luò)提取的特征向量進(jìn)行聚類，K－means不穩(wěn)定導(dǎo)致的），且在adjnoun上的聚類精度是最低的；SS－KK算法在football和adjnoun上的聚類精度比較高，在另外兩個(gè)數(shù)據(jù)集上的表現(xiàn)相對(duì)較差；SS－SCAN算法的聚類精度相比其它兩個(gè)算法在大多數(shù)情況下都是最高的，并且其NMI值隨著已知標(biāo)簽比例的增加大致符合線性增長(zhǎng)的趨勢(shì)，表現(xiàn)相對(duì)穩(wěn)定。

同時(shí)，我們統(tǒng)計(jì)了3個(gè)算法對(duì)4個(gè)數(shù)據(jù)集進(jìn)行聚類所消耗的平均時(shí)間。在實(shí)驗(yàn)中我們發(fā)現(xiàn)引入半監(jiān)督策略對(duì)算法本身的運(yùn)行時(shí)間并不會(huì)有很大程度的改變，在這里我們只給出算法在各種已知比例情況下對(duì)4個(gè)數(shù)據(jù)進(jìn)行聚類的平均時(shí)間，見(jiàn)表2?？芍猄S－SCAN算法的時(shí)間消耗最少。

表2 算法的聚類時(shí)間

綜上所述，SS－SCAN算法的聚類精度更高，聚類結(jié)果更穩(wěn)定，時(shí)間消耗更少，能夠更有效的利用先驗(yàn)知識(shí)指導(dǎo)聚類。

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

本文提出了一種基于密度的半監(jiān)督復(fù)雜網(wǎng)絡(luò)聚類算法，以利用少量的先驗(yàn)知識(shí)提高復(fù)雜網(wǎng)絡(luò)的聚類質(zhì)量。該算法主要包含兩個(gè)重要組成部分：一是利用少量的must－link和cannot－link兩種常用的成對(duì)約束信息，發(fā)現(xiàn)網(wǎng)絡(luò)中所有潛在的成對(duì)約束，最大化先驗(yàn)知識(shí)，以更好的提高聚類質(zhì)量；二是在基于密度的方法基礎(chǔ)上，判斷兩個(gè)節(jié)點(diǎn)是否屬于同一個(gè)社區(qū)時(shí)，綜合考慮了節(jié)點(diǎn)之間的可達(dá)性和成對(duì)約束兩方面的因素，從而更加準(zhǔn)確地對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行有效劃分。在若干真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，本文所提出的算法相對(duì)于其它幾種代表性的半監(jiān)督聚類算法，更能夠有效利用少量的先驗(yàn)知識(shí)，穩(wěn)定地提高聚類的質(zhì)量。

［1］Fortunato Santo.Community detection in graphs ［J］.Physics Reports，2010，486 （3－5）：75－174.

［2］ZHAO Yunpeng，Levina Elizaveta，ZHU Ji.Community extraction for social networks ［J］.Proceedings of the National Academy of Sciences of the United States of America，2011，108 （18）：7321－7326.

［3］YANG Bo，LIU Dayou，LIU Jiming，et al.Complex network clustering algorithms ［J］.Journal of Software，2009，20（1）：54－66 （in Chinese）.［楊博，劉大有，LIU Jiming，等.復(fù)雜網(wǎng)絡(luò)聚類方法 ［J］.軟件學(xué)報(bào)，2009，20 （1）：54－66.］

［4］Mucha Peter J，Richardson Thomas，Macon Kevin，et al.Community structure in time－dependent，multiscale，and multiplex networks ［J］.Science，2010，328 （5980）：876－878.

［5］ZHANG X S，WANG R S，WANG Y，et al.Modularity optimization in community detection of complex networks ［J］.Europhysics Letters，2009，87 （3）：38002.

［6］Good Benjamin H，Montjoye Yves Alexandre de，CLAUSET Aaron.Performance of modularity maximization in practical contexts［J］.Physical Review E，2010，81 （4）：046106.

［7］Tantipathananandh Chayant，Tanya Berger Wolf.Constantfactor approximation algorithms for identifying dynamic communities［C］／／New York：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：827－836.

［8］Hofman J M，Wiggins C H.Bayesian approach to network modularity ［J］.Physical Review Letters，2008，100（25）：258701.

［9］Clauset Aaron，Moore Cristopher，Newman M E J.Hierar－chical structure and the prediction of missing links in networks［J］.Nature，2008，453 （7191）：98－101.

［10］Coscia Michele，Giannotti Fosca，Pedreschi Dino.A classification for community discovery methods in complex networks ［J］.Statistical Analysis and Data Mining，2011，4 （5）：512－546.

［11］ZHAO Weizhong，MA Huifang，LI Zhiqing，et al.Efficiently active learning for semi－supervised document clustering［J］.Journal of Software，2012，23 （6）：1486－1499 （in Chinese）.［趙衛(wèi)中，馬慧芳，李志清，等.一種結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督文檔聚類算法 ［J］.軟件學(xué)報(bào)，2012，23 （6）：1486－1499.］

［12］Xu Xiaowei，Yuruk Nurcan，F(xiàn)eng Zhidan，et al.SCAN：A structural clustering algorithm for networks ［C］／／New York：Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824－833.

［13］MA Xiaoke，GAO Lin，YONG Xuerong，et al.Semi－supervised clustering algorithm for community structure detection in complex networks［J］.Physica A：Statistical Mechanics and its Applications，2010，389 （1）：187－197.

［14］TANG Lei，WANG Xufei，LIU Huan.Community detection via heterogeneous interaction analysis ［J］.Data Mining and Knowledge Discovery，2012，25 （1）：1－33.