一種新的復雜網絡聚類算法

摘 要:揭示網絡簇結構的復雜網絡聚類方法研究具有重要的理論意義和應用價值。應用兩種譜方法將復雜網絡簇結構發現問題轉換為空間數據聚類問題，并將粒子群聚類算法應用到對復雜網絡簇結構的探測，提出了兩種新的結合粒子群聚類的復雜網絡簇結構探測算法。最后在兩類復雜網絡上進行實驗并對實驗結果進行了比較分析，提出的新算法在聚類準確性方面效果更好。

關鍵詞:復雜網絡; 網絡聚類; 網絡簇結構; 譜方法; 粒子群聚類算法

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2097-03

doi:10.3969/j.issn.1001-3695.2010.06.029

New complex network clustering algorithm

LI Jun-jin1， XIANG Yang1， NIU Peng1， LIU Li-ming2， LU Ying-ming3

(1.Xi’an Communications Institute， Xi’an 710106， China; 2.PLA 72556 Unit， Jinan 250022， China; 3.China’s Special Vehicle Research Institute， Beijing 100072， China)

Abstract:Network clustering algorithms which aim to discover all natural network communities from given complex networks are fundamentally important for both theoretical researches and practical applications. This paper used two spectral partition methods in order to transform the communities detecting into cluster analysis problem. Then， applied PSO clustering algorithms to detect cluster structure. Proposed two new network clustering algorithms closely combined with PSO and demonstrated the availability of the algorithm in two different kinds of network datum. It also makes the comparison and analysis of the experimental results and obtains a conclusion that the proposed algorithms present fitness in clustering veracity.

Key words:complex network; network clustering; network cluster structure; spectral partition; PSO clustering

0 引言

現實世界中的諸多系統都以網絡形式存在，并表現出很高的復雜性。網絡簇結構(network cluster structure)是復雜網絡最普遍和最重要的拓撲結構屬性之一，具有同簇節點相互連接密集、異簇節點相互連接稀疏的特點[1~5]。為了揭示出復雜網絡中真實存在的網絡簇結構，人們提出了多種復雜網絡聚類方法。復雜網絡聚類方法的研究對分析復雜網絡的拓撲結構、理解復雜網絡的功能、發現復雜網絡中的隱藏規律以及預測復雜網絡的行為不僅具有十分重要的理論意義，而且在社會網、生物網和萬維網中具有廣泛的應用前景。由于復雜網絡聚類研究具有重要的理論意義和應用價值，它不僅成為計算機領域中最具挑戰性的基礎性研究課題之一，也吸引了來自物理、數學、生物、社會學和復雜性科學等眾多領域的研究者，掀起了一股研究熱潮[6]。

譜方法最早用于解決圖分割(graph partition)問題，近年來被應用到復雜網絡聚類。譜方法采用二次型優化技術最小化預定義的“截”函數。當一個網絡被劃分為兩個子網絡時，“截”即指子網間的連接密度。具有最小“截”的劃分被認為是最優的網絡劃分。針對不同問題，研究者們提出了不同的“截”函數，如針對分布式系統負載平衡提出的平均截(average cut，A-cut)[7，8]以及針對圖像分割提出的規范截(normalized cut，N-cut)[9]等。采用矩陣分析技術，譜方法將求解最小“截”問題轉換為求解帶約束的二次型優化問題:min{(XTMX)/(XTX)}。其中，向量X表示網絡劃分，M表示對稱半正定矩陣。對于平均截，M=D-A表示網絡的拉普拉斯矩陣，其中D表示由節點度構成的對角矩陣，A為網絡的鄰接矩陣;對于規范截，M=D-1/2(D-A)D-1/2表示網絡的規范化拉普拉斯矩陣;對于其他截函數，M是拉普拉斯矩陣的不同變體。由拉格朗日方法，以上約束二次型的近似最優解(即網絡的近似最優劃分)可以通過計算M的第二小特征向量求得。譜方法本質上是一種二分法，在每次二分過程中，網絡被分割成兩個近似平衡的子網絡。當網絡中含有多個簇時，譜方法遞歸地分割現存的子網絡，直到滿足預先定義的停止條件為止。譜方法具有嚴密的數學理論，已發展成數據聚類的一種重要方法(稱為譜聚類法)，被廣泛應用于圖分割和空間點聚類等領域。

