付艷君， 楊云云,2,3， 趙明明， 張俊麗， 謝 剛,2*

(1.太原理工大學電氣與動力工程學院， 太原 030024； 2.太原科技大學山西省高級控制與裝備智能重點實驗室， 太原 030024； 3.復旦大學計算機科學學院， 上海 200433)

時序網絡能夠有效捕獲靜態(tài)網絡在許多方面都無法預測的時態(tài)變化[1]，進而可以更加準確地刻畫網絡如交通網、電力網及生態(tài)網等實際復雜系統(tǒng)的交互關系；而其中的關鍵節(jié)點挖掘對于分析網絡系統(tǒng)特征、理解網絡結構和功能具有顯著的作用[2]。當前，用于挖掘關鍵節(jié)點的算法大都集中于靜態(tài)網絡上，如基于網絡拓撲結構的度中心性、半局部中心性[3]、緊密度中心性、PageRank[4]和hyperlink-induced topic search(HITS)算法等，基于節(jié)點移除和收縮建立的節(jié)點刪除的最短距離法等。在這些方面，任曉龍等[5]及劉建國等[6]對復雜網絡中具有代表性的關鍵節(jié)點挖掘算法做出了系統(tǒng)的闡述、比較和總結。盡管靜態(tài)網絡中關鍵節(jié)點的研究已經取得了一系列可觀的成果，但由于時序網絡中節(jié)點間的連邊會隨時間間斷性地出現(xiàn)和消失[7]，僅僅基于靜態(tài)網絡的研究將忽略時間變化的信息進而影響節(jié)點識別的準確性。因此，如何恰當?shù)貙r序網絡建模并定義節(jié)點的中心性是一項重大挑戰(zhàn)。近些年來研究者們對時序網絡中關鍵節(jié)點識別展開了一系列的研究工作。Barrat[8]將時序網絡中隨時間變化的邊聚合成單個靜態(tài)圖形來研究，但這樣的建模方式一定程度上忽略了時序網絡中的時間屬性；Kempe等[9]提出了一個時序網絡模型作為靜態(tài)圖，其中每條邊都用交互發(fā)生的時間進行標記；Kim等[10]在構建時序網絡時規(guī)定每條邊上發(fā)生的事件僅有一次，并將各個小網絡用有向邊連接，仍然轉化為靜態(tài)圖研究。Tang等[11]提出了基于時間路徑的時間度量方法(如，時序緊密度)以識別網絡中的重要節(jié)點。Huang等[12]將節(jié)點的動態(tài)索引引入到時序網絡中，以衡量節(jié)點的重要性。這些研究成果盡管考慮了時間窗口中網絡結構的時變性，但缺乏不同時間窗口間的聯(lián)系，仍然未能涵蓋時間屬性的所有方面。

為完整揭示時序網絡的結構演變及其動力學過程，將時序網絡與多層網絡分析法相結合，按層內和層間交互關系構建多層時序網絡模型。此外，基于隨機游走的擴散過程來評估不同節(jié)點的影響力。由于經典隨機游走關注在鄰居節(jié)點間的無差別跳轉，忽略具有不同鏈接關系的節(jié)點對網絡的影響不同[13]，進而造成節(jié)點識別的效率低、誤差性高?；诖耍⒒诠?jié)點相似性的有偏隨機游走，并結合多層時序網絡的拓撲結構，將有偏隨機游走應用于PageRank，根據(jù)層內節(jié)點的有偏跳轉以及上層中節(jié)點對下層中副本節(jié)點的單向作用，提出一種集合層內及層間雙重因素的節(jié)點排序算法multilayer temporal biased PageRank(MTB-PR)，可以獲取節(jié)點重要性隨時間變化的情況。隨后，引入偏差參數(shù)來調整節(jié)點對層內及層間因素的依賴性。通過對該算法得出的節(jié)點排序與相應的無偏方法中的結果比較驗證該算法的合理性和有效性；并且可以通過適當調整步行中的偏差來更準確捕獲網絡中排名靠前的節(jié)點。

1 多層時序網絡構建

時序網絡中節(jié)點間的交互關系呈現(xiàn)時變性，隨時間變化可以獲得節(jié)點在不同時間層上的鏈接關系，同時考慮網絡的完整結構演變，前后時間層間必然存在單向影響。因此，具有N個節(jié)點和時間長度為T的時序網絡可以表示成多層拓撲結構(圖1)。多層網絡的層數(shù)通過對T的有效切分得到L=T/t，其中L表示多層時序網絡的層數(shù)，t表示每一層網絡所經歷的時間。多層時序網絡是由多個子網絡按時間順序彼此間形成單向有序鏈接且相互作用的系統(tǒng)。其中相同的一組節(jié)點由同一類型的相互作用所連接，連邊隨時間變化且具有時間先后順序。

