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

段松青，于兴隆,吴 斌,王 柏

(1.中国软件评测中心 云计算促进中心,北京 100048; 2.北京邮电大学 计算机学院，北京 100876)

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

段松青1,2†，于兴隆2,吴 斌2,王 柏2

(1.中国软件评测中心 云计算促进中心,北京 100048; 2.北京邮电大学 计算机学院，北京 100876)

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

社会网络；角色发现；张量；社团演化

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

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

以用户为节点的社团演化，研究的是动态网络中用户联系紧密程度变化的原因、趋势、影响.动态网络社团演化的研究大约始于2004年，通常采用一种或多种研究方式：1)对各时间片的网络快照划分社团，判断相邻时刻社团之间的关系[6-7]； 2)将相邻时刻的网络整合后实行社团划分，再分离不同时刻的社团[8]；3)定义演化事件，以事件描述演化过程[9]；4)演化式社团发现算法[10]；5)对一段时间的网络快照划分社团，再依据时间顺序形成社团演化路径[11]；6)根据节点行为对网络的影响判断社团演化的趋势[12].

综合考虑节点角色和社团结构，本文提出了一种全新的网络演化分析方法RoleTracker，更关注于节点角色与社团功能模式的演化.本文主要贡献是：

1)通过构建邻接张量模型，提出了一种基于张量分解的节点角色发现方法.以张量分解模型识别动态网络中的用户角色，可自动设定角色数量，并反映角色在指定时间段的行为特征，对真实网络具有良好的适应性和实用性.

2)提出了一种基于社团角色距离及节点重叠的社团演化路径的度量模型，考虑了网络演化的拓扑结构特性及社团角色变化过程，其效果高于对比方法.

1 相关工作

1.1 符 号

本文涉及的符号见表1.

表1 符 号

1.2 张 量

张量(Tensor)是多维数组.张量分解模型包括：CP分解模型(CANDECOMP/PARAFAC Decomposition)[13-14]和Tucker分解模型[15].CP模型的基本原理如图1和式(1)，将张量X∈I×J×K分解成若干秩为1的张量之和.其中ar∈I，br∈J，cr∈K，是向量；∘为外积；E为残差，越小越好.

(1)

本文采用CP分解模型实现角色的划分.相类似的工作是Kolda[16]提出的TOPHITS模型，利用web链接构建张量模型挖掘话题信息，分析两个web页面针对某一话题的关联关系.

图1 CP模型原理图

1.3 社团发现

本文选用时间复杂度相对较高，但是模块度函数结果最高的GN算法[17]，其核心思想是：计算网络所有边的介数；不断删除介数最大的边并计算对应网络的模块度；根据模块度较大时的网络得到社团划分结果.

1.4 社团演化

Core-Common算法存在纰漏，无法处理图2的情况：已知社团1(含节点1，2，3，4，5)在时刻2分裂成社团2(含节点1，2)和社团3(含节点3，4)，需用演化路径节点匹配度的方式判断社团4(含节点1，2)与社团2，3的关联.从节点重叠的角度看，社团4显然是社团2的直接后继，与社团3不存在任何关系.但根据式(2) 社团2、社团3都达到了阈值，根据式(3)，演化路径节点匹配度都为2，算法失去了效力.

(2)

(3)

图2 社团演化示例

在评估社团演化路径划分效果时，文献[6]和[7]定义了核心节点稳定度及成员稳定度(MS，Member stability)指标，后者见式(4).

(4)

2 算法模型

RoleTracker的整体流程见图3：一边将数据存入张量模型，进行角色发现，并定义个体角色；另一边将数据转换为时序图，使用GN算法划分社团；再定义社团角色，分析社团演化路径.

2.1 角色发现

2.1.1 构建邻接张量

2．1．2 角色划分

1)CP分解

图3 RoleTracker流程图

2)计算角色活跃度

(5)

3)计算节点角色

