基于關(guān)系層次性的局部社團(tuán)探測方法

鄒斌

（安徽廣播電視大學(xué)，安徽 合肥 230022）

基于關(guān)系層次性的局部社團(tuán)探測方法

鄒斌

（安徽廣播電視大學(xué)，安徽 合肥 230022）

挖掘復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對(duì)研究復(fù)雜系統(tǒng)具有重要的理論和實(shí)踐意義，局部社團(tuán)探測是其主要挑戰(zhàn)之一。目前對(duì)局部社團(tuán)探測方法的研究甚少，且大多算法精確度過低。對(duì)此從關(guān)系的層次性考慮，通過節(jié)點(diǎn)的相對(duì)相似性和一個(gè)參數(shù)α定義了朋友和最好朋友的概念。給出三個(gè)假設(shè)，并在此基礎(chǔ)上設(shè)計(jì)了基于關(guān)系層次性的局部社團(tuán)探測算法（HR）。實(shí)驗(yàn)表明，HR要優(yōu)于當(dāng)前同類算法。最后經(jīng)分析，發(fā)現(xiàn)參數(shù)α的最優(yōu)值與網(wǎng)絡(luò)的平均相對(duì)相似度成正相關(guān)。

社團(tuán)結(jié)構(gòu)；局部社團(tuán)探測；朋友；最好朋友

引言

社團(tuán)結(jié)構(gòu)普遍存在于社會(huì)網(wǎng)、信息網(wǎng)、生物網(wǎng)等，網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對(duì)于理解網(wǎng)絡(luò)的組織結(jié)構(gòu)和其所代表的功能特性有著重要意義。到目前為止，人們提出了很多經(jīng)典的社團(tuán)探測方法。2002年Girvan和Newman提出了“邊界數(shù)”的概念①Grivan M,Newan M E J,"Community Structure Insocial and Biological Networks",Proc of National Academy of Science，Vol.99,No.12,2002,pp.7821-7826.，邊界數(shù)定義為網(wǎng)絡(luò)中通過某條邊的兩點(diǎn)間最短路徑的條數(shù)。社團(tuán)內(nèi)點(diǎn)之間連接緊密，社團(tuán)內(nèi)相互連接的路徑較多，任意兩點(diǎn)之間的最短路徑會(huì)比較均勻地經(jīng)過各條邊，所以社團(tuán)內(nèi)部的邊界數(shù)較低。而不同社團(tuán)之間由于連接較少，導(dǎo)致跨社團(tuán)的邊成為連接不同社團(tuán)的點(diǎn)對(duì)之間的必經(jīng)之路，所以這類邊的邊界數(shù)一般比較高。邊界數(shù)高的邊具有明顯的“橋梁效應(yīng)”。GN算法就是通過刪除邊界數(shù)較高的邊完成社團(tuán)的劃分過程的；Newman隨后又提出了一種快速的模塊度局部最優(yōu)化算法②Newan M E J,"Fast Algorithm for Detecting Community Structure in Networks",phys Rew E,Vol.69,No. 6,2004,066133.，局部最優(yōu)解是可以找到的。首先所有節(jié)點(diǎn)都被看成單個(gè)社團(tuán)，在每次迭代過程中選擇其中一對(duì)社團(tuán)進(jìn)行合并，這對(duì)社團(tuán)的合并可以帶來模塊度增益的最大化，迭代過程一直進(jìn)行，直到模塊度達(dá)到極大值時(shí)停止，Blonde③Blodel,Vincent D.,et al,"Fast Unfolding of Communities inLarge Networks",Statistical Mechanics:Theory and Experiment,No.10,2008,PI0008.也提出了類似的算法。其它的社團(tuán)探測算法還有很多，如基于譜分析的社團(tuán)探測算法④Capocci A,Servedio V D P,Caldarelli G,et al,"Detecting Community in Large Networks",Physica A: Statistical Mechanics and Its Applications,Vol.152,No.2-4,2005,pp.669-676.和標(biāo)簽傳播算法⑤Raghavan U N,Albert R,Kumara S,"Near Linear Time Algorithm to Detect Community Structure in largeacale Networks",Phys ReV E,Vol.76,No.3,2007,036106.等。

