基于密度的半監督復雜網絡聚類算法

孟凡榮，張可為，朱 牧

（中國礦業大學 計算機科學與技術學院，江蘇 徐州221116）

0 引 言

目前，復雜網絡聚類算法得到了廣泛的研究［1－3］，算法主要包括模塊度優化算法［4，5］、 啟發式算法［6，7］、 基 于 模 型的算法［8，9］等，文獻 ［10］給出了詳細的綜述。然而，大多數已有的算法都是無監督的學習方式，不能夠利用少量的先驗知識對復雜網絡的聚類進行有效指導。而往往在很多實際應用中，可以獲取少量有關社區結構的先驗知識，例如類標簽或者成對約束信息等，如何利用這些知識指導復雜網絡的聚類，并提高社區發現的性能，具有非常重要的意義［11］。

針對上述問題，本文提出一種基于密度的半監督復雜網絡聚類算法，以利用少量的先驗知識來有效提高復雜網絡的聚類性能。本文算法首先采用must－link和cannot－link兩種常用的約束對信息來表示先驗知識，并根據must－link的傳遞性質計算并記錄所有相互之間滿足must－link約束的節點集合；然后，在基于密度的復雜網絡聚類算法［12］的基礎上，根據所獲取的所有的約束關系，在對節點集進行遍歷過程中識別并記錄節點之間相互連通的關系，并在先驗知識的指導下發現網絡中隱含的連接信息并進一步修改節點的原有遍歷方式，從而發現滿足連通性和最大性的社區結構。在若干真實復雜網絡上的實驗結果表明，新算法相對于其它幾種代表性的半監督算法，能夠更加有效地提高無監督聚類的性能。

1 密度聚類算法

給定復雜網絡G＝ （V，E），V表示節點的集合，E表示邊的集合，基于密度的復雜網絡聚類算法［12］主要包含如下若干定義：

定義1 節點v的節點結構定義為節點v和其所有鄰居節點組成的節點集，記為N（v），如下所示

定義2 節點v和節點w的結構相似度為將兩個節點的節點結構進行余弦相似度計算得到的結果，記為Sim（v，w），如下所示

定義3 節點v的近鄰節點為節點v的節點結構中所有與v的結構相似度不小于參數ε的節點構成的集合，記為Nε（v），如下所示

定義4 若節點v的近鄰節點數目不小于設定的參數μ，則稱節點v為核節點，表示為Cε，μ（v），如下所示

定義5 如果節點w屬于節點v的近鄰節點，而且節點v是核節點，那么v到w是直接結構聯通，記為Dirrε，μ（v，w），如下所示

定義6 節點v到節點w結構聯通即存在一個節點集，使得節點v與這些節點通過直接結構聯通的傳遞性可以到達節點w。

定義7 結構社區表示算法對網絡進行聚類得到的一個社區，這個社區內部的節點之間是結構聯通的，并且這個社區包含了所有內部節點的結構聯通節點集，即節點數目達到最大。

密度聚類算法遍歷樣本節點集，通過直接結構聯通的傳遞關系將所有與核節點聯系密切的節點都聚到同一個社區中，保證了社區的聯通性和最大性，遍歷過程中如果節點不是核節點則標記為特殊節點。遍歷結束后即完成了對網絡的社區劃分。

2 半監督密度算法

在實際聚類研究中，往往可以獲取少量先驗知識，例如類標簽或者成對約束信息等，本文選擇以約束對信息作為先驗知識。其中，must－link和cannot－link是兩種常用的約束對信息：must－link表示兩者必須隸屬于同一個社區，cannot－link表示兩者必須隸屬于不同的社區［13］。針對普通密度聚類算法無法有效利用先驗知識的問題，本文提出了基于密度的半監督復雜網絡聚類算法。

2.1 先驗知識的表示

定義8 Cm表示所有已知的滿足must－link約束的節點對組成的集合，即

定義9 Cc表示所有已知的滿足cannot－link約束的節點對組成的集合，即

