社交網(wǎng)絡中的社團結構挖掘

范 超，王厚峰

(1. 北京大學 軟件與微電子學院，北京 100871； 2. 北京大學 計算語言學教育部重點實驗室，北京 100871)

1 引言

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，社交網(wǎng)絡在人際交往中發(fā)揮著越來越重要的作用。發(fā)現(xiàn)其中的社團關系，分析社團的屬性，是一項非常有意義的工作。

不少學者從不同角度對社團網(wǎng)絡及其屬性做了研究，出現(xiàn)了小世界特征[1]、冪律分布[2]和社團結構[3-6]等相關的成果。尤其是社團結構，它在反映同一個團體內(nèi)成員的行為特征方面，起著非常重要的作用。近年來，不少研究人員都在研究如何發(fā)掘社團結構[3]。

“人人網(wǎng)”是國內(nèi)影響最廣泛的虛擬社交網(wǎng)絡之一。其前身是“校內(nèi)網(wǎng)”，用戶的主體來自高校在讀或已畢業(yè)的學生。從中發(fā)掘社團結構，有助于分析高校不同群體的一些特點。

除此之外，研究社團結構的挖掘工作還具有其他的一些應用價值和現(xiàn)實意義。一方面，它有助于我們了解社交網(wǎng)絡的內(nèi)在特征與結構；另一方面，它還可以擴展到微博等社會媒體上來，應用于商業(yè)領域，例如，針對發(fā)掘出的社會團體，投放符合其特征和興趣的新聞和廣告，提供個性化服務。另外，研究社團發(fā)掘工作，還能夠為其他諸如突發(fā)事件的應急處理提供支持。通過研究社交網(wǎng)絡中關鍵社團的發(fā)掘，有助于了解重大突發(fā)事件在社團內(nèi)部、以及多個社團之間的傳播與擴散機制，甚至能夠為相關部門制定預警和防范措施提供一定的幫助。

本文從網(wǎng)絡的結構信息和節(jié)點的內(nèi)容信息入手，研究了人人網(wǎng)的社團結構挖掘，并以北京大學的部分用戶數(shù)據(jù)作了實驗。主要內(nèi)容包括： 第一，使用社會網(wǎng)絡分析的方法來標注北大用戶的院系屬性，以此構建評測答案；第二，提出了一個改進的CNM算法，在網(wǎng)絡結構信息基礎上發(fā)掘社團結構；第三，引入節(jié)點屬性的內(nèi)容信息，輔助改進社團發(fā)掘的效果；第四，對實驗結果作了分析，發(fā)現(xiàn)社團反映了不同院系和學科的特點。

2 相關工作

社團是這樣的一些子群體，內(nèi)部連接稠密，外部連接稀疏。有兩種典型的社團： 團塊社團(Clique Communities)和傳遞社團(Transitive Communities)[6]。社團發(fā)掘的典型方法有： 圖劃分方法、隨機塊模型方法和基于模塊的方法。

圖劃分方法(Graph Partitioning)是一種傳統(tǒng)方法，它通過不斷地刪除邊來分離網(wǎng)絡并得到社團。但是，尋找精確的解是一個NP-hard問題[6]。現(xiàn)在，有許多近似算法可以使用，例如，METIS、網(wǎng)絡流方法、Kernighan-Lin算法、譜劃分方法。METIS采用多級迭代二分和多約束的劃分策略[7]；網(wǎng)絡流方法則是借助網(wǎng)絡流理論中的最大流/最小割的框架來劃分社團[8]；Kernighan-Lin算法使用貪心策略，同時最優(yōu)化社團內(nèi)與社團間的邊數(shù)[9]。譜劃分多采用迭代二分法，例如，使用最小的兩個特征值所對應的特征向量進行社團劃分[10]。盡管如此，對于大規(guī)模網(wǎng)絡來說，圖劃分的方法仍然未被廣泛采用。

