基于LFM算法的改進(jìn)社區(qū)發(fā)現(xiàn)算法

肖永嘉，朱征宇

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400000）

基于LFM算法的改進(jìn)社區(qū)發(fā)現(xiàn)算法

肖永嘉，朱征宇

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400000）

由于能夠反映網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)，重疊社區(qū)劃分在各領(lǐng)域有著越來(lái)越重要的作用。LFM算法是其中較為流行的一種社區(qū)劃分方法。但其存在一些缺點(diǎn)，例如在網(wǎng)絡(luò)變得龐大和復(fù)雜的時(shí)候，時(shí)間消耗會(huì)變得巨大。為了解決這一問(wèn)題，提出核心區(qū)域的概念，并藉此對(duì)LMF算法進(jìn)行改進(jìn)。最后通過(guò)實(shí)驗(yàn)驗(yàn)證，發(fā)現(xiàn)該算法能夠減小時(shí)間消耗，同時(shí)能夠得到更為可靠的社區(qū)劃分。

重疊社區(qū)劃分；LFM；核心區(qū)域

0 引言

現(xiàn)實(shí)世界的很多復(fù)雜的相互作用的系統(tǒng)往往被抽象成網(wǎng)絡(luò)來(lái)表示，用來(lái)讓人們更好地理解復(fù)雜系統(tǒng)的全部特性，更好地應(yīng)對(duì)現(xiàn)實(shí)的變化。例如互聯(lián)網(wǎng)環(huán)境下的社交網(wǎng)絡(luò)、電子商務(wù)；流行病傳播學(xué)中的疾病預(yù)防控制過(guò)程，生物學(xué)網(wǎng)絡(luò)中蛋白質(zhì)組織構(gòu)造等。隨著人們對(duì)復(fù)雜網(wǎng)絡(luò)的研究日益深入，社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)存在的普遍特征，由于能有效地揭示網(wǎng)絡(luò)系統(tǒng)中群體的共性規(guī)律，是解決復(fù)雜系統(tǒng)的基礎(chǔ)，又能推進(jìn)相關(guān)應(yīng)用的發(fā)展，已經(jīng)成為網(wǎng)絡(luò)研究的一個(gè)重要分支。而重疊社區(qū)的發(fā)現(xiàn)可以更為準(zhǔn)確地理解網(wǎng)絡(luò)內(nèi)部的拓?fù)浣Y(jié)構(gòu)信息，在近些年的研究中得到了越來(lái)越多的關(guān)注。

1 相關(guān)工作

社區(qū)并沒(méi)有一個(gè)嚴(yán)格意義上的定義，較為廣泛接受的是Newman和Gievan提出的“同一社區(qū)內(nèi)的點(diǎn)與點(diǎn)之間的鏈接更緊密，不同社區(qū)之間的點(diǎn)的鏈接更稀疏[1，2]。”重疊社區(qū)即與其他社區(qū)擁有重疊節(jié)點(diǎn)的社區(qū)。如圖1中G1，G2擁有重疊的節(jié)點(diǎn)A1，A2因此G1，G2都是重疊社區(qū)。

基于局部?jī)?yōu)化的社區(qū)發(fā)現(xiàn)方法可以分為四類(lèi)：局部拓展優(yōu)化方法，從給定的初始節(jié)點(diǎn)逐步合并引起最大的社區(qū)度量增量的近鄰節(jié)點(diǎn)，從而進(jìn)行局部擴(kuò)展優(yōu)化，各方法的主要差異在于對(duì)局部社區(qū)的度量不同。例如子圖度量?jī)?yōu)化的局部社區(qū)擴(kuò)展算法LWP[3]，L-殼擴(kuò)展的社區(qū)發(fā)現(xiàn)算法，LMD算法[4]，LFM算法[5]等；派系過(guò)濾方法CPM[6，12]其定義了一種嚴(yán)格的社區(qū)結(jié)構(gòu)，并允許社區(qū)間存在重疊。為進(jìn)一步分析網(wǎng)絡(luò)社區(qū)的重疊特性基于子圖強(qiáng)度將CPM算法擴(kuò)展到加權(quán)網(wǎng)絡(luò)，提出了一種加權(quán)派系過(guò)濾算法CPMw[7]，為了進(jìn)一步有效應(yīng)用到大規(guī)模的加權(quán)和非加權(quán)社交網(wǎng)絡(luò)提出了一種快速派系過(guò)濾算法SCP標(biāo)簽傳播法（LPA）[8]基于單個(gè)標(biāo)簽傳播，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)被確定地劃分至單一社區(qū)中，忽略了社區(qū)結(jié)構(gòu)的重疊特性，為此拓展出多標(biāo)簽傳播算法copra[9]；以及局部邊聚類(lèi)優(yōu)化方法，菲利波·拉迪奇（Filippo Radicchi）等人定義了一種邊聚類(lèi)系數(shù)，并提出了一種社區(qū)發(fā)現(xiàn)的局部方法[10]，Ahn等人提出了一種基于連邊局部相似性的邊社區(qū)發(fā)現(xiàn)方法來(lái)檢測(cè)社區(qū)的重疊性和層次性[11]，潘磊等人提出另一種局部的邊社區(qū)發(fā)現(xiàn)方法等。