定義10 TMS表示一個由若干自成集合的元素組成并且每個元素內部的任意兩個節點之間滿足mustlink約束的集合，即

定義11 TCS表示在已知TMS集合的情況下對Cc集合進行拓展得到的所有滿足cannot－link約束的節點對組成的集合。

must－link約束具有對稱性和傳遞性。利用這些性質對Cm集合進行計算，可以發現隱含的must－link約束，整合即可知道所有已知的和隱含的must－link約束對，最后將所有相互之間滿足must－link約束的節點集都保存在TMS中。TMS的具體計算步驟見算法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用于根據Cm集合計算TMS集合，為聚類過程提供輸入。其中，算法第1行用于生成一個n×n維矩陣M，如果節點i和節點j滿足 （i，j）∈Cm，則矩陣對應位置的元素為1，否則為0。算法第3－10行用于生成一個集合S’，里面的元素為所有與節點i之間滿足must－link約束的節點。所有的子集S’共同構成了TMS集合。

隨后，我們根據計算得到的TMS集合來對Cc集合進行拓展，可以得到TCS集合。內部元素為所有已知的和計算得到的滿足cannot－link約束的節點對。

2.2 算法描述

算法根據前面獲取的所有約束關系，識別并影響節點之間相互連通的關系，從而發現滿足連通性和最大性的社區結構，見算法2，這部分是算法的核心部分。

算法2：TMSSCAN （G＝ （V，E），ε，μ，Cc，TMS）輸入：V，E，ε，μ，Cc，TMS輸出：聚類結果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的第一個元素，并刪除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開始時默認所有的節點都是未標記的。算法從第1行開始遍歷所有的樣本節點，第2行用于判斷當前節點v是否為核節點，如果是則檢索與節點v連接緊密的所有節點，即TMS集合中節點v所在子集的其它節點（6－10行）和節點v的直接結構聯通節點 （11行），分析這些節點與當前劃分跟TCS集合是否存在矛盾，不矛盾時將節點v和這些節點分配到同一個社區中，存在矛盾則分析下一個與節點v連接緊密的節點，檢索結束即得到一個由節點v拓展得到的社區 （3－17行）；如果節點v不是核節點，則將其標記為特殊節點 （19行）。如此將樣本節點全部遍歷一遍，即可得到最終的聚類結果。

聚類過程中先驗知識的指導作用主要體現在如下部分：TMSSCAN的第6－10行用于將所有與當前節點滿足mustlink約束的節點都加入到隊列中，保證最后能聚到同一個社區；第13行檢測能否將當前節點加入隊列，使得不將滿足cannot－link約束的兩個節點聚到同一個社區。如此，算法在對節點集進行遍歷時充分考慮了TMS集合和TCS集合，保證了先驗知識的有效性。

2.3 復雜度分析

CALTMS用于計算TMS集合，其時間復雜度跟Cm集合有關?？紤]最壞的情況，即所有的節點標簽信息已知，在構造子集S1’時，將遍歷標簽信息為第一類的節點，設其時間復雜度為O（a1），設構造子集數為b，則總共時間復雜度為O（a1＋a2＋a3＋…＋ab），其中a1＋a2＋a3＋…＋ab＝n，因此在最壞情況下CALTMS的時間復雜度為O（n）。

TMSSCAN在聚類過程中，需遍歷網絡中的每個節點。對每個節點v，必須檢索其所有鄰居節點，其時間復雜度為O（deg（v））。所以最終的時間復雜度為O（（deg（v1）＋deg（v2）＋deg（v3）＋…＋deg（vn））／2），其中deg（v1）＋deg（v2）＋…＋deg（vn）＝2 m，因此TMSSCAN聚類過程的時間復雜度為O（m）。

綜上所述，基于密度的半監督復雜網絡聚類算法的時間復雜度為O（m＋n）。在對實際網絡進行分析時，網絡中的邊數和節點數大致相當，即m≈n，所以算法時間復雜度可以記為O（m）?？芍?，本文所提算法的時間復雜度較低，能應用于對大規模復雜網絡進行聚類研究。

3 實驗分析