H是节点与角色在权威性上的映射，每行代表一个节点，每列代表一种角色.Xi,j,k的分解遵循式(6)，由于Ei,j,k是变化的，且若将Tk,:固定，Hi,:的变化要参照Aj,:，而Aj,:又会被T和H的其它元素影响，因此H不同行元素之间大小是相对的，不能直接进行比较；H经过标准化后得到H′，其同行元素代表对应角色的比重.

(6)

(7)

(8)

2.2 社团演化

2.2.1 社团角色

(9)

(10)

计算社团ci和cj的角色距离CRDij，见式(11).

(11)2.2.2 构建社团演化路径

1)建立演化链接

(12)

(13)

(14)

(15)

演化链接的存储方式为：<源社团时间，源社团，目标社团，源社团演化链接加权得分>，例如〈k,i,j,li〉.

2)构建社团演化路径

构建社团演化路径的具体步骤见算法1：第1～4步使用张量分解模型确定节点角色；第5～6步准备社团信息；第7～17步是基于社团角色距离和节点重合度产生社团演化链接.

算法1社团演化路径构建算法．输入：T个时间片的网络结构Gt(k)|k=1，2…，T{}，λ，θ输出：两个相邻时间片上社团的演化链接关系集合ERSet步骤：1根据节点链接关系构建X；2对X进行CP分解，得到H∈ℝV×R，A∈ℝV×R，T∈ℝT×R；3根据T得到角色活跃度RW∈ℝR；4根据RW，H和A得到每个节点的角色；5获得每个时间片的社团集合Ct(k)|k=1，2…，T{}，及每个社团的节点；6计算每个社团的角色；7ERSet=null；8Fork=1：1：TDo9 Forct(k+1)jInCt(k+1)Do10 Forct(k)iInCt(k)Do11 计算社团角色距离CRDij；12 计算社团演化得分di1，di2，di3；13 EndFor14 得到社团演化链接向量Lt(k+1)j；15 若满足li≥θ(∀li∈Lt(k+1)j)，则将〈k，i，j，li〉存入ERSet；16 EndFor17EndFor18ReturnERSet；

算法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 评估社团演化路径

(16)

(17)

3 实验分析

3.1 数据集介绍

实验选用了VAST2008的Caralano/Vidro社会网络数据集，它含2006年6月10天内的400个独立的电话号码之间的通话数据.其中，在第8天发生了一个事件，使得通信网络发生了变化[20].

以用户为节点，通话关系为有向边，通话次数为边权值，构建每天的有向通话网络，基本特征见表2.

表2 VAST2008网络的特征

3.2 角色发现

3.2.1 构建邻接张量X

将每天划分成4个时间片(分别是0:00-5:59，6:00-11:59，12:00-17:59，18:00-23:59)，共有40个时间片，故可得X∈400×400×40.

3.2.2CP分解

对X进行CP分解，角色个数从1到8，分别计算残差平方和与核心一致性.当角色数目为6时，是满足条件的最优解.

分解得到H∈400×6，A∈400×6，T∈40×6.

3.2.3 分析T矩阵

T每一列元素对应某一角色，以时间为横轴，具体得分为纵轴，可得角色随时间活跃度变化情况，见图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.

以得分最大的角色标记该时间片，统计各角色所占时间片比例，则得到图5“T”所对应柱状图.角色1、2、6在较多时间片领先于其它角色，说明这三类角色在较多时间片上具有较高的爆发性.

图4 角色活跃图

3.2.4 分析H和A矩阵

将H和A标准化得到H′和A′，进而得到节点角色.图5“H”，“A”柱状图表明角色1，2，3人数较多.

图5 角色比例图

统计36种节点角色对应的节点数，得到表3，可见用户最多的角色是〈HRole1,ARole1〉，说明不少用户行为模式和角色1一致.而角色6对应的〈HRole6,ARole6〉用户只有2位，分别是300和309，他们都只在最后三天有通话记录.用户300被6个地点、15位用户呼叫14次，时长4.5小时；向6个地点、12位用户呼叫12次，时长3.7小时.而用户309被24个地点、47位用户呼叫145次，时长43.5小时；向5个地点、9位用户呼叫20次，时长5小时.用户300与309的行为模式与角色6完全一致，极有可能是恐怖份子在发动事件后收集情报的成员.因此本文用户角色划分方式是有效的.

