RoleTracker:基于角色的社會網(wǎng)絡(luò)演化分析方法*

段松青，于興隆,吳 斌,王 柏

(1.中國軟件評測中心 云計算促進中心,北京 100048; 2.北京郵電大學 計算機學院，北京 100876)

RoleTracker:基于角色的社會網(wǎng)絡(luò)演化分析方法*

段松青1,2?，于興隆2,吳 斌2,王 柏2

(1.中國軟件評測中心 云計算促進中心,北京 100048; 2.北京郵電大學 計算機學院，北京 100876)

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

社會網(wǎng)絡(luò)；角色發(fā)現(xiàn)；張量；社團演化

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

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

以用戶為節(jié)點的社團演化，研究的是動態(tài)網(wǎng)絡(luò)中用戶聯(lián)系緊密程度變化的原因、趨勢、影響.動態(tài)網(wǎng)絡(luò)社團演化的研究大約始于2004年，通常采用一種或多種研究方式：1)對各時間片的網(wǎng)絡(luò)快照劃分社團，判斷相鄰時刻社團之間的關(guān)系[6-7]； 2)將相鄰時刻的網(wǎng)絡(luò)整合后實行社團劃分，再分離不同時刻的社團[8]；3)定義演化事件，以事件描述演化過程[9]；4)演化式社團發(fā)現(xiàn)算法[10]；5)對一段時間的網(wǎng)絡(luò)快照劃分社團，再依據(jù)時間順序形成社團演化路徑[11]；6)根據(jù)節(jié)點行為對網(wǎng)絡(luò)的影響判斷社團演化的趨勢[12].

綜合考慮節(jié)點角色和社團結(jié)構(gòu)，本文提出了一種全新的網(wǎng)絡(luò)演化分析方法RoleTracker，更關(guān)注于節(jié)點角色與社團功能模式的演化.本文主要貢獻是：

1)通過構(gòu)建鄰接張量模型，提出了一種基于張量分解的節(jié)點角色發(fā)現(xiàn)方法.以張量分解模型識別動態(tài)網(wǎng)絡(luò)中的用戶角色，可自動設(shè)定角色數(shù)量，并反映角色在指定時間段的行為特征，對真實網(wǎng)絡(luò)具有良好的適應性和實用性.

2)提出了一種基于社團角色距離及節(jié)點重疊的社團演化路徑的度量模型，考慮了網(wǎng)絡(luò)演化的拓撲結(jié)構(gòu)特性及社團角色變化過程，其效果高于對比方法.

1 相關(guān)工作

1.1 符 號

本文涉及的符號見表1.

表1 符 號

1.2 張 量

張量(Tensor)是多維數(shù)組.張量分解模型包括：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分解模型實現(xiàn)角色的劃分.相類似的工作是Kolda[16]提出的TOPHITS模型，利用web鏈接構(gòu)建張量模型挖掘話題信息，分析兩個web頁面針對某一話題的關(guān)聯(lián)關(guān)系.

圖1 CP模型原理圖

1.3 社團發(fā)現(xiàn)

本文選用時間復雜度相對較高，但是模塊度函數(shù)結(jié)果最高的GN算法[17]，其核心思想是：計算網(wǎng)絡(luò)所有邊的介數(shù)；不斷刪除介數(shù)最大的邊并計算對應網(wǎng)絡(luò)的模塊度；根據(jù)模塊度較大時的網(wǎng)絡(luò)得到社團劃分結(jié)果.

1.4 社團演化

Core-Common算法存在紕漏，無法處理圖2的情況：已知社團1(含節(jié)點1，2，3，4，5)在時刻2分裂成社團2(含節(jié)點1，2)和社團3(含節(jié)點3，4)，需用演化路徑節(jié)點匹配度的方式判斷社團4(含節(jié)點1，2)與社團2，3的關(guān)聯(lián).從節(jié)點重疊的角度看，社團4顯然是社團2的直接后繼，與社團3不存在任何關(guān)系.但根據(jù)式(2) 社團2、社團3都達到了閾值，根據(jù)式(3)，演化路徑節(jié)點匹配度都為2，算法失去了效力.

(2)

(3)

圖2 社團演化示例

在評估社團演化路徑劃分效果時，文獻[6]和[7]定義了核心節(jié)點穩(wěn)定度及成員穩(wěn)定度(MS，Member stability)指標，后者見式(4).

(4)

2 算法模型

RoleTracker的整體流程見圖3：一邊將數(shù)據(jù)存入張量模型，進行角色發(fā)現(xiàn)，并定義個體角色；另一邊將數(shù)據(jù)轉(zhuǎn)換為時序圖，使用GN算法劃分社團；再定義社團角色，分析社團演化路徑.

2.1 角色發(fā)現(xiàn)

2.1.1 構(gòu)建鄰接張量

2．1．2 角色劃分

1)CP分解

圖3 RoleTracker流程圖

2)計算角色活躍度

(5)

3)計算節(jié)點角色

H是節(jié)點與角色在權(quán)威性上的映射，每行代表一個節(jié)點，每列代表一種角色.Xi,j,k的分解遵循式(6)，由于Ei,j,k是變化的，且若將Tk,:固定，Hi,:的變化要參照Aj,:，而Aj,:又會被T和H的其它元素影響，因此H不同行元素之間大小是相對的，不能直接進行比較；H經(jīng)過標準化后得到H′，其同行元素代表對應角色的比重.

(6)

(7)

(8)

2.2 社團演化

2.2.1 社團角色

(9)

(10)

