社团演化特征构造及预测

何 伟,胡学钢,李 磊,林耀进,李慧宗,潘剑寒

1(合肥工业大学 计算机与信息学院,合肥 230009)2(闽南大学 计算机科学学院,福建 漳州 363000)3(安徽理工大学 经济与管理学院,安徽 淮南 232001)4(江苏师范大学 计算机科学与技术学院,江苏 徐州 221116)

1 引 言

复杂网络是对多主体交互或关联的有效建模手段,现实世界中存在着大量的复杂网络系统,如 Internet 、WWW、社交网络、科学家合作网络、通信网络、蛋白质相互作用网络、基因调控网络等.信息技术的发展和海量数据的获取,催生了对大规模复杂网络数据分析的需求,对复杂网络的相关研究提出了挑战.

复杂网络中的社团结构描述了一种非均质连接特性,即网络由不同的节点簇所构成,簇内节点连接相对紧密,而簇间的连接相对稀疏[1].作为介于网络微观结构和宏观结构之间的中尺度结构,社团结构是网络中个体行为与整体功能之间的桥梁,对网络的结构和功能分析具有重要意义,针对社团结构物理意义和数学特性的研究也成为了近年来的热点[2].

传统的社团结构分析大多针对具有固定拓扑结构的静态网络,实际网络往往会随着时间推移发生改变.例如,在科学家合作网络中,新的研究者不断加入,已有研究者也会退出;研究者之间的合作可能变得紧密,也可能变得稀疏;不同领域的研究者会开展新的合作,原有合作也可能停止.这种变化导致网络中社团结构的持续演化,传统的静态方法无法用于动态性分析.

社团演化预测通过分析历史社团数据判断社团的未来趋势,对理解动态网络结构和功能具有重要意义.社团演化预测通常分为社团检测、演化事件检测、特征数据集构造、分类器训练几个基本步骤.随着社团检测、演化事件检测两类前置研究的发展,社团演化预测在近几年受到了越来越多的关注.在社团演化预测框架中,特征集构造是难点和核心问题之一.特征集的构建以表示时序网络拓扑结构的一组矩阵数据、不同网络快照中的社团隶属为输入,目标是提取出能够完整准确刻画社团结构、时序变化的特征集合.已有研究存在两个问题:一方面,没有完整考虑三种尺度(微观、介观、宏观)上的结构信息;另一方面,构造分类器时,采用固定长度的演化链数据作为输入,丢失了不同长度演化链中蕴含的时序信息.针对上述问题,本文提出了基于多元结构特征的社团演化预测方法,从演化数据中中提取社团的多尺度结构特征、时序特征、行为特征,并针对多重长度演化链构造集成分类器进行预测.

2 相关工作

2.1 动态网络及社团演化事件检测

Leskovec 等通过追踪网络拓扑特征的度量对网络演化进行了分析,实验结果表明,随着时间的推移和网络规模的扩大会发生一系列变化,如网络变得更加稠密、度分布指数增大、有效直径减小[3].2009年,Asur 针对动态网络中的节点定义了多种关键事件,提出了增量式的节点事件检测方法,并分析探讨了节点事件对社团事件之间的关联[4].

通过对科学家合作网络和通话网络进行动态分析,Palla 等发现社团的生命周期与社团内的动态行为以及社团规模密切相关,节点更替频繁的大社团和节点稳定的小社团能够存在更久[5,6].同时他们首次定义了六种社团演化事件,即社团的扩张、缩小、合并、分裂、形成和消亡.Takaffoli 提出了一种社团演化追溯及事件检测方法MODEC[7],该方法通过比较时序网络中社团的相似度来追踪演化中的社团,定义了相关规则用于判定Palla提出的六种演化事件.该研究还分析了时序网络中节点行为与社团演化事件之间的关联,提出少数影响力高的节点行为与演化事件之间相关性较高.在Palla提出的演化事件基础上,Bródka等提出了一种演化事件检测方法GED[8].该方法首先采用最大团过滤算法CPM找出静态社团结构,再通过比较连续时间片中社团的大小、相互包容度(inclusion)来发现连续社团.

Gliwa等定义了一组社团演化事件:稳定、规模变化、分离、附加、分裂、合并、分裂后合并、衰退[9].同时提出了一种社团演化追踪方法 SGCI,其基本思想是在固定长度的时间窗口中寻找持续性的社团,判断标准为社团在特定长度时间窗口内的存活时间超过阈值.

2.2 演化社团预测