本文研究了復雜網絡聚類算法中譜方法的基本原理，其主要工作是將粒子群優化算法應用于復雜網絡聚類，通過PSO聚類算法和譜方法中的平均截方法[7，8]與規范截方法[9]相結合，提出了兩種新的復雜網絡聚類算法，即基于PSO聚類的譜方法和基于PSO+K-means聚類的譜方法，并在人工隨機網絡和兩個現實社會網絡上實驗驗證了新方法的有效性。

1 算法描述

1.1 PSO聚類算法

基于社會生態學的粒子群優化算法(particle swarm optimization，PSO)[10]主要是在群體的集群行為和自組織原則指導下的隨機搜索和優化技術，它強調分布式、相對簡單主體之間直接或間接的交互作用，具有很強的適應性和魯棒性，被廣泛用于解決搜索和優化問題。2003年，Merwe等人[11]提出了標準PSO聚類算法，用于對一般數據集的聚類，同時最早提出了一般形式下PSO算法與K-means算法相結合的混合聚類方法。

假設在D維搜索空間中有n個粒子組成的一個群體，第i個粒子在D維空間中的位置表示為xi=(xi1，xi2，…，xiD)。第i個粒子經歷過的最好位置(有最好適應度)記為Pi=(pi1，pi2，…，piD)，每個粒子的飛行速度為Vi=(vi1，vi2，…，viD);在整個群體中，所有粒子經歷過的最好位置為Pg=(pg1，pg2，…，pgD)。每一代粒子根據下面的公式更新自己的速度和位置:

vk+1id=wvkid+c1ξ(pkid-xkid)+c2η(pkgd-xkid)(1)

xk+1id=xkid+vk+1id(2)

其中:w為慣性權重;c1和c2為學習因子;ξ，η∈U[0，1]是在[0，1]內均勻分布的偽隨機數。

PSO聚類算法中粒子的適應度函數為Je:

Je=∑Ncj=1[∑zp∈Cjd(zp，mj)]/|Cj|Nc(3)

mj=1nj∑zp∈Cjzp(4)

d(zp，mj)=∑Nbk=1(zpk-mjk)2(5)

其中:Nb為數據的維數;Nc為聚簇的個數;zp表示樣本的數據向量;nj表示簇Cj中樣本的個數;mj表示簇Cj中樣本的均值(中心)。

基本PSO聚類算法的流程如下:

a)初始化粒子群，隨機選擇簇的中心并賦值給各個粒子，隨機產生粒子的速度。

repeat

b)對每個粒子按照最小距離原則對數據進行劃分，按式(3)計算各個粒子的適應值，更新個體極值。

c)根據各個粒子的個體極值找出全局極值和全局極值位置。

d)按速度(式(1))更新粒子的速度，并把它限制在vmax內。

e)按位置(式(2))更新粒子的位置。

until滿足終止條件

f)輸出最優粒子的位置即最優的Nc個聚類中心。

算法的終止條件可以是達到一定的循環次數，簇的中心變化很小或簇的成員不再改變。

PSO與K-means算法相結合的混合算法的基本思路是先用K-means方法得到一組簇的中心，然后在粒子群初始化時將其賦值給某個粒子，其余粒子隨機初始化，最后用標準PSO聚類算法完成聚類。該方法可簡記為PSO+K-means方法。

1.2 基于PSO的復雜網絡聚類算法

復雜網絡聚類與空間數據聚類有很多相似之處。目前應用空間數據聚類來探測復雜網絡的簇結構主要分為兩大步驟:a)將原問題轉換為數值聚類問題，即要把網絡中節點間的聯系在特征向量空間中表述出來，譜方法正好可以實現這一轉換;b)對轉換后的數據進行聚類并將聚類結果還原為相應的社團結構。 根據上述思路本文提出了兩種基于PSO聚類的復雜網絡簇結構算法。其算法的基本思想是首先應用譜方法中的A-cut方法或N-cut方法將復雜網絡聚類問題轉換為空間數據聚類問題;通過應用A-cut方法或N-cut方法將復雜網絡中的簇結構信息轉換為由非平凡特征向量構成的空間數據集。該空間數據集中的每個數據樣本對應原復雜網絡中的一個節點。通過對該空間數據集中數據樣本的聚類得出復雜網絡中節點的簇信息，最終完成復雜網絡聚類。

