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

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

0 引 言

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

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

本文針對譜聚類中聚類算法的特點，提出了一種基于主成分分析 （PCA）法的社團挖掘算法。在利用PCA將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息轉(zhuǎn)化為各節(jié)點的協(xié)方差矩陣信息，并在此基礎(chǔ)上，利用譜分析方法分析該協(xié)方差矩陣，從而以網(wǎng)絡(luò)中主要信息的數(shù)目作為譜聚類中選擇特征向量的維數(shù)，達(dá)到提高算法精確度的目的。

1 預(yù)備知識

1.1 PCA方法簡介

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

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

1.2 社團結(jié)構(gòu)挖掘中的譜聚類算法

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

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

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

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

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

輸入：一個具有N個節(jié)點的復(fù)雜網(wǎng)絡(luò)鄰接矩陣A

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

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

（4）初始化一個隊列Q，用來保存當(dāng)前待劃分的子圖結(jié)構(gòu)并求的A對應(yīng)的拉普拉斯矩陣的特征值和特征向量，并按序排列。

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

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

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

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

3 算法應(yīng)用

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

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

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

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

圖2 美國足球大聯(lián)盟的社團劃分結(jié)果

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

4 結(jié)束語

圖3 向量維數(shù)和社團劃分精度關(guān)系曲線

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

［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，F(xiàn)u 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.