楊 成，杜文才,2

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

?

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

楊 成1，杜文才1,2

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

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

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

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

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

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

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

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

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

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

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

1 問(wèn)題分析與算法描述

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

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

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

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

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

(1)

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

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

(2)

定義3 節(jié)點(diǎn)適應(yīng)度 社區(qū)增加一個(gè)新的節(jié)點(diǎn)，其適應(yīng)度f(wàn)S會(huì)發(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)度 候選鄰接邊的引入所帶來(lái)的適應(yīng)度的變化量

(5)

1.3 模塊度函數(shù) 判斷當(dāng)前社區(qū)的鄰居節(jié)點(diǎn)是否屬于邊界節(jié)點(diǎn)需要引入模塊度函數(shù)QS[12]，該模塊度函數(shù)基于節(jié)點(diǎn)相似性，是對(duì)社區(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ù) 對(duì)于一個(gè)網(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ū)挖掘的過(guò)程中引入節(jié)點(diǎn)相似性模塊度有效地減小了邊社區(qū)挖掘?qū)τ谳斎雲(yún)?shù)的不同而帶來(lái)了差異性，優(yōu)化了社區(qū)挖掘的結(jié)果.

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

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

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

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

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

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

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

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

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

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

采用虛擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)在特征網(wǎng)絡(luò)上進(jìn)行測(cè)試，并與不同方法比較.實(shí)驗(yàn)環(huán)境是一臺(tái)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 評(píng)價(jià)指標(biāo) 很多社區(qū)挖掘算法的過(guò)程其實(shí)就是一個(gè)聚類(lèi)的過(guò)程，因此針對(duì)聚類(lèi)算法的評(píng)價(jià)在很大程度上可以應(yīng)用到對(duì)社區(qū)挖掘算法的評(píng)價(jià).

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

(9)

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

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

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

(10)

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

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

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

隨著Zout的增大，Newman-benchmark的社區(qū)結(jié)構(gòu)越來(lái)越不明顯，本文算法在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ū)挖掘算法的測(cè)試.

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

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

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

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

3 結(jié)束語(yǔ)

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