社會網(wǎng)絡(luò)中的社區(qū)挖掘算法研究

楊 成，杜文才,2

( 1.海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228；2.澳門城市大學(xué), 澳門 999078)

?

社會網(wǎng)絡(luò)中的社區(qū)挖掘算法研究

楊 成1，杜文才1,2

( 1.海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228；2.澳門城市大學(xué), 澳門 999078)

結(jié)合點(diǎn)社區(qū)和邊社區(qū)的優(yōu)點(diǎn)，對邊社區(qū)結(jié)構(gòu)，采用網(wǎng)絡(luò)中的局部信息進(jìn)行挖掘，以邊適應(yīng)度和點(diǎn)相似性為基礎(chǔ)，提出了新的社區(qū)挖掘算法.根據(jù)特定的中心性原則設(shè)定一條初始的邊作為種子，為了得到該邊所在的局部社區(qū)的社區(qū)結(jié)構(gòu)，不斷最大化一個適應(yīng)度函數(shù)，并通過基于點(diǎn)相似性的模塊度函數(shù)來進(jìn)行邊界點(diǎn)識別.

社交網(wǎng)絡(luò)； 邊適應(yīng)度； 節(jié)點(diǎn)相似度； 社區(qū)挖掘

18世紀(jì)，瑞典數(shù)學(xué)家歐拉解決了柯尼斯堡問題，圖論由此誕生，歐拉成為圖論的創(chuàng)始人，之后更多的學(xué)者投入到對圖的研究工作中.20世紀(jì)30年代開始，有些學(xué)者開始關(guān)注社會網(wǎng)絡(luò)的研究工作，目前社會網(wǎng)絡(luò)的研究是社會學(xué)領(lǐng)域中最受關(guān)注的研究方向之一[1].

隨著互聯(lián)網(wǎng)的普及，尤其是移動互聯(lián)網(wǎng)的發(fā)展，各種類型的網(wǎng)絡(luò)社交平臺和應(yīng)用相繼出現(xiàn)，并產(chǎn)生了巨大的社會效應(yīng)和經(jīng)濟(jì)效應(yīng)，從傳統(tǒng)的論壇到大熱的博客和微博，再以微信為代表的移動社交應(yīng)用擁有數(shù)億的用戶.在這個信息產(chǎn)生財(cái)富的年代，企業(yè)界尤其是互聯(lián)行業(yè)逐漸重視起社會網(wǎng)絡(luò)的分析,寄希望于挖掘隱藏在社會網(wǎng)絡(luò)背后的信息、知識以及規(guī)律用以推動企業(yè)的發(fā)展[2].

文獻(xiàn)[3]提出了一種指標(biāo)作為社區(qū)結(jié)構(gòu)的評價(jià)標(biāo)準(zhǔn)，構(gòu)建社區(qū)結(jié)構(gòu)的過程則是從給定節(jié)點(diǎn)出發(fā)以最大化指標(biāo)作為社區(qū)挖掘的規(guī)則選取臨近節(jié)點(diǎn)加入社區(qū).文獻(xiàn)[4]定義了局部社區(qū)模塊度，以極大化局部社區(qū)模塊度為聚類規(guī)則，合并滿足聚類規(guī)則的鄰接節(jié)點(diǎn)并迭代運(yùn)算實(shí)現(xiàn)局部社區(qū)挖掘.文獻(xiàn)[5]認(rèn)為核心節(jié)點(diǎn)對網(wǎng)絡(luò)的影響巨大，中心節(jié)點(diǎn)作為網(wǎng)絡(luò)的核心節(jié)點(diǎn)，應(yīng)圍繞其展開社區(qū)挖掘，一方面能夠提高社區(qū)挖掘的精確度，另一方面也更具有現(xiàn)實(shí)意義.文獻(xiàn)[6]定義了社區(qū)和外部節(jié)點(diǎn)的連接相似度作為指標(biāo)，通過迭代運(yùn)算并在每次迭代過程中通過特定的剪枝算法提高精確度縮小運(yùn)算范圍，而迭代終止條件則為不能通過添加任何外部節(jié)點(diǎn)使模塊度M增大.文獻(xiàn)[7]通過網(wǎng)絡(luò)根據(jù)一定的條件構(gòu)建樹，依據(jù)最大流最小割定理從給定節(jié)點(diǎn)出發(fā)對網(wǎng)絡(luò)進(jìn)行分割，從而實(shí)現(xiàn)社區(qū)挖掘.上述文獻(xiàn)都是設(shè)定社區(qū)結(jié)構(gòu)評價(jià)標(biāo)準(zhǔn)，在由初始節(jié)點(diǎn)向外部聚類的過程中，根據(jù)待合并節(jié)點(diǎn)帶來的社區(qū)評價(jià)指標(biāo)增益判斷該節(jié)點(diǎn)是否應(yīng)該納入社區(qū).此方法在聚類過程中往往忽略了待合并節(jié)點(diǎn)與外部鄰接子圖的連接情況，這就使得給定節(jié)點(diǎn)的位置以及評價(jià)指標(biāo)設(shè)定會在很大程度上影響社區(qū)挖掘的結(jié)果，準(zhǔn)確性和穩(wěn)定性往往欠佳.

