基于社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究

毋建軍

(北京政法職業(yè)學(xué)院 信息技術(shù)系, 北京 102628)

?

基于社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究

毋建軍

(北京政法職業(yè)學(xué)院 信息技術(shù)系, 北京 102628)

摘要：隨著社交網(wǎng)絡(luò)的快速發(fā)展及應(yīng)用,圍繞社交網(wǎng)絡(luò)用戶及信息交互自發(fā)形成的網(wǎng)絡(luò)社區(qū)已經(jīng)成為當(dāng)前社交網(wǎng)絡(luò)研究領(lǐng)域的重要分支，并取得了許多研究進(jìn)展及成果，但仍然存在許多挑戰(zhàn)及問題。本文從網(wǎng)絡(luò)社區(qū)研究的網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)信息、時(shí)間三個(gè)重要因素考慮，在網(wǎng)絡(luò)社區(qū)的定義、特性的基礎(chǔ)上，分類、對(duì)比了典型的社區(qū)發(fā)現(xiàn)模型、算法及社區(qū)劃分評(píng)價(jià)方法，并對(duì)其存在的問題及未來發(fā)展方向進(jìn)行了分析探討。

關(guān)鍵詞：社交網(wǎng)絡(luò)；社區(qū)算法；動(dòng)態(tài)社區(qū)；SNS分析

0引言

隨著Twitter、Facebook、新浪微博、人人網(wǎng)、微信等社交網(wǎng)絡(luò)的廣泛應(yīng)用，社交網(wǎng)絡(luò)大數(shù)據(jù)集合孕育而生，在大數(shù)據(jù)基礎(chǔ)上，不同領(lǐng)域、學(xué)科的研究人員基于社交網(wǎng)絡(luò)的鏈接結(jié)構(gòu)、用戶交互行為、信息擴(kuò)散傳播等方面，進(jìn)行了社交網(wǎng)絡(luò)用戶關(guān)系挖掘、信息擴(kuò)散傳播的機(jī)制分析、網(wǎng)絡(luò)結(jié)構(gòu)變遷、新型(網(wǎng)絡(luò))虛擬關(guān)系演化等基礎(chǔ)性問題的研究。

早期關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)的研究主要著重于小規(guī)模的網(wǎng)絡(luò)(如問卷調(diào)查、美國大學(xué)生足球網(wǎng)絡(luò)等)。但近年來隨著社交網(wǎng)絡(luò)規(guī)模及應(yīng)用的急劇發(fā)展，關(guān)于復(fù)雜網(wǎng)絡(luò)的研究及數(shù)據(jù)集的采樣規(guī)模，已遞增為百萬或千萬、甚至上億。社交網(wǎng)絡(luò)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)研究中一個(gè)新興的研究領(lǐng)域。Watts等[1]提出的小世界模型,描述網(wǎng)絡(luò)具有集聚、較小平均路徑長度等特性。Barahasi等驗(yàn)證了度分布服從冪律分布p(k)=ck-r的復(fù)雜網(wǎng)絡(luò)[2,3]，具有“小世界”、 “聚集性”、“無標(biāo)度”等特性。

在社交網(wǎng)絡(luò)中，人們之間是如何進(jìn)行交互、傳遞信息、它們之間的結(jié)構(gòu)如何形成、遷移；哪些用戶具有相似的愛好及興趣、哪些用戶在社交網(wǎng)絡(luò)信息傳播中具有重要的作用及天然優(yōu)勢；它們之間是否會(huì)自發(fā)的形成具有直接鏈接(拓?fù)浣Y(jié)構(gòu)社區(qū))或不具有之間鏈接的社區(qū)(隱含社區(qū))，這些都是當(dāng)前社交網(wǎng)絡(luò)(SNS,Social Network Site)研究中的熱點(diǎn)。本文將就社交網(wǎng)絡(luò)(SNS)研究的基礎(chǔ)核心熱點(diǎn)—社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)(探測)進(jìn)行分析。

1社交網(wǎng)絡(luò)特性及社區(qū)定義