本文的主要工作是針對(duì)LFM算法在時(shí)間復(fù)雜度上的明顯不足進(jìn)行改進(jìn)，得到了較原算法在時(shí)間，評(píng)價(jià)效果都更為出色的改進(jìn)算法。

圖1

2 算法介紹

2.1 相關(guān)定義

網(wǎng)絡(luò)可以通過(guò)抽象成圖G=（V，E）來(lái)表示，其中V= {v1，v2，v3，…}表示節(jié)點(diǎn)的集合，E={e1，e2，e3，…}表示邊的集合。

LFM算法中的適應(yīng)度f(wàn)G的定義如下：

其中kGin和kGout分別指的是圖G中內(nèi)部和外部度數(shù)的總和，∝是一個(gè)正實(shí)數(shù)參數(shù)用來(lái)控制社區(qū)的規(guī)模。較大的∝值會(huì)產(chǎn)生較小的社區(qū)，較小的∝值會(huì)導(dǎo)致社區(qū)較大。此外原算法的作者對(duì)∝的取值進(jìn)行了分析：在多數(shù)情況下當(dāng)∝<0.5時(shí)整個(gè)網(wǎng)絡(luò)被劃分為一個(gè)社區(qū)，當(dāng)∝>2時(shí)，每個(gè)節(jié)點(diǎn)都是一個(gè)單獨(dú)的社區(qū)。同時(shí)對(duì)本文實(shí)驗(yàn)包含的三個(gè)測(cè)試集上時(shí)的實(shí)驗(yàn)表明：∝取值為0.9時(shí)效果最好。

適應(yīng)度函數(shù)的定義如下：

其中G+{A}表示G中包含A的子圖，G-{A}則表示G中不包含A的子圖。如果fGA>0則表明將節(jié)點(diǎn)A加入社區(qū)G有益于提高社區(qū)質(zhì)量，則將節(jié)點(diǎn)A加入社區(qū)G。

2.2 LFM算法的思想

首先引入包含頂點(diǎn)A的自然社區(qū)的獲取過(guò)程：

假設(shè)已有一個(gè)包含節(jié)點(diǎn)A的子圖G，

①對(duì)G的所有鄰接點(diǎn)循環(huán)操作，計(jì)算每個(gè)鄰接點(diǎn)對(duì)G的適應(yīng)度函數(shù)值；

②將適應(yīng)度值最大的點(diǎn)加入子圖G形成更大的子圖G'；

③重新計(jì)算子圖G'中的所有點(diǎn)的適應(yīng)度值；

④如果其中一個(gè)節(jié)點(diǎn)的適應(yīng)度值變?yōu)樨?fù)數(shù)，則將該節(jié)點(diǎn)從子圖G'中剔除，形成新的子圖G"；

⑤如果發(fā)生④，則從③開(kāi)始重復(fù)，否則，以子圖G"從①開(kāi)始重復(fù)，直到第①步中所有鄰接點(diǎn)對(duì)子圖G的適應(yīng)度值都為負(fù)數(shù)時(shí)結(jié)束。

對(duì)于LFM算法的執(zhí)行過(guò)程就可以概括為以下幾步：

①隨機(jī)選取一個(gè)節(jié)點(diǎn)A；