表3 角色对应的节点数

3.3 社团演化路径分析

3.3.1 实验算法

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

表4 实验算法

(18)

本文所提算法，取λ=[1,1,1]，θ取1，2，3(对应I1，I2，I3)，代表满足三种标准中任1项、2项、全部时才构建演化链接.

3.3.2 计算各时刻社团平均的成员稳定度

各算法效果为I1≥I2≻B3≻B2≥B1和I3≻B5≻B4,具体分析如下．

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时效果显著优于对比算法.

天(a) B1，B2，B3，B4，B5，I1对比图

天(b) l1,l2,l3对比图

3.3.3 分析社团演化路径

图8 由I1得到的ct(1)9演化路径图

4 结 论

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

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

LIUJun.Anintroductiontosocialnetworkanalysis[M].Beijing:SocialSciencesAcademicPress,2004. (InChinese)

[2]EVERETTMG,BORGATTISP.Regularequivalence:generaltheory[J].JournalofMathematicalSociology, 1994, 19(1):29-52.

[3]BORGATTISP,EVERETTMG.Twoalgorithmsforcomputingregularequivalence[J].SocialNetworks, 1993, 15(4):361-376.

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

YANGWu,LIYang,LULing.Micro-bloghottopicsdetectionmethodbasedonuserroleorientation[J].JournalofComputerApplications, 2013, 33(11): 3076-3079. (InChinese)

[5]ZHUT,WANGB,WUB,etal. Role defining using behavior-based 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 Sheng-qi. CommTracker: A core-based algorithm of tracking community evolution[J]. Journal of Frontiers of Computer Science and Technology, 2009 (3): 282-292. (In Chinese)

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

WANG Ding-hong. Analysis about individual and the whole network based on weighted scientific co-authorship 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,etal. Community evolution mining in dynamic social networks[J]. Procedia-Social and Behavioral Sciences, 2011, 22(1): 49-58.

[10]SUN Y, TANG J, HAN J,etal. 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,etal. 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 N-way generalization of "Eckart-Young" decomposition[J]. Psychometrika, 1970, 35(3): 283-319.

[15]TUCKER L R. Some mathematical notes on three-mode factor analysis[J]. Psychometrika, 1966, 31(3): 279-311.

[16]KOLDA T G, BADER B W, KENNY J P. Higher-order 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 3-way modeling (PARAFAC) of fluorescence landscapes[R]. Frederiksberg: The Royal Veterinary and Agricultural University, 1999.

[20]YE Q, ZHU T, HU D,etal. Cell phone mini challenge award: Social network accuracy-exploring temporal communication in mobile call graphs[C]// Visual Analytics Science and Technology, 2008. Columbus: IEEE, 2008: 207-208.

RoleTracker: Method for Tracking the Role-Based Evolution in Social Network

DUAN Song-qing1,2†,YU Xing-long2,WU Bin2,WANG Bai2

(1. Cloud Testing Center, China Software Testing Center, Beijing 100048,China;2. School of Computer Science, Beijing Univ of Posts and Telecommunications, Beijing 100876,China)

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.

social network; role discovery; tensor; network evolution

1674-2974(2015)08-0132-09

2014-05-19

973国家重点基础研究发展计划项目(2013CB329603)；国家自然科学基金资助项目(71231002,61375058)，National Natural Science Foundation of China(71231002，61375058) ；北京市教育委员会共建项目专项资助；教育部-中国移动科研基金(MCM20123021)

段松青(1987-)，男，湖南郴州人，中国软件评测中心工程师，博士

†通讯联系人，E-mail:dsq58629@163.com

TP391

A