隨機塊模型方法(Stochastic Blockmodeling)是社團發(fā)掘的另一種方法。該方法以一定的概率對社團進行劃分，劃分過程具有不確定性。Nowicki和Snijders提出了一般的隨機塊模型的方法，使用Gibbs采樣來推導位置的后驗分布[11]。Wang等人提出了泛化的隨機塊模型，支持使用屬性信息和主題特定的知識[12]。Zhang等人則提出了適用于大規(guī)模社會網(wǎng)絡的隨機社團發(fā)現(xiàn)模型[13]。但是，隨機塊模型的方法引入了概率模型，可能會導致求解過于復雜。

模塊性方法(modularity-based method)是廣泛使用的一種社團劃分法，其核心是模塊性Q[4]。該方法最早由Newman在2004年提出，它是一個評價社團結構的利益函數(shù)，其值反映整個網(wǎng)絡結構的優(yōu)劣。Q值越高，表明社團內(nèi)的連接越緊密，并且社團間的連接越稀疏。假設G=(V,E)是一個無向圖，|V|=n，|E|=m。G由鄰接矩陣表示，Axy是鄰接矩陣第x行和第y列上的元素：

節(jié)點x的度定義為：kx=ΣyAxy，因此，模塊性Q由式(2)計算：

其中，kx為x的度數(shù)，Cx代表節(jié)點x屬于社團Cx。如果x和y在同一個社團內(nèi)，函數(shù)φ(Cx,Cy)為1，否則為0。Pxy是隨機情況下x和y之間可能的節(jié)點度，已有實驗表明，對于網(wǎng)絡中較好的社團結構，這個值通常高于0.3[5]。

目前已有多種基于模塊性的方法用于發(fā)掘社團。Newman最初采用了一種貪心最優(yōu)化Q的策略[4]；后來，出現(xiàn)了更有效的CNM算法[5]；近來，受到譜聚類理論的啟發(fā)，Newman采用模塊性矩陣的特征向量，來輔助最大化模塊性指標[14]。

Danon等人[15]的研究表明，基于模塊性的方法優(yōu)于其他方法。CNM算法作為優(yōu)秀的模塊最大化方法，在準確性和處理效率上都達到了不錯的效果。另外，它能夠同時利用網(wǎng)絡的結構信息和節(jié)點的內(nèi)容信息，本文以CNM算法作為社團結構發(fā)掘的基本算法。

3 CNM算法和改進

首先簡要地介紹一下CNM算法的原理，然后提出兩種改進方案： 引入網(wǎng)絡結構信息和引入節(jié)點內(nèi)容信息。

3.1 CNM算法

CNM算法是一個基于模塊性Q的層次聚合式聚類算法，通過貪心法最優(yōu)化Q得到一個社團結構。為了提升算法的效率，Clauset引入了一些高級數(shù)據(jù)結構[5]，使算法更為有效。算法的要點是采用平衡二叉樹和最大堆來減少計算代價，通過自底向上歸并。具體步驟如下： (1)所有網(wǎng)絡中的節(jié)點作為一個單一的社團；(2)對于任意兩個社團，計算它們合并后ΔQ的增量，貪心地選擇使ΔQ最大的兩個社團合并。因為合并會導致每個團體內(nèi)部的ΔQ發(fā)生變化，因此，更新所有與新社團有連接的社團的數(shù)據(jù)結構信息，再重復上一步的過程；(3)當ΔQ<0時，終止算法。算法的運行復雜度為O(m*d*logn)，其中，d為層次聚類樹的深度。Clauset認為在真實的社交網(wǎng)絡中，通常有m～n、d～logn[5]，因此，算法復雜度為O(n*log2n)。

3.2 引入網(wǎng)絡結構信息改進CNM算法

雖然CNM算法能夠非常有效地發(fā)掘社團結構，但結果并不十分完美。對于人人網(wǎng)而言，存在很多節(jié)點用戶是網(wǎng)絡的人氣節(jié)點，連接著許多互不關聯(lián)的社團(例如，學校的不同院系)，在社團間的交流中起到重要的作用。也就是說，這些節(jié)點有著較高的betweenness。所謂betweenness，就是經(jīng)過某一點Y，連接其他兩個點X和Z的最短路徑數(shù)占二者最短路徑總數(shù)的比例[16]。這些節(jié)點具有控制其他用戶交流的能力。Betweenness的概念可以擴展到邊上，Givan和Newman提出了一個“邊betweenness”的概念[3]，這些邊通常是連接著兩個社團的關鍵邊，刪除這些邊可以使不同社團之間的連接邊更少。而社團發(fā)現(xiàn)的目標就是盡量使社團內(nèi)的邊更多，社團間的邊盡量少。引入betweenness的網(wǎng)絡結構信息，可以進一步提升傳統(tǒng)CNM算法的發(fā)現(xiàn)精度。