社交網(wǎng)絡(luò)是一種全新的虛擬交流形態(tài)，人們通過網(wǎng)絡(luò)空間進(jìn)行相互交流，并形成比較親密的關(guān)系或不同的角色，即社交網(wǎng)絡(luò)中總是有一部分較為活躍的用戶充當(dāng)著組織者(領(lǐng)導(dǎo)者)的角色，其他用戶在相同的話題或興趣下，逐漸聚合在一起，從而形成一個(gè)有自我認(rèn)同的虛擬網(wǎng)絡(luò)社區(qū)。另外Stanley Milgram 的“六度分隔”理論、Cameron Marlowe的120及150法則的理論也在社交網(wǎng)絡(luò)應(yīng)用中得到了驗(yàn)證。

目前，社交網(wǎng)絡(luò)中關(guān)于社區(qū)(社團(tuán))的定義紛雜并沒有統(tǒng)一的標(biāo)準(zhǔn)，大致可分為基于鏈接關(guān)系的社區(qū)、基于信息內(nèi)容的社區(qū)、鏈接和內(nèi)容相結(jié)合的社區(qū)三類。基于鏈接關(guān)系的社區(qū)，通常把社交網(wǎng)絡(luò)中的用戶作為節(jié)點(diǎn)，用戶之間的關(guān)系作為邊，網(wǎng)絡(luò)中那些內(nèi)部連接“緊密”、外部連接“稀疏”的子團(tuán)結(jié)構(gòu)，稱為虛擬網(wǎng)絡(luò)社區(qū)。Radicchi等針對(duì)社區(qū)內(nèi)部鏈接緊密、社區(qū)間連接稀疏不能很好量化、應(yīng)用于社區(qū)結(jié)構(gòu)劃分的缺陷，提出了強(qiáng)社區(qū)組織和弱社區(qū)組織，強(qiáng)社區(qū)中節(jié)點(diǎn)之間連接的度大于其與社區(qū)外部節(jié)點(diǎn)所連接的度；弱社區(qū)組織中全部節(jié)點(diǎn)的度大于社區(qū)中所有節(jié)點(diǎn)與外部節(jié)點(diǎn)相連接的度之和。Palla等人提出由幾個(gè)全連通的子社區(qū)構(gòu)成的社區(qū)，子社區(qū)之間共有許多節(jié)點(diǎn)，所有的k-群子社區(qū)組成一個(gè)k-群社區(qū)，社區(qū)中任意一個(gè)節(jié)可以通過鄰接的k-群社區(qū)互通(共有k-1個(gè)節(jié)點(diǎn))，社區(qū)中某一節(jié)點(diǎn)有可能同屬于幾個(gè)社區(qū)，社區(qū)與社區(qū)之間有大量的重疊節(jié)點(diǎn)[4]。文獻(xiàn)[5]中利用模塊化函數(shù)，對(duì)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)進(jìn)行定量地描述，并用于評(píng)價(jià)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)劃分的質(zhì)量。

Rheingold把虛擬社區(qū)[6]定義為認(rèn)識(shí)的人們之間分享知識(shí)、信息所形成的社團(tuán)。在研究中，通常把社交網(wǎng)絡(luò)關(guān)系轉(zhuǎn)化為圖的結(jié)構(gòu)，圈子或群體中用戶作為圖的節(jié)點(diǎn)，用戶之間的連接或信息轉(zhuǎn)發(fā)、評(píng)論或相似話題當(dāng)做圖的邊，在不同的應(yīng)用場景下，通過不同的社區(qū)發(fā)現(xiàn)算法，把社交網(wǎng)絡(luò)劃分為不同的子網(wǎng)絡(luò)社區(qū)。

2社交網(wǎng)絡(luò)(SNS)社區(qū)發(fā)現(xiàn)模型

社交網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)化為圖結(jié)構(gòu)的描述建模，可以分為靜態(tài)和動(dòng)態(tài)兩類，靜態(tài)建模和動(dòng)態(tài)建模的主要區(qū)別在于動(dòng)態(tài)社區(qū)發(fā)現(xiàn)模型考慮了社交網(wǎng)絡(luò)的時(shí)間特性，在不同時(shí)刻，其結(jié)構(gòu)有可能發(fā)生變化，而靜態(tài)社區(qū)發(fā)現(xiàn)模型假設(shè)社交網(wǎng)絡(luò)結(jié)構(gòu)(取某一時(shí)刻)不發(fā)生變化。

