大型社交网络社区结构演化

宝鹏庆，范磊



大型社交网络社区结构演化

宝鹏庆，范磊

摘 要：大型社交网络已经成为互联网最主要的组成部分，是人们获取信息、分享交流的主要渠道。而其中的社区结构指的是社交网络中一些人呈现出的紧紧聚集的群落关系,同一社区内的用户往往拥有相同的兴趣话题。以往对社区结构的研究大多集中于使用无监督的社区发现算法在大型社交网络中给出用户的社区划分方法。而针对社交网络中社区对应的拓扑结构，重点在时间维度上考察以社区结构为基础的邻接图的固有特征对其社区成长的影响，利用有监督的机器学习方法，给出各个特征的重要性排名以及预测社区成员增长率的预测模型。研究数据集主要基于豆瓣小组功能。

关键词：社交网络；社区结构；社区演化；

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