寶鵬慶，范磊

?

大型社交網(wǎng)絡社區(qū)結構演化

寶鵬慶，范磊

摘 要：大型社交網(wǎng)絡已經(jīng)成為互聯(lián)網(wǎng)最主要的組成部分，是人們獲取信息、分享交流的主要渠道。而其中的社區(qū)結構指的是社交網(wǎng)絡中一些人呈現(xiàn)出的緊緊聚集的群落關系,同一社區(qū)內(nèi)的用戶往往擁有相同的興趣話題。以往對社區(qū)結構的研究大多集中于使用無監(jiān)督的社區(qū)發(fā)現(xiàn)算法在大型社交網(wǎng)絡中給出用戶的社區(qū)劃分方法。而針對社交網(wǎng)絡中社區(qū)對應的拓撲結構，重點在時間維度上考察以社區(qū)結構為基礎的鄰接圖的固有特征對其社區(qū)成長的影響，利用有監(jiān)督的機器學習方法，給出各個特征的重要性排名以及預測社區(qū)成員增長率的預測模型。研究數(shù)據(jù)集主要基于豆瓣小組功能。

關鍵詞：社交網(wǎng)絡；社區(qū)結構；社區(qū)演化；

0 引言

以往的社區(qū)結構研究主要集中在從巨大的社交網(wǎng)絡拓

撲圖中探索性的發(fā)現(xiàn)社區(qū)結構[1]，而從2006年開始由Lars Backstrom等開始了動態(tài)社區(qū)的研究[2]。本文研究社交網(wǎng)絡的社區(qū)結構，從已經(jīng)人工劃分好的社區(qū)結構中去尋找靜態(tài)的拓撲信息與動態(tài)的社區(qū)成長信息間的隱含關聯(lián)，為在線社區(qū)甚至真實社區(qū)的組織者和管理者提供社區(qū)更好成長的管理策略。

1 研究背景

1.1 在線社交網(wǎng)絡社區(qū)結構

社交網(wǎng)絡是由真實用戶在社交網(wǎng)絡平臺上構建起的復雜網(wǎng)絡，由于用戶間在真實世界中的關聯(lián)關系以及用戶在社交網(wǎng)絡平臺上構建起的關聯(lián)關系，會形成“物以類聚，人以群分”的聚集效應，而在一定范圍內(nèi)，聚集非常緊密的用戶以及用戶關聯(lián)關系的集合，我們稱之為社區(qū)結構。其他的命名方法也有“群組”、“簇”、“社團”[1-2]等等，本文則以社區(qū)結構來指代這一集合。

1.2 動態(tài)社區(qū)結構

近年來，這種動態(tài)的社區(qū)屬性逐漸被更多的學者關注和研究[2]。而動態(tài)社區(qū)結構的研究又可以大致分為兩類，第一是動態(tài)的社區(qū)結構發(fā)現(xiàn)算法的研究[3-4]，即從原先的某一時間節(jié)點上的算法推廣到擁有時間屬性的社區(qū)發(fā)現(xiàn)算法，旨在找出一些平穩(wěn)的不隨時間推移而顯著變化的核心社區(qū)結構。第二是社區(qū)結構的演化研究[2][5]，即針對社區(qū)結構中的拓撲信息的更新進行分析，旨在對其中的演化過程進行建模以及預測，從而對社區(qū)結構的變化做出量化的解釋。

1.3 動態(tài)社區(qū)的研究方法及不足

在以前的研究的預測模型中，加入了預測目標月前一個月的成長率作為預測模型的一個特征，而單單使用社區(qū)拓撲信息得到的模型準確率卻不盡如人意。此外，以前研究中并沒有將社區(qū)的成員數(shù)負增長作為一個單獨的目標變量進行預測，原因可能是在其數(shù)據(jù)集中不存在此類情況。

針對上述的不足之處，本文提出了兩個動態(tài)社區(qū)的研究目標，一是根據(jù)社交網(wǎng)絡的社區(qū)拓撲信息預測一個社區(qū)在短期以及長期情況下成員數(shù)量是增加還是減少，二是同樣根據(jù)拓撲信息預測一個社區(qū)在短期以及長期情況下成員數(shù)量增加的幅度是高于平均增長率還是低于平均增長率。通過在實際的數(shù)據(jù)集上的實驗研究，本文提取了基于社區(qū)拓撲信息的特征并以此構建分類器對上述問題進行解答，并分析了特征對于社區(qū)成長的影響。