2.1靜態(tài)社區(qū)模型

靜態(tài)社區(qū)發(fā)現(xiàn)主要是基于某一時(shí)刻網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)進(jìn)行描述、分析，用圖G來描述社交網(wǎng)絡(luò)結(jié)構(gòu),頂點(diǎn)表示用戶,邊表示有鏈接或轉(zhuǎn)發(fā)、評(píng)論等。在此基礎(chǔ)上，基于圖理論或數(shù)據(jù)挖掘方法，實(shí)現(xiàn)社交網(wǎng)絡(luò)(SNS)社區(qū)的發(fā)現(xiàn)和提取。其形式化建模描述如下：

通常用無向圖G=(V,E)表示社交網(wǎng)絡(luò)關(guān)系，描述如下：

(1) V表示頂點(diǎn)集合。即v∈V,表示社交網(wǎng)絡(luò)中的用戶。

(2) E是邊集合。邊e=(v1,v2),e∈E,表示分別頂點(diǎn)V1和頂點(diǎn)V2之間有相互的聯(lián)系。

靜態(tài)SNS的社區(qū)結(jié)構(gòu)表示為CS，P=(C1,C2,C3,···,Cn)是對(duì)圖G中頂點(diǎn)集合V的分割，分割后的集合Ci符合如下條件:

(1)Ci子集內(nèi)頂點(diǎn)間連接比外部緊密。

(2)Ci子集與Cj子集內(nèi)每個(gè)頂點(diǎn)i≠j之間都連接比子集內(nèi)部松散。

在前述靜態(tài)SNS社區(qū)組織的定義中,如圖1所示，緊密、松散程度可以有多種衡量測度,常用的測度有凝聚度和分離度[7]及后續(xù)的模塊度。

圖1　社交網(wǎng)絡(luò)(SNS)社區(qū)

2.2動(dòng)態(tài)社區(qū)模型

真實(shí)社交網(wǎng)絡(luò)中，SNS社區(qū)結(jié)構(gòu)隨時(shí)間變化有可能增加或刪減。在時(shí)間因素的基礎(chǔ)上，建立動(dòng)態(tài)的SNS數(shù)學(xué)模型，描述社區(qū)結(jié)構(gòu),是動(dòng)態(tài)社交網(wǎng)絡(luò)社區(qū)劃分研究的關(guān)鍵難點(diǎn)。

由于SNS網(wǎng)絡(luò)結(jié)構(gòu)隨著時(shí)間在不斷變化，節(jié)點(diǎn)之間的連接有可能增加或刪除。在不同時(shí)刻對(duì)SNS社交結(jié)構(gòu)進(jìn)行采樣，得到一個(gè)時(shí)間序列的靜態(tài)SNS的無向圖，每一個(gè)無向圖稱作動(dòng)態(tài)SNS在這個(gè)時(shí)刻的社交網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)淇煺铡Ｈ缭跁r(shí)刻1得到網(wǎng)絡(luò)結(jié)構(gòu)快照G1,在時(shí)刻2得到網(wǎng)絡(luò)結(jié)構(gòu)快照G2,依次類推,得到Gn-1，Gn等網(wǎng)絡(luò)結(jié)構(gòu)快照。用圖序列G1,G2,G3,···,Gn表示從時(shí)刻1到時(shí)刻n的SNS網(wǎng)絡(luò)結(jié)構(gòu)，其中Gi=(Vi,Ei)是動(dòng)態(tài)SNS在時(shí)刻i的網(wǎng)絡(luò)拓?fù)淇煺眨琲=1,2,3,…,n。在時(shí)刻i,的SNS社區(qū)結(jié)構(gòu)表示為Cs,i，Pi=(C1,C2,C3,···,Cn)是頂點(diǎn)集合V的一個(gè)社區(qū)劃分,其中:

(1)Cs,i滿足定義上述靜態(tài)SNS社區(qū)的形式化描述,對(duì)任意i≥1。

(2)拓?fù)渖鐓^(qū)結(jié)構(gòu)Cs,i與Cs,i-1之間的變化不大，具有典型的局部特性，滿足于給定常數(shù)σ，如公式(1)所示

(1)

