范 超，王厚峰

(1. 北京大學(xué) 軟件與微電子學(xué)院，北京 100871； 2. 北京大學(xué) 計(jì)算語言學(xué)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871)

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

3 CNM算法和改進(jìn)

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

3.1 CNM算法

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

3.2 引入網(wǎng)絡(luò)結(jié)構(gòu)信息改進(jìn)CNM算法

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

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

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

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

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

算法描述如下：

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

輸出：劃分的社團(tuán)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的計(jì)算復(fù)雜度為O(mn)；每次刪除betweenness最高的邊的時(shí)間復(fù)雜度為O(m)，總的復(fù)雜度為O(αm)；第三步CNM算法的計(jì)算復(fù)雜度為O(m*d*logn)。真實(shí)的網(wǎng)絡(luò)中，有m～n、d～logn，因此，改進(jìn)算法的復(fù)雜度為O(n2)。

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

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

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

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

這里，特征詞的權(quán)重wij采用標(biāo)準(zhǔn)的tf.idf的計(jì)算方法，如式(3)所示。

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

(3)

其中nj> 0

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

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

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

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

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

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

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

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

4.2 標(biāo)準(zhǔn)答案的構(gòu)建和評價(jià)方法

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

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

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

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

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

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

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

5. 通過人工的方法標(biāo)記剩余的一些用戶。

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

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

5 實(shí)驗(yàn)結(jié)果和分析

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

5.1 實(shí)驗(yàn)結(jié)果

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

5.1.1 使用網(wǎng)絡(luò)結(jié)構(gòu)信息改進(jìn)的結(jié)果

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

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

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

表1使用betweenness改進(jìn)的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)容信息改進(jìn)的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 使用結(jié)構(gòu)和內(nèi)容信息改進(jìn)的結(jié)果

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

表3融合兩種信息改進(jìn)的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

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

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

表4 CNM與三組實(shí)驗(yàn)運(yùn)行時(shí)間對比

5.2 結(jié)果分析

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

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

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

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

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

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

表7北大本科27個(gè)學(xué)院的社團(tuán)識(shí)別情況(按學(xué)院人數(shù)降序排列)

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

6 總結(jié)與展望

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

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

[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.