以下的算法依次刪除betweeenness最高的一些邊，并把這一過程作為CNM算法的預處理步驟，其過程可簡單地表示為：

1) 計算網(wǎng)絡中所有邊的betweenness；

2) 刪除betweenness最高的α條邊；

3) 使用CNM算法來發(fā)現(xiàn)社團的結構，每次選擇使得模塊性Q值增大最多的一條邊來合并，直到它的增加值小于或等于0，停止合并。

算法描述如下：

輸入：刪除的邊數(shù)α，網(wǎng)絡圖graph

輸出：劃分的社團clusterSet

ImprovedCNMClusterer clust = initImprovedCNMClusterer(graph);

clust.removeEdges(α);

clusterSet = clust.CNMcluster();

removeEdges(α)函數(shù)偽代碼：

BetweennessCentrality bc = computeAllBetweennessCentrality(graph);

If α > 0 and α < graph.getEdgeCount()

FOR k=0 to α

toRemove; score = 0;

//find the edge whose betweenness is maximum

FOR e in g.getEdges()

IF bc.getEdgeScore(e) > score

toRemove = e;

score = bc.getEdgeScore(e);

//remove the edge

g.removeEdge(to_remove);

第一步betweenness的計算復雜度為O(mn)；每次刪除betweenness最高的邊的時間復雜度為O(m)，總的復雜度為O(αm)；第三步CNM算法的計算復雜度為O(m*d*logn)。真實的網(wǎng)絡中，有m～n、d～logn，因此，改進算法的復雜度為O(n2)。

3.3 引入節(jié)點內(nèi)容信息改進CNM算法

除了網(wǎng)絡本身的結構信息，節(jié)點的一些屬性反映了它的某些特征。一般而言，具有相同或相似特征的節(jié)點應該屬于同一社團。具體到人人網(wǎng)的北大用戶上，可以通過引入節(jié)點的屬性信息發(fā)現(xiàn)共同院系的兩個沒有連接的用戶。最近，已有學者融合結構和內(nèi)容信息發(fā)掘社團[17-19]，本文使用人人網(wǎng)用戶的日志信息，在改進CNM算法方面做了初步嘗試。

引入節(jié)點內(nèi)容的基本方法是： 通過用戶日志內(nèi)容，計算任意兩個用戶之間的相似度，若相似值高于某個閾值β，則將兩個用戶連在一起，無論原有網(wǎng)絡中用戶節(jié)點是否相連。

為了計算節(jié)點間的相似度，首先利用用戶節(jié)點的屬性構造用戶模型。這里僅采用日志信息，把每個用戶的所有日志合并，再抽取特征，用一個向量來表示用戶模型。具體方法是：先分詞并標詞性，去掉停用詞，再抽取其中的名詞作為特征，使得每個用戶對應一個特征向量di= (wi1,wi2, …,win)；之后，用cosine法計算兩個特征向量的相似度。

這里，特征詞的權重wij采用標準的tf.idf的計算方法，如式(3)所示。

wij=tfij*idfj=fij* (log2(n/nj)+1)

(3)

其中nj> 0

cosine相似度的計算公式如式(4)所示。

預處理中，計算所有節(jié)點對之間的相似度為O(n2)，CNM算法的復雜度為O(m*d*logn)，因此，引入節(jié)點內(nèi)容信息的算法復雜度為O(n2)。

4 實驗

4.1 數(shù)據(jù)采集