2 社區(qū)演化建模

本文將給出一個基于CART決策樹分類的社區(qū)成長率預測模型的設計，其整體的系統(tǒng)架構如圖一所示。整體目標是基于集成的決策樹分類系統(tǒng)通過社區(qū)的的拓撲信息得到社區(qū)在未來一段時間內(nèi)社區(qū)成員數(shù)增長率的具體情況。以下每一小節(jié)將針對每個模塊進行詳細地設計描述。

2.1 社區(qū)規(guī)模聚類模塊

在不同規(guī)模的社區(qū)中，會呈現(xiàn)出不同的成長模式。較小規(guī)模的社區(qū)其成員數(shù)增長模式較多變，且變化量通常較大，而規(guī)模較大的社區(qū)則更多出現(xiàn)穩(wěn)步增長的模式。這是因為大型社區(qū)的基數(shù)已經(jīng)非常大，如果要獲得爆發(fā)式增長其需要增加的用戶量會非常大。由于社區(qū)成長在不同社區(qū)規(guī)模下呈現(xiàn)的截然不同的成長模式，需要將社區(qū)按初始規(guī)模分類后再進行預測模型的建立，如圖1所示：

圖1　社區(qū)成員成長率預測模型流程圖

在本模塊中，使用KMeans聚類算法對社區(qū)的初始成員數(shù)進行聚類分析。由于社交網(wǎng)絡的無尺度特性，故在本模塊中采用取對數(shù)后的成員數(shù)作為聚類算法的輸入。對不同總數(shù)量及分布不同的社區(qū)數(shù)據(jù)，應采用不同的聚類個數(shù)作為聚類算法的輸入。

2.2 社區(qū)特征提取模塊

根據(jù)每個社區(qū)的初始拓撲信息提取結構特征作為預測模型的輸入是對社區(qū)演化建模的重要過程。在以往的社區(qū)研究中已經(jīng)有許多的特征提取方法[2-5]。本文參考傳統(tǒng)的社區(qū)拓撲特征提取方法以及在實際數(shù)據(jù)中測試的具體情況使用了三大類的特征，分別用來衡量一個社區(qū)的核-邊緣結構，社區(qū)連通性以及社區(qū)聚集性如表1所示：

表1　社區(qū)特征類別及其描述

社區(qū)的核邊緣結構如圖2所示：

圖2　核-邊緣結構示例

其中每個圓點代表一個用戶，有向的箭頭代表一個從出發(fā)用戶到終點用戶的關注關系。用戶A、用戶B、用戶C、用戶D都是同一社區(qū)內(nèi)的用戶，而用戶E以及用戶F不是社區(qū)內(nèi)的用戶，不同的是用戶E關注著社區(qū)內(nèi)的用戶A，而用戶F沒有與社區(qū)內(nèi)用戶的關聯(lián)。對于所有類似用戶E這樣的沒有加入社區(qū)但是關注著社區(qū)內(nèi)某個成員的用戶，我們稱他們?yōu)樯鐓^(qū)的邊緣，而相對應的，社區(qū)內(nèi)的成員就稱為社區(qū)的核，這樣就構成了一個社區(qū)核-邊緣結構。邊緣用戶是社區(qū)的潛在加入者，相比較于與社區(qū)毫無關聯(lián)的用戶，他們更可能因為朋友的推薦等理由加入社區(qū)。所以表三中提出的核邊緣類別特征就旨在描述一個社區(qū)的邊緣的特征。

一個社區(qū)的核中會有一部分節(jié)點的入度和出度都為零，這些節(jié)點對于結構上的貢獻是最少的，稱之為無效節(jié)點，相反的剩下的節(jié)點稱為有效節(jié)點。平均邊緣粉絲個數(shù)的意義是每個社區(qū)內(nèi)用戶在邊緣中擁有的平均粉絲數(shù)量。而邊緣指向核的邊數(shù)指的是平均每個社區(qū)內(nèi)用戶擁有的社區(qū)外的被關注關系的數(shù)量。

另外一類特征是用來描述一個社區(qū)內(nèi)部聚集性的特征。全局聚集系數(shù)是一個網(wǎng)絡中閉三角形數(shù)量與所有可能的三元組的數(shù)量的比值，用來衡量一個網(wǎng)絡的整體聚集情況。研究中為了簡化聚集系數(shù)的處理，將有向圖轉(zhuǎn)換為無向圖后進行閉三角形比例的計算。衡量社區(qū)內(nèi)部聚集性的另一個特征是最大強連通子圖比例。強連通子圖指的是一個社區(qū)拓撲中用戶兩兩之間都存在一條路徑的子圖。其中節(jié)點數(shù)量最大的強連通子圖就是最大強連通子圖，其節(jié)點數(shù)量與整個社區(qū)的節(jié)點數(shù)量的比值就是最大強連通子圖比例。