圖1 時序網絡到多層時序網絡的映射圖Fig.1 Mapping from temporal network to multilayer temporal network

2 多層時序網絡中節(jié)點重要度評判

本節(jié)對經典隨機游走的擴散過程進行了改進，提出了基于節(jié)點相似性的有偏隨機游走?；诙鄬訒r序網絡中不同時間層間存在的單向作用，將有偏隨機游走應用于PageRank，提出了一種集合層內及層間雙重因素的節(jié)點排序算法多層時序PageRank。

2.1 基于節(jié)點相似性的有偏隨機游走

隨機游走是描述復雜實體上發(fā)生擴散過程的基本模型之一。在經典擴散過程中，隨機游走者通常以相等概率隨機跳轉到相鄰節(jié)點，一定程度忽略了節(jié)點的異質性[14]。Ding等[15]在傳統(tǒng)的擴散過程中引入了有偏游走的思想，使得某一時刻的隨機游走者強制性的偏向于跳轉到具有某些特殊屬性(例如度，強度或聚類)的鄰居節(jié)點。然而這些算法大多強調節(jié)點局部或全局的拓撲屬性，忽略了節(jié)點間相互作用對整個網絡的影響?，F(xiàn)考慮現(xiàn)實社交網絡中，人們更傾向于與自己關系更為相似的人建立親密關系，例如，朋友的朋友往往也會成為朋友。商業(yè)競爭網絡中，兩個企業(yè)越相似，它們的競爭就越激烈。即節(jié)點間的相似度越高，則彼此間的影響力越大。所以，引入節(jié)點間相似性指標作為衡量節(jié)點局部重要性的標志，給出節(jié)點相似性矩陣的定義如下：

定義1節(jié)點相似性矩陣S。具有N個節(jié)點的網絡中節(jié)點i與其鄰居節(jié)點j的相似性Sij為

(1)

式(1)中：α(i)與α(j)分別為節(jié)點i和j的鄰居節(jié)點集。

式(1)表明：①兩個節(jié)點之間擁有的共同鄰居數(shù)越多，則彼此之間越相似，這與現(xiàn)實世界相符合，擁有很多共同朋友的兩個人彼此之間成為朋友的概率更大；生物網中，物種之間生態(tài)需求越是一致則他們的形態(tài)越相似。②相鄰節(jié)點之間的相似性存在差異，即節(jié)點i對節(jié)點j的相似度不同于節(jié)點j對節(jié)點i的相似度，鄰居節(jié)點數(shù)量較多的一方對另一方的影響力更大。這與直觀判斷相符，以生態(tài)競爭網絡為例，食物相似的物種為爭奪食物,競爭會相對更加激烈，而這個過程中，食物種類較多的物種由于存在較多選擇，因而受到來自食物種類較少的物種的競爭壓力遠遠低于其本身對后者帶來的競爭壓力。

基于上述分析，將節(jié)點相似性引入隨機游走過程，得出了基于節(jié)點相似性有偏隨機游走的跳轉概率。

(2)

2.2 多層時序有偏PageRank算法

PageRank算法是建立在經典隨機游走模型基礎上的節(jié)點排序算法，它不僅考慮節(jié)點自身重要性，同時關注其鄰居節(jié)點的影響，具有較強的向多層網絡擴展的優(yōu)勢。本節(jié)將有偏隨機游走應用于PageRank，結合多層時序網絡的拓撲結構對節(jié)點進行中心性度量?？紤]到多層時序網絡中層間鏈接呈現(xiàn)為時序相繼性的有向連邊，節(jié)點在上一時刻的狀態(tài)必然會影響其在下一時刻的重要性且這種影響只能通過時刻t影響時刻t+1的狀態(tài)，呈現(xiàn)單向性。所以，綜合考慮網絡中節(jié)點和層的雙重特性，在各層內引入有偏隨機游走，評估相鄰節(jié)點間的相似性對節(jié)點的影響。與此同時，結合層間的單向有序聯(lián)系，進一步深入分析上一時刻節(jié)點的中心性對下一時刻該節(jié)點中心性的影響。具體步驟如下：

(3)

