RoleTracker：基于角色的社会网络演化分析方法

段松青等

摘要：已有的用户角色研究中，不少学者定义了角色的数目和特征，对特定数据集取得了较好的效果，但存在的两个问题：1）通用性较差，若更换数据集必须重新分析；2）现实世界中用户行为和关系纷繁复杂，用户角色多种多样，难以通过人为的定义去描述和识别.因此，本文基于张量分解模型提出了一种用户角色发现算法，它不仅能自动设定角色数量，而且能反映角色在指定时间段的行为特征.进一步将用户角色延伸到社团角色，提出基于社团角色距离和节点重叠的社团演化分析方法.实验结果表明，识别出的用户角色其行为特征与实际情况吻合，提出的社团演化分析方法其效果也高于对比算法.

关键词：社会网络；角色发现；张量；社团演化

中图分类号：TP391 文献标识码：A

RoleTracker： Method for Tracking the RoleBased

Evolution in Social Network

DUAN Songqing1，2，YU Xinglong2，WU Bin2，WANG Bai2

（1. Cloud Testing Center， China Software Testing Center， Beijing100048，China；

2. School of Computer Science， Beijing Univ of Posts and Telecommunications， Beijing100876，China）

Abstract：In the existing study of user roles， many scholars have defined the number and characteristics of roles，which have achieved good results in a particular dataset. But there are two problems： 1） the generality is poor，i.e.， it must be reanalyzed if the dataset has been replaced； 2） in the real world， user's behavior and relationships are complicate and user roles are varied. So it's very difficult to describe and identify them with the artificial definition. So， this article proposed a user role found algorithm based on the tensor decomposition model. This algorithm can not only set the number of roles automatically， but also reflect the behavior characteristics of the role in specified period of time. Furthermore， this article extended user role to community roles and raised a community evolution analysis method based on the distance of community roles and the node overlapping. The experiment results indicate that the behavior characteristics of the identified roles are consistent with the fact， and the community evolution analysis method proposed has better effect than comparison algorithms.

Key words：social network； role discovery； tensor； network evolution

复杂网络（Complex network）是对现实世界的抽象，以节点代表各实体，以节点之间的边代表实体之间的关系，它代表了呈现高度复杂性的网络，并具有自组织、自相似、小世界、无标度等特性.社会网络（Social network）是指社会行动者以及社会关系的集合[1]，关注的是人与人之间的互动和联系.社会网络分析（SNA，Social network analysis）是西方社会学学者基于数学方法﹑图论对社会结构和社会关系进行定量分析的方法，也是复杂网络研究的一部分.

用户角色识别是将具有类似行为特征或社会地位的用户划分为一类，并研究不同角色及所属个体之间的差异性以及在网络中发挥的作用.识别用户的角色，有助于寻找特定的用户（如舆论领袖），并对他们采取相应的措施（如监控言论、推广产品等）.社会网络中角色识别是一个核心的研究点，主要包括：1）基于网络结构的研究，它根据结构等价性[2]和计算规则结构等价[3]，将具有相似地位的节点视为同一角色；2）基于行为模式的研究[4-5]，认为用户行为的差异导致了不同的用户角色，因此识别一组类似而有代表性的用户行为是角色识别的突破口.

算法1的计算复杂度由2部分组成：

基于张量的角色发现，包括构建邻接张量，进行CP分解，利用误差平方和与核一致性诊断指标选择模型.主要耗时在CP分解环节，每次迭代的复杂度为Ο（k），k为张量中非零值个数，m次迭代和r次模型选择，故复杂度为m·r·Ο（k）.

社团动态演化路径分析，包括构建时序图，社团发现，社团演化路径分析.其中，GN算法复杂度为Ο（n3），n为网络中节点的个数.假设每个时间片，社团数目均值为cn，共有t个时间片，则复杂度为（t-1）·Ο（cn2）.故总复杂度为（t-1）·Ο（cn2）+t·Ο（n3）.

获得所有的社团演化链接关系后，可构建所有时间片上各社团之间演化关系网，也可以查看某个社团的演化轨迹.

2.2.3评估社团演化路径

.

3.2.3分析矩阵

每一列元素对应某一角色，以时间为横轴，具体得分为纵轴，可得角色随时间活跃度变化情况，见图4.可以看出：

1）角色的活跃度随时间变化呈现周期性，且与人每天的作息基本一致；

2）role1和role第8天到第10天突然消失；

3）role6在第7天突然出现，且表现活跃；

4）role3，role4和role5的行为模式相对平稳. role5在演化全程中上下浮动较大，而role3最稳定.

可推断，在第7天到第8天的时间里发生了大事件，导致网络中的几个角色有很大变化，或消失或出现.大多数角色的峰值出现在第3天到第5天，说明在这三天内节点之间的联系更频繁，可能是对最后三天发生的大事件进行谋划，故交流较多.

得到角色活跃度RW1=0.166 5，RW2=0.167 5，RW3=0.194 5，RW4=0.181 9，RW5=0.176 8，RW6=0.112 8.可见总体活跃度高的是角色3，4，5，最弱的是角色6.

3.3社团演化路径分析

3.3.1实验算法

如表4，本文对比算法方式有CommTracker（B1）和CoreCommon（B2）；针对图2的问题，将式（2）变更为式（18），命名为“CoreCommon Modified”，以此作为B3.为便于比较，针对10张网络图分别运行PageRank算法，取前20%的作为核心节点.为了说明并不是依照任意标准构建社团演化链接都是合理的，本文选用了两种极限情况进行对比：相邻时刻任意社团之间无演化链接，命名为“NoneCommLink”（B4）；相邻时刻任意社团之间存在演化链接，命名为“AllCommLink”（B5）.

