基于PCA的社團結構譜聚類改進算法

李 琳，李生紅，陸松年，陳秀珍

（1.上海交通大學電子與電氣工程學院，上海200240；2.上海交通大學信息安全工程學院，上海200240）

0 引 言

復雜網絡是通過對大規(guī)模網絡和各種復雜系統(tǒng)的數學抽象而出現的一個新的研究方向。自從1998年Watts等人提出小世界網絡和Albert提出BA無標度網絡以來，復雜網絡的很多特點逐漸被學者們重視［1］。社團結構作為復雜網絡的一個主要特征，可以用來分析計算機網絡、生物網絡和社會網絡，因此逐漸成為了研究的熱點。

近些年來，很多學者從不同的視角出發(fā)，提出了很多社團結構的發(fā)掘算法。這些社團結構挖掘算法主要分為三大類：一類是通過研究網絡中節(jié)點和連邊的拓撲結構特點，構造了衡量網絡節(jié)點相似度的指標量，通過該指標合并與分裂網絡從而形成網絡社團結構［2］。這類算法精確度較高，但是時間消耗很大；第二類算法通過賦予每個節(jié)點一個唯一的標簽值來標識不同的社團，之后迭代的將每個節(jié)點的標簽值更新為被該節(jié)點的直接鄰居節(jié)點持有最多的標簽值。這類算法時間復雜度較低，一般為線性復雜度，但是社團查找的精度較差［3，4］。第三類是借助矩陣等數學工具，通過分析由網絡鄰接矩陣構造的拉普拉斯矩陣的特征值和特征向量的數學特征，利用譜聚類達到社團結構分離的目的［5，6］。這類算法精確度比第二種算法要好，而時間復雜度較第一種算法低很多，因此被很多學者研究。

本文針對譜聚類中聚類算法的特點，提出了一種基于主成分分析 （PCA）法的社團挖掘算法。在利用PCA將網絡拓撲結構信息轉化為各節(jié)點的協(xié)方差矩陣信息，并在此基礎上，利用譜分析方法分析該協(xié)方差矩陣，從而以網絡中主要信息的數目作為譜聚類中選擇特征向量的維數，達到提高算法精確度的目的。

1 預備知識

1.1 PCA方法簡介

在對某一事物的研究過程中，往往會從多個方面和特征去研究事物，以期更加全面的了解事物的本質。但是特征的增多也帶來了計算復雜度增大的情況。因此，主成分分析法作為一種可以實現大規(guī)模的數據降維工具，使研究者利用較少的變量獲得較多信息。

設有n個樣品，每個樣品有p個指標，這樣子就有np個數據，記為：X＝（xij）n×p。首先對這p個指標的樣本值去掉平均值然后利用p個均值計算p個指標的協(xié)方差矩陣，記為covp×p；在此基礎上，計算協(xié)方差矩陣cov的p個特征值并按照降序排列λ1≥λ2≥....≥λp及其對應的p 個特征向量α1，α2....αp；最后，通過積累貢獻率來決定應該取前m個向量來作為原始p個指標的主成分。這樣就從一組樣本中導出了p個指標的m個主成分。

1.2 社團結構挖掘中的譜聚類算法

借助矩陣和聚類算法等數學工具，社團結構挖掘的譜聚類算法逐步完善起來［7］。對于一個有N個節(jié)點的網路圖，計算該網絡圖的拉普拉斯矩陣的特征值并按照從小到大的順序排序0＝λ1≤λ2≤λ3≤...≤λN，每個特征值對應的特征向量依次記為α1α2α3...αN。取這 N 個特征向量的前k個向量組成N個k維向量 （特征值0對應的特征向量除外），最后采用聚類算法不斷的二分網絡以達到社團劃分的目的。這種方法擴展了傳統(tǒng)的譜聚類算法通過第二小的特征值對應特征向量中各維數據的正負號劃分社團的模式。文獻 ［8，9］通過研究表明，取多個特征向量在很多情況下社團劃分效果要比只取第二小特征值對應的特征向量效果要好，但是并沒有探討如何自適應的確定應選擇特征向量個數的方法?；谝陨系姆治?，本文通過PCA預處理網絡數據，通過分析網絡拓撲結構的特點，從而自適應的決定譜聚類方法中特征向量的個數。