計算社團ci和cj的角色距離CRDij，見式(11).

(11)2.2.2 構(gòu)建社團演化路徑

1)建立演化鏈接

(12)

(13)

(14)

(15)

演化鏈接的存儲方式為：<源社團時間，源社團，目標社團，源社團演化鏈接加權(quán)得分>，例如〈k,i,j,li〉.

2)構(gòu)建社團演化路徑

構(gòu)建社團演化路徑的具體步驟見算法1：第1～4步使用張量分解模型確定節(jié)點角色；第5～6步準備社團信息；第7～17步是基于社團角色距離和節(jié)點重合度產(chǎn)生社團演化鏈接.

算法1社團演化路徑構(gòu)建算法．輸入：T個時間片的網(wǎng)絡(luò)結(jié)構(gòu)Gt(k)|k=1，2…，T{}，λ，θ輸出：兩個相鄰時間片上社團的演化鏈接關(guān)系集合ERSet步驟：1根據(jù)節(jié)點鏈接關(guān)系構(gòu)建X；2對X進行CP分解，得到H∈?V×R，A∈?V×R，T∈?T×R；3根據(jù)T得到角色活躍度RW∈?R；4根據(jù)RW，H和A得到每個節(jié)點的角色；5獲得每個時間片的社團集合Ct(k)|k=1，2…，T{}，及每個社團的節(jié)點；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部分組成：

基于張量的角色發(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)絡(luò)中節(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 評估社團演化路徑

(16)

(17)

3 實驗分析

3.1 數(shù)據(jù)集介紹

實驗選用了VAST2008的Caralano/Vidro社會網(wǎng)絡(luò)數(shù)據(jù)集，它含2006年6月10天內(nèi)的400個獨立的電話號碼之間的通話數(shù)據(jù).其中，在第8天發(fā)生了一個事件，使得通信網(wǎng)絡(luò)發(fā)生了變化[20].

以用戶為節(jié)點，通話關(guān)系為有向邊，通話次數(shù)為邊權(quán)值，構(gòu)建每天的有向通話網(wǎng)絡(luò)，基本特征見表2.

表2 VAST2008網(wǎng)絡(luò)的特征

3.2 角色發(fā)現(xiàn)

3.2.1 構(gòu)建鄰接張量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分解，角色個數(shù)從1到8，分別計算殘差平方和與核心一致性.當角色數(shù)目為6時，是滿足條件的最優(yōu)解.

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

3.2.3 分析T矩陣

T每一列元素對應某一角色，以時間為橫軸，具體得分為縱軸，可得角色隨時間活躍度變化情況，見圖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)絡(luò)中的幾個角色有很大變化，或消失或出現(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.

以得分最大的角色標記該時間片，統(tǒng)計各角色所占時間片比例，則得到圖5“T”所對應柱狀圖.角色1、2、6在較多時間片領(lǐng)先于其它角色，說明這三類角色在較多時間片上具有較高的爆發(fā)性.

圖4 角色活躍圖

3.2.4 分析H和A矩陣

將H和A標準化得到H′和A′，進而得到節(jié)點角色.圖5“H”，“A”柱狀圖表明角色1，2，3人數(shù)較多.

圖5 角色比例圖

統(tǒng)計36種節(jié)點角色對應的節(jié)點數(shù)，得到表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完全一致，極有可能是恐怖份子在發(fā)動事件后收集情報的成員.因此本文用戶角色劃分方式是有效的.

表3 角色對應的節(jié)點數(shù)

3.3 社團演化路徑分析

3.3.1 實驗算法

如表4，本文對比算法方式有CommTracker(B1)和Core-Common(B2)；針對圖2的問題，將式(2)變更為式(18)，命名為“Core-Common Modified”，以此作為B3.為便于比較，針對10張網(wǎng)絡(luò)圖分別運行PageRank算法，取前20%的作為核心節(jié)點.為了說明并不是依照任意標準構(gòu)建社團演化鏈接都是合理的，本文選用了兩種極限情況進行對比：相鄰時刻任意社團之間無演化鏈接，命名為“NoneCommLink”(B4)；相鄰時刻任意社團之間存在演化鏈接，命名為“AllCommLink”(B5).

表4 實驗算法

(18)

本文所提算法，取λ=[1,1,1]，θ取1，2，3(對應I1，I2，I3)，代表滿足三種標準中任1項、2項、全部時才構(gòu)建演化鏈接.

3.3.2 計算各時刻社團平均的成員穩(wěn)定度

各算法效果為I1≥I2?B3?B2≥B1和I3?B5?B4,具體分析如下．

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)于對比算法.

天(a) B1，B2，B3，B4，B5，I1對比圖

天(b) l1,l2,l3對比圖

3.3.3 分析社團演化路徑

圖8 由I1得到的ct(1)9演化路徑圖

4 結(jié) 論

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

[1] 劉軍.社會網(wǎng)絡(luò)分析導論[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:一種基于核心的社區(qū)演化跟蹤算法[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] 王丁弘.加權(quán)科研合作網(wǎng)絡(luò)個體及網(wǎng)絡(luò)整體演化分析[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國家重點基礎(chǔ)研究發(fā)展計劃項目(2013CB329603)；國家自然科學基金資助項目(71231002,61375058)，National Natural Science Foundation of China(71231002，61375058) ；北京市教育委員會共建項目專項資助；教育部-中國移動科研基金(MCM20123021)

段松青(1987-)，男，湖南郴州人，中國軟件評測中心工程師，博士

?通訊聯(lián)系人，E-mail:dsq58629@163.com

TP391

A