Bródka在GED演化事件检测的基础上提出了社团演化预测的基本流程,并在四个实际网络数据上验证了该方法的可行性[10].该研究采用前序社团的演化事件和社团尺寸作为分类特征,预测精度较低,且受参数影响大.2013年,Bródka和Gliwa等合作,在GED和SGCI两种演化事件检测方法的基础上对博客圈进行社团演化预测[11].特征集构造抽取了多种社团的介观特征,包括社团的中心性、外链边密度、内聚性和尺寸,同时对比不同分类方法的预测准确率.实验表明该方法较Bródka的预测方法在准确性上有所提升,针对不同事件的分类器效果存在差异.在不同网络中的事件频次统计表明,两种演化事件检测方法都存在类别倾斜的问题,SGCI方法检测出大量的附加事件,GEB方法则检测出大量的分裂事件.后续工作中,Saganowski等结合社团结构信息和推文相关信息构造特征集,改进了分类流程,加入了特征选择和交叉验证步骤,将预测方法扩展到了带有向边的社交网络中[12].在构造特征集时,除原有介观特征外,额外考虑了社团内节点互惠性和多种微观特征聚合,微观特征包括节点度数、入度、出度、介数中心性、接近中心性、奇异值中心性,聚合方式包括求和、平均、最小和最大.该研究还对采用不同长度演化链数据的分类准确性进行了对比.对基于SGCI方法提取的连续社团,演化预测准确率随着演化链增长而逐渐提高;对基于GED方法提取的连续社团,准确率不一定随演化链增长而提高.

Diakidis等用同样的方法对2014世界杯相关的推文信息网络进行了社团演化预测,文章实验中实验对比了多种分类器的分类结果并分析了不同持续时间社团中各种特征的信息增益[13].

Takaffoli在MODEC演化模型的基础上提出了一种综合利用关键节点信息、社团结构信息、历史事件信息及社交网络主题信息的社团演化预测方法[14].实验采用了不同分类算法对邮件通信网络和科学家合作网络进行了预测,并考察了不同特征与各类演化事件的相关性.

2016年,Shahriari等采用GED方法检测演化事件,针对社团中关键节点信息、社团结构信息、时序和历史事件信息构造特征集并进行分类[15].通过对多类网络的预测和分析,找出了不同网络中持久社团的特点,以及不同特征与演化事件的相关性.

3 基于多元特征的社团演化预测方法

社团演化预测过程分为以下四步:提取网络快照中的社团结构;检测各时间窗口的演化事件,获取类别标签;根据社团演化数据构造特征数据集;用得到的数据集训练分类器,进行预测.

3.1 社团检测和演化事件检测

本文采用GED方法检测时序快照中的连续社团和演化事件[9].GED方法定义了图G1在图G2中的包容度I(G1,G2)作为判断一个图对另一个图的包含程度:

其中NIG1(x)为节点x在图G1中的影响力度量.乘积的左边项度量了图G2节点在图G1中所占比例,右边项度量了G2中共同节点与G1中节点在社团中影响力聚合是否相近,两者结合同时度量了数量和质量上的包含程度.以该度量为基础,GED定义并检测七种演化事件,包括维持、扩张、缩小、合并、分裂、形成和消亡.

3.2 特征集构造

为完整准确地刻画社团演化特性,本文抽取结构、时序、行为三类特征,其中结构特征反映三种不同尺度下的社团拓扑特性,时序特征反映从前序社团到后续社团的改变,行为特征为前一时间窗口发生的演化事件.

3.2.1 结构特征

1)微观结构特征

微观层面的节点行为是介观层面社团和宏观层面网络演化的根源,微观结构特征考察社团中节点的相关特性.网络中的节点占据不同的结构位、具有不同的行为,角色是对其结构位或行为的抽象,一些关键角色对社团演化有较大的影响[16].本文针对网络中心、社团核心、中介三种关键角色抽取特征.

网络中心是在整体网络中具有强影响力的节点,本文用概率分布接近正态分布的接近中心度(Closeness Centrality)作为节点的影响力度量,计算所有节点的接近中心度,求出分布均值μ和方差σ,将中心度大于阈值μ+2σ的节点(正态分布的95%置信区间为[μ-2σ,μ+2σ])视作网络中心.社团核心是社团内部的高影响力节点,本文采用与网络中心同样的方法在社团子图(仅包含内部连边)中进行提取.中介是连接不同社团的关键节点,本文采用CPM算法得到重叠社团,将重叠节点视作中介节点.表1列出了针对三类角色所构造的微观结构特征.

表1 社团微观结构特征Table 1 Microscopic structural feature of community

2)介观结构特征

介观结构特征考察社团自身的结构特征,表2列出了本文构造的介观结构特征.