2 基于PCA的譜聚類改進算法

譜平分法通過分析由網絡鄰接矩陣得到的拉普拉斯矩陣的特征值和特征向量的特點，從理論上證明了不為零的特征值所對應的特征向量的各元素中，同一社團內的節(jié)點對應的元素是近似相等的。譜聚類算法利用聚類算法，通過對多個不為零的特征值對應的特征向量進行聚類，可以更好的劃分社團網絡。但是傳統(tǒng)的譜聚類算法中并沒有給出特征向量個數的選取方法。如果把每一維特征向量中的元素都看作是在一維坐標軸上的取值，一般認為選取一個不為零特征值對應的特征向量，可以很好的將網絡劃分為兩個社團；選取k個特征值可以將網絡劃分為k－1個社團。但是文獻 ［8，9］結果表明，并不是選取越多的特征向量，社團劃分的效果就越好，因此動態(tài)的選取特征值的個數k可以提高社團檢測的精確度。

對于一個有N個節(jié)點的網絡無向圖，其鄰接矩陣記為AN×N＝ （a1，a2...aN），其中ai（i＝1，2...N）為AN×N的N 個 列 向 量。分 析ai（i＝ 1，2...N）ai可 知，ai＝ （ai1，ai2...aiN）T可以看作是網絡結構的N 個指標。對于每個指標ai，其中的各個樣本點代表的是節(jié)點i和其它各個節(jié)點之間的連接關系。分析復雜網絡中的社團結構，屬于同一個社團的節(jié)點，其直接鄰居節(jié)點數目較多，映射到鄰接矩陣中就是節(jié)點對應的列向量的有著很大的相似性，即同一社團內部的節(jié)點對應的指標之間相關度較大。以此為依據，通過PCA算法，可以預測該網絡中存在的社團的數目，并作為譜聚類算法中向量個數的選取標準。

基于PCA的譜聚類算法步驟如下：

輸入：一個具有N個節(jié)點的復雜網絡鄰接矩陣A

輸出：劃分為M個節(jié)點集合的社團劃分結果

（3）計算cov的N個從大到小的特征值及其特征向量λ1≥λ2≥....≥λN，并根據積累貢獻率和預先確定的閥值γ0做比較來確定n的取值。

（4）初始化一個隊列Q，用來保存當前待劃分的子圖結構并求的A對應的拉普拉斯矩陣的特征值和特征向量，并按序排列。

（5）在特征向量序列中選出前k個特征向量，其中k＝log2n。利用均值聚類算法對選出來的k個特征向量做分類，然后利用文獻中［9，10］的模塊度計算公式判斷社團劃分是否合理。

（6）如果合理，則將該部分網絡劃分為2部分，然后對新劃分出來的社團按照完全二叉樹的編號順序編號，放入隊列Q中，然后根據劃分結果，更改網絡節(jié)點的社團編號。如果不合理，檢測隊列Q中是否還有待劃分的子圖，如果有，則轉步驟 （5），如果沒有，則轉步驟 （7）。

（7）對劃分結果做進一步優(yōu)化，對于該算法劃分出來的單一節(jié)點利用節(jié)點度劃歸到連接最緊密的社團結構中去。

上面介紹的基于PCA的譜分析改進算法盡管是對于無權圖的鄰接矩陣做的分析，借助PCA的數學意義可以很自然的推廣到加權圖中，由于算法相似，在此也就不做過多討論。

3 算法應用