上面所述的都是全局的社團(tuán)探測算法。但是在現(xiàn)實(shí)中，很難獲取網(wǎng)絡(luò)的全局信息，而且許多情況下只需要知道某些節(jié)點(diǎn)所在的社團(tuán)信息，并不需要知道整個(gè)網(wǎng)絡(luò)的情況，所以局部社團(tuán)探測算法的設(shè)計(jì)是非常有意義的。局部社團(tuán)探測算法的研究不多，這些算法主要都是一些擴(kuò)張算法。如文獻(xiàn)①Clauset A,"Finding Local Community Structure in Networks",Physical Review E,Vol.72,No.2,2005,026132.提出了一種基于R值的局部社團(tuán)探測算法，該算法首先定義一個(gè)局部模塊度R，然后應(yīng)用貪婪算法的思想，迭代添加使R值增加最大的鄰居節(jié)點(diǎn)，直到社團(tuán)達(dá)到預(yù)定的規(guī)模，該算法最大的缺點(diǎn)是事先需要知道社團(tuán)的大小。其它的還有類似的基于隨機(jī)種子擴(kuò)張的LFM算法②Luo F,Wang J Z,"Promislow E.Exploring Local CommunityStructures in Large Networks",Web Intelligence and Agent Systems,Vol.6,No.4,2008,pp.387-400.，基于模塊度M的LMD算法③Chen Q,Wu T T,Fang M,"Detecting Local Community Structures in Complex Networks Based on LocalDegree Central Nodes",Physica A:Statistical Mechanics and Its Applications,Vol.392,No.3,2013,pp.529-537.等。

本文考慮關(guān)系的層次性，通過節(jié)點(diǎn)的相對(duì)相似性和一個(gè)參數(shù)α定義了朋友和最好朋友的概念。在現(xiàn)實(shí)中，如果我的最好朋友在一個(gè)朋友圈，我基本上也屬于這個(gè)朋友圈；如果我和某個(gè)人互為朋友，則我們?cè)谝粋€(gè)朋友圈的可能性就很大；還有如果我的很多朋友都在這個(gè)朋友圈，我很難不在這個(gè)圈子內(nèi)?；谶@些現(xiàn)象提出了三個(gè)假設(shè)，然后可以得到任意一個(gè)節(jié)點(diǎn)通過擴(kuò)張得到的社團(tuán)。實(shí)驗(yàn)表明，本文的算法要優(yōu)于當(dāng)前同類算法。最后經(jīng)分析，還發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象：參數(shù)α的最優(yōu)值與網(wǎng)絡(luò)的平均相對(duì)相似度成正相關(guān)。

1相關(guān)定義

在現(xiàn)實(shí)生活中可能認(rèn)識(shí)的人很多，不是每個(gè)人都能稱作為朋友，而朋友又有好與普通之分。如圖1，所有節(jié)點(diǎn)都是A所認(rèn)識(shí)的人，而能稱作朋友的有4個(gè)，4個(gè)里面還有1個(gè)最好朋友?？梢约僭O(shè)節(jié)點(diǎn)A和自己的最好朋友（唯一）一定在一個(gè)社團(tuán)（很難想象你和你的唯一兄弟身處兩個(gè)社團(tuán)，這違背社團(tuán)的定義）；節(jié)點(diǎn)A的普通朋友如果絕大多數(shù)在一個(gè)社團(tuán)內(nèi)，則A也一定在這個(gè)社團(tuán)；另外，還可以認(rèn)為如果兩個(gè)節(jié)點(diǎn)互為朋友，則這兩個(gè)節(jié)點(diǎn)在一個(gè)社團(tuán)內(nèi)（在網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)互為朋友，則說明他們可能有著某種相似結(jié)構(gòu)，且互相緊密相連，這與社團(tuán)內(nèi)部緊密相連不謀而合）。根據(jù)這些假設(shè)，可以用擴(kuò)張的算法得到網(wǎng)絡(luò)任意一個(gè)節(jié)點(diǎn)所在的社團(tuán)。在這里首先給出節(jié)點(diǎn)的朋友與最好朋友的定義。