本文選擇人人網(wǎng)數(shù)據(jù)進行實驗。由于人人網(wǎng)的數(shù)據(jù)龐大，本文主要采集了北京大學的在校學生用戶數(shù)據(jù)作為實驗數(shù)據(jù)。利用人人網(wǎng)的開放API，可以采集到用戶的部分屬性信息和所有關系信息，包括： 用戶id、用戶名、學校、朋友id的集合、用戶日志。

采用廣度優(yōu)先策略爬取用戶數(shù)據(jù)。首先，選取北京大學的某個用戶作為種子節(jié)點，抓取用戶信息和好友信息；然后，把好友關系中屬于北京大學的用戶保留下來，放到待爬取列表中；再通過這些好友，不斷地向外抓取，直至所有待爬取列表為空。最終，從人人網(wǎng)獲取到的數(shù)據(jù)量為77 677個，其中有76%的用戶來自北京大學。所有用戶的好友人數(shù)為12 630 015，平均好友為162.6個。其中，好友數(shù)量隨用戶人數(shù)的分布關系如圖1所示。由于人人網(wǎng)限制了最大好友數(shù)量為1 000，所以，除了在1 000的點上有一個暴增之外，基本上是隨著好友數(shù)量的增加，用戶的人數(shù)不斷減少。

圖1 用戶人數(shù)與好友數(shù)量分布統(tǒng)計

同樣，再計算所有用戶中任意兩個用戶之間的最短路徑(圖2)。人人網(wǎng)中的用戶距離在6以內(nèi)，絕大多數(shù)是3和2(42.42%用戶的距離為3，35.08%用戶的距離為2)。當然，在真實的網(wǎng)絡中，也可能出現(xiàn)一個北京大學同學認識的某個同學在人人網(wǎng)上并沒有加為好友的情況，但從實驗結果來看，基本上符合六度分離的原則。

4.2 標準答案的構建和評價方法

在社團挖掘領域，主流的評測方法是采用真實的數(shù)據(jù)作為評價的標準答案[3-6]。在以大學生為主的人人網(wǎng)上，院系內(nèi)部的學生之間的關系相對于其他院系，通常會更加緊密。因此，本文采用用戶所在的院系這一屬性作為劃分不同團體的答案。

由于人人網(wǎng)的API限制，用戶所在的院系屬性無法被獲取到。為了解決這一問題，我們從網(wǎng)上找到了北京大學官方發(fā)布的09屆畢業(yè)生名單，名單包含了所有09屆本科畢業(yè)生的姓名以及所在院系。本文通過如下方法來構建一個09屆北京大學本科畢業(yè)生的用戶網(wǎng)絡：

1. 把人人網(wǎng)的用戶名預處理成規(guī)整的形式。例如，用戶“劉少龍 Aspen”處理成“劉少龍”(人人網(wǎng)允許在真實姓名后添加一個后綴)；

圖2 兩個用戶節(jié)點間最短路徑的分布

2. 把用戶中沒有歧義的用戶名與畢業(yè)生名單進行對比，若名單中含有該名字，則挑選出來并附上其所在的學院放到隊列Q中。例如，“鮑重錚”在人人網(wǎng)數(shù)據(jù)中只有一個，對應到名單中的“數(shù)學科學學院”，加入Q；而數(shù)據(jù)中有多個“王碩”，則推遲處理；

3. 統(tǒng)計重名用戶的好友所在的學院，若好友中屬于某一學院的人數(shù)大于一定個數(shù)(初始階段這個值設定的較高)，我們認定該用戶屬于相應的學院，并把這些用戶加入Q中；

4. 重復步驟3，通過迭代，發(fā)現(xiàn)更多的用戶及所在學院；

5. 通過人工的方法標記剩余的一些用戶。

通過上述過程，從人人網(wǎng)數(shù)據(jù)中找到了所有3 645名09屆本科生中的2 375名，作為本文評測的數(shù)據(jù)和答案。在這些數(shù)據(jù)中，只有重名情況存在不確定性，但最后通過人工驗證得到的答案也是基本可靠的。值得一提的是，使用社會網(wǎng)絡中的好友關系為解決重名問題提供了一種思路。

本文采用聚類度量指標P-IP score[20]來進行評價。P-IP score包括純度(Purity)、逆純度(InversePurity)和F值(Fscore)這三個指標。其中，F(xiàn)值為前兩個的調(diào)和平均數(shù)。