下面以真實的數據集為例，測試算法的效果。第一個例子來源于Lusseau等在文獻 ［11］中介紹的海豚社會網絡的社團結構。該文章的作者在7年的時間里，對新西蘭神奇灣中生活的62只寬吻海豚之間關系作了深入的研究。通過對這62只海豚的社會關系進行數學抽象，形成網絡圖。Lusseau等人使用無向圖對這個生物社會作了建模，62個節(jié)點中每個節(jié)點都代表了一只寬吻海豚，他們之間的連邊表示了兩只海豚之間的交流頻率，因此準確的反應了這些海豚之間的社會關系。文獻 ［11］的作者觀察發(fā)現，這個海豚群體可以自然的分為二個較大的社團，其中的一個社團主要含有雄性的寬吻海豚，另一個社團主要有雌性海豚組成。這是由于在7年的研究過程中有一只關鍵的海豚離開了原始的群落而造成的。進一步的觀察發(fā)現，較大的一個社團也可以進一步分解為更小的社團，這些社團反映了海豚群落中的社會學關系。

圖1表示了本文提出的算法在該數據集上的測試結果。從實驗結果可以知道，本文提出的算法將海豚網絡劃分為了3個主要的社團，最大的一個社團中含有絕大多數的海豚，較小的一個社團只有11只海豚。進一步的分析發(fā)現，本算法將多數節(jié)點都正確的合并在了一起。比如節(jié)點48，該節(jié)點的6個直接鄰居節(jié)點中有5個和它屬于同一個社團，只有一個節(jié)點與它在不同的社團中；如節(jié)點10的所有鄰居節(jié)點都被劃分在了和10相同的社團中。這個劃分結果得到了文獻 ［12］的支持。本文的算法將海豚網絡劃分為了3個社團，這是由于圖1中的社團II和社團III之間的連邊遠遠小于社團內部的連邊造成的。比如節(jié)點55、28、42還有18等處于社團邊界的節(jié)點都與同社團內的節(jié)點緊密連接。

為了進一步測試本方法在復雜網絡上的效果，選取了US College football網絡數據作為測試數據［13］。該網絡中的數據表示了2000賽季美國高校足球聯盟中的115個球隊之間的對決狀況。在該圖中，各所高校 （用他們的校名表示）用網絡圖中的節(jié)點表示，節(jié)點間的邊代表了兩只球隊在常規(guī)賽季中的交手情況。由于美國足球聯盟的體系劃分，將大約8到12支隊伍劃分為一個聯盟，聯盟內部的比賽相對較頻繁，而聯盟間的比賽相對較少，每只球隊大約會有7場左右的聯盟內部比賽，4場左右的聯盟間的比賽，并且聯盟間的球隊比賽一般都是遵循地域相近的原則。因此這些足球聯盟可以自然的看作是網絡中的社團結構。

圖2是本算法在Football網絡上分析的結果。為了更加清晰的表示節(jié)點間的關系，該圖縮小了精確度，只是將本算法劃分在同一社團中的節(jié)點放在一起，而社團間的連邊簡化為了一條邊來表示。通過PCA分析網絡數據，并取積累貢獻率為95%時，本算法表明應選取7個特征向量用于聚類。從圖2中的分析結果可以看到，總共有7個社團的球隊被完全正確的劃分出來，其它的4個社團只有一到兩個節(jié)點與事實不符。因此，絕大多數的球隊節(jié)點都被劃分在了正確的聯盟中，而少數不正確的劃分是由于一些節(jié)點所在的聯盟本身較為松散，聯盟內部的連邊較少，還有4個節(jié)點原本就不屬于任何一個社團。本算法應用于Football網絡，精確度可以達到92%，與GN算法［2］以及FCM算法［14］相比精確度更高。

圖2 美國足球大聯盟的社團劃分結果