Lin[8]等人指出SNS網(wǎng)絡(luò)結(jié)構(gòu)的變化實(shí)際上是非常緩慢的. 單等人通過對(duì)Enron的真實(shí)數(shù)據(jù)分析統(tǒng)計(jì)也進(jìn)行驗(yàn)證，即在相鄰的時(shí)刻i-1和時(shí)刻i，SNS的拓?fù)浣Y(jié)構(gòu)變化相對(duì)于整個(gè)圖結(jié)構(gòu)而言非常小。但其結(jié)論是否適用Twitter、Facebook等大型的社交網(wǎng)絡(luò)，尚不清楚有待驗(yàn)證。

3傳統(tǒng)社區(qū)發(fā)現(xiàn)算法

傳統(tǒng)劃分社區(qū)結(jié)構(gòu)的算法主要分為：圖分割法和層次聚類法兩大類[9,10]。

3.1圖分割法

基于圖的分割是將網(wǎng)絡(luò)劃分成節(jié)點(diǎn)數(shù)相等的子網(wǎng)或群組，使得子網(wǎng)內(nèi)部節(jié)點(diǎn)連接緊密，子網(wǎng)或群組之間的連接數(shù)較少，然后通過不斷迭代獲得所要求的子網(wǎng)數(shù)目。其中代表性算法有Kernighan-Lin算法和Laplace矩陣特征值的譜平分法。Kernighan-Lin算法把網(wǎng)絡(luò)分割為兩個(gè)規(guī)模大小已知的社團(tuán)，在分割過程中通過增益函數(shù)Q，來判定社區(qū)劃分的好壞。

Fiedler等人[11]利用譜平分法，對(duì)無向網(wǎng)絡(luò)G的Laplace矩陣的特征值進(jìn)行分析，利用Laplace矩陣特征值分割網(wǎng)絡(luò)為社區(qū)組織。譜平分法在網(wǎng)絡(luò)只能分割為兩個(gè)社區(qū)時(shí)，效果較為明顯。通常轉(zhuǎn)化后Laplace矩陣較為稀疏，在特征向量計(jì)算方面比較簡單及快速，在有明顯的優(yōu)勢。但Laplace特征值的譜平分法無法將網(wǎng)絡(luò)劃分為三個(gè)或三個(gè)以上的社區(qū)或社團(tuán)(每次只能將網(wǎng)絡(luò)平分)，網(wǎng)絡(luò)的多個(gè)社區(qū)(社團(tuán))劃分，需要應(yīng)用該算法對(duì)子社區(qū)或社團(tuán)多次平分，其缺陷是需要清楚知道社團(tuán)的規(guī)模大小。為此Capocci等提出了一種基于標(biāo)準(zhǔn)矩陣N=K-1A的譜平分算法。該算法僅取其中一個(gè)特征向量(K-1個(gè))，便可將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為k個(gè)社區(qū)。

3.2層次聚類法

層次聚類法分為層次分裂法(divisive method)和層次聚合法(agglomerative method)兩類。主要利用節(jié)點(diǎn)之間的相似性或者連接強(qiáng)度，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行社區(qū)劃分。層次分裂法是通過不斷重復(fù)尋找對(duì)網(wǎng)絡(luò)圖中相似性最低的節(jié)點(diǎn)對(duì)之間的邊，然后進(jìn)行刪減，自上往下逐步把網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分割，最終形成不同的社區(qū)。而層次聚合法通過計(jì)算并選擇相似性最高的節(jié)點(diǎn)對(duì)，根據(jù)相似度從強(qiáng)到弱連接相應(yīng)節(jié)點(diǎn)對(duì)，自底向上，不斷地往原始空的網(wǎng)絡(luò)圖中添加邊，最終構(gòu)成樹狀圖(Dendrogram)，依據(jù)應(yīng)用需求橫切樹狀圖，獲得不同的社區(qū)組織，如下圖3所示；不論是分裂還是聚合方法，都可終止于任意步驟，則在此狀態(tài)下的網(wǎng)絡(luò)劃分，便構(gòu)成網(wǎng)絡(luò)社區(qū)組織。在劃分后層次聚類樹中，不同的社區(qū)劃分層次得到的社區(qū)結(jié)構(gòu)不盡相同，Newman[13]等使用度量函數(shù)Q來評(píng)價(jià)社區(qū)劃分質(zhì)量。模塊度定義如公式(2)所示：