5 實驗結果和分析

本文進行了多組對比實驗，原始的CNM算法作為評價的baseline。同時，我們對社團發(fā)現(xiàn)的結果進行一個分析，簡單地對北京大學不同院系和學科的特點做了分析解釋。

5.1 實驗結果

實驗結果分三部分： 第一部分在baseline的基礎上，引入了網(wǎng)絡結構的信息betweenness進行改進；第二部分在baseline的基礎上，僅增加了節(jié)點的一些內(nèi)容信息進行改進；第三部分，融合前兩部分的結果。

5.1.1 使用網(wǎng)絡結構信息改進的結果

表1是在相同數(shù)據(jù)集上，CNM算法和利用betweenness預處理的改進算法的一個實驗結果，括號中是預處理刪除betweenness最高的邊數(shù)的閾值α。Baseline的F值達到了83.96%，取得了一個較好的效果。這一結果也驗證了使用院系屬性來劃分社團是基本有效的，人人網(wǎng)中存在著這么一種社團結構。從結果中還能看到，當刪除的邊數(shù)為21時，F(xiàn)值達到最大88.28%，取得最高的社團發(fā)現(xiàn)精度。當不斷增加預處理刪除的邊數(shù)時，F(xiàn)值有一個波動。刪除過多的邊，F(xiàn)值低于CNM算法的水平，這是因為刪除過多的邊破壞了網(wǎng)絡的社團結構，導致了純度和逆純度兩者都下降。

5.1.2 使用節(jié)點內(nèi)容信息改進的結果

表2是在原CNM算法基礎上，僅增加內(nèi)容信息的結果。括號中的數(shù)字表示相似度閾值β，當兩個節(jié)點之間的內(nèi)容相似度高于這個值時，會保證在這兩個節(jié)點間有一條邊。結果顯示，僅引入內(nèi)容信息，能有2個多的百分點提升。但如果閾值設置過低，會導致過多的邊被引入，甚至增加不同社團之間的連邊，反而會降低性能。

表1使用betweenness改進的CNM算法和原始CNM算法的對比

Methods/%PurityInversePurityFscoreBaseline(CNM)89．1879．3283．96ImproCNM(20)89．3081．1785．05ImproCNM(21)90．6186．0688．28ImproCNM(22)87．3782．5684．90ImproCNM(23)89．3580．8884．90ImproCNM(24)88．1780．3784．09ImproCNM(25)90．8283．6287．07ImproCNM(26)90．8679．7884．96ImproCNM(27)89．6875．5782．03ImproCNM(28)89．2282．5685．76ImproCNM(29)90．8677．1783．46ImproCNM(30)91．2475．6682．72ImproCNM(35)87．1672．2178．98

表2使用內(nèi)容信息改進的CNM算法和原始CNM算法的對比

Methods/%PurityInversePurityFscoreBaseline(CNM)89．1879．3283．96ImproCNM(0．95)90．1979．4184．46ImproCNM(0．9)90．5381．4385．74ImproCNM(0．85)90．3681．3985．64ImproCNM(0．8)89．6082．2785．78ImproCNM(0．75)89．7382．0285．70ImproCNM(0．7)92．0080．7686．01ImproCNM(0．65)85．9885．4385．71ImproCNM(0．6)84．5581．6883．09ImproCNM(0．55)85．7777．8581．62ImproCNM(0．5)86．5777．7381．91ImproCNM(0．45)87．6370．5778．18

5.1.3 使用結構和內(nèi)容信息改進的結果

原始的CNM算法本質(zhì)上僅采用了網(wǎng)絡的結構信息，因為網(wǎng)絡中任意兩點之間是否連邊來自真實的網(wǎng)絡，是確定的。通過融合betweenness的結構信息改進和節(jié)點內(nèi)容的改進，得到如表3的結果，這里取效果最好的一組數(shù)據(jù)β=0.7。

表3融合兩種信息改進的CNM算法和原始CNM算法的對比(β=0.7)