式(3)中：σ是阻尼系數(shù)，根據(jù)經驗研究，取σ=0.85；指數(shù)η取值為0或1，當η=0時，有偏PageRank恢復為無偏PageRank(CPR)，即節(jié)點i的CPR中心性為

(4)

(5)

需要注意的是，η=0時，多層時序有偏PageRank(MTB-PR)將恢復為無偏的情況，即為多層時序無偏PageRank(MTU-PR)。

(6)

節(jié)點的重要性最終取決于漫游者訪問節(jié)點的頻率的大小。根據(jù)這些訪問頻率得到的節(jié)點排名正好是多層時序PageRank中心度量產生的排序，反映了每個節(jié)點在整個網絡中重要性。

3 數(shù)據(jù)建模與結果分析

3.1 數(shù)據(jù)收集與建模

本文數(shù)據(jù)集取自association for computing machinery(ACM)Hypertext 2009會議[16]期間大約2 d內111名與會人員面對面交互的動態(tài)過程。每個人都是一個節(jié)點，持續(xù)時間大于20 s的面對面互動則構建為邊。按時間相繼性將數(shù)據(jù)按天切分，構建為兩層的多層時序網絡，層間相同節(jié)點創(chuàng)建時序相繼性的有向邊。其中各層為無向無權網絡。網絡基本統(tǒng)計特性如表1所示。

3.2 實驗結果分析

3.2.1 引入節(jié)點相似性對節(jié)點排名的影響

首先利用經典PageRank(CPR)對網絡各層中的節(jié)點進行排序，然后通過基于節(jié)點相似性的有偏PageRank(SBPR)對節(jié)點排名，兩者的排名結果如圖2所示。

圖2 通過經典PageRank(CPR)和有偏PageRank(SBPR)算法所得的節(jié)點排名對比結果Fig.2 Comparison of node rankings obtained by classical PageRank (CPR) and node similarity-based biased PageRank (SBPR)

顯而易見，SBPR對作者排名的影響是非常顯著的，這可以從圖2中節(jié)點的分散分布得到證明。從圖2中的局部放大圖可以看到，節(jié)點顯著地分散在圖2中黑色直線的兩側，表明基于相似性的有偏PageRank(SBPR)克服了經典PageRank以均勻概率游走忽略了節(jié)點異質性的問題，兩者結果之間的顯著差異進一步證明考慮節(jié)點間相似性的重要性，因為其在確定與會者排名方面發(fā)揮了重要作用。

3.2.2 多層時序有偏PageRank與多層時序無偏PageRank所得節(jié)點重要性分析

在ACM Hypertext 2009網絡中應用多層時序有偏PageRank(MTB-PR)算法，分別考慮η=0和η=1的情況，值得注意的是，η=0時，多層時序有偏PageRank恢復為無偏的情況。首先在層1和層2中使用無偏PageRank(CPR)(即經典PageRank)對與會者排名，然后通過已有的層1中的PageRank在層2上計算多層時序無偏PageRank(MTU-PR)，以上對應于η=0的情形。當η=1時，與無偏的情況類似，首先使用基于相似性的有偏PageRank(SBPR)來獲得層1與層2中與會者的中心性排名。再次，計算層2上節(jié)點的多層時序有偏PageRank(MTB-PR)。在這里，僅考慮偏差參數(shù)a=1、b=1的情況。如圖3所示，節(jié)點在兩層網絡中的排名(即散點圖分布)有很大差異，表明無偏或有偏的多層時序PageRank對與會者排名產生了顯著的影響，這種現(xiàn)象闡明了這樣一個事實：與MTU-PR相比，MTB-PR在隨機游走過程中加入了節(jié)點間相似性的影響，這導致MTB-PR找到排名靠前的節(jié)點的效率更高，進而能夠更有效地探索多層時序網絡。

圖3 各層中通過CPR或SBPR所得節(jié)點排名分別與其相對應的通過MTU-PR或MTB-PR所得排名的對比結果Fig.3 Comparison between nodes for CPR and SBPR in each layer with corresponding multilayer temporal MTU-PR and MTB-PR values

另外，節(jié)點在第一層中交流的方式和顯著性會影響其在下一層網絡中的顯著性，即無偏或有偏的多層時序PageRank可以提高第一層中重要性突出的節(jié)點在第二層中的中心性排名，如圖3(a)、圖3(b)與圖3(c)、圖3(d)的對比結果所示，在兩層網絡中排名都較高的與會者106獲得了更大的MTU-PR或MTB-PR。而在第二層中重要性較為顯著的與會者9受到第一層排名靠后的影響，其在MTU-PR或MTB-PR中重要性相比第二層都所有降低。