在此基礎(chǔ)上，筆者提出了一種邊社區(qū)挖掘算法，具有以下優(yōu)點(diǎn)

1) 同時(shí)使用節(jié)點(diǎn)和邊作為研究對象，突破傳統(tǒng)社區(qū)挖掘使用節(jié)點(diǎn)作為出發(fā)點(diǎn)的慣性思維.

2) 提出了一種基于邊適應(yīng)度的聚類規(guī)則以應(yīng)用于社區(qū)挖掘擴(kuò)張過程.

3) 基于中心性原則選擇初始種子邊，有利于提高社區(qū)挖掘的速度并優(yōu)化社區(qū)挖掘的結(jié)果.

4) 通過邊界節(jié)點(diǎn)識別控制社區(qū)挖掘聚類過程，從而減少了由人工輸入?yún)?shù)的不確定而導(dǎo)致的社區(qū)的范圍和大小的差異.

1 問題分析與算法描述

目前比較普遍的社區(qū)挖掘方法將社區(qū)的本質(zhì)視為節(jié)點(diǎn)集合，而在同一個集合內(nèi)部的節(jié)點(diǎn)具有某種意義上的共性[8].首先構(gòu)建某種社區(qū)結(jié)構(gòu)評價(jià)指標(biāo)，比如N-G模塊度[9]，在聚類的過程中根據(jù)最大化指標(biāo)的原則判斷節(jié)點(diǎn)的歸屬，從而最終完成社區(qū)挖掘.此類算法往往都基于較為基礎(chǔ)的特性，其思想對學(xué)者們的研究具有巨大的啟迪意義，很多新算法都會用到其思想，然而基礎(chǔ)算法通常只適用于社區(qū)結(jié)構(gòu)相對明顯的復(fù)雜網(wǎng)絡(luò)，有時(shí)會存在諸如以下的問題：1)初始節(jié)點(diǎn)的位置很大程度上影響社區(qū)挖掘的結(jié)果；2)對于聚類停止的條件難以判斷，即便可以根據(jù)先驗(yàn)知識對評價(jià)指標(biāo)設(shè)置閾值來控制聚類的終止，但是很多情況下難以得到精準(zhǔn)的閾值.

基于上述分析，筆者提出了一種新的社區(qū)挖掘算法.算法分為邊社區(qū)聚類和邊界節(jié)點(diǎn)識別2個階段，一方面根據(jù)邊社區(qū)的特性通過分析社區(qū)鄰域范圍內(nèi)連接緊密度從給定初始種子邊出發(fā)展開社區(qū)挖掘；另一方面在對鄰接邊的聚類過程中，根據(jù)節(jié)點(diǎn)相似性對當(dāng)前的邊界節(jié)點(diǎn)進(jìn)行判斷，從而判斷迭代的終止并在一定范圍內(nèi)控制社區(qū)的規(guī)模完成局部的社區(qū)挖掘；最后重復(fù)上述過程，最終找到整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu).

