莊明明,王藝華

目前很多復(fù)雜網(wǎng)絡(luò)算法都能夠成功地發(fā)現(xiàn)社區(qū),但是并不是每種劃分都是最優(yōu)結(jié)果,需要有一種定量的標(biāo)準(zhǔn)來判斷何種劃分是最好的.為解決這一問題,人們提出了模塊性函數(shù)Q.同一算法的多種劃分結(jié)果中,模塊性函數(shù)值越高,則認(rèn)為該劃分越合理.但需要明確的是,一種劃分是否優(yōu)于另外一種劃分存在不確定性,其中主要原因是社區(qū)的劃分依賴于特定的社團(tuán)概念及采用的模塊性函數(shù)[1].本文基于已有的Q函數(shù),提出一種新的重疊社區(qū)模塊性函數(shù),從理論和實(shí)驗(yàn)兩個(gè)方面證明該函數(shù)復(fù)合Newman提出的模塊性函數(shù)應(yīng)該具備的基本性質(zhì).另外,利用復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法和經(jīng)典實(shí)驗(yàn)數(shù)據(jù),并與經(jīng)典的EQ函數(shù)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比.

1 研究背景及現(xiàn)狀

在社區(qū)發(fā)現(xiàn)算法的發(fā)展過程當(dāng)中,Newman和Girvan[2]最先給出了模塊性函數(shù)的定義:

其中矩陣e為k×k(將網(wǎng)絡(luò)劃分為k個(gè)社團(tuán))的對(duì)稱矩陣,元素eij表示社區(qū)i中的節(jié)點(diǎn)與社區(qū)j中的節(jié)點(diǎn)相連接的邊的數(shù)目在總的邊數(shù)目里所占的比例;eii則表示社區(qū)i內(nèi)部所有邊占全部邊的比例;表示連接社區(qū)i中的全部節(jié)點(diǎn)的邊在總的邊數(shù)里所占的比例;‖X‖ =.同時(shí),Newman和Girvan指出如果所有的節(jié)點(diǎn)都在一個(gè)社區(qū)中,Q函數(shù)的值為0;Q越趨近于1,說明社區(qū)結(jié)果的模塊化程度越高.

基于Newman和Girvan提出的Q函數(shù),很多人進(jìn)行了很多的改進(jìn),以使適應(yīng)不同的網(wǎng)絡(luò)及社區(qū)定義標(biāo)準(zhǔn).Fortunato在文獻(xiàn)[1]中綜述了關(guān)于加權(quán)無向圖、無權(quán)有向圖、加權(quán)有向圖的硬劃分(每個(gè)節(jié)點(diǎn)只屬于一個(gè)社區(qū))下的模塊性函數(shù).Nicosia等人[3]首先將Newman等人定義的Q函數(shù)推廣到有向圖中,進(jìn)而提出了評(píng)價(jià)有向網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)的Qov函數(shù).尚明生等[4]提出關(guān)于重疊社區(qū)的模塊性Qo函數(shù).

當(dāng)一個(gè)節(jié)點(diǎn)可能屬于多個(gè)社區(qū),即出現(xiàn)重疊社區(qū)時(shí),這些定義就不適用了.基于此,人們?cè)诤罄m(xù)的研究當(dāng)中,針對(duì)重疊社區(qū)提出了相應(yīng)的模塊性函數(shù).Shen等[5]提出EAGLE算法的同時(shí),為了能在樹狀圖中選擇某一層作為社區(qū)發(fā)現(xiàn)的結(jié)果,提出了一種能夠評(píng)價(jià)重疊社區(qū)結(jié)構(gòu)的Q函數(shù)的擴(kuò)展,即EQ函數(shù)

其中Ov表示節(jié)點(diǎn)v所屬社區(qū)的數(shù)目,A為鄰接矩陣,kv為節(jié)點(diǎn)v的度,m表示網(wǎng)絡(luò)中邊的數(shù)目.

當(dāng)社區(qū)結(jié)構(gòu)是非重疊時(shí)(每個(gè)節(jié)點(diǎn)至多只屬于一個(gè)社區(qū)),EQ的值和Q函數(shù)一致.另外,如果所有的節(jié)點(diǎn)都在一個(gè)社區(qū)中,EQ函數(shù)的值為0.Shen等[5]指出,較高的EQ值代表著較強(qiáng)的重疊社區(qū)結(jié)構(gòu).

2 一種新的重疊社區(qū)模塊性函數(shù)