(2)

元素eij表示社區(qū)i和社區(qū)j之間所有的邊占整個(gè)網(wǎng)絡(luò)所有邊的比例，i∈Ci,j∈Cj，Ci表示社區(qū)i, Cj表示社區(qū)j，∑ieii表示矩陣中對(duì)角線的所有元素之和，表示網(wǎng)絡(luò)中所有社區(qū)的內(nèi)部邊(即該邊的兩個(gè)端點(diǎn)屬于同一個(gè)社區(qū))占整個(gè)網(wǎng)絡(luò)所有邊的比例；ai=∑eij表示第i行(或者第j列)所有元素之和，表示與社區(qū)i中節(jié)點(diǎn)相連的所有的邊占整個(gè)網(wǎng)絡(luò)所有邊的比例。Q越接近1表明社區(qū)結(jié)構(gòu)特征越明顯，得到社區(qū)的劃分越好。

圖3　層次聚類及分裂法網(wǎng)絡(luò)社區(qū)劃分過程

如何定義相似度是層次聚類算法的關(guān)鍵所在。其特點(diǎn)是能夠發(fā)現(xiàn)高相似性的節(jié)點(diǎn)對(duì)，而相似度較小的社區(qū)邊界節(jié)點(diǎn)社區(qū)劃分精度較低；層次聚類法具有不需已知社團(tuán)規(guī)模的優(yōu)勢，但最終社區(qū)(社團(tuán))劃分的個(gè)數(shù)也無從知曉。其不適用于大型真實(shí)網(wǎng)絡(luò)應(yīng)用。

3.3GN系列算法

(3)

Tyler[14]等人采用網(wǎng)絡(luò)部分節(jié)點(diǎn)的方法代替GN算法中所有節(jié)點(diǎn)作為源節(jié)點(diǎn)，只計(jì)算這些節(jié)點(diǎn)所對(duì)應(yīng)邊的邊介數(shù)，以彌補(bǔ)GN算法的計(jì)算效率缺陷。另外，Radicchi等人[15]提出自包含GN算法，通過定量的社區(qū)結(jié)構(gòu)定義，量化評(píng)價(jià)社區(qū)結(jié)構(gòu)。GN算法在劃分網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)時(shí)，通常會(huì)獲得較為準(zhǔn)確的效果，但算法復(fù)雜度較大，限制它僅應(yīng)用于規(guī)模較小的網(wǎng)絡(luò)。

在大規(guī)模的網(wǎng)絡(luò)下，基于GN算法改進(jìn)的快速社團(tuán)劃分算法(NF算法)，將貪婪算法和層次聚合算法相結(jié)合，適用于節(jié)點(diǎn)達(dá)百萬的復(fù)雜網(wǎng)絡(luò)。在計(jì)算速度方面，Clauset等人對(duì)NF快速算法進(jìn)行了改進(jìn)，提出了CNM算法，該算法通過使用堆結(jié)構(gòu)和Q函數(shù)，降低了算法的時(shí)間復(fù)雜度為O(nlog2n)，接近線性時(shí)間復(fù)雜度。NF算法和CNM算法相比，前者利用連接矩陣對(duì)模塊度ΔQ變化進(jìn)行計(jì)算，后者通過構(gòu)建模塊度增量矩陣ΔQ，更新矩陣元素，來得到模塊化Q值變化最大的社區(qū)合并。若兩個(gè)社區(qū)間無邊連接，則模塊度Q值的不變。在算法應(yīng)用中，可以通過只保存有邊連接的社區(qū)及相應(yīng)的模塊度變化值，節(jié)省算法的存儲(chǔ)空間。

4存在問題及未來方向