②探測(cè)獲取包含節(jié)點(diǎn)A的自然社區(qū)；

③隨機(jī)選取一個(gè)為被劃分至任意社區(qū)的節(jié)點(diǎn)B；

④探測(cè)獲取包含節(jié)點(diǎn)B的自然社區(qū)，不管其臨節(jié)點(diǎn)是否屬于其他社區(qū)；

⑤從③開(kāi)始重復(fù)，直至所有的節(jié)點(diǎn)都被至少分配在一個(gè)社區(qū)。

算法存在的問(wèn)題有：

①在獲取自然社區(qū)時(shí)會(huì)有節(jié)點(diǎn)反復(fù)加入社區(qū)然后被剔除的死循環(huán)現(xiàn)象；

②在獲取自然社區(qū)時(shí)每加入一個(gè)新的節(jié)點(diǎn)都要重新計(jì)算一下社區(qū)內(nèi)所有節(jié)點(diǎn)針對(duì)該社區(qū)的適應(yīng)度值，導(dǎo)致計(jì)算量巨大。

針對(duì)上述兩條缺點(diǎn)，我們采取如下措施：

①在自然社區(qū)發(fā)現(xiàn)過(guò)程中，對(duì)現(xiàn)有社區(qū)G的所有鄰接點(diǎn)進(jìn)行區(qū)別標(biāo)記，如果某個(gè)鄰接點(diǎn)曾被加入臨時(shí)社區(qū)則在自然社區(qū)的獲取過(guò)程中不再將其加入臨時(shí)社區(qū)。

②引入核心區(qū)域的概念，并規(guī)定在獲取自然社區(qū)的過(guò)程中，如果節(jié)點(diǎn)A屬于現(xiàn)有社區(qū)的核心區(qū)域則則認(rèn)為該節(jié)點(diǎn)將確定屬于現(xiàn)有社區(qū)，不再計(jì)算其適應(yīng)度值。

這樣就解決了原算法中出現(xiàn)的問(wèn)題，極大地提高了算法速度和劃分社區(qū)的質(zhì)量。

2.3 改進(jìn)算法思想

我們定義：如果某一個(gè)節(jié)點(diǎn)A在只跟當(dāng)前社區(qū)G內(nèi)的節(jié)點(diǎn)有邊相連，則該節(jié)點(diǎn)屬于當(dāng)前社區(qū)的核心區(qū)域。如上圖2所示。

根據(jù)適應(yīng)度值的定義：

我們可以得到表達(dá)式：

因此我們給出結(jié)論如果節(jié)點(diǎn)A屬于臨時(shí)社區(qū)G的核心區(qū)域，則將節(jié)點(diǎn)A加入社區(qū)G有益于社區(qū)劃分質(zhì)量的提高。

圖2

此外，我們對(duì)臨時(shí)社區(qū)的所有鄰接點(diǎn)增加一個(gè)標(biāo)記位，用來(lái)表示該鄰接點(diǎn)是否被訪問(wèn)過(guò)即計(jì)算過(guò)其對(duì)社區(qū)G的適應(yīng)度值，在拓展過(guò)程中，如果鄰接點(diǎn)中出現(xiàn)了已被訪問(wèn)過(guò)的節(jié)點(diǎn)，則說(shuō)明該節(jié)點(diǎn)在臨時(shí)社區(qū)G’重新計(jì)算適應(yīng)度值的過(guò)程中不再有益于提高社區(qū)劃分質(zhì)量，我們認(rèn)為該節(jié)點(diǎn)將永遠(yuǎn)不利于提高社區(qū)劃分質(zhì)量。因此我們?cè)谛滦纬傻纳鐓^(qū)G”的拓展過(guò)程中將跳過(guò)該節(jié)點(diǎn)，不再重復(fù)計(jì)算其對(duì)社區(qū)的適應(yīng)度值。

改進(jìn)后的包含節(jié)點(diǎn)A的自然社區(qū)獲取過(guò)程如下：

假設(shè)已有一個(gè)包含節(jié)點(diǎn)A的子圖G，

①對(duì)G的所有鄰接點(diǎn)進(jìn)行判斷，如果屬于當(dāng)前社區(qū)的核心區(qū)域，則對(duì)其標(biāo)記并直接加入當(dāng)前社區(qū)，如果不是進(jìn)入②；

