毋建軍

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

?

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

毋建軍

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

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

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

0引言

隨著Twitter、Facebook、新浪微博、人人網(wǎng)、微信等社交網(wǎng)絡(luò)的廣泛應用，社交網(wǎng)絡(luò)大數(shù)據(jù)集合孕育而生，在大數(shù)據(jù)基礎(chǔ)上，不同領(lǐng)域、學科的研究人員基于社交網(wǎng)絡(luò)的鏈接結(jié)構(gòu)、用戶交互行為、信息擴散傳播等方面，進行了社交網(wǎng)絡(luò)用戶關(guān)系挖掘、信息擴散傳播的機制分析、網(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)查、美國大學生足球網(wǎng)絡(luò)等)。但近年來隨著社交網(wǎng)絡(luò)規(guī)模及應用的急劇發(fā)展，關(guān)于復雜網(wǎng)絡(luò)的研究及數(shù)據(jù)集的采樣規(guī)模，已遞增為百萬或千萬、甚至上億。社交網(wǎng)絡(luò)已經(jīng)成為復雜網(wǎng)絡(luò)研究中一個新興的研究領(lǐng)域。Watts等[1]提出的小世界模型,描述網(wǎng)絡(luò)具有集聚、較小平均路徑長度等特性。Barahasi等驗證了度分布服從冪律分布p(k)=ck-r的復雜網(wǎng)絡(luò)[2,3]，具有“小世界”、 “聚集性”、“無標度”等特性。

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

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

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

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

Rheingold把虛擬社區(qū)[6]定義為認識的人們之間分享知識、信息所形成的社團。在研究中，通常把社交網(wǎng)絡(luò)關(guān)系轉(zhuǎn)化為圖的結(jié)構(gòu)，圈子或群體中用戶作為圖的節(jié)點，用戶之間的連接或信息轉(zhuǎn)發(fā)、評論或相似話題當做圖的邊，在不同的應用場景下，通過不同的社區(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)和動態(tài)兩類，靜態(tài)建模和動態(tài)建模的主要區(qū)別在于動態(tài)社區(qū)發(fā)現(xiàn)模型考慮了社交網(wǎng)絡(luò)的時間特性，在不同時刻，其結(jié)構(gòu)有可能發(fā)生變化，而靜態(tài)社區(qū)發(fā)現(xiàn)模型假設(shè)社交網(wǎng)絡(luò)結(jié)構(gòu)(取某一時刻)不發(fā)生變化。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

3.1圖分割法

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

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

3.2層次聚類法

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

(2)

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

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

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

3.3GN系列算法

(3)

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

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

4存在問題及未來方向

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

責任編輯：程艷艷

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

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

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

中圖分類號：TP391

文獻標志碼：A

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