由于互聯(lián)網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)本身具有復(fù)雜性、多變性等特點(diǎn)，尤其是網(wǎng)絡(luò)結(jié)構(gòu)實(shí)際環(huán)境中，并不是單一的、靜態(tài)、簡單的結(jié)構(gòu)，圍繞網(wǎng)絡(luò)進(jìn)行的社區(qū)結(jié)構(gòu)劃分存在多個(gè)維度，多種方法，但是大多數(shù)還是采用單一的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并沒有考慮網(wǎng)絡(luò)節(jié)點(diǎn)本身的信息或節(jié)點(diǎn)所參與的話題，如何把拓?fù)浣Y(jié)構(gòu)分析和話題分析相結(jié)合，分析、發(fā)現(xiàn)社區(qū)，必將是社區(qū)發(fā)現(xiàn)一個(gè)重要的研究點(diǎn)。此外，人們對(duì)社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與用戶行為的影響，如何刻畫和控制社交信息在網(wǎng)絡(luò)上的傳播等都還在不斷的探索和發(fā)現(xiàn)中，特別是以微博為代表的社交網(wǎng)絡(luò)所包含的信息相當(dāng)豐富，如何利用這些屬性信息挖掘社區(qū)是值得探討的問題。另外，微博社交網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)是動(dòng)態(tài)性，如何運(yùn)用社交網(wǎng)絡(luò)微博信息進(jìn)行動(dòng)態(tài)社區(qū)發(fā)現(xiàn)不僅是當(dāng)前的研究熱點(diǎn)，也是當(dāng)前信息推薦、廣告定點(diǎn)投放的重要市場應(yīng)用方向。

參考文獻(xiàn)：

[1]Watts D J，Strogatz S H．Collective Dynamics of‘Small World’Networks[J]．Nature，1998，393(6684)：440-441.

[2]Barabasi AL,Albert R．Emergence of Scaling in Random Networks[J]．Science，1999，286(10)：504.

[3]Baralbasi AL,Albert R,Jeong H. Mean-field Theory for Scalefree Random Networks[J]．Phys Review，1999(272)：173-187.

[4]Palla G,Dernyi I,el at．Uncovering the Overlapping Community Structure of Complex Networks inNature and Society[J].Nature，2005，435，(6)：814-818.

[5]NewmanME,Girvan M．Finding and Evaluating Community Structure in Networks[J].Phys Rev E Stat Nonlin Soft Matter Phys，2004，69(2)：026113.

[6]Howard Rheingold.The Virtual Community[M].London:HarperPerennial, 1994.

[7]Steinbach M, Tan PN, el at. Support Envelopes: A technique for Exploring the Structure of Association Patterns[C].SIGKDD2004:296-305.

[8]Lin YR, Chi Y, Zhu SH,Sundaram H, Tseng BL. FacetNet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks[C]. WWW’08:proceeding of the 17th international conference on world wide web,2008:685-694.

[9]JohnScott.Social Network Analysis[J].Sociology,1998,22(1):109-127.

[10]Garey MR,Johnson DS．Computers and intractability：A Guide to the Theory of NP-Completeness[M].Newyork:W.H.Freeman & Co Ltd.1979.

[11]Fiedler M,Praha. Algebraic Connectivity of Graphs[J].Journal of Czechoslovak Mathematical.1973,23(2):298-305.

[13]Newman MEJ. Fast Algorithm for Detecting Community Structure in Setworks[J]. Physical Review E,2003,69(6):066133.

[14]Tyler JR,Wilkinson DM,el at. Automated Discovery of Community Structure within Organizations[J].Information Socity,2003,21(2):143-153.

[15]Radicchi F,Castellano C,et al．Defining and Identilying Communities in Networks[J].PNAS.2003,101(9):2658-2663.

責(zé)任編輯：程艷艷

Analysis of Community Discovery Algorithms Based on Social Communication Networks

WU Jianjun

(Department of Information Technology, Beijing College of Politics and Law, Beijing 102628, China)

Abstract：Along with the rapid development and application of social communication network, online community centering on social communication network users and information interaction becomes an important branch in the field of social communication network study. Although many results have been made, there are many challenges and problems. Considering network structure, network information and time, this paper analyzes and compares typical community discovery models, algorithms and evaluation methods based on the definitions and features of network community, and discusses the problems and future development direction.

Keywords：social network; community algorithm; dynamic community; SNS analysis

收稿日期：2016-04-30

基金項(xiàng)目：北京政法職業(yè)學(xué)院課題(KYZX201404)

作者簡介：毋建軍(1977- )，男，山西河津人，講師，碩士，主要從事社交網(wǎng)絡(luò)方面研究。

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3907(2016)06-0035-04