對(duì)于重疊社區(qū),假設(shè)隸屬度矩陣為Uk×n,其中k為社區(qū)數(shù),n為節(jié)點(diǎn)數(shù),Uij表示節(jié)點(diǎn)j屬于社區(qū)i的強(qiáng)度,對(duì)任意節(jié)點(diǎn)j均有1.結(jié)合以上幾個(gè)重疊社區(qū)模塊性函數(shù)的定義,本文提出新的模塊性函數(shù)

其中c為社區(qū)數(shù),Ci表示第i個(gè)社區(qū),ku為節(jié)點(diǎn)u的度,m為網(wǎng)絡(luò)的邊數(shù).

文獻(xiàn)[3]指出,Newman提出的模塊性函數(shù)最重要的性質(zhì)有如下兩點(diǎn):

1)當(dāng)全部節(jié)點(diǎn)都屬于同一個(gè)社團(tuán)的時(shí)候,Q=0;

2)Q值越高,則所劃分的社團(tuán)結(jié)構(gòu)越合理.

對(duì)于Qu,可以證明是滿足以上兩條性質(zhì)的.首先,當(dāng)全部節(jié)點(diǎn)都屬于同一個(gè)社區(qū)的時(shí)候,對(duì)任意u有U1u=1,即有

在一個(gè)完全沒有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)中,一個(gè)節(jié)點(diǎn)u屬于某個(gè)社區(qū)的隸屬度(小于等于1)與同時(shí)屬于同一個(gè)模塊的其他鄰近節(jié)點(diǎn)的隸屬度相差是很大的,完全沒有關(guān)聯(lián)性,則產(chǎn)生的Q值也是非常小的.相反,若網(wǎng)絡(luò)有很強(qiáng)的社區(qū)結(jié)構(gòu),若兩個(gè)節(jié)點(diǎn)同時(shí)屬于一個(gè)社區(qū),可以預(yù)見的情況下是該兩個(gè)節(jié)點(diǎn)的隸屬度大小是相近的,從而產(chǎn)生的模塊性函數(shù)應(yīng)該是最大的.即該模塊性函數(shù)也應(yīng)該是滿足模塊性函數(shù)的第二個(gè)性質(zhì).

對(duì)于第二個(gè)性質(zhì),目前尚缺乏對(duì)模塊性函數(shù)優(yōu)劣進(jìn)行評(píng)判的定性標(biāo)準(zhǔn),其優(yōu)劣只能通過實(shí)際網(wǎng)絡(luò)的實(shí)驗(yàn),人為地進(jìn)行判斷其優(yōu)劣.通過使用比較多的基于非負(fù)矩陣分解的重疊社區(qū)發(fā)現(xiàn)算法[6]對(duì)Qu進(jìn)行實(shí)驗(yàn)驗(yàn)證,實(shí)驗(yàn)數(shù)據(jù)為社會(huì)學(xué)家Zachary用兩年的時(shí)間來觀察美國一所大學(xué)中空手道俱樂部34名成員間的社會(huì)關(guān)系而構(gòu)造的社會(huì)網(wǎng)絡(luò)數(shù)據(jù).他構(gòu)造的成員之間的社會(huì)關(guān)系網(wǎng)是基于這些成員在俱樂部內(nèi)部及外部的交往情況的,該網(wǎng)絡(luò)包含34個(gè)結(jié)點(diǎn)78條邊[7].該數(shù)據(jù)是社會(huì)網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集.忽略由于NMF分解造成的不穩(wěn)定性問題,一次運(yùn)行結(jié)果如圖1.

圖1 Qu值變化趨勢(shì)圖

從圖1可以看出,Qu值在社區(qū)數(shù)為2時(shí)取得最大值,也即最佳劃分為兩個(gè)社區(qū),其后Qu值總體上呈下降趨勢(shì),只有一個(gè)最大值,可知此模塊性函數(shù)定義是符合要求的.

3 實(shí)驗(yàn)結(jié)果對(duì)比

目前存在許多真實(shí)網(wǎng)絡(luò)數(shù)據(jù),而且被廣大的研究者作為實(shí)驗(yàn)數(shù)據(jù)進(jìn)行相關(guān)實(shí)驗(yàn),如Karate俱樂部網(wǎng)絡(luò)、新西蘭海豚網(wǎng)絡(luò)、美國大學(xué)生足球比賽網(wǎng)絡(luò)數(shù)據(jù)等.本文也采用這些數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù),同時(shí)選用基于非負(fù)矩陣分解重疊社區(qū)發(fā)現(xiàn)算法(CNMF)和模糊C_均值重疊社區(qū)發(fā)現(xiàn)算法(FCMDA)對(duì)目標(biāo)數(shù)據(jù)進(jìn)行社區(qū)劃分,分別計(jì)算相應(yīng)的EQ值和Qu值.實(shí)驗(yàn)過程均在同等硬件、軟件條件下使用Java語言實(shí)現(xiàn).