②對(duì)G的非核心區(qū)域且未訪問(wèn)過(guò)的鄰接點(diǎn)循環(huán)操作，計(jì)算每個(gè)鄰接點(diǎn)對(duì)G的適應(yīng)度函數(shù)值；

③將適應(yīng)度值最大的點(diǎn)加入子圖G形成子圖G'，并將其標(biāo)記為已訪問(wèn);

④重新計(jì)算子圖G'中的所有非核心區(qū)域的點(diǎn)的適應(yīng)度值；

⑤如果其中一個(gè)節(jié)點(diǎn)的適應(yīng)度值變?yōu)樨?fù)數(shù)，則將該節(jié)點(diǎn)從子圖G'中剔除，并將其標(biāo)記為已訪問(wèn)過(guò)，形成新的子圖G"；

⑥如果發(fā)生⑤，則從②開(kāi)始重復(fù)，否則，以子圖G"從①開(kāi)始重復(fù)。

直到所有鄰接點(diǎn)對(duì)子圖G的適應(yīng)度值都為負(fù)數(shù)時(shí)結(jié)束。

3 實(shí)驗(yàn)

本章通過(guò)實(shí)驗(yàn)驗(yàn)證我們提出的改進(jìn)算法的性能，我們將其與LFM原算法以及其他幾種較有代表性的算法進(jìn)行比較，分別是CPM，COPRA。其中為了使這兩個(gè)算法效果最佳，在CPM算法中我們選取k取值為3，COPRA算法中v的取值為3。而在LFM算法及我們的改進(jìn)算法中，我們參考LFM作者的分析取效果最佳的0.9。

3.1 實(shí)驗(yàn)環(huán)境

處理器Intel core i5-5200U 2.20GHz，內(nèi)存4G，硬盤(pán)500G，系統(tǒng)為Windows7 x64，編程語(yǔ)言為Java，開(kāi)發(fā)環(huán)境為Eclipse4.4。

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)包括真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集兩大類(lèi)。

五組真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的參數(shù)如下，其中karate網(wǎng)絡(luò)為W.W.Zachary描述的20世紀(jì)70年代一所美國(guó)大學(xué)的空手道俱樂(lè)部中34名成員之間的友誼關(guān)系圖，dolphin網(wǎng)絡(luò)為David Lusseau描述的新西蘭神奇峽灣一個(gè)擁有62只海豚族群的關(guān)系網(wǎng)絡(luò)，American football網(wǎng)絡(luò)為Girvan等人描述的2000年秋季常規(guī)賽IA級(jí)別的115只球隊(duì)比賽的關(guān)系網(wǎng)絡(luò)，email網(wǎng)絡(luò)為具有1133個(gè)節(jié)點(diǎn)和5451條邊的網(wǎng)絡(luò)，blogs網(wǎng)絡(luò)為Adamic和Glance在2005年記錄的關(guān)于美國(guó)政治的3982個(gè)博客之間超鏈接的有向網(wǎng)絡(luò)。

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

人工合成網(wǎng)絡(luò)數(shù)據(jù)集的生成我們采用LFR（Lancichinetti-Fortunato-Radicchi）基準(zhǔn)程序來(lái)構(gòu)造人工網(wǎng)絡(luò)。根據(jù)Santo Fortunat在個(gè)人網(wǎng)站上提供的源程序，運(yùn)行時(shí)的需要按如下格式輸入?yún)?shù)：benchmark-N-kmaxk-maxc-on-mu-om。

其中N表示節(jié)點(diǎn)數(shù)目，k表示網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度；kmax表示節(jié)點(diǎn)的最大度；minc表示最小社區(qū)包含的節(jié)點(diǎn)的個(gè)數(shù)；maxc表示最大社區(qū)包含的節(jié)點(diǎn)的個(gè)數(shù)；on表示重疊節(jié)點(diǎn)的個(gè)數(shù)，om表示每個(gè)重疊節(jié)點(diǎn)屬于幾個(gè)社區(qū)；mu表示用來(lái)表示社區(qū)的混亂程度，mu越大社區(qū)發(fā)現(xiàn)的難度越大。

3.3 評(píng)價(jià)指標(biāo)Qov和NM I