社团与之后所有时刻、在演化路径中的社团相比，得到的平均成员稳定度，越高越好.

各算法效果为I1≥ I2B3B2≥B1和I3B5B4，具体分析如下.

1）B1：时刻1未能建立与时刻2的演化链接，导致节点交集为空；从时刻2起和B2算法几乎重叠.

2）B2：仅仅在时刻1比B1算法占优势，说明算法改进效果欠佳.

3）B3：整个过程均高于B2，B1，在时刻1和8，有较高的增幅，说明本文在B2上的改进是有效的.

4）B4：效果最差，因为无演化链接，节点交集始终为空.

5）B5：整体效果倒数第二，由于演化链接太多，节点交集就是待比较社团自身大小，所占比例低.

6）I1：仅满足本文一项要求时，效果最好，远高于其它算法.从表4可见，除第1时刻有20个新增社团外，其余时刻仅有1个新增社团，即演化网上大部分社团都建立了演化链接关系.虽然I1链接数排名第二，但并不意味多多益善，排名第一的B5效果很差.

7）I2：排名第二，与I1接近，新增社团数比I1多了1个，链接数却少了27%.

8）I3：效果较差，性能不稳定，在B2附近上下震荡，新增社团数远高于I1，I2，但建立的链接数仅123条，排名倒数第二.说明I3标准过于严格，导致效果下降.

总之，本文所提算法，采用λ=[1，1，1]，θ取1，2时效果显著优于对比算法.

4结论

本文以网络演化分析为研究对象，提出一种基于角色的社会网络演化分析方法，用于分析动态网络的时间特性、节点行为模式以及社团演化规律.实验表明本方法不仅能划分出合理的节点角色，还能较好地构建社团之间的演化链接，形成演化路径.下一步将根据社团演化情况研究节点发挥的作用及评估方式.

参考文献

刘军.社会网络分析导论[M].北京：社会科学文献出版社，2004.

LIU Jun. An introduction to social network analysis[M].Beijing： Social Sciences Academic Press，2004. （In Chinese）

[2]EVERETT M G， BORGATTI S P. Regular equivalence： general theory[J]. Journal of Mathematical Sociology， 1994， 19（1）：29-52.

[3]BORGATTI S P， EVERETT M G. Two algorithms for computing regular equivalence[J]. Social Networks， 1993， 15（4）：361-376.

[4]杨武，李阳，卢玲.基于用户角色定位的微博热点话题检测方法[J].计算机应用，2013，33（11）：3076-3079.

YANG Wu， LI Yang， LU Ling. Microblog hot topics detection method based on user role orientation[J]. Journal of Computer Applications， 2013， 33（11）： 3076-3079. （In Chinese）

[5]ZHU T， WANG B， WU B， et al. Role defining using behaviorbased clustering in telecommunication network[J]. Expert Systems with Applications， 2011， 38（4）： 3902-3908.

[6]王翼，吴斌，杨胜琦.CommTracker：一种基于核心的社区演化跟踪算法[J].计算机科学与探索，2009（3）：282-292.

WANG Yi， WU Bin， YANG Shengqi. CommTracker： A corebased algorithm of tracking community evolution[J]. Journal of Frontiers of Computer Science and Technology， 2009 （3）： 282-292. （In Chinese）

[7]王丁弘.加权科研合作网络个体及网络整体演化分析[D].北京：北京邮电大学，2011.

WANG Dinghong. Analysis about individual and the whole network based on weighted scientific coauthorship network[D]. Beijing： Beijing University of Posts and Telecommunications， 2011. （In Chinese）

[8]PALLA G， BARABASI A L， VICSEK T. Quantifying social group evolution[J]. Nature， 2007， 446（7136）： 664-667.

[9]TAKAFFOLI M， SANGI F， FAGNAN J， et al. Community evolution mining in dynamic social networks[J]. ProcediaSocial and Behavioral Sciences， 2011， 22（1）： 49-58.

[10]SUN Y， TANG J， HAN J， et al. Community evolution detection in dynamic heterogeneous information networks[C]// Proceedings of the Eighth Workshop on Mining and Learning with Graphs. Washington： ACM， 2010： 137-146.

[11]ROSVALL M， BERGSTROM C T. Mapping change in large networks[J]. PloS one， 2010， 5（1）： e8694.

[12]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. Philadelphia：ACM， 2006： 44-54.

[13]HARSHMAN R A. Foundations of the PARAFAC procedure： Models and conditions for an "explanatory" multimodal factor analysis[J].UCLA Working Papers in Phonetics， 1970， 16（1）： 1-84.

[14]CARROLL J D， CHANGJ J. Analysis of individual differences in multidimensional scaling via an Nway generalization of "EckartYoung" decomposition[J]. Psychometrika， 1970， 35（3）： 283-319.

[15]TUCKER L R. Some mathematical notes on threemode factor analysis[J]. Psychometrika， 1966， 31（3）： 279-311.

[16]KOLDA T G， BADER B W， KENNY J P. Higherorder web link analysis using multilinear algebra[C]// Proceedings of the5th IEEE International Conference on Data Mining. Houston： IEEE， 2005： 5-14.

[17]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

[18]BRO R. PARAFACTutorial and applications[J]. Chemometrics and Intelligent Laboratory Systems， 1997， 38（2）： 149-171.

[19]BAUNSGAARD D. Factors affecting 3way modeling （PARAFAC） of fluorescence landscapes[R]. Frederiksberg： The Royal Veterinary and Agricultural University， 1999.

[20]YE Q， ZHU T， HU D， et al. Cell phone mini challenge award： Social network accuracyexploring temporal communication in mobile call graphs[C]// Visual Analytics Science and Technology， 2008. Columbus： IEEE， 2008： 207-208.