RoleTracker：基于角色的社會網(wǎng)絡演化分析方法

段松青等

摘要：已有的用戶角色研究中，不少學者定義了角色的數(shù)目和特征，對特定數(shù)據(jù)集取得了較好的效果，但存在的兩個問題：1）通用性較差，若更換數(shù)據(jù)集必須重新分析；2）現(xiàn)實世界中用戶行為和關(guān)系紛繁復雜，用戶角色多種多樣，難以通過人為的定義去描述和識別.因此，本文基于張量分解模型提出了一種用戶角色發(fā)現(xiàn)算法，它不僅能自動設(shè)定角色數(shù)量，而且能反映角色在指定時間段的行為特征.進一步將用戶角色延伸到社團角色，提出基于社團角色距離和節(jié)點重疊的社團演化分析方法.實驗結(jié)果表明，識別出的用戶角色其行為特征與實際情況吻合，提出的社團演化分析方法其效果也高于對比算法.

關(guān)鍵詞：社會網(wǎng)絡；角色發(fā)現(xiàn)；張量；社團演化

中圖分類號：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

復雜網(wǎng)絡（Complex network）是對現(xiàn)實世界的抽象，以節(jié)點代表各實體，以節(jié)點之間的邊代表實體之間的關(guān)系，它代表了呈現(xiàn)高度復雜性的網(wǎng)絡，并具有自組織、自相似、小世界、無標度等特性.社會網(wǎng)絡（Social network）是指社會行動者以及社會關(guān)系的集合[1]，關(guān)注的是人與人之間的互動和聯(lián)系.社會網(wǎng)絡分析（SNA，Social network analysis）是西方社會學學者基于數(shù)學方法﹑圖論對社會結(jié)構(gòu)和社會關(guān)系進行定量分析的方法，也是復雜網(wǎng)絡研究的一部分.

用戶角色識別是將具有類似行為特征或社會地位的用戶劃分為一類，并研究不同角色及所屬個體之間的差異性以及在網(wǎng)絡中發(fā)揮的作用.識別用戶的角色，有助于尋找特定的用戶（如輿論領(lǐng)袖），并對他們采取相應的措施（如監(jiān)控言論、推廣產(chǎn)品等）.社會網(wǎng)絡中角色識別是一個核心的研究點，主要包括：1）基于網(wǎng)絡結(jié)構(gòu)的研究，它根據(jù)結(jié)構(gòu)等價性[2]和計算規(guī)則結(jié)構(gòu)等價[3]，將具有相似地位的節(jié)點視為同一角色；2）基于行為模式的研究[4-5]，認為用戶行為的差異導致了不同的用戶角色，因此識別一組類似而有代表性的用戶行為是角色識別的突破口.

算法1的計算復雜度由2部分組成：

基于張量的角色發(fā)現(xiàn)，包括構(gòu)建鄰接張量，進行CP分解，利用誤差平方和與核一致性診斷指標選擇模型.主要耗時在CP分解環(huán)節(jié)，每次迭代的復雜度為Ο（k），k為張量中非零值個數(shù)，m次迭代和r次模型選擇，故復雜度為m·r·Ο（k）.

社團動態(tài)演化路徑分析，包括構(gòu)建時序圖，社團發(fā)現(xiàn)，社團演化路徑分析.其中，GN算法復雜度為Ο（n3），n為網(wǎng)絡中節(jié)點的個數(shù).假設(shè)每個時間片，社團數(shù)目均值為cn，共有t個時間片，則復雜度為（t-1）·Ο（cn2）.故總復雜度為（t-1）·Ο（cn2）+t·Ο（n3）.

獲得所有的社團演化鏈接關(guān)系后，可構(gòu)建所有時間片上各社團之間演化關(guān)系網(wǎng)，也可以查看某個社團的演化軌跡.

2.2.3評估社團演化路徑

.

3.2.3分析矩陣

每一列元素對應某一角色，以時間為橫軸，具體得分為縱軸，可得角色隨時間活躍度變化情況，見圖4.可以看出：

1）角色的活躍度隨時間變化呈現(xiàn)周期性，且與人每天的作息基本一致；

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

3）role6在第7天突然出現(xiàn)，且表現(xiàn)活躍；

4）role3，role4和role5的行為模式相對平穩(wěn). role5在演化全程中上下浮動較大，而role3最穩(wěn)定.

可推斷，在第7天到第8天的時間里發(fā)生了大事件，導致網(wǎng)絡中的幾個角色有很大變化，或消失或出現(xiàn).大多數(shù)角色的峰值出現(xiàn)在第3天到第5天，說明在這三天內(nèi)節(jié)點之間的聯(lián)系更頻繁，可能是對最后三天發(fā)生的大事件進行謀劃，故交流較多.

得到角色活躍度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張網(wǎng)絡圖分別運行PageRank算法，取前20%的作為核心節(jié)點.為了說明并不是依照任意標準構(gòu)建社團演化鏈接都是合理的，本文選用了兩種極限情況進行對比：相鄰時刻任意社團之間無演化鏈接，命名為“NoneCommLink”（B4）；相鄰時刻任意社團之間存在演化鏈接，命名為“AllCommLink”（B5）.

社團與之后所有時刻、在演化路徑中的社團相比，得到的平均成員穩(wěn)定度，越高越好.

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

1）B1：時刻1未能建立與時刻2的演化鏈接，導致節(jié)點交集為空；從時刻2起和B2算法幾乎重疊.

2）B2：僅僅在時刻1比B1算法占優(yōu)勢，說明算法改進效果欠佳.

3）B3：整個過程均高于B2，B1，在時刻1和8，有較高的增幅，說明本文在B2上的改進是有效的.

4）B4：效果最差，因為無演化鏈接，節(jié)點交集始終為空.

5）B5：整體效果倒數(shù)第二，由于演化鏈接太多，節(jié)點交集就是待比較社團自身大小，所占比例低.

6）I1：僅滿足本文一項要求時，效果最好，遠高于其它算法.從表4可見，除第1時刻有20個新增社團外，其余時刻僅有1個新增社團，即演化網(wǎng)上大部分社團都建立了演化鏈接關(guān)系.雖然I1鏈接數(shù)排名第二，但并不意味多多益善，排名第一的B5效果很差.

7）I2：排名第二，與I1接近，新增社團數(shù)比I1多了1個，鏈接數(shù)卻少了27%.

8）I3：效果較差，性能不穩(wěn)定，在B2附近上下震蕩，新增社團數(shù)遠高于I1，I2，但建立的鏈接數(shù)僅123條，排名倒數(shù)第二.說明I3標準過于嚴格，導致效果下降.

總之，本文所提算法，采用λ=[1，1，1]，θ取1，2時效果顯著優(yōu)于對比算法.

4結(jié)論

本文以網(wǎng)絡演化分析為研究對象，提出一種基于角色的社會網(wǎng)絡演化分析方法，用于分析動態(tài)網(wǎng)絡的時間特性、節(jié)點行為模式以及社團演化規(guī)律.實驗表明本方法不僅能劃分出合理的節(jié)點角色，還能較好地構(gòu)建社團之間的演化鏈接，形成演化路徑.下一步將根據(jù)社團演化情況研究節(jié)點發(fā)揮的作用及評估方式.

參考文獻

劉軍.社會網(wǎng)絡分析導論[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：一種基于核心的社區(qū)演化跟蹤算法[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]王丁弘.加權(quán)科研合作網(wǎng)絡個體及網(wǎng)絡整體演化分析[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.