圖1 節(jié)點(diǎn)A的關(guān)系層次圖

定義G(V,E)為一個(gè)無向網(wǎng)絡(luò)，其中V為節(jié)點(diǎn)集合，E為邊集合。Γ(v)為節(jié)點(diǎn)v所有鄰居的集合，為集合元素的個(gè)數(shù)。于是網(wǎng)絡(luò)中任意兩個(gè)有連邊的節(jié)點(diǎn)x,y的相似關(guān)系的強(qiáng)弱可以用共同鄰居的個(gè)數(shù)（共同鄰居越多相似性越大）來衡量：

由上式可以看出兩個(gè)節(jié)點(diǎn)只要有連邊就有關(guān)系。接著給出節(jié)點(diǎn)的最大相似性指標(biāo)：

因此節(jié)點(diǎn)v和其所有鄰居相對(duì)相似度可以定義為：

由上式可以看出：S(x,y)=S(y,x)，但是RS(v,v0)≠RS (v0,v)。顯然，根據(jù)節(jié)點(diǎn)v和其所有鄰居相對(duì)相似度，再給定一個(gè)參數(shù)α，可以給出節(jié)點(diǎn)v在參數(shù)α下的所有朋友集合fα(v)。若，v0∈fα(v),則須滿足：

由上式可以看出：f0(v)是節(jié)點(diǎn)v的所有鄰居的集合；f1(v)為和節(jié)點(diǎn)v最相似節(jié)點(diǎn)集合。于是可以給出節(jié)點(diǎn)v的最好朋友集合：

由上式可以看出如果節(jié)點(diǎn)v最相似的鄰居唯一則有最好朋友，否則沒有最好朋友。

2 HR算法

2.1 算法設(shè)計(jì)與步驟

根據(jù)上述定義，可以給出前文提到的三個(gè)假設(shè)的規(guī)范表達(dá)，設(shè)G為某個(gè)節(jié)點(diǎn)通過擴(kuò)張得到的社團(tuán)。

假設(shè)1：若v∈G，則fmax(v)∈G,；若fmax(v)∈G，則v∈G（節(jié)點(diǎn)v和自己的最好朋友在一個(gè)社團(tuán)）；

假設(shè)2：若v1fα(v2)，v2∈fα(v1),v1∈G則v2∈G（節(jié)點(diǎn)v1,v2互為朋友，則兩個(gè)節(jié)點(diǎn)同屬一個(gè)社團(tuán)）；

圖2 實(shí)例網(wǎng)絡(luò)

根據(jù)上述三個(gè)假設(shè)可以找到任意一個(gè)節(jié)點(diǎn)所在的社團(tuán)。如表1是圖2所有節(jié)點(diǎn)的信息，其中a= 0.6?，F(xiàn)在要尋找節(jié)點(diǎn)1所在的社團(tuán)。

表1 圖2中每個(gè)節(jié)點(diǎn)的屬性信息（鄰居集合和相對(duì)相似度集合一一對(duì)應(yīng)）

首先，節(jié)點(diǎn)2是節(jié)點(diǎn)1的最好朋友，則節(jié)點(diǎn)2在這個(gè)社團(tuán)（假設(shè)1）；接著節(jié)點(diǎn)2又是節(jié)點(diǎn)4的最好朋友，所以節(jié)點(diǎn)4并入該社團(tuán)（假設(shè)1）；節(jié)點(diǎn)3的朋友是節(jié)點(diǎn)2和4，它們都在社團(tuán)內(nèi)，所以節(jié)點(diǎn)3也屬于該社團(tuán)（假設(shè)3）；節(jié)點(diǎn)5和節(jié)點(diǎn)2互為朋友，所以節(jié)點(diǎn)5在社團(tuán)內(nèi)（假設(shè)2）；又節(jié)點(diǎn)6、7、8分別和節(jié)點(diǎn)5互為朋友，所以它們也是社團(tuán)的一部分（假設(shè)2）。這時(shí)，由節(jié)點(diǎn)1擴(kuò)張的社團(tuán)為：1、2、3、4、5、6、7、8。又社團(tuán)的所有鄰居與社團(tuán)內(nèi)部節(jié)點(diǎn)都不滿足三個(gè)假設(shè)條件，所以擴(kuò)張結(jié)束。得到的結(jié)果可以看到與實(shí)際情況吻合。下面給出基于多層次相似關(guān)系的局部社團(tuán)探測方法（HR）的步驟。

