基于社交網絡的社區發現算法研究

毋建軍

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

?

基于社交網絡的社區發現算法研究

毋建軍

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

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

關鍵詞：社交網絡；社區算法；動態社區；SNS分析

0引言

隨著Twitter、Facebook、新浪微博、人人網、微信等社交網絡的廣泛應用，社交網絡大數據集合孕育而生，在大數據基礎上，不同領域、學科的研究人員基于社交網絡的鏈接結構、用戶交互行為、信息擴散傳播等方面，進行了社交網絡用戶關系挖掘、信息擴散傳播的機制分析、網絡結構變遷、新型(網絡)虛擬關系演化等基礎性問題的研究。

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

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

1社交網絡特性及社區定義

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

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

Rheingold把虛擬社區[6]定義為認識的人們之間分享知識、信息所形成的社團。在研究中，通常把社交網絡關系轉化為圖的結構，圈子或群體中用戶作為圖的節點，用戶之間的連接或信息轉發、評論或相似話題當做圖的邊，在不同的應用場景下，通過不同的社區發現算法，把社交網絡劃分為不同的子網絡社區。

2社交網絡(SNS)社區發現模型

社交網絡結構轉化為圖結構的描述建模，可以分為靜態和動態兩類，靜態建模和動態建模的主要區別在于動態社區發現模型考慮了社交網絡的時間特性，在不同時刻，其結構有可能發生變化，而靜態社區發現模型假設社交網絡結構(取某一時刻)不發生變化。

2.1靜態社區模型

靜態社區發現主要是基于某一時刻網絡社區結構進行描述、分析，用圖G來描述社交網絡結構,頂點表示用戶,邊表示有鏈接或轉發、評論等。在此基礎上，基于圖理論或數據挖掘方法，實現社交網絡(SNS)社區的發現和提取。其形式化建模描述如下：

通常用無向圖G=(V,E)表示社交網絡關系，描述如下：

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

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

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

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

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

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

圖1　社交網絡(SNS)社區

2.2動態社區模型

真實社交網絡中，SNS社區結構隨時間變化有可能增加或刪減。在時間因素的基礎上，建立動態的SNS數學模型，描述社區結構,是動態社交網絡社區劃分研究的關鍵難點。

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

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

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

(1)

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

3傳統社區發現算法

傳統劃分社區結構的算法主要分為：圖分割法和層次聚類法兩大類[9,10]。

3.1圖分割法

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

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

3.2層次聚類法

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

(2)

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

圖3　層次聚類及分裂法網絡社區劃分過程

如何定義相似度是層次聚類算法的關鍵所在。其特點是能夠發現高相似性的節點對，而相似度較小的社區邊界節點社區劃分精度較低；層次聚類法具有不需已知社團規模的優勢，但最終社區(社團)劃分的個數也無從知曉。其不適用于大型真實網絡應用。

3.3GN系列算法

(3)

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

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

4存在問題及未來方向

由于互聯網網絡結構本身具有復雜性、多變性等特點，尤其是網絡結構實際環境中，并不是單一的、靜態、簡單的結構，圍繞網絡進行的社區結構劃分存在多個維度，多種方法，但是大多數還是采用單一的網絡拓撲結構，并沒有考慮網絡節點本身的信息或節點所參與的話題，如何把拓撲結構分析和話題分析相結合，分析、發現社區，必將是社區發現一個重要的研究點。此外，人們對社交網絡拓撲結構與用戶行為的影響，如何刻畫和控制社交信息在網絡上的傳播等都還在不斷的探索和發現中，特別是以微博為代表的社交網絡所包含的信息相當豐富，如何利用這些屬性信息挖掘社區是值得探討的問題。另外，微博社交網絡的一個重要特點是動態性，如何運用社交網絡微博信息進行動態社區發現不僅是當前的研究熱點，也是當前信息推薦、廣告定點投放的重要市場應用方向。

參考文獻：

[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

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

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

中圖分類號：TP391

文獻標志碼：A

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