圖3表示的是對于Football網絡數據，當不采用PCA分析網絡主要信息時，譜聚類算法中用于聚類的特征向量的個數和社團劃分精確度之間的關系。由該曲線可以看到譜聚類算法中用作聚類的特征向量的個數從1開始逐漸增多的時候，社團劃分的精確度逐漸上升，當達到4時，上升的趨勢開始變得平穩(wěn)，但是依然穩(wěn)步上升，當取得向量個數為7的時候達到峰值。之后，隨著特征向量的增多，譜分析算法的檢測精確度開始下降。這與本算法通過PCA提取網絡主要信息后確定的特征向量選取個數相同。由此可見，本算法通過PCA提取網絡主要信息，在一定的積累貢獻率條件下獲取譜分析中特征向量選取的最優(yōu)個數，從而提高了傳統(tǒng)譜分析檢測復雜網絡社團結構的精確度。

4 結束語

圖3 向量維數和社團劃分精度關系曲線

將網絡鄰接矩陣的N個列向量看作復雜網絡的N個指標，通過分析復雜網絡社團中節(jié)點之間連接邊的關系特點，借助PCA的信息壓縮特性提取網絡數據的主要信息，并在此基礎上改進了傳統(tǒng)的譜聚類方法，根據網絡特點確定譜聚類中用于聚類的特征向量的個數，從而提高了社團劃分的精確度。本文提出的算法是基于譜分析的改進算法，因此在檢測精確度上存在不完善的問題。比如，圖1中的節(jié)點2未被正確的劃分。另外，本算法基于PCA的分析方法分析網絡社團結構，但是PCA中的積累貢獻度對社團結構的影響還有待研究。因此，如何進一步提高本算法的精確度，探討PCA中積累貢獻度和網絡社團結構和數目之間的關系將是今后進一步展開工作的主要方向。

［1］Watts D J，Strogatz S H.Collective dynamics of‘small－world’networks ［J］.Nature，1998，393 （6684）：440－442.

［2］Newman M E J，Girvan M.Finding and evaluating community structure in networks ［J］.Phys Rev E，2004，69 （15）：026113

［3］Lovroubelj，Marko Bajec.Robust network community detection using balanced propagation ［J］.Eur Phys J B，2011，81 （3）：353－362.

［4］Leung I X Y，Hui P，Lio P，et al.Towards real－time community detection in large networks ［J］.Phys Rev E，2009，79：066107.

［5］Belkacem Serrour，Alex Arenas，Sergio Gómez.Detecting communities of triangles in complex networks using spectral optimization ［J］. Computer Communications，2011，34：629－634.

［6］Wang Gaoxia，Shen Yi，Ouyang Ming.A vector partitioning approach to detecting community structure in complex networks［J］.Computers ＆ Mathematics with Applications，2008，55（12）：2746－2752.

［7］Jeffrey Q Jang，Andreas W M Dress.A spectral clusteringbased framework for detecting community structures in complex networks ［J］. Applied Math Letters，2009，22 （9）：1479－1482.

［8］Charles J Alpert.Spectral partitioning：The more eigenvectors，the better ［C］／／32nd Conference on Design Automation，1995：195－200.

［9］Ye Zhengqing，Hu Songnian，Yu Jun.Adaptive clustering algorithm for community detection in complex networks ［J］.Phys Rev E，2008，78 （4）：046115.

［10］Xie Fuding，Ji Min.The detection of community structure in network via an improved spectral method ［J］.Physica A，2009，388 （15－16）：3268－3272.

［11］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long lasting associations ［J］.Behavioral Ecology and Sociobiology，2003，54 （4）：396－405.

［12］Chen Duanbing，Fu Yan，Shang Mingsheng.A fast and efficient heuristic algorithm for detecting community structures in complex networks ［J］.Physica A，2009，388 （13）：2741－2749.

［13］Sonia Cafieri，Pierre Hansen，Leo Liberti.Edge ratio and community structure in networks ［J］.Phys Rev E，2010，81 （2Pt 2）：026105.

［14］Zhang J H，Zhang S H，Zhang X S.Detecting community structure in complex networks based on measure of information discrepancy ［J］.Physica A，2008，387 （7）：1675－1682.