設(shè)CS(v)是由節(jié)點(diǎn)v擴(kuò)展得到的社團(tuán)，ACS為準(zhǔn)社團(tuán)，ACS中的元素會(huì)逐個(gè)移動(dòng)到CS中，F(xiàn)S為朋友集合。則給定一個(gè)節(jié)點(diǎn)v0，由v0擴(kuò)張得到社團(tuán)CSv0的步驟為：

算法1：

初始化：CS=O，ACS=｛v0｝，F(xiàn)S=。

Step1：從ACS中取出一個(gè)元素v放入CS這中，即，ACS=ACS-v,CS=CS∪v。

Step2：討論節(jié)點(diǎn)v：ACS=ACS∪(fmax(v)-CS)；假設(shè)1）。

Step3：討論節(jié)點(diǎn)v的鄰居，對(duì)任意v1∈Γ(v)且v1∈(ACS∪CS):

（1）若fmax(v1)=v，則ACS=ACS∪(v1-CS（)假設(shè)1）。

（2）若v∈fα(v1)，v1∈fα(v),則ACS=ACS∪(v1-CS)（假設(shè)2）。

（3）若v∈fα(v1)，則FS=FS∪v（1存在朋友在社團(tuán)內(nèi)的節(jié)點(diǎn)）。

Step5：轉(zhuǎn)到step4，直到FS不變。

2.2 算法分析與改進(jìn)

該算法是經(jīng)過對(duì)節(jié)點(diǎn)的鄰居和節(jié)點(diǎn)的關(guān)系分析，然后一步步擴(kuò)張得到該節(jié)點(diǎn)的所在的社團(tuán)。但是，節(jié)點(diǎn)會(huì)不會(huì)出現(xiàn)擴(kuò)張不出去的狀況呢？如圖2和表1，若想找節(jié)點(diǎn)3所在的社團(tuán)，但是節(jié)點(diǎn)3沒有最好朋友，也沒有節(jié)點(diǎn)以節(jié)點(diǎn)3為最好朋友，甚至沒有節(jié)點(diǎn)和節(jié)點(diǎn)3互為朋友。所以，以節(jié)點(diǎn)3為初始點(diǎn)，得到的社團(tuán)就是節(jié)點(diǎn)3本身。這和實(shí)際情況不相符，所以需要對(duì)算法進(jìn)行改進(jìn)。

遇到上述情況，只需考慮該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)擴(kuò)張情況，如果節(jié)點(diǎn)的鄰居擴(kuò)充得到的社團(tuán)包含這個(gè)節(jié)點(diǎn)，則該社團(tuán)就是這個(gè)節(jié)點(diǎn)所在的社團(tuán)，否則可以說明該節(jié)點(diǎn)為孤立點(diǎn)。如圖2，節(jié)點(diǎn)3的鄰居2和4擴(kuò)張得到的社團(tuán)都是：

1、2、3、4、5、6、7、8，所以可以認(rèn)為節(jié)點(diǎn)3所在的社團(tuán)為：1、2、3、4、5、6、7、8。

這里可以給定一個(gè)參數(shù)β，用來控制最小社團(tuán)大小。則由v0擴(kuò)張得到社團(tuán)CS(v0)的步驟為：

算法2：

Step1：通過算法1得到CS(v0)，若CS(v0)＞β，轉(zhuǎn)step3，否則轉(zhuǎn)step2。