最后一類特征用來衡量一個社區(qū)的連通性。社區(qū)內(nèi)兩個用戶之間互相關注稱為雙向邊，這樣的邊在連通其他社區(qū)用戶上起到了比較關鍵的作用。雙向邊的數(shù)量與總的社區(qū)內(nèi)的邊的數(shù)量的比值就是雙向邊比例，其值越高，說明社區(qū)的流通性越好。

2.3 建立目標變量

本文選擇的目標變量一共為4個，分別為某社區(qū)在短期內(nèi)成員是否會增長，長期內(nèi)成員是否會增長，短期內(nèi)成員增長率是否高于同規(guī)模的社區(qū)平均增長率以及長期內(nèi)成員增長率是否高于同規(guī)模的社區(qū)平均增長率。

2.4 數(shù)據(jù)采樣以及集成的CART決策樹分類器模塊

本模塊中將采用集成的決策樹CART作為分類算法的分類器。決策樹擁有比較良好的解釋性，其樹形結構的展示結果符合人類思維模式。在數(shù)據(jù)采樣模塊中，將有放回的從加入目標變量后的同規(guī)模社區(qū)的特征數(shù)據(jù)中抽取等比例70%的正負樣本作為訓練集對決策樹進行訓練。重復采樣100次，建立100棵互相獨立的決策樹，并使用余下的30%數(shù)據(jù)作為評估該分類器錯誤率的測試集。最終的預測模型由100棵決策樹集成，對于一條測試數(shù)據(jù)，將由100棵決策樹進行投票，最終占比較大的結果為最終的預測模塊給出的目標變量的預測值。

3 豆瓣小組數(shù)據(jù)

本文的實驗數(shù)據(jù)集來自真實社交網(wǎng)絡，豆瓣的小組功能(http://www.douban.com/group/explore)所對應的數(shù)據(jù)。其中本研究抽取的信息是每個小組包含的成員ID(一個字符串)以及他們之間的互相關注的關系。在豆瓣中，用戶的關注關系是有向的。為了與社區(qū)結構的概念對應，在下文中，將用社區(qū)來代替豆瓣小組的說法。

3.1 數(shù)據(jù)抓取

數(shù)據(jù)存儲在本地的Mysql數(shù)據(jù)庫中。通過對社區(qū)數(shù)字ID的遍歷，得到豆瓣社區(qū)的總數(shù)量為37.8萬。由于其中有很大部分社區(qū)已經(jīng)沒有任何更新即處在死亡狀態(tài)，對我們的研究沒有意義，所以需要將他們篩選出數(shù)據(jù)集。這里參考的標準是每個社區(qū)中用戶最后發(fā)帖的日期，定義閾值為5天，即在第一次快照的5天之內(nèi)有成員發(fā)帖行為的社區(qū)我們認為他仍然存活，可以作為研究對象。經(jīng)過這一篩選，剩余1.5萬的總社區(qū)數(shù)量。這里總共涉及的用戶為1.19億，總的關系數(shù)量為1.22億。

3.2 數(shù)據(jù)分析

在所有社區(qū)中，第一次快照時社區(qū)成員數(shù)最少為10，最大為80萬，分布如圖3所示：

圖3　社區(qū)成員數(shù)量概率密度圖（橫坐標為對數(shù)作標）

由于社交網(wǎng)絡的無尺度特性，所以其中橫坐標用對數(shù)坐標代替。豆瓣的整體社區(qū)規(guī)模要大于以往研究中使用的數(shù)據(jù)集[2-5]，豆瓣的數(shù)據(jù)集上的社區(qū)研究能體現(xiàn)出更大規(guī)模社區(qū)的一些特征。

3.3 參數(shù)選取

在本研究中需要具體確定的參數(shù)有社區(qū)規(guī)模聚類的聚類數(shù)，目標變量中長期以及短期的時間節(jié)點的定義以及CART決策樹的一些分類器參數(shù)。

對于社區(qū)規(guī)模的聚類，如圖3所示，社區(qū)的規(guī)模在對數(shù)坐標下總體呈現(xiàn)橄欖型的分布，所以將其分為小型社區(qū)、中型社區(qū)以及大型社區(qū)是比較合理的劃分方法。對各規(guī)模的社區(qū)統(tǒng)計量的展示，如表2所示：

表2　豆瓣各規(guī)模社區(qū)統(tǒng)計量（保留一位小數(shù)）

對于目標變量中的短期以及長期的定義，由于豆瓣數(shù)據(jù)集本身采集時間有限，所以對于社區(qū)結構的長期影響在本研究定為采集的最大值240天。而在短期增長率的時間節(jié)點設定上，為排除上小節(jié)中論述的用戶突增現(xiàn)象，設定短期增長率為第一次快照后40天社區(qū)用戶數(shù)的增長率。在這個時間點上，95%社區(qū)的成員增長率處在平穩(wěn)的水平上，即和上一時間點以及下一時間點的增長率處在同一水平上。

分類器的具體參數(shù)設置經(jīng)過在數(shù)據(jù)集上的反復測試，在先剪枝的過程中使用當某個葉子節(jié)點中的樣本書低于50時便不再分裂，后剪枝的過程中使用代價復雜度為0.001作為剪枝標準。

4 實驗分析

4.1 提取社區(qū)特征

儲存在本地的拓撲數(shù)據(jù)實際是所有社區(qū)的數(shù)據(jù)的并集，去除了所有社區(qū)的公共部分?？紤]到需要對每個社區(qū)都進行特征的提取，所以每次我們并行地從整個拓撲數(shù)據(jù)中抽取若干個社區(qū)的詳細數(shù)據(jù)進行計算，待返回結果后再進行下一個社區(qū)的特征計算。經(jīng)過測試，在配備Intel Xeon E5處理器以及內(nèi)存為32G的服務器上，對于節(jié)點數(shù)在百萬級別的計算同時開8個進程可以達到比較好的效果。