對(duì)于真實(shí)網(wǎng)絡(luò)，我們使用模塊度Qov對(duì)社區(qū)的劃分質(zhì)量進(jìn)行判斷，模塊度的提出基于一個(gè)簡(jiǎn)單地理念：如果一個(gè)子圖是社區(qū)那么它的內(nèi)部節(jié)點(diǎn)之間的連邊數(shù)一定比隨機(jī)生成的自圖的內(nèi)部節(jié)點(diǎn)的連變數(shù)多。模塊度的相關(guān)概念可以參考文章，這里只給出公式。

對(duì)于由LFR基準(zhǔn)程序生成的人工合成網(wǎng)絡(luò)，在生成網(wǎng)絡(luò)的同時(shí)程序會(huì)給出參考社區(qū)劃分，因此我們用標(biāo)準(zhǔn)化互信息度NMI（Normalized Mutual Information）來(lái)評(píng)價(jià)各種算法得到的社區(qū)劃分與已知社區(qū)劃分的相似程度。如果NMI=1則表示算法得到的結(jié)果與已知的社區(qū)劃分完全一致。

3.4 人工合成網(wǎng)絡(luò)上的時(shí)間對(duì)比

為了驗(yàn)證我們的改進(jìn)算法與原算法在時(shí)間上的改進(jìn)，我們使用LFR基準(zhǔn)程序生成兩組人工合成網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目分別從1000-10000，10000-100000.為了降低整個(gè)實(shí)驗(yàn)過(guò)程的總耗時(shí)，我們將mu置為0.1。

其他參數(shù)取值分別為k=10，maxk=50，minc=10，maxc=50，on=100，om=0.1。

圖3

可以看到我們的改進(jìn)算法在網(wǎng)絡(luò)規(guī)模相對(duì)較?。ü?jié)點(diǎn)數(shù)<10000）時(shí)與原算法相比具有顯著提升，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加我們的算法與原算法在時(shí)間消耗上的差距相對(duì)變小，主要原因是網(wǎng)絡(luò)規(guī)模的劇增導(dǎo)致社區(qū)的鄰接點(diǎn)數(shù)目劇增。導(dǎo)致在標(biāo)記鄰接點(diǎn)和判斷是否為核心區(qū)域時(shí)消耗大量的時(shí)間。

3.5 現(xiàn)實(shí)網(wǎng)絡(luò)效果Qov對(duì)比

可以看到我們的改進(jìn)算法在Karate，football，email三個(gè)網(wǎng)絡(luò)中效果優(yōu)于原算法，在dolphins網(wǎng)絡(luò)中持平，在blogs網(wǎng)絡(luò)中效果比原算法差；與CPM算法相比我們的改進(jìn)算法在Karate，football和blogs網(wǎng)絡(luò)中效果較好，在dolphins和email網(wǎng)絡(luò)中效果較差；與Copra算法相比，我們的改進(jìn)算法在karate，email和blogs網(wǎng)絡(luò)中效果較好，在dolphins和football網(wǎng)絡(luò)中效果較差。

表2

3.6 人工合成網(wǎng)絡(luò)效果對(duì)比

為了比較各算法在不同類(lèi)型網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)質(zhì)量，我們根據(jù)網(wǎng)絡(luò)規(guī)模N及每個(gè)重疊節(jié)點(diǎn)所屬的社區(qū)個(gè)數(shù)om的不同，生成了四組由大小網(wǎng)絡(luò)和大小社區(qū)組合而成具有不同特征的人工網(wǎng)絡(luò)。為了降低計(jì)算復(fù)雜度，我們將影響社區(qū)復(fù)雜程度的參數(shù)mu固定為0.1。其他參數(shù)如下圖所示。

得到的各組數(shù)據(jù)分別如下所示：

表3

我們可以看到在網(wǎng)絡(luò)規(guī)模較小的情況下（第1，2組數(shù)據(jù)），我們的改進(jìn)算法的社區(qū)劃分質(zhì)量高于其他三種算法；在網(wǎng)絡(luò)規(guī)模較大，同時(shí)社區(qū)規(guī)模較大的情況下的情況下（第3組數(shù)據(jù)）我們的改進(jìn)算法的社區(qū)劃分質(zhì)量也高于其他三種算法；只有在網(wǎng)絡(luò)規(guī)模較大且社區(qū)規(guī)模較小的情況下，我們的改進(jìn)算法的社區(qū)劃分質(zhì)量遜色于CPM算法，但仍然高于原算法和COPRA算法。