Step2：對(duì)于任意v∈Γ(CS(v0))，由算法1計(jì)算CS(v)。直到存在v使得CS(v0)∈CS(v)，則CS(v0)=CS (v)。如果對(duì)任意v，CS(v0)∈CS(v)都成立，則轉(zhuǎn)step3。

Step3:輸出Γ(CS(v0))。

這里Γ(CS(v0))為CS(v0).中所有節(jié)點(diǎn)的鄰居集合。參數(shù)β的取值默認(rèn)為2，因?yàn)槿齻€(gè)節(jié)點(diǎn)組成一個(gè)社團(tuán)是很有可能存在的，實(shí)驗(yàn)也驗(yàn)證當(dāng)β取大于2時(shí)，完全是增加計(jì)算量，基本不會(huì)改變節(jié)點(diǎn)擴(kuò)張結(jié)果。

2.3 復(fù)雜度分析

設(shè)由節(jié)點(diǎn)v擴(kuò)張得到的社團(tuán)CS(v)的規(guī)模是n1，社團(tuán)的邊數(shù)為m1（與社團(tuán)內(nèi)部所有節(jié)點(diǎn)相連的邊個(gè)數(shù)），該社團(tuán)內(nèi)部的平均度為＜k＞。算法主要有兩個(gè)部分：相似度計(jì)算和算法擴(kuò)張。因?yàn)楣?jié)點(diǎn)的相似度基于共同鄰居，所以時(shí)間復(fù)雜度大致為：m1＜k＞2。而擴(kuò)張過程只針對(duì)其鄰居，所以算法的復(fù)雜度大概為：n1＜k＞。綜上所述HR算法的時(shí)間復(fù)雜度約為：m1＜k＞2+n1＜k＞?？梢钥闯霰疚腍R算法時(shí)間復(fù)雜度不高，接近線性。

3 數(shù)值實(shí)驗(yàn)

本文將HR算法分別與Clauset-R①Clauset A,"Finding Local Community Structure in Networks",Physical ReviewE,Vol.72.No.2,2005, 026132.、LFM②Luo F,Wang J Z,"Promislow E.Exploring Local CommunityStructures in Large Networks",Web Intelligence and Agent Systems,Vol.6,No.4,2008,pp.387-400.、LMD③Chen Q,Wu T T,"Fang M.Detecting Local Community Structures in Complex Networks Based on LocalDegree Central Nodes",Physica A:Statistical Mechanics and Its Applications,Vol.329,No.3,2013,pp.pp.529-537.等局部社團(tuán)挖掘算法進(jìn)行比較。為了方便，采用最常見的幾種網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測試。其中包括Zachary空手道俱樂部成員關(guān)系網(wǎng)（Karate）④Zachary W W,"An Information Flow model for Conflict and Fission in Small Groups".Journal of Anthropological Research,Vol.33,No.4,1977,pp.452-473.、寬吻海豚網(wǎng)絡(luò)(dolphins)⑤Lusseau D,Schneider K,Boisseau O J,Haase P,Slooten E,Dawson S M,"The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-lasting Associations",Behavioral Ecology and Sociobiology,Vol.54,No.4,2003,pp.396-405.、美國政治書籍網(wǎng)絡(luò)(polbooks)⑥Newman M E J,"Modularity and Community Structure in Networks",Proceedings of National Academy of Sciences of the United States of America,Vol.103,No.23,2006,pp.8577-8582.和美國大學(xué)橄欖球聯(lián)賽網(wǎng)絡(luò)(football)⑧Grivan M,Newan M E J."Community Structure Insocial and Biological Networks",Proc of National A－cademy of Science,Vol.99,No.12,2002,pp.7821-7826.四個(gè)網(wǎng)絡(luò)。

3.1 算法結(jié)果評(píng)價(jià)指標(biāo)

在這里應(yīng)用三個(gè)指標(biāo)來衡量算法的優(yōu)越：準(zhǔn)確率P、召回率R和綜合評(píng)級(jí)指標(biāo)F⑧Strehl A,Ghosh J,"Cluster Ensembles-A Knowledge Reuse Framework for Combining Multiple Partitions", Journal on Machine Learning Research,No.3,2002,pp.583-61.。