實驗環境為：處理器Inter（R）Core（TM）2Duo 2.8GHz PC，內存2G，操作系統為 Windows 7，編程環境為Visual Studio 2008C＋＋.Net。

3.1 數 據

為了驗證算法的聚類性能，我們在Newman數據中的真實網絡上進行了聚類分析，網絡的具體信息見表1。

表1 Newman真實網絡數據

3.2 方 法

我們用基于密度的半監督復雜網絡聚類算法 （SSSCAN）對表1中的數據進行聚類分析，將結果與半監督譜聚類算法 （SS－SP）［13］、基于 Ncut的半監督核K－means算法 （SS－KK）［13］的聚類結果進行了對比。

實驗中，我們選擇被廣為使用的NMI［14］作為算法聚類精度的評價標準，其計算公式如下

式中：N——一個矩陣，Nij——既在類Xi中又在簇Yj中的節點的個數，Ni.——矩陣第i行求和的結果，N.j——矩陣第j列求和的結果。

3.3 結 果

我們分別用SS－SCAN、SS－SP和SS－KK 算法在4個數據集上進行聚類分析，實驗結果如圖1、圖2、圖3、圖4所示。其中橫坐標表示數據中已知標簽節點的比例，考慮實際情況中已知比例不會太多的問題，其取值范圍為［0，50%］；縱坐標表示聚類結果的NMI值，NMI值越高表示聚類精度越高。

實驗表明在使用半監督學習之前 （對應圖中已知比例為0的聚類結果），SS－SCAN算法在football數據和karate數據上的聚類精度相比其它兩個算法更高，但在其它兩個數據上的聚類結果就沒有這個現象，說明在使用半監督學習之前，SS－SCAN相比其它兩個算法在聚類精度上并沒有絕對優勢。

使用半監督學習后 （對應圖中已知比例不為0的聚類結果），可以發現，SS－SP算法在前3個數據集上的聚類精度比較高，但其波動現象相對比較明顯 （這是由于算法利用K－means來對網絡提取的特征向量進行聚類，K－means不穩定導致的），且在adjnoun上的聚類精度是最低的；SS－KK算法在football和adjnoun上的聚類精度比較高，在另外兩個數據集上的表現相對較差；SS－SCAN算法的聚類精度相比其它兩個算法在大多數情況下都是最高的，并且其NMI值隨著已知標簽比例的增加大致符合線性增長的趨勢，表現相對穩定。

同時，我們統計了3個算法對4個數據集進行聚類所消耗的平均時間。在實驗中我們發現引入半監督策略對算法本身的運行時間并不會有很大程度的改變，在這里我們只給出算法在各種已知比例情況下對4個數據進行聚類的平均時間，見表2?？芍猄S－SCAN算法的時間消耗最少。

表2 算法的聚類時間

綜上所述，SS－SCAN算法的聚類精度更高，聚類結果更穩定，時間消耗更少，能夠更有效的利用先驗知識指導聚類。

4 結束語

本文提出了一種基于密度的半監督復雜網絡聚類算法，以利用少量的先驗知識提高復雜網絡的聚類質量。該算法主要包含兩個重要組成部分：一是利用少量的must－link和cannot－link兩種常用的成對約束信息，發現網絡中所有潛在的成對約束，最大化先驗知識，以更好的提高聚類質量；二是在基于密度的方法基礎上，判斷兩個節點是否屬于同一個社區時，綜合考慮了節點之間的可達性和成對約束兩方面的因素，從而更加準確地對復雜網絡進行有效劃分。在若干真實網絡上的實驗結果表明，本文所提出的算法相對于其它幾種代表性的半監督聚類算法，更能夠有效利用少量的先驗知識，穩定地提高聚類的質量。

［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，等.復雜網絡聚類方法 ［J］.軟件學報，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）.［趙衛中，馬慧芳，李志清，等.一種結合主動學習的半監督文檔聚類算法 ［J］.軟件學報，2012，23 （6）：1486－1499.］

［12］Xu Xiaowei，Yuruk Nurcan，Feng 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.