對于某復雜網絡G (V， E，W )，給定一個簇的數目k，基于PSO聚類的復雜網絡簇結構探測算法的基本步驟如下:

a)由連接權矩陣W得出網絡的度矩陣D=(di)n×n。其中D為對角矩陣，di為第i個節點的度，n為節點數。注意，這里考慮的均為無向網絡。

b)用譜方法將尋找復雜網絡的簇結構問題轉換為數據的聚類問題。設A為網絡的鄰接矩陣。對于平均截方法，具體就是計算M=D-A的前k-1個非平凡特征向量e1，e1，…，ek-1(ei∈Rn×1，i=1，…，k-1)并組成矩陣E。對于規范截方法，具體就是計算M=D-1/2(D-A)D-1/2的前k-1個非平凡特征向量e1，e1，…，ek-1(ei∈Rn×1，i=1，…，k-1)并組成矩陣E。由E的行向量得到n個數據向量形式的待聚類樣本。

c)用基于PSO的聚類算法，如基本PSO聚類算法或PSO+K-means聚類算法對上面得到的數據樣本集E進行聚類。

2 實驗與分析

為了定量地分析和比較本文提出的復雜網絡聚類算法的性能，分別選取了不同的基準數據集與基于K-means聚類的復雜網絡聚類算法，從聚類精度和算法穩定性兩個方面進行對比實驗。

首先采用已知簇結構的隨機網絡測試所選擇算法的聚類精度和穩定性。該實驗方法被相關工作廣泛采用，已成為測試復雜網絡聚類算法準確性的一種基準方法[1，12，13]。已知簇結構的隨機網絡定義為RN(C，s，d，pin)。其中，C表示網絡簇的個數;s表示每個簇包含節點的個數;d 表示網絡中節點的平均度;pin表示簇內連接密度(即簇內連接總數與網絡連接總數的比值)，pin值越大，隨機網絡的簇結構越明顯，反之簇結構越模糊。特別地，當pin<0.5 時，認為該隨機網絡不具有簇結構。一個隨機網絡被正確聚類當且僅當預定義的C個網絡簇被全部正確識別，且沒有某個簇被進一步分割為多個子簇。圖1和2 給出了實驗結果，這里所采用的隨機網絡是被普遍采用的基準隨機網絡RN(4，32，16，pin)，pin分別取0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0。在圖1和2中，y軸分別表示聚類精度和聚類精度的標準差，曲線上的每個數據點是采用不同算法進行100次隨機實驗得到的平均值。

從圖1可以看出，對于隨機網路，在網絡簇結構比較明顯的情況下(pin>0.6)，基于PSO聚類的譜方法(A-cut方法和N-cut方法)均能得到很好的聚類精度(>98%);在網絡簇結構不明顯的情況下(pin<0.5)，所有算法的聚類精度都很低，但是與基于K-means的譜方法相比，基于PSO聚類的譜方法的聚類精度更高。從圖2可以看出，基于PSO+K-means聚類的譜方法在獲得最高的聚類精度的同時聚類精度的標準差最低，說明基于PSO+K-means聚類的譜方法穩定性最強。

為進一步測試本文算法的性能，選取兩個基準社會網絡Karate club網絡[14]和Football網絡[1]進行實驗。圖3是Karate club網絡，它是20世紀70年代初期Zachary用了兩年的時間觀察得到的美國一所大學中的空手道俱樂部成員間的相互社會關系網絡。在Zachary的調查過程中，該俱樂部的主管與校長之間因是否提高俱樂部收費的問題產生了爭執，結果該俱樂部分裂成了兩個分別以主管和校長為核心的小俱樂部。