（1）準(zhǔn)確率

準(zhǔn)確率反映了劃分結(jié)果中正確節(jié)點(diǎn)數(shù)量占劃分結(jié)果規(guī)模的比例。其定義如下：

（2）召回率

召回率反映了真實(shí)社團(tuán)中被正確劃分出的節(jié)點(diǎn)的比例。其定義如下：

（3）綜合評(píng)價(jià)指標(biāo)

P值和R值只能反映算法的某一方面。P值高說明劃分結(jié)果中正確的節(jié)點(diǎn)的數(shù)量占劃分結(jié)果規(guī)模的比例較大，但是卻不能判斷是否過劃分，比如極端的情況下只劃分出社團(tuán)的一個(gè)節(jié)點(diǎn)，其P值達(dá)到最大為1。R值高說明真實(shí)社團(tuán)中更多的節(jié)點(diǎn)被劃分出來，但是卻不能判斷是否欠分割，比如極端情況下將整個(gè)網(wǎng)絡(luò)劃分為一個(gè)社團(tuán)，其R值最大為1。因此單從P值和R值無法判斷一個(gè)算法的性能，所以下面給出一個(gè)更合理指標(biāo)，即綜合評(píng)價(jià)指標(biāo)F：

3.2 實(shí)驗(yàn)結(jié)果

應(yīng)用HR算法求得每個(gè)節(jié)點(diǎn)所在的社團(tuán)，分別計(jì)算其P、R、F指標(biāo)，然后平均得到最終HR算法的三個(gè)評(píng)價(jià)指標(biāo)結(jié)果見表2。表中Clauset-R、LFM和LMD算法結(jié)果來源于文獻(xiàn)⑨Chen Q,Wu T T,"Fang M.Detecting Local Community Structures in Complex Networks Based on LocalDegree Central Nodes",Physica A:Statistical Mechanics and Its Applications,Vol.329,No.3,2013,pp.529-537.。其中HR算法中的參數(shù)a=0.6。結(jié)果表明HR算法明顯優(yōu)于其它三種算法。

3.3 參數(shù)分析

很明顯，參數(shù)α的取值不同，得到結(jié)果也不同。如圖3可以看出，隨著α增大，HR算法的P指標(biāo)逐漸增加，R指標(biāo)逐漸減小。這是因?yàn)?，?dāng)α很小的時(shí)候，節(jié)點(diǎn)和他的鄰居更容易成為朋友，所以由假設(shè)2（兩個(gè)節(jié)點(diǎn)互為好友在同一個(gè)社團(tuán)）可知，整個(gè)網(wǎng)絡(luò)很難被分開，是欠劃分的狀況，所以R值很大，P值很小。隨著增大，社團(tuán)被劃分的越來越細(xì)，所以P值逐漸增加，R值逐漸減少，當(dāng)α很大的時(shí)候會(huì)出現(xiàn)過劃分的情況。

表2 HR算法與其它算法在四個(gè)網(wǎng)絡(luò)實(shí)驗(yàn)中的結(jié)果

綜合評(píng)價(jià)指標(biāo)在F在P指標(biāo)和R指標(biāo)雙重影響下，大致會(huì)呈現(xiàn)先增加后減小的趨勢。于是，這里就會(huì)有參數(shù)α當(dāng)取得什么值的時(shí)候F最大的問題存在。不同的網(wǎng)絡(luò)，最優(yōu)參數(shù)α的取值顯然不同。最終是希望能找到這個(gè)最優(yōu)參數(shù)α，如在Karate網(wǎng)絡(luò)中當(dāng)a=0.45時(shí)F=0.974要遠(yuǎn)遠(yuǎn)優(yōu)于大致取的α= 0.6的情況；在polbooks網(wǎng)絡(luò)這種情況更甚，當(dāng)α= 0.3時(shí)F=1，也就是說無論從哪個(gè)節(jié)點(diǎn)開始擴(kuò)張找到的社團(tuán)都與實(shí)際相符。因此尋找最優(yōu)α或?qū)ふ沂鞘裁匆蛩卦谟绊懽顑?yōu)參數(shù)α的取值對(duì)提高算法的精確度有很大的幫助。