4.2 分類錯誤率分析

對模型進行訓練并對測試集進行測試，得到如下的模型分類錯誤率列如表3所示：

表3　模型分類錯誤率（保留三位小數(shù)）

從3個維度進行模型分類錯誤率的分析。第一是預測成員數(shù)是否增長的錯誤率要低于預測成員數(shù)是否大幅增長的錯誤率。說明對成員增長率小于零的社區(qū)，它們在拓撲結構上呈現(xiàn)的模式是比較明顯的，使用拓撲信息可以比較簡單地將那些成員數(shù)量負增長的社區(qū)預測出來。第二是對社區(qū)長期成員數(shù)增長率的預測的錯誤率要高于對社區(qū)短期成員增長率的預測。原因是第一次快照時的社區(qū)拓撲對社區(qū)成長的影響會隨時間的推移而逐漸減弱以及在社區(qū)的長期發(fā)展過程中可能會發(fā)生在第二節(jié)中提到的用戶突增現(xiàn)象，而這種現(xiàn)象是無法在本模型中得到預測的。這與Leskovec等在Ning數(shù)據(jù)集上得到的結論是吻合的[5]。第三是在研究社區(qū)成員數(shù)是否會增長的預測模型中，社區(qū)規(guī)模越大錯誤率越低，說明在大型社區(qū)中的成員衰退現(xiàn)象是最容易被發(fā)現(xiàn)的，而在小型社區(qū)中，這一現(xiàn)象呈現(xiàn)的模式可能會比較多樣。

與其他算法的對比如表4所示：

表4　模型平均分類錯誤率（保留三位小數(shù)）

其中L算法指Leskovec等人在[5]中使用的預測模型，B算法指BackStrom等人在[2]中使用的預測模型。由于使用的目標變量略有區(qū)別，這里僅對平均的模型錯誤率進行比較。在B模型中，研究者對目標變量進行了只取頭尾兩部分的樣本篩選的做法，從而提高了精度[2]，其并沒有給出取平均值做為閾值的預測模型。另外。B模型中沒有取短期或長期作為研究分割。可以發(fā)現(xiàn)，與L模型相比，無論短期或是長期本模型都取得了錯誤率上的減少，而基本與B模型經(jīng)過樣本篩選的錯誤率持平。

4.3 特征重要性分析

圖4給出了決策樹的樹模型示例，如圖4所示：

圖4　型社區(qū)短期成員是否增長的預測模型樹形圖

