模糊譜聚類重疊社區發現算法

Overlapping Community Discovery Algorithm Based on Fuzzy Spectral Clustering

閆曉鵬1孫永波2(江西師范大學計算機信息工程學院1，江西南昌　330022;萊蕪鋼鐵冶金生態工程技術有限公司2，山東萊蕪　271104)

?

模糊譜聚類重疊社區發現算法

第一作者閆曉鵬(1990－)，女，現為江西師范大學軟件工程專業在讀碩士研究生;主要從事本體論和語義Web、數據挖掘、社會網絡分析方面的研究。

0　引言

早期的社區發現研究是針對非重疊社區，認為網絡可以被分割成若干個互不相連的社區，每個節點只能屬于唯一的社區。然而，在實際的社交網絡中，存在一些節點同時隸屬于不同的社區，且這些節點在社區間的信息傳播和演變中起著重要的中介或過濾的作用，能夠銜接各個社區。為此，研究者們陸續提出一系列算法來挖掘網絡重疊社區。例如:派系過濾算法(clique percolation method，CPM)［1－2］;基于標簽傳播的算法:社區重疊傳播算法(community overlap propagation algorithm，COPRA)［3］、平衡多標簽算法(balanced multi－label propagation algorithm，BMLPA)［4］、揚聲器監聽器標簽傳播算法(speaker－listener label propagation algorithm，SLPA)［5］等。基于局部社區優化和擴展的算法包括:局部適應度最大化(local fitness maximization，LFM)［6］、貪婪團擴展(greedy clique expansion，GCE)［7］、平等識別網絡中模塊組織(democratic estimate of the modular organization of a network，DEMON)［8］、序列統計局部最優方法(order statistics local optimization method， OSLOM)［9］等?；阪溄泳垲惖姆椒ò?基于鏈接圖劃分的LINK算法［10］、基于映射方程的連接社區(link community)發現方法［11］、基于鏈接最大似然(link maximum likelihood)的方法［12］等。

但是在重疊社區發現中產生冗余社區仍是目前研究面臨的一個問題。針對該問題，提出一種基于模糊譜聚類的重疊社區發現算法(fuzzy spectral clusteringbased overlapping community discovery，FSC－OCD)。

1　譜圖理論

譜圖理論使用線性代數理論和矩陣理論來研究圖的鄰接矩陣，并進一步研究圖中所包含的信息。

為簡化計算，將拉普拉斯矩陣進行歸一化，表示為:

拉普拉斯矩陣屬于對稱半正定矩陣，其所有的特征值都是非負實數，即λi≥0，i =1，2，…，n。

2　模糊集

一般的聚類算法多是硬聚類算法，由于重疊社區中每個節點有可能屬于多個社區，而模糊理論可以用于解決邊界不清晰的問題，因此，本文在提出的算法中引入模糊集合論來挖掘重疊社區。

設論域U是有限集，令U = { u1，u2，…，un}，U上的任意模糊集合，其隸屬函數為uA～(ui)，i =1，2，…，n，則可以表示為:

式中:“?”為論域中的元素ui與其隸屬度uA～(ui)之間的對應關系。

為了度量被分類對象間的相似程度，根據相似系數法建立樣本集的模糊相似矩陣。論域U上的相似關系R，數據點元素為m維向量，表示為:

在論域上建立的相似矩陣可以表示為:

3　基于模糊譜聚類的重疊社區發現算法

為提高劃分重疊社區的質量，需準確地量化節點之間的相互關系［13］，并評估每個節點的重要性。利用網絡拓撲結構信息度量節點的局部連接相似度，作為一個影響鄰居節點的權值。因此，將節點的局部連接相似度定義如下。

定義1(局部連接相似度):對于無權無向圖G = (V，E)，V = { v1，v2，…，vn}為節點集，vi表示節點。鄰接矩陣表示為W = wij(i，j =1，2，…，n)，wij用局部連接相似度來度量，表示節點vi和vj之間的權值，衡量節點vj對節點vi的重要程度，則局部連接相似度定義為:

式中: Aij為無權網絡圖0－1鄰接矩陣，0表示節點間不連通，1表示節點間連通; ki為節點vi的度; Sij為節點vi和vj共同鄰居的集合。如果2個節點間不存在連接，那么它們之間的局部連接相似度為0。

定義2(冗余社區):連接社區Ci和社區Cj的邊的權重EWij由這兩個社區共同包含的節點個數得到。EWij的表達式為:

當兩個社區的重疊程度大于某一閾值?，則稱社區Ci和Cj互為冗余社區，將兩社區合并成一個較大的社區。經過試驗，發現這個值設在0.70左右比較合理。

FSC-OCD算法描述如下。

輸入:網絡數據集的鄰接矩陣A = (aij)n×n，聚類劃分的個數k。

輸出:劃分的重疊社區結構。

①根據數據集構造一張圖，計算圖中連接點的權重作為節點間的相似度，將圖用鄰接矩陣W表示，其中每個節點的權重wij用局部連接相似度來度量。

②用W每列元素之和構造一個對角矩陣D，拉普拉斯矩陣表示為L，并對L進行歸一化處理，得到一個對稱矩陣Lsym。

③計算Lsym的特征值，并按從小到大對特征值排序，進一步計算前k個特征值對應的特征向量x1，x2，…，xk。該k個特征向量構成特征向量矩陣X =［x1，x2，…，xk］∈Rn×k，其中每一行看作k維空間中的一個向量。

④采用Z-score標準化將數據統一映射到［0，1］區間上，標準化后的數據為:

式中: Xi為數據的均值; si為數據的標準差。

⑤計算表示數據對象間相似程度的相似系數rij，在數據域上建立標定的模糊相似矩陣R。

⑥對R依次用二乘法計算R2，R4，…，R2t，求出R的傳遞閉包t(R)。

⑦根據截斷閾值λ，計算λ截矩陣R*，初步獲得重疊社區結構。

⑧檢測重疊社區中的冗余社區，并合并冗余社區。

4　算法仿真

對FSC算法進行仿真，并分別與經典的COPRA、LFM兩種重疊社區發現算法進行比對。試驗的運行環境是英特爾計算機、2 GHz處理器、2 GB內存，操作系統為Windows 7，編程環境為Matlab 2012b;采用擴展后的模塊度函數EQ［14］來評價重疊社區劃分的質量。

在仿真試驗中，本文選取了3個經典的、不同規模的實際網絡，包括空手道聯盟網絡(Zachary KarateNetwork)、海豚關系網絡(Dolphins Social Network)以及美國大學橄欖球聯盟網(American College Football)標準數據集，如表1所示。

表1　3個真實網絡Tab.1 Three real networks

圖1～圖3分別是FSC-OCD算法用于Karate、Dolphins和Football網絡劃分的效果圖，該算法在3個實際網絡上對應的評價指標EQov的值分別為0.75、0. 68、0.78，檢測到的重疊節點個數分別為8、10、9。

圖1　FSC-OCD算法用于Karate網絡Fig.1 FSC-OCD algorithm used to Karate network

圖2　FSC-OCD算法用于Dolphins網絡Fig.2 FSC-OCD algorithm used to Dolphins network

圖3　FSC-OCD算法用于Football網絡Fig.3 FSC-OCD algorithm used to Football network

3種算法仿真結果對比如表2所示。

表2　3種算法在實際網絡上的試驗結果Tab.2 Experimental results of three algorithms for actual network

從表2可以看出，基于模糊譜聚類的重疊社區發現算法能更準確、有效地劃分出實際網絡中的重疊社區，從而提高重疊社區劃分的質量，且有效避免因局部最優解產生的冗余社區。

5　結束語

針對重疊社區發現算法中受局部最優解的影響導致檢測結果中出現冗余社區的問題，結合譜模糊聚類所具有的邊界不確定劃分性能，提出了一種基于模糊譜聚類的重疊社區發現算法。改進的算法對陷入局部極值的個體使用模糊集策略處理，避免出現局部最優現象，有效地減少了無用的迭代。試驗結果表明，FSCOCD算法可以有效避免因局部最優解產生的冗余社區，從而提高重疊社區劃分的質量。