1.1 選擇初始邊 社區(qū)挖掘算法的結(jié)果往往對種子的位置比較敏感，從不同的初始種子出發(fā)得到的結(jié)果往往不同，所以初始種子的選取至關(guān)重要.有的社區(qū)挖掘算法通過隨機(jī)選擇初始種子，比如文獻(xiàn)[10]通過隨機(jī)算法選擇一個節(jié)點(diǎn)作為種子，所以其結(jié)果具有一定程度的隨機(jī)性.文獻(xiàn)[11]通過選擇網(wǎng)絡(luò)中的最大子團(tuán)作為初始的種子.但是團(tuán)是一種非常嚴(yán)格的定義，在現(xiàn)實(shí)的社會網(wǎng)絡(luò)中，很少能夠觀察到大規(guī)模的團(tuán)，此外，團(tuán)的結(jié)構(gòu)非常不穩(wěn)定，因?yàn)閯h除其中的任意一條邊都會導(dǎo)致團(tuán)被破壞.最重要的是尋找網(wǎng)絡(luò)中的團(tuán)特別是在大規(guī)模網(wǎng)絡(luò)中尋找團(tuán)，計(jì)算復(fù)雜度太高.

采用選取中心性較強(qiáng)的邊作為初始的種子.基于這種考量，采用聚類系數(shù)對邊進(jìn)行排序，從中選取密度較大區(qū)域的邊.

定義1 邊聚類系數(shù)在網(wǎng)絡(luò)中，由節(jié)點(diǎn)i和節(jié)點(diǎn)j構(gòu)成了一條邊，則此條邊的邊聚類系數(shù)定義為

(1)

1.2 邊的適應(yīng)度函數(shù) 對于一個社區(qū)來說，質(zhì)就是整個網(wǎng)絡(luò)的一個子圖.社區(qū)挖掘的算法就是尋找整個網(wǎng)絡(luò)的一個子圖，此子圖內(nèi)部的聯(lián)系盡可能頻繁和緊密，而子圖與外部的聯(lián)系則盡量稀疏.最極端的情況是網(wǎng)絡(luò)的一個子圖，該子圖是個完全圖并且與外部沒有邊.在以節(jié)點(diǎn)為中心的社區(qū)挖掘算法中，通常會定義一個適應(yīng)度函數(shù)作為目標(biāo)函數(shù)，從種子節(jié)點(diǎn)出發(fā)，通過不停地聚類使得目標(biāo)函數(shù)的值持續(xù)增加，根據(jù)貪心算法的思想從候選節(jié)點(diǎn)集選出特定節(jié)點(diǎn).適應(yīng)度表示子圖內(nèi)部與外部的緊密度，增加和刪除成員都會使這個子圖的適應(yīng)度值產(chǎn)生變化.社區(qū)挖掘的過程就是從種子出發(fā)不停地增加可以使適應(yīng)度值變大的成員，直至沒有這樣的新成員可以加入.針對節(jié)點(diǎn)型社區(qū)，Lancichinetti[10]等提出了一種比較典型的適應(yīng)度函數(shù).

定義2 適應(yīng)度 對于一個社區(qū)S，其適應(yīng)度為

(2)

定義3 節(jié)點(diǎn)適應(yīng)度 社區(qū)增加一個新的節(jié)點(diǎn)，其適應(yīng)度fS會發(fā)生改變，定義此改變量為該節(jié)點(diǎn)的節(jié)點(diǎn)適應(yīng)度，把新加入的節(jié)點(diǎn)設(shè)為A，其適應(yīng)度為

(3)

同理可定義邊社區(qū)適應(yīng)度和邊適應(yīng)度.

定義4 邊社區(qū)適應(yīng)度 邊社區(qū)適應(yīng)度為

(4)

定義5 邊適應(yīng)度 候選鄰接邊的引入所帶來的適應(yīng)度的變化量

(5)

1.3 模塊度函數(shù) 判斷當(dāng)前社區(qū)的鄰居節(jié)點(diǎn)是否屬于邊界節(jié)點(diǎn)需要引入模塊度函數(shù)QS[12]，該模塊度函數(shù)基于節(jié)點(diǎn)相似性，是對社區(qū)劃分結(jié)果的一種量化.

定義7 節(jié)點(diǎn)相似性 在網(wǎng)絡(luò)G中，若節(jié)點(diǎn)i與節(jié)點(diǎn)j之間具有連接，則i和j的節(jié)點(diǎn)相似性為

(6)

其中，ω(i,k)表示連接節(jié)點(diǎn)i和k的邊的權(quán)重.本文暫時(shí)只考慮非權(quán)重網(wǎng)絡(luò)，所以ω(i,k)=1.

定義8 模塊度函數(shù) 對于一個網(wǎng)絡(luò)，模塊度為