其中内聚度为社团内边密度与社团外边密度的比值,对于图G(V,E)中的社团C(VC,EC),其与社团外节点的连接数为OEC,内聚度计算公式为:

图G(V,E)中节点i的集聚系数ClusterCoefi定义为i所有邻居所构成子图的边密度,全局集聚系数定义为图中所有节点集聚系数的均值:

度数中心度用于度量网络中节点度数的差异程度,图G(V,E)的度数中心度定义如下:

其中Di为节点i的度数,Dmax为所有所有节点度数的最大值.

表2 社团介观结构特征Table 2 Mesoscopic structural feature of community

3)宏观结构特征

宏观结构特征将社团看做整体,反映其在全局和局部环境中的影响力和相对特性,表3列出了本文抽取的宏观结构特征.

表3 社团宏观结构特征Table 3 Macroscopic structural feature of community

整体网络是社团所处的全局环境,为考察社团其在整个网络中的相关特性,首先构建社团网络(network of communities),即把社团看做节点,根据社团重叠与否确定节点间是否连边,重叠节点个数作为边的权重.本文采用社团节点在社团网络中的PageRank值度量社团在全局环境中的影响力,用微观、介观特征在所有社团中的归一化值度量社团的全局相对特性.

与社团相邻的所有社团及其连边构成其局部环境,首先需要构造由社团与其邻接社团构成的中心网络(ego network).本文采用社团在中心网络内的结构洞值[17]度量社团在局部环境中的影响力,采用微观、介观特征在中心网络中的归一化值度量社团的局部相对特性.

3.2.2 时序特征

时序特征包括前一时间窗口内发生的变动、社团已存活时间、后序社团与前序社团的相似和差异(表4).

表4 社团时序特征Table 4 Sequential feature of community

3.2.3 行为特征

行为特征为当前时间窗口的形成、维持、合并、分裂、尺寸变化(扩张和缩小)五类事件,表5列出了本文抽取的行为特征.

表5 社团行为特征Table 5 Behaviour feature of community

3.2.4 演化链特征样本

表6 预测事件及类别标签Table 6 Prediction event and classification label

3.3 分类器训练和预测

由于有多个类别标签,本文采用One vs Rest策略对五类事件分别构造分类器.已有方法针对所有事件都采取固定长度演化链训练分类器,但不同长度演化链蕴含的时序信息有差异,最优长度与网络类型、具体演化事件相关.使用固定长度演化链无法充分利用不同长度演化链中蕴含的信息,也不能适应各类网络和演化事件[12].为解决该问题,本文提出一种多长度演化链集成(Multi-length Evolution Chains Ensemble)分类方法,以不同长度演化链作为输入,分别构造分类器.基分类器的选择无特殊限定,此处采用Random Forest作为基分类器(图1).

图1 利用不同长度演化链的集成分类器MECEFig.1 Ensemble classifier MECE using multi-length evolution chains

4 实验分析

4.1 数据及预处理

本文使用邮件通信网络Enron*http://www.cs.cmu.edu/～enron/和科学家合作网络DBLP*http://projects.csail.mit.edu/dnd/DBLP/两个数据集,表7列出了数据集的基本统计信息.

Enron 数据集记录了安然公司32个月内的电子邮件通信.原始网络数据为有环有向多边无权图,每个节点代表一位安然员工,每条边代表一封邮件,方向为邮件发送方到接收方.本文对Enron数据集按月划分,节点集合为整个网络中最大弱连通分支中的节点,忽略边的方向,合并节点对之间的边并删除所有的环,每条边的权值为当前时间窗口内两点间的邮件数.

DBLP记录了32年间的计算机领域论文合作情况.原始网络数据为无环无向多边无权图,每个节点代表一位科学家,每条边代表一次论文合作.本文对DBLP数据集按年划分,节点集合为整个网络中最大连通分支中的节点,合并节点对之间的边,每条边的权值为当前时间窗口内两位科学家的合作次数.

其中γ∈(0,1)为衰减系数,离当前时间点越久远权值衰减越严重,此处令γ=0.5.

4.2 参数设置

4.3 实验结果

分别通过已有研究中的方法[10,14]与本文构造特征集合(分别表示为F_10、F_14、F),用RandomForest方法[18]和本文MECE方法构造分类器(分别为RF和MECE),其中RF分类器以长度为4的演化链作为输入数据,MECE方法中演化链最大长度为10,采用十折交叉验证求出平均F1值(表8,表9).

表8 Enron数据集上不同特征和分类器组合得到的平均F1值Table 8 Average F1 scores of Enron dataset classification results combining different features and classifier