針對每一個分類器都可以給出具體的分裂信息，此處為了方便展示，只展示層高為二的用來預測小型社區(qū)中短期成員是否增長的預測模型。其中葉子節(jié)點處的1代表成員增長率為正，0代表成員增長率為負。

從樹形圖中可以發(fā)現(xiàn)，在預測一個小型社區(qū)短期內(nèi)成員是否會增長的問題中，有效節(jié)點比例以及雙向邊比例占了比較大的因素。當一個小型社區(qū)內(nèi)互聯(lián)的用戶越多時，該社區(qū)反而更容易損失用戶。一個直觀的理解就是在小型社區(qū)中，如果形成了一個小團體，那么不屬于該小團體的用戶可能因為無法融入小團體而退出社區(qū)。所以在社區(qū)創(chuàng)立的初始階段，社區(qū)管理者應該以更多優(yōu)秀的內(nèi)容來贏取更多原本與社區(qū)無聯(lián)系的用戶，而不用專注于提升社區(qū)的社交屬性。

而同樣在預測短期成員是否增長的問題下，大型社區(qū)與中型社區(qū)中最主要的決定因素是平均的邊緣粉絲數(shù)量，分隔閾值約等于45。也就是那些平均邊緣粉絲數(shù)量低于45的社區(qū)，由于社區(qū)的邊緣粉絲規(guī)模太小，更容易造成社區(qū)內(nèi)成員的減少。這與在小型社區(qū)中發(fā)現(xiàn)的模式是截然不同的。

通過分析對應規(guī)模的社區(qū)在某個具體問題上的決策樹模型，可以獲得該類社區(qū)出現(xiàn)成員流失以及成員增速緩慢的最主要原因以及具體的分裂閾值。通過組織社區(qū)活動來調(diào)整社區(qū)拓撲結構，將有效地改善社區(qū)的管理狀況使社區(qū)獲得更好的成長。

5 總結

通過對在線社交網(wǎng)絡豆瓣的小組功能的數(shù)據(jù)抓取和分析，本研究得到了一系列針對社區(qū)拓撲結構與其成長模式之間的關聯(lián)。給出了一種對社區(qū)演化建模的方法，包括社區(qū)拓撲的特征提取方法、演化模型的建立方法以及在真實數(shù)據(jù)集上的驗證分析。研究結果可以對社區(qū)的管理者和組織者在社區(qū)發(fā)展的策略上產(chǎn)生指導意義。動態(tài)社區(qū)的演化研究更符合社交網(wǎng)絡的特性，針對社區(qū)結構的演化還可以提出更精細更準確地預測以及分析模型，這也是本文作者未來繼續(xù)研究的指導方向。

參考文獻

[1] Newman M. E. J Detecting community structure in networks, Eur. Phys[J]. J. B 38, 321-330 (2004).

[2] Backstrom L, Huttenlocher D, Kleinberg J, et al. Group formation in large social networks: membership, growth, and evolution[C]//Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006: 44-54.

[3] Gong M G, Zhang L J, Ma J J, et al. Community detection in dynamic social networks based on multiobjective immune algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467.

[4] Giatsoglou M, Vakali A. Capturing social data evolution using graph clustering[J]. IEEE Internet Computing, 2013 (1): 74-79.

[5] Kairam S R, Wang D J, Leskovec J. The life and death of online groups: Predicting group growth and longevity[C]//Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012: 673-682.

Evolution of Communities in Large Social Network

Bao Pengqing, Fan Lei
(Department of Information Security Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

Abstract:As a main part of Internet, large social network has become the main platform for people to gain information and share their thoughts in recent years. Community in social network indicates the group of users who are connected densely and share same topics and interests. Past works focus on the unsupervised learning algorithm of exploring the potential community structures. While this paper studies the structure of communities which are already labeled in social network, and gives both a prediction model to predict the community growth and a rank of feature importance. The data are built on Douban group.

Key words:Social Network; Community Structure; Community Evolution

收稿日期：（2015.10.20）

作者簡介：寶鵬慶（1991-），上海，男，上海交通大學，信息安全工程學院，碩士研究生，研究方向：社交網(wǎng)絡、數(shù)據(jù)挖掘，上海，200240 范 磊（1975-），男，上海交通大學，信息安全工程學院，副教授，研究方向：數(shù)據(jù)挖掘，信息安全，上海，200240

基金項目：上海市基礎研究重大重點項目項目（13JC1403500）

文章編號：1007-757X(2016)02-0039-04

中圖分類號：TP311

文獻標志碼：A