Football網絡是根據美國大學生足球聯賽得出的一個復雜網絡。足球聯賽中有若干支球隊，網絡的節點代表一只足球隊，兩個節點之間的邊表示兩支球隊之間進行過一場比賽。聯賽中存在若干的聯盟，每個球隊都屬于其中一個聯盟，聯盟內部球隊間進行的比賽次數多于聯盟之間的球隊間進行的比賽次數。該網絡數據收集于2000年賽季的真實比賽情況，由Girvan與Newman收集整理而成，存在115支球隊(節點)及616場比賽(邊)，包含了12個聯盟。Football網絡如圖4所示。

實驗結果如表1所示。從表1可以看出，對于Karate club網絡和Football 網絡，基于PSO聚類的譜方法(A-cut方法和N-cut方法)同樣獲得了較高的聚類精度和較低的聚類精度標準差。其中基于基本PSO聚類的譜方法在Karate club網絡上的聚類精度最高(>98%)，基于PSO+K-means聚類的譜方法在Football 網絡上聚類精度最高(>92%)。在三種方法中，基于PSO+K-means聚類的譜方法得到的聚類精度的標準差均最低。

3 結束語

復雜網絡聚類是最重要的復雜網絡分析方法之一，復雜網絡簇結構探測已成為一個具有挑戰性的研究課題。盡管人們已經投入了大量的、艱苦的研究工作并取得諸多令人鼓舞的研究結果，但復雜網絡聚類問題還遠未被很好地解決。本文首先介紹了復雜網絡聚類中的兩種譜方法(A-cut方法和N-cut方法)和兩種空間聚類方法(PSO聚類算法和PSO+K-means聚類算法);然后提出和分析了兩種基于PSO聚類的復雜網絡簇結構探測算法，即基于PSO聚類的譜方法和基于PSO+K-means聚類的譜方法;最后在10個隨機復雜網絡和兩個基準社會網絡上進行實驗，驗證了兩種算法在復雜網絡聚類分析中的有效性。從實驗結果可知，通過將PSO聚類算法與譜方法相結合，有效提高了譜方法在復雜網絡聚類中的聚類精度和穩定性。

表1 不同算法在基準社會網絡上100次隨機實驗結果(聚類精度±標準差)

算法

Karate club網絡Football網絡

A-cutN-cutA-cutN-cut

K-means86.1176±8.001793.6471±7.789681.2000±6.006782.4174±7.0682

PSO98.9118±3.130898.5882±2.406781.5217±3.978081.9217±4.1726

PSO+K-means97.0588±0.000097.0588±0.000092.5130±1.379892.6870±0.8790

參考文獻:

[1]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J].Proceedings of the National Academy of Science of USA，2002，99(12):7821-7826.

[2]GUIMERA R， AMARAL L A N. Functional cartography of complex metabolic networks[J].Nature，2005，433(7028):895-900.

[3]PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structures of complex networks in nature and society[J].Nature，2005，435(7043):814-818.

[4]WILKINSON D M， HUBERMAN B A. A method for finding communities of related genes[J].Proceedings of the National Academy of Science of USA，2004，101(1):5241-5248.

[5]RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks[J].Proceedings of the National Academy of Science of USA，2004，101(9):2658-2663.

[6]楊博，劉大有，LIU Ji-ming，等.復雜網絡聚類方法[J].軟件學報，2009，20(1):54-66.

[7]FIEDLER M. Algebraic connectivity of graphs[J].Czechoslovakian Mathematical Journal，1973，23(2):298-305.

[8]FIEDLER M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory[J].Czechoslovakian Mathematical Journal，1975，25(4):619-637.

[9]SHI Jian-bo， MALIK J. Normalized cuts and image segmentation[J].IEEE Trans on Pattern Analysis and Machine Intelligent，2000，22(8):888-904.

[10]KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.1995:1942-1948.

[11]Van der MERWE D W，ENGELBRECHT A P. Data clustering using particle swarm optimization[C]//Proc of IEEE Congress on Evolutionary Computation.2003:215-220.

[12]NEWMAN M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E，2004，69(6):066133-1-11.

[13]NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks[J].Physical Review E，2004，69(2):026113-1-15.

[14]ZACHARY W W. An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research，1977，33(4):452-473.