通過MTU-PR和MTB-PR所得到排名前40的與會者情況如圖4所示。在40個排名的前10名與會者中，第106位與會者由于在兩層網絡中都獲得了較高的CPR和SBPR，最終獲得了更大的MTU-PR和MTB-PR，因此在圖4(a)和圖4(b)中都排名第1。除此之外，其余9名與會者的排名在圖4(a)和圖4(b)中出現(xiàn)了明顯的差異，圖4(b)中新的與會者111和51排名進入前10，而原先在圖4(a)中排名第2的與會者25則排名相對靠后，變?yōu)榈?2名。同時，圖4(a)和圖4(b)中同時位于前10的與會者排名位置也發(fā)生了顯著變化。產生的差異在于與有偏多層時序PageRank相關的漫游者在接收上層節(jié)點中心性影響的同時通過評估節(jié)點間的相似性優(yōu)先訪問與源節(jié)點相似度高的目標節(jié)點，而無偏方法中的步行者僅以均勻概率隨機地移動到目的地節(jié)點。上述結果表明，通過考慮節(jié)點間相互作用的影響，有偏多層時序PageRank通常優(yōu)于其無偏的情況，可以探索并識別ACM Hypertext 2009網絡中的關鍵節(jié)點，并能更有效地找到一些最有影響力的與會者。

圖4 根據(jù)MTU-PR和MTB-PR得到的排名前40的節(jié)點Fig.4 Centrality values of the top 40 participants given by MTU-PR and MTB-PR

3.2.3 不同偏差參數(shù)下節(jié)點的排序結果分析

最后，通過改變偏差參數(shù)a、b生成多層時序有偏PageRank(MTB-PR)研究不同的偏差參數(shù)a、b如何影響與會者在超文本動態(tài)聯(lián)系網絡中的中心性排名，結果如圖5所示。

圖5(a)對應于參數(shù)a=1且b=1、3、5的情形，b越大，層內因素即節(jié)點間相似度在漫游者選擇目標節(jié)點優(yōu)先訪問時所占權重越大，此時，節(jié)點中心性更多地受到層內因素的影響。隨著b的增大，與會者50、88、109的中心性逐漸增加，表明他們在第二層中具有舉足輕重的作用。與會者59、75、106排名的降低則表明隨機游走過程中他們是與源節(jié)點相似度較小的節(jié)點。

如圖5(b)將偏差參數(shù)設置為a=1、3、5且b=1。此時，a>b，層間因素即來自于上層節(jié)點中心性的影響所占權重更大。這導致漫游者優(yōu)先訪問在第一層具有高強度的節(jié)點。參數(shù)a、b的不同取值導致了圖5(a)和圖5(b)中節(jié)點中心性的不同分布。與會者25、52、59、106占據(jù)突出地位，而9、56、59卻有所降低，這表明前者得到來自上一層中節(jié)點中心性的增益更大。

上述分析證實了文中的假設，即由于各層拓撲結構的不同及層間的有序單向作用，多層時序網絡中節(jié)點的中心性受到層內和層間因素協(xié)同效應的強烈影響。通過改變偏差參數(shù)值，MTB-PR可以有效捕獲這些效應，又可以根據(jù)兩者影響權重的大小有針對性地挖掘有重要影響的與會者。

圖5 ACM Hypertext 2009網絡中不同參數(shù)值下節(jié)點的排名結果Fig.5 The ranking of nodes for different parameter values in the ACM Hypertext 2009 network

4 結論

從時序網絡和多層網絡相結合的角度出發(fā)，構建了多層時序網絡模型，該模型完整揭示了時序網絡基于時間的結構演變及其動力學過程，能廣泛適用于實際問題。提出一種基于節(jié)點相似性有偏游走的MTB-PR節(jié)點重要性評估算法，該算法考慮相鄰節(jié)點間相互作用以及層間因素對節(jié)點重要性的影響，并引入偏差參數(shù)用于調整節(jié)點在整個網絡中的相對重要性對于層內及層間因素的依賴程度，提高了時序網絡中關鍵節(jié)點評估的準確性。以ACM Hypertext 2009會議數(shù)據(jù)為實驗數(shù)據(jù)，對節(jié)點重要性進行分析和評價，驗證了算法的可靠性和科學性。下一步，將針對時序網絡中一組關鍵節(jié)點進行重要性評估。