Methods/%PurityInversePurityFscoreBaseline(CNM)89．1879．3283．96ImproCNM(20)90．5780．2985．12ImproCNM(21)88．8976．3782．16ImproCNM(22)92．3077．9884．54ImproCNM(23)89．9486．9188．40ImproCNM(24)90．2881．5285．67ImproCNM(25)91．2985．8988．51ImproCNM(26)90．9176．7683．24ImproCNM(27)91．0481．5686．04ImproCNM(28)90．5379．0384．39ImproCNM(29)90．9581．2285．81ImproCNM(30)92．7679．2485．47ImproCNM(35)89．5274．8281．51

結果表明，融合兩種信息的結果會比僅使用結構信息的結果略微好一些。其中，最高F值88.51%僅比表1中的最高值88.28%提高0.23個百分點。這一結果符合Hsu對一般社會網(wǎng)絡進行分析的結論： 基于圖的關系特征已經(jīng)足夠有效，利用屬性特征的效果一般[21]。

最后，三組改進算法與CNM算法的運行時間如表4所示。根據(jù)之前的分析，三組改進算法的計算復雜度均為O(n2)，但融合兩種信息的算法顯然在時間上要大于前兩者，而真實社交網(wǎng)絡下CNM算法的復雜度大致為O(n*log2n)，實驗也論證了其速度明顯要快很多。

表4 CNM與三組實驗運行時間對比

5.2 結果分析

CNM算法能夠發(fā)現(xiàn)北京大學的大部分院系的社團結構，但人數(shù)少且內(nèi)部聯(lián)系弱的院系社團結構要弱一些(例如，考古文博學院)。使用3.2中的改進算法，通過刪除betweenness最高的若干條邊，能夠發(fā)現(xiàn)這些院系。當預處理中刪除25條邊時，一個18人的社團被算法找到，其中的17人都來自考古文博學院(參見表5和表6)。

表5 CNM算法的社團發(fā)現(xiàn)結果

表6改進的CNM算法的社團發(fā)現(xiàn)結果removednum=25(粗體表示新發(fā)現(xiàn)的院系)

社團編號社團節(jié)點個數(shù)節(jié)點正確的個數(shù)判定的學院151305298醫(yī)學部88265249信息科學技術學院152147143外國語學院…………1510431歷史學系2571817考古文博學院1711515信息管理系…………

不管如何刪除邊，一些院系仍然無法通過這一方法發(fā)現(xiàn)，如表7所示。其中，人數(shù)小于50的10個院系中，社會學系、哲學系、心理學系和藝術學院四個沒有被發(fā)現(xiàn)，這四個院系屬于人文社科院系。一般而言，人文社科學生相對活躍，社交圈更為大，容易和不同背景的學生成為好友；而理工科背景的學生相對單一，大多數(shù)好友是同院系的同學。

另一方面，人數(shù)大于50的17個院系中，僅有國際關系學院的學生(人數(shù)為93)難以被聚成一個團體。說明國際關系學院的內(nèi)聚程度不夠高，國關的學生視野廣闊，同其他學院的學生有大量的往來，喜好聯(lián)系。

表7北大本科27個學院的社團識別情況(按學院人數(shù)降序排列)

學院編號學院名稱學院人數(shù)不能被發(fā)現(xiàn)的學院27醫(yī)學部34025信息科學技術學院25921外國語學院14915經(jīng)濟學院13817法學院1231數(shù)學科學學院1183物理學院11416光華管理學院1126化學與分子工程學院10825元培學院957生命科學學院9314國際關系學院93√10中國語言文學系888城市與環(huán)境學院8424新聞與傳播學院674地球與空間科學學院5722馬克思主義學院5420政府管理學院442工學院4219社會學系42√11歷史學系3418信息管理系3413哲學系24√9心理學系20√12考古文博學院1826軟件與微電子學院1823藝術學院11√

6 總結與展望