(7)

(8)

若ΔQS>0，當(dāng)前社區(qū)并入則該邊界節(jié)點(diǎn)；若ΔQS≤0，則認(rèn)為v不屬于社區(qū)C，是C的邊界節(jié)點(diǎn).在社區(qū)挖掘的過程中引入節(jié)點(diǎn)相似性模塊度有效地減小了邊社區(qū)挖掘?qū)τ谳斎雲(yún)?shù)的不同而帶來了差異性，優(yōu)化了社區(qū)挖掘的結(jié)果.

1.4 基于邊社區(qū)的聚合過程以及基于點(diǎn)社區(qū)的邊界點(diǎn)識別 算法的整體流程如下

步驟1 基于邊聚類系數(shù)的邊排序，并按從大到小的順序生成隊(duì)列Q；

步驟2 選取Q中第一條邊作為種子邊加入到社區(qū)C中；

步驟3 從該種子出發(fā)不停的聚集新的邊到社區(qū)，同時(shí)更新隊(duì)列Q；

步驟4 基于模塊度函數(shù)的邊界節(jié)點(diǎn)識別；

步驟5 重復(fù)迭代步驟3和4，直到社區(qū)結(jié)構(gòu)達(dá)到完全穩(wěn)定(步驟5在大部分情況下可以忽略，但是α比較小時(shí)，可以采用步驟5來保證社區(qū)結(jié)構(gòu)的大小，此時(shí)的社區(qū)特性更傾向于模塊度函數(shù))；

步驟6 從Q中選取下一條邊作為新的種子，重復(fù)步驟3，4和5的過程；

步驟7 直到所有的邊都被分配到社區(qū)中為止.

第一部分是對邊的排序，排序算法的時(shí)間復(fù)雜度通常都為O(m log2m)，m為整個網(wǎng)絡(luò)的邊的數(shù)量.第二部分是構(gòu)建局部社區(qū)，時(shí)間復(fù)雜度為O(e2)，e是構(gòu)成局部社區(qū)邊的數(shù)量，而構(gòu)建整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)則是第二部分的重復(fù).從整個算法的角度考慮，時(shí)間復(fù)雜度為O(m log2m+c*e2)，其中c為整個網(wǎng)絡(luò)的社區(qū)個數(shù).最極端的情況是整個網(wǎng)絡(luò)是一個社區(qū)，此情況下的時(shí)間復(fù)雜度為O(m2).針對于絕大部分的真實(shí)網(wǎng)絡(luò)，極端情況一般不會出現(xiàn).

2 實(shí)驗(yàn)與結(jié)果分析

采用虛擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)在特征網(wǎng)絡(luò)上進(jìn)行測試，并與不同方法比較.實(shí)驗(yàn)環(huán)境是一臺Lenovo PC Intel(R) CPU：Core(TM) i3 550 @3.20 GHz，內(nèi)存：2 Gi MB，操作系統(tǒng)：Microsoft Windows 7 64位，程序環(huán)境：Java 1.8.0_45.

2.1 評價(jià)指標(biāo) 很多社區(qū)挖掘算法的過程其實(shí)就是一個聚類的過程，因此針對聚類算法的評價(jià)在很大程度上可以應(yīng)用到對社區(qū)挖掘算法的評價(jià).

聚類純度(Purity)作為評價(jià)聚類效果的指標(biāo)之一，可以說是最為簡單和直觀，其計(jì)算公式如下

(9)

其中，X是聚類結(jié)果中節(jié)點(diǎn)所構(gòu)成的集合，Y是標(biāo)準(zhǔn)答案所構(gòu)成的集合.聚類純度反映了被正確劃分的節(jié)點(diǎn)數(shù)量和所有節(jié)點(diǎn)數(shù)量的比值，經(jīng)過歸一化的處理，取值范圍是0～1，反映了聚類結(jié)果和標(biāo)準(zhǔn)答案的相似程度越來越大直至完全相同.

在聚類純度的定義中，N=|X|.若令N=|Y|，結(jié)算結(jié)果稱為查全率(recall).聚類純度反映的是節(jié)點(diǎn)集中有多少是被正確劃分，查全率則反映標(biāo)準(zhǔn)數(shù)據(jù)集中有多少被正確劃分.

F-measure是兩者的調(diào)和指標(biāo)