3.1 新西蘭海豚網(wǎng)絡(luò)

Lusseau等在新西蘭長時(shí)間地對(duì)62只寬吻海豚的生活習(xí)性進(jìn)行了觀察,構(gòu)造了包含有62個(gè)結(jié)點(diǎn)的社會(huì)網(wǎng)絡(luò).他們研究發(fā)現(xiàn)這些海豚的交往呈現(xiàn)出特定的模式,網(wǎng)絡(luò)中相應(yīng)的兩個(gè)結(jié)點(diǎn)之間有一條邊存在,對(duì)應(yīng)的是這兩只海豚經(jīng)常一起頻繁活動(dòng)[8].類似于人的社交網(wǎng)絡(luò),如Karate俱樂部網(wǎng)絡(luò),從而可以推知,該海豚網(wǎng)絡(luò)也存在社區(qū)結(jié)構(gòu).新西蘭海豚網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)結(jié)果如表1.

表1 新西蘭海豚網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)Q值

表2 美國大學(xué)生足球比賽網(wǎng)絡(luò)數(shù)據(jù)實(shí)驗(yàn)Q值

從表1可以看出,CNMF算法所取得的Qu值和EQ值均比FCMDA算法所取得的Qu值和EQ值高,從Qu值和EQ值可得到相同的結(jié)論:CNMF算法的實(shí)驗(yàn)結(jié)果優(yōu)于FCMDA算法.另外,兩種算法所得到的Qu值均比EQ值略低.

3.2 美國大學(xué)生足球比賽網(wǎng)絡(luò)

美國大學(xué)生足球(橄欖球)比賽網(wǎng)絡(luò)是2000年秋季美國高校橄欖球甲級(jí)常規(guī)賽季的關(guān)系數(shù)據(jù).該網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)代表一個(gè)球隊(duì),節(jié)點(diǎn)之間的邊代表兩個(gè)球隊(duì)之間有比賽.該網(wǎng)絡(luò)共有115個(gè)節(jié)點(diǎn)、613條邊.在比賽的過程當(dāng)中,這些球隊(duì)被隨機(jī)分成12個(gè)小組,每個(gè)小組有8到12支球隊(duì)組成.組內(nèi)球隊(duì)間比賽多于組間比賽次數(shù),從而很自然地可以認(rèn)為這些球隊(duì)之間存在社區(qū)結(jié)構(gòu)[9].美國大學(xué)生足球(橄欖球)比賽網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如表2.從表2可以看出,CNMF算法所取得的Qu值0.226和EQ值0.252 668均比FCMDA算法所取得的Qu值0.146 235和EQ值0.166 858高,從Qu值和EQ值可得到相同的結(jié)論:CNMF算法的實(shí)驗(yàn)結(jié)果優(yōu)于FCMDA算法.另外,兩種算法所得到的Qu值均比EQ值略低.

4 結(jié)論

本文主要介紹重疊社區(qū)劃分評(píng)價(jià)指標(biāo)——模塊性函數(shù),根據(jù)已有的Q函數(shù),提出一種新的重疊社區(qū)模塊性函數(shù),并從理論及實(shí)證兩方面證明該函數(shù)的可行性.同時(shí),通過復(fù)雜網(wǎng)絡(luò)社區(qū)劃分研究常用的實(shí)驗(yàn)數(shù)據(jù)和算法進(jìn)行實(shí)驗(yàn)對(duì)比,以驗(yàn)證其可行性,本文實(shí)驗(yàn)結(jié)果中具有一定的可行性,但是其可行性還需要進(jìn)行大量的實(shí)驗(yàn)對(duì)比才能夠有更好的說服力,后續(xù)研究可以嘗試從這方面進(jìn)行.

參考文獻(xiàn):

[1]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486:75-174.

[2]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Phys.Rev.E,2004,69(2):026113.

[3]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanies:Theory and Experiment,2009(3):03024.

[4]Shang M S,Chen D B,Zhou T.Detecting Overlapping Communities Based on Community Cores in Complex Networks[J].Chinese Physics Letters,2010,27(5):058901.

[5]Shen H W,Cheng X Q,Cai K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A,2009,388:1706-1712.

[6]Zarei M,Izadi D,Samani K A.Detecting overlapping community structure of networks based on vertex–vertex correlationss[J].Journal of Statistical Mechanics:Theory and Experiment,2009(11):11013.

[7]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33:452-456.

[8]David Lusseau,Karsten Schneider,Oliver J.Boisseau,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54:396-405.

[9]Girvan M,Newman M.Community structure in social and biological networks[J].PNAS,2002,99(12):7821-7826.