圖3 HR算法評(píng)價(jià)指標(biāo)隨著參數(shù)變化圖

首先定義網(wǎng)絡(luò)平均相對(duì)相似度為Mean-RS網(wǎng)絡(luò)中所有不為零的相對(duì)相似度（計(jì)算如公式3）的平均值。如圖4所示發(fā)現(xiàn)參數(shù)α的最優(yōu)值與網(wǎng)絡(luò)平均相對(duì)相似度成正相關(guān)。這很容易理解，參數(shù)α就是通過網(wǎng)絡(luò)相對(duì)相似度來控制節(jié)點(diǎn)的朋友集合，網(wǎng)絡(luò)的平均相對(duì)相似度越大，參數(shù)α的設(shè)置應(yīng)該相應(yīng)的增大。

結(jié)束語

本文基于關(guān)系的層次性設(shè)計(jì)了一種局部社團(tuán)探測方法。該算法根據(jù)一個(gè)參數(shù)α和節(jié)點(diǎn)的相對(duì)相似度定義該節(jié)點(diǎn)的朋友與最好朋友集合。然后提出三條假設(shè)：（1）節(jié)點(diǎn)和它的最好朋友同屬于一個(gè)社團(tuán)；（2）兩個(gè)節(jié)點(diǎn)互為朋友在一個(gè)社團(tuán)；（3）節(jié)點(diǎn)的大多數(shù)朋友在一個(gè)社團(tuán)，則這個(gè)節(jié)點(diǎn)也屬于這個(gè)社團(tuán)?；诖?，通過設(shè)計(jì)的算法可以給出任意節(jié)點(diǎn)所在的社團(tuán)。實(shí)驗(yàn)表明效果優(yōu)于當(dāng)前的同類算法。最后，本文還討論了最優(yōu)參數(shù)α的取值問題，雖然發(fā)現(xiàn)了參數(shù)α的最優(yōu)值與網(wǎng)絡(luò)的平均相對(duì)相似度成正相關(guān)，這只能指導(dǎo)對(duì)參數(shù)的取值，但是最后還是無法精確給出在什么時(shí)候可已得到最好的擴(kuò)張結(jié)果，這將是以后研究的內(nèi)容。

Local community detection based on the hierarchy in relations

ZOU Bin

Community structure detection bears both theoretical and practical significance for the study of complex systems.The local community detection is one of its main challenges.Now,there is little research based on local community detection methods,and the precision of most of algorithm is low.Hence we consider the hierarchy in relations,through the relative similarity of the nodes and the concept of friend and best friend defined by a parameter.Three hypotheses are presented.Through the three hypotheses,we design the local community detection algorithm based on the hierarchy in relations(HR).The experimental results show that our algorithm is superior to the similar algorithm.Finally,we found that the optimal value of parameters is proportional to the network of average relative similarity through analysis.

community structure;local community detection;hierarchy in relations;friend;best friend

圖4 最優(yōu)參數(shù)和網(wǎng)絡(luò)平均相對(duì)相似度的關(guān)系圖

TP399

A

1009-9530（2016）05-00111-05

2015-12-30

安徽省高校優(yōu)秀青年人才支持計(jì)劃重點(diǎn)項(xiàng)目“基于動(dòng)態(tài)時(shí)序模糊軟集的不確定性信息度量模型研究與應(yīng)用”（gxyqZD2016453）；安徽廣播電視大學(xué)青年基金項(xiàng)目“基于時(shí)序模糊軟集金融風(fēng)險(xiǎn)預(yù)警數(shù)學(xué)模型”（qn15-20）

鄒斌（1981-），男，安徽廣播電視大學(xué)講師，碩士，研究方向：智能計(jì)算和復(fù)雜網(wǎng)絡(luò)。