參考文獻

［1］Palla G，Derényi I，Farkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435(7043):814－818.

［2］Li Junqiu，Wang Xingyuan，Cui Yaozu.Uncovering the overlapping community structure of complex networks by maximal cliques［J］.Physica A: Statistical Mechanics and Its Applications，2014，415(1): 398－406.

［3］Gregory S.Finding overlapping communities in networks by label propagation［J］.New Journal of Physics，2010，12(10):103018.

［4］Wu Zhihao，Lin Youfang，Gregory S，et al.Balanced multi-label propagation for overlapping community detection in social networks［J］.Journal of Computer Science and Technology，2012，27(3):468－479.

［5］Zhen Lin，Zheng Xiaolin，Nan Xin，et al.CK-LPA: efficient community detection algorithm based on label propagation with community kernel［J］.Physica A: Statistical Mechanics and Its Applications，2014，416(15):386－399.

［6］Lancichinetti A，Fortunato S，Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks［J］.New Journal of Physics，2009，11(3):33015.

［7］Lee C，Reid F，McDaid A，et al.Detecting highly overlapping community structure by greedy clique expansion［A］/ /Proceeding SNA-KDD Workshop［C］/ /Washington DC，USA:IEEE，2010:33－42.

［8］Coscia M，Rossetti G，Giannotti F，et al.Uncovering hierarchical and overlapping communities with a local-first approach［J］.ACM Transactions on Knowledge Discovery from Data，2014，9(1):615－623.

［9］Lancichinetti A，Radicchi F，Ramasco J J，et al.Finding statistically significant communities in networks［J］.PloS One，2011，6(4):18961.

［10］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multi-scale complexity in networks［J］.Nature，2010，466(7307):761－764.

［11］Kim Y，Jeong H.Map equation for link communities［J］.Physical Review E，2011，84(2):26110.

［12］Ball B，Karrer B，Newman M E J.Efficient and principled method for detecting communities in networks［J］.Physical Review E，2011，84(3):36103.

［13］Granovetter M S.The strength of weak ties［J］.American Journal of sociology，1973，78(6):1360－1380.

［14］Chira C，Gog A.Fitness evaluation for overlapping community detection in complex networks［J］.Evolutionary Computation (CEC)，2011，1(1):5－8.

Overlapping Community Discovery Algorithm Based on Fuzzy Spectral Clustering

閆曉鵬1孫永波2
(江西師范大學計算機信息工程學院1，江西南昌330022;萊蕪鋼鐵冶金生態工程技術有限公司2，山東萊蕪271104)

摘要:為克服傳統重疊社區發現算法產生局部最優解的缺陷，提出一種新的基于模糊譜聚類的重疊社區發現算法。用局部連接相似度度量構造原始樣本數據集的相似度矩陣，并采用譜方法將原樣本嵌入到一個低維空間。在這個空間上，構造模糊相似矩陣，采用模糊聚類劃分社區，檢測并合并冗余社區。試驗結果表明，該算法能夠有效地提高重疊社區劃分的質量。

關鍵詞:模糊譜聚類模糊理論譜方法重疊社區相似度矩陣冗余社區二乘法

Abstract:To overcome the shortcoming of local optimal solution existing in traditional overlapping community discovery method，a new overlapping community discovery algorithm based on fuzzy spectral clustering is proposed.The similarity matrix of original sample data set is constructed using similarity measure of the local connection，and the original sample is embedded into a low dimensional space by using spectral method.In this space，the fuzzy similar matrix is constructed，and the community is divided by fuzzy clustering，redundant communities are detected and merged.The experimental results show that the algorithm effectively improves the quality of dividing overlapping community.

Keywords:Fuzzy spectral clustering Fuzzy theory Spectral method Overlapping community Similarity matrix Redundant communities Square method

中圖分類號:TH－3; TP301

文獻標志碼:A

DOI:10.16086/j.cnki.issn1000－0380.201603007

修改稿收到日期:2015－05－11。