大型社交網絡社區結構演化

寶鵬慶，范磊

?

大型社交網絡社區結構演化

寶鵬慶，范磊

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

關鍵詞：社交網絡；社區結構；社區演化；

0 引言

以往的社區結構研究主要集中在從巨大的社交網絡拓

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

1 研究背景

1.1 在線社交網絡社區結構

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

1.2 動態社區結構

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

1.3 動態社區的研究方法及不足

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

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

2 社區演化建模

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

2.1 社區規模聚類模塊

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

圖1　社區成員成長率預測模型流程圖

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

2.2 社區特征提取模塊

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

表1　社區特征類別及其描述

社區的核邊緣結構如圖2所示：

圖2　核-邊緣結構示例

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

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

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

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

2.3 建立目標變量

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

2.4 數據采樣以及集成的CART決策樹分類器模塊

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

3 豆瓣小組數據

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

3.1 數據抓取

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

3.2 數據分析

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

圖3　社區成員數量概率密度圖（橫坐標為對數作標）

由于社交網絡的無尺度特性，所以其中橫坐標用對數坐標代替。豆瓣的整體社區規模要大于以往研究中使用的數據集[2-5]，豆瓣的數據集上的社區研究能體現出更大規模社區的一些特征。

3.3 參數選取

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

對于社區規模的聚類，如圖3所示，社區的規模在對數坐標下總體呈現橄欖型的分布，所以將其分為小型社區、中型社區以及大型社區是比較合理的劃分方法。對各規模的社區統計量的展示，如表2所示：

表2　豆瓣各規模社區統計量（保留一位小數）

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

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

4 實驗分析

4.1 提取社區特征

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

4.2 分類錯誤率分析

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

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

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

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

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

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

4.3 特征重要性分析

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

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

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

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

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

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

5 總結

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

參考文獻

[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-），上海，男，上海交通大學，信息安全工程學院，碩士研究生，研究方向：社交網絡、數據挖掘，上海，200240 范 磊（1975-），男，上海交通大學，信息安全工程學院，副教授，研究方向：數據挖掘，信息安全，上海，200240

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

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

中圖分類號：TP311

文獻標志碼：A