Overlapping Community Discovery Algorithm Based on Fuzzy Spectral Clustering

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

?

模糊譜聚類重疊社區(qū)發(fā)現(xiàn)算法

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

0　引言

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

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

1　譜圖理論

譜圖理論使用線性代數(shù)理論和矩陣?yán)碚搧硌芯繄D的鄰接矩陣，并進(jìn)一步研究圖中所包含的信息。

為簡化計(jì)算，將拉普拉斯矩陣進(jìn)行歸一化，表示為:

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

2　模糊集

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

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

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

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

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

3　基于模糊譜聚類的重疊社區(qū)發(fā)現(xiàn)算法

為提高劃分重疊社區(qū)的質(zhì)量，需準(zhǔn)確地量化節(jié)點(diǎn)之間的相互關(guān)系［13］，并評估每個節(jié)點(diǎn)的重要性。利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息度量節(jié)點(diǎn)的局部連接相似度，作為一個影響鄰居節(jié)點(diǎn)的權(quán)值。因此，將節(jié)點(diǎn)的局部連接相似度定義如下。

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

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

定義2(冗余社區(qū)):連接社區(qū)Ci和社區(qū)Cj的邊的權(quán)重EWij由這兩個社區(qū)共同包含的節(jié)點(diǎn)個數(shù)得到。EWij的表達(dá)式為:

當(dāng)兩個社區(qū)的重疊程度大于某一閾值?，則稱社區(qū)Ci和Cj互為冗余社區(qū)，將兩社區(qū)合并成一個較大的社區(qū)。經(jīng)過試驗(yàn)，發(fā)現(xiàn)這個值設(shè)在0.70左右比較合理。

FSC-OCD算法描述如下。

輸入:網(wǎng)絡(luò)數(shù)據(jù)集的鄰接矩陣A = (aij)n×n，聚類劃分的個數(shù)k。

輸出:劃分的重疊社區(qū)結(jié)構(gòu)。

①根據(jù)數(shù)據(jù)集構(gòu)造一張圖，計(jì)算圖中連接點(diǎn)的權(quán)重作為節(jié)點(diǎn)間的相似度，將圖用鄰接矩陣W表示，其中每個節(jié)點(diǎn)的權(quán)重wij用局部連接相似度來度量。

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

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

④采用Z-score標(biāo)準(zhǔn)化將數(shù)據(jù)統(tǒng)一映射到［0，1］區(qū)間上，標(biāo)準(zhǔn)化后的數(shù)據(jù)為:

式中: Xi為數(shù)據(jù)的均值; si為數(shù)據(jù)的標(biāo)準(zhǔn)差。

⑤計(jì)算表示數(shù)據(jù)對象間相似程度的相似系數(shù)rij，在數(shù)據(jù)域上建立標(biāo)定的模糊相似矩陣R。

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

⑦根據(jù)截?cái)嚅撝郸?，?jì)算λ截矩陣R*，初步獲得重疊社區(qū)結(jié)構(gòu)。

⑧檢測重疊社區(qū)中的冗余社區(qū)，并合并冗余社區(qū)。

4　算法仿真

對FSC算法進(jìn)行仿真，并分別與經(jīng)典的COPRA、LFM兩種重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行比對。試驗(yàn)的運(yùn)行環(huán)境是英特爾計(jì)算機(jī)、2 GHz處理器、2 GB內(nèi)存，操作系統(tǒng)為Windows 7，編程環(huán)境為Matlab 2012b;采用擴(kuò)展后的模塊度函數(shù)EQ［14］來評價重疊社區(qū)劃分的質(zhì)量。

在仿真試驗(yàn)中，本文選取了3個經(jīng)典的、不同規(guī)模的實(shí)際網(wǎng)絡(luò)，包括空手道聯(lián)盟網(wǎng)絡(luò)(Zachary KarateNetwork)、海豚關(guān)系網(wǎng)絡(luò)(Dolphins Social Network)以及美國大學(xué)橄欖球聯(lián)盟網(wǎng)(American College Football)標(biāo)準(zhǔn)數(shù)據(jù)集，如表1所示。

表1　3個真實(shí)網(wǎng)絡(luò)Tab.1 Three real networks

圖1～圖3分別是FSC-OCD算法用于Karate、Dolphins和Football網(wǎng)絡(luò)劃分的效果圖，該算法在3個實(shí)際網(wǎng)絡(luò)上對應(yīng)的評價指標(biāo)EQov的值分別為0.75、0. 68、0.78，檢測到的重疊節(jié)點(diǎn)個數(shù)分別為8、10、9。

圖1　FSC-OCD算法用于Karate網(wǎng)絡(luò)Fig.1 FSC-OCD algorithm used to Karate network

圖2　FSC-OCD算法用于Dolphins網(wǎng)絡(luò)Fig.2 FSC-OCD algorithm used to Dolphins network

圖3　FSC-OCD算法用于Football網(wǎng)絡(luò)Fig.3 FSC-OCD algorithm used to Football network

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

表2　3種算法在實(shí)際網(wǎng)絡(luò)上的試驗(yàn)結(jié)果Tab.2 Experimental results of three algorithms for actual network

從表2可以看出，基于模糊譜聚類的重疊社區(qū)發(fā)現(xiàn)算法能更準(zhǔn)確、有效地劃分出實(shí)際網(wǎng)絡(luò)中的重疊社區(qū)，從而提高重疊社區(qū)劃分的質(zhì)量，且有效避免因局部最優(yōu)解產(chǎn)生的冗余社區(qū)。

5　結(jié)束語

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

參考文獻(xiàn)

［1］Palla G，Derényi I，F(xiàn)arkas 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，F(xiàn)ortunato 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
(江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院1，江西南昌330022;萊蕪鋼鐵冶金生態(tài)工程技術(shù)有限公司2，山東萊蕪271104)

摘要:為克服傳統(tǒng)重疊社區(qū)發(fā)現(xiàn)算法產(chǎn)生局部最優(yōu)解的缺陷，提出一種新的基于模糊譜聚類的重疊社區(qū)發(fā)現(xiàn)算法。用局部連接相似度度量構(gòu)造原始樣本數(shù)據(jù)集的相似度矩陣，并采用譜方法將原樣本嵌入到一個低維空間。在這個空間上，構(gòu)造模糊相似矩陣，采用模糊聚類劃分社區(qū)，檢測并合并冗余社區(qū)。試驗(yàn)結(jié)果表明，該算法能夠有效地提高重疊社區(qū)劃分的質(zhì)量。

關(guān)鍵詞:模糊譜聚類模糊理論譜方法重疊社區(qū)相似度矩陣冗余社區(qū)二乘法

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

文獻(xiàn)標(biāo)志碼:A

DOI:10.16086/j.cnki.issn1000－0380.201603007

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