4 結(jié)語(yǔ)

本文針對(duì)LFM算法的不足提出了相對(duì)應(yīng)的改進(jìn)方案，結(jié)果表明在時(shí)間和社區(qū)劃分質(zhì)量上相較于原算法都有了顯著地提升。但是無(wú)論原算法還是我們的改進(jìn)算法都存在社區(qū)劃分不穩(wěn)定的缺點(diǎn)，如何提高其穩(wěn)定性有待進(jìn)一步的工作。

[1]M.E.J.Newman And M.Girvan.Finding and Evaluating Community Structure In Networks.Physical Review E，69:026113，2004.

[2]V.Nicosia，G.Mangioni，V.Carchiolo and M.Malgeri.Extending the Definition Of Modularity To Directed Graphs With Overlapping Communities，Arxiv:0801.1647v4[Physics.Data-an]24 Mar 2009

[3]Luo F，Wang JZ，Promislow E.Exploring Local Community Structures In Large Networks.Web Intelligence and Agent System，2008，6（4）:387-400.

[4]Chen Q，Wu T T，F(xiàn)ang M.Detecting Local Community Structures In Complex Networks Based on Local Degree Central Nodes.Physica A-statistical Mechanics And Its Applications,2013,392(3):529-37.

[5]Lancichinetti A,Fortunato S,KertéSz J.Detecting The Overlapping and Hierarchical Ommunity Structure in Complex Networks.New Journal of Physics,2009,11（3）：033015.

[6]Palla G,Derenyi I,Farkas IEt Al.Uncovering the Overlapping Community Structure of Complex Networks in Nature And Society. Nature,2005,435（7043）：814-8.

[7]Farkas I,Bel D,Palla G Et A l.Weighted Network Modules.New Journal Of Physics,2007,9（6）：180.

[8]Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks.Physical Review E,Statistical,Nonlinear,and SoftMatter Physics,2007,76（3 Pt2）：036106.

[9]Gregory S.Finding Overlapping Communities In Networks By Label Propagation.New Journal of Physics,2010,12（10）：103018.

[10]Radicchi F,Castellano C,Cecconi F Et Al.Defining and Identifying Communities in Networks.Proceedings of the National Academy of Sciences of the United States of America,2004,101（9）：2658-2663.

[11]Symeon Papadopoulos As,Athena Vakali,Yiannis Kompatsiaris Et Al.Bridge Bounding:a Local Approach for Efficient Community Discovery In Complex Networks.Physics And Society,2009.

[12]DeréNyi I,Palla G,Vicsek T.Clique Percolation In Random Networks.Physical Review Letters,2005,94（16）：160202.

Im proved Algorithm of Overlapping Community Detection Based on LFM

XIAO Yong-jia，ZHU Zheng-yu

（College of Computer Science,Chongqing University，Chongqing 400000）

Overlapping community detection has becomemore and more important since it can reveals the inner structure of networks.LFM algorithm is one of themost popular way to detect communities in complex networks,however the algorithm itself has some weaknesses,such as large time consumption when the network become large and complex.To overcome these problems,based on LFM,presents an improved LFM algorithm(M-LFM)which proposes a definition of core area and apply it into the process of community detection with LFM. Experiments on real networks and artificial networks show that the improved algorithm can decrease time consumption and get better result than LFM.

肖永嘉（1991-），男，山東臨沂人，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)中重疊社區(qū)發(fā)現(xiàn)算法研究

2017-03-15

2017-05-10

1007-1423（2017）14-0021-06

10.3969/j.issn.1007-1423.2017.14.004

朱征宇（1959-），男，安徽馬鞍山人，博士生導(dǎo)師，研究生方向?yàn)閿?shù)據(jù)挖掘技術(shù)、互聯(lián)網(wǎng)技術(shù)與檢索方法、電子商務(wù)網(wǎng)站與應(yīng)用、軟件工程方法與應(yīng)用、智能交通

Overlapping Community Detection;LFM;Core Area