本文主要研究社交網(wǎng)絡的社團結構發(fā)掘。一方面，使用了CNM算法發(fā)掘社團結構，引入邊的betweenness概念，通過刪除最高值的邊進行預處理來改進CNM算法。另一方面，除了社交網(wǎng)絡的結構信息之外，用戶的日志內(nèi)容也被用來輔助改進算法的精度。值得一提的是，本文以人人網(wǎng)上的北京大學學生數(shù)據(jù)進行實驗，挖掘出的社團結構在很大程度上解釋了北京大學院系學科的特點。在其他高校是否具有同樣的特點，還需要更多的實驗來驗證。當然，本文的社交對象僅僅關注了在校學生的社區(qū)交往情況，沒有展示其他層面的社交關系，比如，高校學生畢業(yè)后的工作關系。這些問題都將在后續(xù)的工作中加以考慮。

未來的工作包括： 如何確定該刪除多少條betweenness高的邊；引入更多的人人網(wǎng)用戶屬性(狀態(tài)、愛好等等)數(shù)據(jù)進行分析；引入其他的交互數(shù)據(jù)(比如評論和@等用戶交互信息)來進一步精化社團發(fā)現(xiàn)的精度；分析除高校外其他層面的社交網(wǎng)絡關系。

[1] WattsD J， Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442.

[2] Barabasi A L， Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439): 509-512.

[3] Girvan M， Newman M E J. Community Structure in Social and Biological Networks[J]. PNAS, 2001, 99(12): 7821-7826.

[4] Newman M E J， Girvan M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69 (2): 026113.

[5] Clauset A, Newman M E J, Moore C. Finding Community Structure in Very Large Networks[J]. Physical Review E, 2004, 70(6): 066111.

[6] Chen J, Community Mining: Discovering Communities in Social Networks[D]. Edmonton, Alberta: University of Alberta, 2010.

[7] Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distriuted Computing, 1998, 1(48): 96-129.

[8] Satuluri V, Parthasarathy S. Scalable graph clustering using stochastic flows: applications to community discovery[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). Paris, France: 2009: 737-746.

[9] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 1970(49): 291-307.

[10] Ng A, Jordan M, Weiss Y. On spectral clustering: analysis and an algorithm[C]//Proceedings of the 15th Annual Conference on Neural Information Processing Systems (NIPS 2001). Vancouver, British Columbia, Canada: 2001: 849-856.

[11] Nowicki K, Snijders T A B. Estimation and prediction for stochastic blockstructures[J]. Journal of the American Statistical Association, 2001, 96(455): 1077-1087.

[12] Wang X, Mohanty N, McCallum A. Group and Topic Discovery from Relations and Their Attributes[C]//Proceedings of the 19th Annual Conference on Neural Information Processing Systems (NIPS 2006). Whistler, B.C., Canada: 2006: 1449-1456.

[13] Zhang H, et al. An LDA-based Community Structure Discovery Approach for Large-Scale Social Networks[C]//Proceedings of the IEEE Conference on Intelligence and Security Informatics. New Brunswick, New Jersey: 2007: 200-207.

[14] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.

[15] Danon L, et al., Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9), 09008.

[16] Scott J, Social Network Analysis: a handbook. 2nd ed[M]. London: SAGE Publications, 2000: 208.

[17] Zhou Y, Cheng H, Yu J X. Clustering large attributed graphs: an efficient incremental approach[C]//Proceedings of the 10th IEEE International Conference on Data Mining (ICDM 2010). Sydney, Australia: 2010: 689-698.

[18] Zhou Y, Cheng H, Yu J X. Clustering large attributed information networks: an efficient incremental computing approach[J]. Data Mining and Knowledge Discovery Journal, 2012, 25(3): 450-477.

[19] Zhou Y, Liu L. Clustering Analysis in Large Graphs with Rich Attributes[J]. Data Mining: Foundations and Intelligent Paradigms, 2012, 23: 7-27.

[20] Hotho A, Staab S, Stumme G. WordNet improves Text Document Clustering[C]//Proceedings of the SIGIR 2003 Semantic Web Workshop. Toronto, Canada: Citeseer, 2003: 541-544.

[21] Hsu W, Lancaster J. Structural link analysis from user profiles and friends networks: A feature construction approach[C]//Proceedings of the 1th International AAAI Conference on Weblogs and Social Media (ICWSM 2007). Boulder, Colorado, USA: 2007: 75-80.