(10)

本文實(shí)驗(yàn)部分采用聚類純度，查全率和調(diào)和指標(biāo)3個指標(biāo)作為對結(jié)果的驗(yàn)證.

2.2 計(jì)算機(jī)生成網(wǎng)絡(luò) 基于Newman模型的測試數(shù)據(jù)集GN-benchmark[13]包含128 個節(jié)點(diǎn)，有4個規(guī)模一樣社區(qū),網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度數(shù)K=16.Zin表示節(jié)點(diǎn)的內(nèi)部度，Zout表示節(jié)點(diǎn)的外部度，所有邊Zout+Zin的平均值是16.針對任何一條邊，其存在于某個社區(qū)內(nèi)部的概率Pin=Zin/( Zout+Zin)，存在于2個社區(qū)之間的概率Pout=Zout/(Zout+Zin).

GN-benchmark應(yīng)用極為廣泛，許多社區(qū)挖掘算法都會通過GN-benchmark驗(yàn)證效率和精確度.

隨著Zout的增大，Newman-benchmark的社區(qū)結(jié)構(gòu)越來越不明顯，本文算法在GN-benchmark(Zout=3)時(shí)依然有良好的結(jié)果.

2.3 真實(shí)網(wǎng)絡(luò) 表1是實(shí)驗(yàn)所用到的真實(shí)網(wǎng)絡(luò)的基本數(shù)據(jù)[14-15]，采用的真實(shí)網(wǎng)絡(luò)廣泛用于社區(qū)挖掘算法的測試.

表1 真實(shí)屬性數(shù)據(jù)的測試網(wǎng)絡(luò)

以美國高校橄欖球聯(lián)賽網(wǎng)和美國政治博客網(wǎng)為例，分別運(yùn)用本文算法進(jìn)行社區(qū)挖掘，求得聚類純度p，查全率r以及調(diào)和指標(biāo)F的各項(xiàng)數(shù)值.對比其他3種算法，圖1和圖2是各算法的在評價(jià)指標(biāo)上的表現(xiàn).綜合3種指標(biāo)可以發(fā)現(xiàn)：文獻(xiàn)[3]和文獻(xiàn)[16]的算法在聚類純度和查全率相差比較大；文獻(xiàn)[5]的算法聚類純度和調(diào)和指標(biāo)2項(xiàng)指標(biāo)差距不大，但查全率較低.本文算法則同時(shí)具有較高的聚類純度和查全率，從而使得F值在維持在較高水平.此外，針對2個數(shù)據(jù)集的劃分結(jié)果都達(dá)到了很好的模塊度值，分別為0.371和0.389.實(shí)驗(yàn)結(jié)果證明了本文算法在社區(qū)挖掘上的準(zhǔn)確性和有效性.

綜合針對計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)可以得出：針對不同的數(shù)據(jù)集，邊適應(yīng)度和節(jié)點(diǎn)相似性的社區(qū)挖掘算法在聚類純度、查全率方面相比其它算法都有一定程度的提高.盡管無法在聚類純度、查全率2項(xiàng)評價(jià)指標(biāo)上同時(shí)達(dá)到最優(yōu)，但是在結(jié)果中，這2項(xiàng)評價(jià)指標(biāo)都維持在較高水平，在整體上體現(xiàn)出了優(yōu)勢，表2中的綜合調(diào)和指標(biāo)也充分驗(yàn)證了此結(jié)論.

表2 4種算法中的適應(yīng)度函數(shù)值

3 結(jié)束語

結(jié)合點(diǎn)社區(qū)和邊社區(qū)的優(yōu)點(diǎn)提出了基于邊適應(yīng)度和點(diǎn)相似性的挖掘算法, 通過網(wǎng)絡(luò)中的局部信息展開社區(qū)挖掘，并以邊界節(jié)點(diǎn)識別達(dá)到控制社區(qū)規(guī)模和范圍的目的，從而解決已有方法對初始節(jié)點(diǎn)敏感，終止條件難以獲得等問題.在計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)分布進(jìn)行實(shí)驗(yàn)，對實(shí)驗(yàn)結(jié)果的分析證明了針對不同的網(wǎng)絡(luò)環(huán)境，本文提出的基于邊界節(jié)點(diǎn)識別的社區(qū)挖掘算法具有較高的穩(wěn)定性和準(zhǔn)確率，能夠較為真實(shí)的對網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)進(jìn)行分析.如何將社區(qū)挖掘算法進(jìn)一步應(yīng)用于大規(guī)模的含權(quán)網(wǎng)絡(luò)以及動態(tài)明序網(wǎng)絡(luò)，將是下一步學(xué)習(xí)研究工作的重點(diǎn).