表9 DBLP数据集上不同特征和分类器组合得到的平均F1值Table 9 Average F1 scores of Enron dataset classification results combining different features and classifier

由表8、表9中前三列数据可以看出,对于Enron和DBLP的五种事件,在同样采用RF分类器的情况下,本文所构造的特征能更有效地刻画社团特性,预测准确率更高.研究[10]中通过归一化和聚合节点特征获取了多种社团结构特征,但缺乏关键节点特征、时序特征(社团结构特征与前序社团结构特征的差异).研究[14]所构造的介观特征中则遗漏了社团尺寸这一关键特征,也没有构造社团的宏观特征.由表8、表9中后两列数据可看出,针对多重长度演化链的集成分类方法MECE具有更高的预测准确率.

5 结束语

社团演化预测研究对理解网络结构和功能具有重要意义,随着动态网络数据的不断累积,该研究将具有越来越广泛的应用前景.本文提出了一种基于多元特征构造的社团演化预测方法,通过在网络快照中构造社团多尺度结构特征、时序特征、行为特征,有效刻画了社团的结构和动态特性,并将不同长度的演化链数据用于集成分类器训练.实验表明了本文特征构造方法的有效性和分类方法的准确性.

：

[1] Girvan,Michelle,and Mark EJ Newman.Community structure in social and biological networks[C].Proceedings of the National Academy of Sciences 99,2002,12:7821-7826.

[2] Fortunato,Santo.Community detection in graphs[R].Physics Reports 486,2010,3:75-174.

[3] Leskovec Jure,Jon Kleinberg,Christos Faloutsos.Graphs over time:densification laws,shrinking diameters and possible explanations[C].Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Nining,ACM,2005:177-187.

[4] Asur Sitaram,Srinivasan Parthasarathy,Duygu Ucar.An event-based framework for characterizing the evolutionary behavior of interaction graphs[C].ACM Transactions on Knowledge Discovery from Data (TKDD)3,2009，4:16.

[5] Palla Gergely,Albert-László Barabási,et al.Community dynamics in social networks[J].Fluctuation and Noise Letters 7,2007,(3):273-287.

[6] Palla Gergely,Albert-László Barabási, Tamás Vicsek.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[7] Takaffoli,Mansoureh,Justin Fagnan,Farzad Sangi,et al.Tracking changes in dynamic information networks[C].Computational Aspects of Social Networks (CASoN),2011 International Conference on,IEEE,2011:94-101.

[8] Bródka Piotr,Stanisaw Saganowski,Przemysaw Kazienko.GED:the method for group evolution discovery in social networks[J].Social Network Analysis and Mining,2013:1-14.

[9] Gliwa Bogdan,Anna Zygmunt,Aleksander Byrski.Graphical analysis of social group dynamics[C].Computational Aspects of Social Networks (CASoN),2012 Fourth International Conference on,IEEE,2012:41-46.

[10] Bródka Piotr,Przemysaw Kazienko,Bartosz Kooszczyk.Predicting group evolution in the social network[C].International Conference on Social Informatics,Springer Berlin Heidelberg,2012:54-67.

[11] Gliwa Bogdan,Piotr Bródka,Anna Zygmunt,et al.Different approaches to community evolution prediction in blogosphere[C].Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining,ACM,2013:1291-1298.

[12] Saganowski Stanisaw,Bogdan Gliwa,Piotr Bródka,et al.Predicting community evolution in social networks[J].Entropy,2015,17(5):3053-3096.

[13] Diakidis Georgios,Despoina Karna,Dimitris Fasarakis-Hilliard,et al.Predicting the evolution of communities in social networks[C].Proceedings of the 5th International Conference on Web Intelligence,Mining and Semantics,ACM,2015.

[14] Takaffoli,Mansoureh,Reihaneh Rabbany,Osmar R.Zaïane.Community evolution prediction in dynamic social networks[C].Advances in Social Networks Analysis and Mining (ASONAM),2014 IEEE/ACM International Conference on,2014.

[15] Shahriari Mohsen,Stephen Gunashekar,Marven von Domarus,et al.Predictive analysis of temporal and overlapping community structures in social media[C].Proceedings of the 25th International Conference Companion on World Wide Web,International World Wide Web Conferences Steering Committee,2016.

[16] Fagnan Justin,Reihaneh Rabbany,Mansoureh Takaffoli,et al.Community dynamics:event and role analysis in social network analysis[C].International Conference on Advanced Data Mining and Applications,Springer International Publishing,2014.

[17] Burt,Ronald S.Structural hole[M].Harvard Business School Press,Cambridge,MA,1992.

[18] Breiman,Leo.Random forests[J].Machine Learning,2001,45 (1):5-32.