[1] Goltsev A V, Dorogovtsev S N, Oliveira J G, et al. Localization and spreading of diseases in complex networks[J]. Physical Review Letters, 2012, 109(12):2 733-2 737.

[2] Xie J, Szymanski B K. LabelRank: A stabilized label propagation algorithm for community detection in networks: proceedings of the Network Science Workshop (NSW) 2013,West Point, April 29-May 1, 2013[C].[S.l.]:IEEE,138-143.

[3] Clauset A. Finding local community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2005, 72(2):254-271.

[4] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2003, 101(9):2 658-2 663.

[5] Chen Q, Wu T T, Fang M. Detecting local community structures in complex networks based on local degree central nodes[J]. Physica A Statistical Mechanics & Its Applications, 2013, 392(3):529-537.

[6] Wu Y J, Huang H, Hao Z F, et al. Local community detection using link similarity[J]. Journal of Computer Science & Technology, 2012, 27(6):1 261-1 268.

[7] Qi X, Tang W, Wu Y, et al. Optimal local community detection in social networks based on density drop of subgraphs[J]. Pattern Recognition Letters, 2014, 36(1):46-53.

[8] Meo P D, Ferrara E, Fiumara G, et al. Mixing local and global information for community detection in large networks[J]. Journal of Computer & System Sciences, 2014, 80(1):72-87.

[9] Newman M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23):8 577-8 582.

[10] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2008, 11(3):19-44.

[11] Lee C, Reid F, Mcdaid A, et al. Detecting highly overlapping community structure by greedy clique expansion: proceeding of the International Conference on Knowledge Discovery and Data Mining, Bellevue, Washington, July 24-28, 2010[C]. [S.l.] :[s.n.], 2010.

[12] Feng Z, Xu X, Yuruk N, et al. A novel similarity-based modularity function for graph partitioning:proceeding of the International Conference on Data Warehousing and Knowledge Discovery, Regensburg, September 3-7, 2007[C]. Heidelberg: Springer, 2007.

[13] Newman M E, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2):26 113-26 128.

[14] Institute of Web Science and Technologies at the University of Koblenz-Landau. US airports network dataset-KONECT [EB/OL]. (2013-11-08). [2016-02-20]. http://konect.uni-koblenz.de/networks/opsahl-usairport.

[15] Institute of Web Science and Technologies at the University of Koblenz-Landau. US power grid network dataset-KONECT [EB/OL]. (2013-11-08). [2016-02-20]. http://konect.uni-koblenz.de/networks/opsahl-powergrid.

[16] Luo F, Wang J Z, Promislow E. Exploring local community structures in large networks[J]. Web Intelligence & Agent Systems, 2008, 6(4):387-400.

Algorithm for Community Detection in Social Networks

Yang Cheng1, Du Wencai1,2

(1. College of Information Science and Technology, Hainan University, Haikou 570228, China;2. Faculty of International Tourism and Management, City University of Macau, Macau 999078, China)

In our report, a novel algorithm for discovering local communities in networks was proposed, which was based on fitness and point similarity, combined the advantages of point community and edge community, and mininged the edge community structure using local information. According to the specific central principle, an original edge was used as a seed. In order to obtain the community structure the local community, the fitness function was constantly maximized, and was used to obtain a local edge community. The modular degree function based on point similarity was used for the boundary node identification.

social networks; edge fitness; node similarity; communities detecting

2016-03-11

楊成(1988-)，男，安徽六安人，海南大學(xué)2013級碩士研究生，研究方向：數(shù)據(jù)挖掘，移動社交網(wǎng)絡(luò)等，E-mail：bityangc@qq.com

杜文才(1953- )，男，江蘇徐州人，博導(dǎo)，教授，研究方向：信息與通信工程,物聯(lián)網(wǎng)等，E-mail：wencai@hainu.edu.cn

1004-1729(2016)03-0237-06

TP 391

A DOl：10.15886/j.cnki.hdxbzkb.2016.0036