移動P2P社會網絡中關鍵節點發現方法*

白宇清，李海健，蔡青松+

1.北京工商大學計算機與信息工程學院，北京1000482.廊坊師范學院數學與信息科學學院，河北廊坊065000

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0350-13

?

移動P2P社會網絡中關鍵節點發現方法*

白宇清1，李海健2，蔡青松1+

1.北京工商大學計算機與信息工程學院，北京100048
2.廊坊師范學院數學與信息科學學院，河北廊坊065000

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0350-13

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61170296, 6137309 (國家自然科學基金); the Beijing Committee of Science and Technology Program under Grant No. KM201110011004 (北京市教委科技計劃); the Collaborative Innovation Centre for State-Owned Assets Administration of Beijing Technology and Business University under Grant No. GZ20131102 (北京工商大學國有資產管理協同創新中心項目).

Received 2015-09,Accepted 2015-11.

CNKI網絡優先出版: 2015-12-03, http://www.cnki.net/kcms/detail/11.5602.TP.20151203.0922.004.html

摘要：傳統的消息傳播關鍵節點發現方法大多針對靜態網絡進行研究。針對移動P2P社會網絡這類復雜的動態時變網絡，提出了一種其時效性隨時間和傳播路徑衰減的一般類型消息傳播過程中關鍵節點的發現方法。將靜態網絡中基于通路（walk）的節點中心性分析方法擴展到移動P2P社會網絡中，將消息傳播路徑分解到時間-空間兩個維度上，并利用兩個衰減因子分別刻畫消息的效用隨傳播路徑長度衰減及隨時間推移衰減這兩種自然特性，利用節點的歷史相遇信息，得到了節點傳播能力的量化分析函數，以此刻畫節點對時效性消息的相對傳播能力。基于真實Trace數據的實驗結果驗證了該方法的可行性。由于所述方法考慮了消息時空兩個維度上所有可能的傳播路徑，也可用于有效預測網絡的演化和不同節點在未來傳播或獲取消息時的相對重要程度。關鍵詞：移動P2P社會網絡；實時消息傳播；中心性分析方法；動態通路

1　引言

近年來，隨著具有短距無線通信能力（如Blue-Tooth、Wi-Fi、Zigbee等）的移動智能設備（諸如智能手機、PDA、可穿戴設備）的大規模普及，人們日常生活中的相遇信息可以幾近完整地記錄下來，這不僅促進了傳統社會網絡[1]及機會網絡[2]在信息感知、處理和傳播等領域的研究，也使得對人的真實社交情形進行更加深入的研究，以提出更加高效的消息傳播機制成為可能。

隨著移動互聯網的興起，作為社會網絡和機會網絡相結合的產物，移動P2P（peer-to-peer）社會網絡[3]日益受到研究學者的關注，成為無線網絡領域的又一研究熱點。移動P2P社會網絡是一類節點間通過對等通信自組織組網形成的網絡。該網絡的節點是具有短距無線通信能力的移動智能設備。設備雖無法自主移動，但依賴其載體（人）的社會性移動，設備間可發生相遇并進行信息交換，使這種通信模式具有典型的社會性特征。移動P2P社會網絡主要針對人的社會屬性或人的移動性對網絡動態性的影響，人的社會關系演化對網絡形態演化的影響，如何利用人的社會性或移動性提升網絡消息傳播效率等方面內容[4]進行研究。移動P2P社會網絡的相關研究不僅可應用于傳統社會網絡所涉及的瞬態社交網絡、基于情景的移動社交、基于個體特性的廣告推送等方面[5]，還對城市規劃、疫情擴散、社會關系挖掘與分析等領域有重要指導意義[6]。在如今這個社交活動從娛樂化向工具化過渡的時代，移動P2P社會網絡無疑具有良好的研究前景和應用價值。而“追蹤、發現對消息傳播有關鍵作用的節點”這類問題，一直是該領域的熱點問題。

移動P2P社會網絡是復雜網絡的一種，一方面該類網絡節點數目眾多，另一方面該類網絡節點因具有復雜的社會屬性而使節點的移動模式復雜多變，最終導致節點具有較強的動態性。在移動P2P社會網絡中，節點間幾乎不存在完整的端到端路徑，節點不依靠固定的基礎設施，采用“存儲-攜帶-轉發”的數據傳輸模式，利用智能設備的短距通信接口以自組織的方式與其他設備發生相遇而交換信息。由于節點在各自的社會性上存在差異，導致節點的移動性不同并有不同的相遇模式，最終使不同節點有不同的消息傳播與消息獲取能力。如何在這類網絡中發現消息傳播的關鍵節點，并利用其提升網絡消息傳播效率成為研究學者們普遍關注的問題。

在已有的復雜網絡研究工作[7-8]中，學者借助社會網絡分析法（social network analysis，SNA）提出諸如Katz中心度、節點度中心性等測度，用于衡量節點在信息傳播過程中的重要性。但這些研究大多通過疊加歷史相遇數據將網絡抽象為一個靜態網絡來處理，因此這些方法未能完全體現網絡的重要特征——網絡動態性與時變演化性。實際場景中，由于人的頻繁社會活動使得節點之間的相遇關系隨時間不斷動態變化，利用疊加圖的方法會造成大量重要相遇信息的缺失，無法準確刻畫網絡的演化過程。如圖1所示，隨著時間推移及網絡演化，從拓撲角度來看，節點A或節點B都能夠將消息逐跳地、間接地傳遞給節點F，但是節點F卻不能將消息傳遞給節點A或節點B；而使用傳統的疊加圖刻畫網絡后，從其拓撲結構看，節點A或節點B與節點F間均存在可達路徑，表示節點A或節點B與節點F均可進行雙向信息傳遞。出現這種錯誤是由于疊加圖中未能體現網絡演化的時向性。

Fig.1　 Time-ordered snapshots and overlapping graph圖1　時間快照與疊加圖演示

移動P2P社會網絡是網絡拓撲隨時間不斷變化的時變動態網絡，為準確刻畫其拓撲演化過程，本文利用時間演化圖模型（time evolving graph，TEG）對其進行建模分析。TEG模型將動態演化的網絡抽象為隨時間不斷變化的一系列拓撲快照序列，每個快照刻畫一個時間間隔內的網絡狀態。需要說明的是，快照間時間間隔的選取方法是目前仍無定論的問題[9]，本文一方面根據經驗值，一方面根據具體的網絡情景選取相應的時間單位進行拓撲快照的劃分。

節點間傳遞一個消息等效于節點間產生或傳遞一個影響，節點可對其他節點產生的總影響稱為節點的影響力[7]，而節點的中心性是表示節點影響力大小的常用測度[8]。故本文使用節點的中心性測度作為其在網絡中傳播消息時的關鍵程度的衡量指標。傳統基于通路（walk）的節點中心性分析方法，因靜態網絡不涉及時間因素，實質為只計算空間維度上的所有長度通路（可理解為一張快照上的通路）的加權和。與之不同，本文同時考慮空間維度和時間維度上的所有長度通路（即動態通路，包含只涉及某一快照的通路和涉及多個快照的通路）的加權和來體現某一節點對網絡中其余節點的影響力大小。利用通路而不是“路徑（path）”或“最短路徑（the shortest path）”進行計算是因為移動P2P社會網絡中的節點動態性較強，節點間難以長時間維持穩定的通信鏈路，而消息在每個節點上的存儲一般具有一定時長的生存期，節點會充分利用每次的相遇機會進行最大功率的信息傳輸來保證將更多的消息傳遞出去。這種數據傳輸模式必然導致消息在傳遞過程中會經過重復的節點或重復的邊，而通路恰可以正確刻畫這種消息傳遞路徑。另外，本文在考慮對不同長度動態通路進行不同程度衰減的同時，也考慮節點間相遇的前后關系以及消息的實時性，利用時間衰減因子對等步長但產生時間相對久遠的動態通路進行更大程度的衰減。這樣做的原因在于節點對網路中其他節點產生的“舊影響”應當隨時間推移逐漸變得不再重要，即網絡中的“舊消息”的影響力應當隨時間推移而衰減。

本文針對移動P2P社會網絡這類動態時變網絡，借助SNA方法，并結合靜態物理學中計算粒子之間彈性勢能的“格林函數”方法，將靜態網絡中基于中心性指標的分析方法擴展到移動P2P社會網絡，利用兩種衰減因子分別刻畫消息的效用隨傳播路徑長度衰減及隨時間推移衰減這兩種自然特性，利用節點的歷史相遇信息，提出一種節點傳播能力的量化分析函數，刻畫節點對時效性消息的相對傳播能力。本文考慮消息的實時性，一方面有助于量化分析節點傳播實時消息的能力，另一方面通過歷史數據對一段時間內的節點消息傳播能力進行綜合考慮，可識別出“最近較活躍”的節點，將其作為實時性消息傳播的關鍵節點從網絡的眾多節點中挑選出來。基于真實Trace數據的實驗表明，本文方法可快速準確計算出各節點的消息傳播關鍵程度，且當利用本文方法選出來的關鍵節點作為消息傳播的起始節點時，網絡的消息覆蓋速率明顯提升。另外本文方法考慮了消息時空兩個維度上所有可能的傳播路徑，因此也可用于有效預測網絡的演化和不同節點在未來傳播或獲取消息時的相對重要程度。在某些網絡環境下，當衰減因子取值恰當時，本文方法的預測準確度最大可接近90%。

2　相關研究工作與現狀

移動P2P社會網絡由機會網絡和社交網絡結合而產生，是具有顯著的拓撲動態性和演化性的一類復雜網絡。復雜網絡領域已有的研究工作[10-11]等用于研究人的移動性問題。基于這些工作，文獻[12-13]提出了基于節點不同連接機制的機會消息傳遞方法。但是由于人移動性具有不可預知性使得網絡呈高度動態性，在移動P2P社會網絡中研究拓撲演化規律以及發現消息傳播的關鍵節點成為一類極具挑戰性的問題。隨著針對該領域研究的增多，準確刻畫網絡形態的問題受到更多的關注。文獻[14]提出了隨機圖的概念，然而由于隨機圖的邊獨立性，使其不能很好地應用于動態網絡分析。而文獻[15]提出的時間演化圖模型則受到普遍的關注。該模型不同于靜態圖論與隨機圖，向網絡中引入時間因素，將動態演化的網絡沿時間方向刻畫為離散的拓撲快照序列。該模型可用于在相鄰快照間研究拓撲演化特性，并可在單一快照內研究節點的空間拓撲關系。

針對網絡內的關鍵節點發現問題，許多研究利用SNA方法提出基于中心性的研究方法[7-8]，給出諸如度中心性、Katz中心性等測度。但中心性度量方法最初是基于靜態網絡提出的，因此并不直接適用于移動P2P社會網絡這類動態網絡。在移動P2P社會網絡中，因節點具有的個體社會性差異，使得其在消息傳播能力上也存在一定的差異，研究工作[16]針對該問題利用真實相遇數據驗證了這一觀點，但是并未提出有效的分析模型或關鍵節點發現方法。已有的研究[17]將基于通路的中心性分析方法從靜態網絡中擴展到動態網絡中，利用Katz中心度衡量節點的影響力大小。但是該方法的參數對快照拓撲形態的依賴性較大且不具有彈性，并不易于利用。研究工作[18]針對Email網絡研究了消息隨時間傳播效應遞減的情況，提出了評估節點傳播能力的方法。

上述工作大多基于通路以及中心性的概念對節點的影響力或消息傳播能力進行度量，其缺陷主要集中于兩個問題：（1）上述有些工作基于靜態網路研究，不適用于動態網絡分析；（2）有些工作并未考慮網絡演化的時間因素，即消息的實時性或節點之間產生影響的先后關系。本文為盡量改正上述缺陷，在網絡動態性極強，節點之間消息傳遞強烈依賴于相遇機會的移動P2P社會網絡中，將傳統的靜態網絡分析方法擴展到動態網絡的同時，充分考慮消息的實時性及節點間產生影響的先后順序，提出移動P2P社會網絡中傳播實時消息的關鍵節點發現方法，并利用真實環境采集的Trace數據對方法進行了驗證。

3　系統建模

3.1靜態網絡中節點的中心性

圖G=(V,E)表示一個包含n個節點m條邊的無權簡單靜態圖，V定義為節點集合且|V| =n，E定義為節點之間連邊的集合且|E| =m (m,n∈Z+)。圖G對應的n×n維鄰接矩陣表示為Α=aij(i,j∈V)，當節點i、j之間存在連邊時aij=1，否則aij=0。由于圖G為無權簡單靜態圖，故aii=0。

本文利用通路而不是“路徑”或“最短路徑”進行計算是因為移動P2P社會網絡中的節點因其載體的社會性而具有高度動態性，節點間幾乎不存在完整端到端路徑，并且難以長時間維持通信鏈路的穩定。節點采用“存儲-攜帶-轉發”的數據傳輸模式，而每個節點一般只在一定時長的消息生存期內攜帶該消息，故節點會充分利用每次的相遇機會進行最大功率的信息傳輸來保證將更多的消息傳遞出去。這種數據傳輸模式必然導致消息在傳遞過程中會經過重復的節點或重復的邊。“路徑”或“最短路徑”均不存在重復的邊或點，而通路卻可以正確刻畫這種消息傳遞路徑。現給出靜態網絡中通路的定義。

定義1（通路）靜態圖G=(V,E)中(V={v1,v2,…, vn},E={e1,e2,…,en})的通路表示為一個頂點與邊交替出現的序列，即若節點i、j之間存在vie1v1e2…ewvj這樣一個序列，則表示節點i、j之間存在一條通路。

引理1若鄰接矩陣Α的w (w∈Z+)次冪為Αw，其i、j位置為k（即(Αw)ij=k），表示節點i、j之間長度為w的通路條數為k條。

本文旨在找到消息傳播的關鍵節點，而節點的關鍵程度等效于節點在網絡中的影響力大小，本文借助SNA方法，使用中心性指標表示節點的影響力大小。節點對網絡中其余節點的影響力越大，該節點與網絡其余節點產生聯系的可能性越大，節點之間的消息傳遞越容易完成，節點對于消息傳播的關鍵程度越大。節點間產生聯系以及節點間進行消息傳遞的過程均是沿節點間的通路發生的，通路長度越長，節點之間產生聯系或進行消息傳遞途經的節點越多，產生影響或完成消息傳遞的難度越大。故本文按照“長步長通路衰減更多，短步長通路衰減較少”的原則對不同長度的通路設置不同權重。本文使用n×n維矩陣S表示節點對網絡中的其余節點的影響力矩陣，Sij表示節點i對節點j的影響力大小。Sij的值越大，節點i對節點j的影響力越大，節點i與節點j產生聯系或節點i向節點j成功傳遞消息的可能性越大。(S1)i表示節點i的中心性指標，即節點i在網絡中的總影響力大小。(S1)i越大，節點i在網絡中的影響力越大，節點i的作用越關鍵。其中1是n×1維向量1=(1,1,…,1)T。最終，按照通路計算方法及上述衰減原則可得到下式：進而使用S1、(S)1分別表示傳播、獲取消息的關鍵程度。

由式（1）可知，Sij將由節點i開始并在節點j結束的所有長度的通路按其長度進行衰減并求加權和。從另一角度來看，通路的長度可表示節點之間關系的親密程度，經歷較短步長產生聯系的節點之間的親密程度要比經歷較長步長的節點之間的親密程度更強，故Sij為長步長通路賦予較小權重，為短步長通路賦予較大權重，表示節點對與其關系更緊密的節點有更大的影響，或消息在關系親密的節點之間更容易傳播。讓長度為w的通路按照的方式衰減。式（1）通過級數運算變換為式（2）：

本文為不同長度通路設置權重的思路來源于靜態物理學中計算粒子之間彈性勢能的“格林函數”。“格林函數”應用于這樣的一個網絡：節點彼此之間由彈簧連接并處于同一水平面上，在起始時刻彈簧處于自然松弛狀態，在之后的某一時刻，將某一個節點向上提拉到一個高度，網絡中的其他節點在彈簧的牽引下也會各自被拉伸到某一高度，此時彈簧處于拉伸狀態，節點間因彈簧的連接而產生了彈力。“格林函數”用于計算該類網絡中節點間的彈性勢能。移動P2P社會網絡與上述網絡有很大的相似性，移動P2P社會網絡中的節點之間也存在類似于“彈簧”這樣的關聯——社會關系，節點間因各自社會關系而彼此關聯，社會關系緊密程度直接決定節點間的相遇頻度以及節點間的相互影響程度。本文借鑒這種思路，利用“具有不同社會關系緊密程度的節點間會產生不同程度的相互影響”作為評判節點在網絡中關鍵程度的依據是合理且是可行的。

t+1t+1T

3.2動態演化網絡中節點的中心性刻畫

移動P2P社會網絡是動態性極強的一類網絡，節點的社會性移動使節點之間的連邊在不斷產生和消失。為最大程度捕捉網絡的動態演化性，本文利用時間演化圖模型對該類時變網絡進行建模和分析，使用中心性指標作為判斷節點關鍵程度的依據，并將傳統的基于通路的中心性計算方法擴展到時變網絡中。此處首先給出時間演化圖的定義。

定義2（時間演化圖）對于任意節點集|| V =n，令T?[Tstart,Tend]為起始時間Tstart、終止時間Tend上的任意時間集合，Δt=(ti,ti+1]∈T(i∈Z+)為快照間隔。若令Gi=(V,Ei)為時間間隔(ti,ti+1]內定義在節點集V上的子圖，則g:={Gi}為定義在區間[Tstart,Tend]上的時間演化圖。

根據定義2，給定快照時間間隔Δt，演化圖g:={Gi}由一系列沿時間方向構成的靜態快照組成，其對應的鄰接矩陣序列可表示為{Ai}。為將前文所提的靜態網絡中的中心性度量方法擴展到動態網絡中，需要將通路的概念引入到時間演化圖中。在此給出動態通路的形式化定義。

定義3（動態通路）定義在一個非遞減的離散時間序列t1≤t2≤…≤tr≤…≤tk(t1,tk∈T)上的頂點與連邊的序列vie1v1e2…vmervm+1…ewvj構成節點i到節點j的長度為w的動態通路，當且僅當第r個快照的鄰接矩陣滿足(Αr)imim+1≠0。

在移動P2P社會網絡中，因為節點采取“存儲-攜帶-轉發”的數據傳輸模式，所以節點間不僅在同一拓撲快照內會產生聯系，也可以跨拓撲快照產生聯系。如圖1所示，節點B在前兩個時間快照內沒有與節點F發生直接接觸，但是節點B在T1時刻將消息傳給節點C，由節點C攜帶節點B的消息在T2時刻和節點F發生相遇時，將節點B的消息傳給節點F。即通過節點C，節點B與節點F間完成了消息傳遞，或說通過節點C，節點F受到了節點B的間接影響，而節點B和節點C間在T1時刻產生了直接影響。節點之間的直接影響沿空間維度上的通路傳遞，間接影響沿時間維度上的通路傳遞。將空間維度和時間維度上產生的通路統稱為動態通路，并將其明確地分為相對應的兩類：空間通路與時間通路。空間通路是在某單一靜態快照中形成的通路，而時間通路由若干個連續（亦可不連續）快照的通路組成。

本文將判定節點在網絡中關鍵程度的中心性指標Sij的計算思路擴展到移動P2P社會網絡中。將節點間產生的所有長度動態通路進行加權求和，并且依舊按照“長步長通路賦予較小權重，短步長通路賦予較大權重”的方式得到節點在移動P2P社會網絡中的動態中心性指標矩陣Dt，(Dt)ij表示截止到第t個拓撲快照，節點i、j之間的影響力大小。特別的，因為節點采取“存儲-攜帶-轉發”的數據傳輸方式，當節點在當前快照無法將消息傳遞給另一節點時，節點將在該快照內繼續“攜帶”該消息，即節點把消息傳遞給自身，所以在計算動態中心性指標Dt時，在節點的動態通路加權公式中加上n×n維矩陣I，表示節點把消息傳遞給自己。最終，得到如下公式：

式（3）展開為式（4）后不難發現，式（3）考慮了所有的動態通路組合：（1）在同一拓撲快照內起始和終止的所有長度的通路；（2）不同拓撲快照內起始和終止的所有長度的通路。在同一拓撲快照內長度為w的通路按照βww!的方式衰減，利用不同拓撲快照完成的長度為w的通路按照βw(l1!l2!…lr!)的方式衰減，其中w=l1+l2+…+lr表示跨越了r個拓撲快照完成了長度為w的通路，并在第r個拓撲快照中完成了w中的lr步。

3.3動態網絡中節點對時效性消息的傳播能力度量

雖然式（3）對等步長的時間通路和空間通路進行了不同程度的衰減，但是這種方法依舊存在缺陷：這種衰減方式只按照通路長度對時間通路與空間通路進行衰減，并未體現節點之間產生影響的先后順序或消息的實時性，即未考慮動態通路產生的時間先后順序。特別地，可把節點之間的影響與消息的實時性看為是等效的。這是因為節點之間傳遞了消息即是節點之間產生了影響，消息的實時性亦即是節點之間產生的影響的實時性。

在實際中，節點之間產生影響的先后順序或消息的實時性是十分重要的。節點之間的影響強度或消息效用往往隨時間推移而遞減。即使消息（影響）傳遞歷經的動態通路長度相同，但最近或當前發生的事件或某一節點對另一節點最近產生的影響往往重要程度更高。人們更重視“最近”發生的事件或“最新的”消息，而不是傳播了相同的動態通路長度的很久之前發生的事件或傳播了很久的“舊消息”。故本節考慮節點之間消息（影響）的實時性，使用tk表示第k個快照中產生的動態通路的“發生時刻”，“發生時刻”越大，表示該時刻距“當前時刻”越近，該時刻產生的影響越重要，該時刻產生的動態通路應受到較少的衰減。

綜合考慮上述問題，本文使用節點在網絡中的影響力大小（節點中心性指標）作為評判節點關鍵程度的評價指標，提出傳播實時消息的關鍵節點發現的迭代計算公式：

Qk+1=(e-αΔtk+1Qk+I)(eβAk+1

+I)-I（5）式（5）是迭代式，其中Δtk+1=tk+1-tk，k∈Ν，Q0=0。本文利用n×n維矩陣Qk表示截止到第k個快照時移動P2P社會網絡中節點的影響力矩陣，第k個拓撲快照網絡對應的鄰接矩陣表示為Αk。本文對時間因素按照自然指數方式進行衰減，設置時間衰減因子α，且α可根據網絡的實際情形對衰減程度進行調節。利用e-αΔt對不同靜態快照中的通路按照快照產生的先后順序進行衰減，并保證同一個靜態快照中不同長度的空間通路在時間維度上的衰減程度相同。另外，Qt+11、(Qt+1)T1分別表示節點傳播、獲取實時性消息的關鍵程度。

下文給出式（5）能夠正確計算移動P2P社會網絡中節點之間影響力的說明，并利用數學歸納法證明其正確性。

證明當k=0時，Q1=eβA1表示當前只有一個快照且Q0=0（迭代式的初始值），所有通路的起始和終止全部發生在快照Α1（此時網絡中只有空間通路）。該式和式（3）的含義相同。

當k=1時，Q2=(e-αΔt2eβA1+I)(eβA2

+I)-I，展開后

得到Q2=e-αΔt2eβA1eβA2

+e-αΔt2eβA1

+eβA2

，公式中第一部分表示在快照Α1起始并在快照Α2結束的所有長度的時間通路的加權和；第二部分表示在快照Α1起始并終止的所有長度的空間通路的加權和；第三部分表示在快照Α2起始并終止的所有長度的空間通路的加權和。由以上3個部分作為計算截止到第2個快照的節點間影響力的計算元素，一方面考慮了所有長度動態通路的起始終止的可能性的組合，另一方面考慮了不同動態通路產生的時間前后因素。

設k=s時，Qs+1=(e-αΔts+1Qs+I)(eβAs+1

+I)-I成立。則k=s+1時，考慮所有動態通路起始和終止的情況和其所有長度情況時有：

公式中第一部分表示延續k=s時的情況，并在第s+2個拓撲快照又前進了m（m≥0，m=0時表示節點將信息傳給自己）步新形成的動態通路加權和；第二部分表示截止到第s+1個拓撲快照，在之前任一拓撲快照中起始并在之后任一拓撲快照中終止的所有長度的時間通路的加權和；第三部分表示在第s+2個拓撲快照起始并在該快照中終止的所有長度的空間通路的加權和。進一步化簡可得：

Qs+2=(e-αΔts+2Qs+1+I)(eβAs+2

+I)-I（7）即得證式（5）成立。

4　實驗驗證

4.1實驗數據

為驗證本文提出的傳播實時消息的關鍵節點發現方法的有效性，采用CRAWDAD[19]提供的從真實環境采集的Trace數據對本文方法進行若干驗證。選取基于兩種常用無線通信接口Bluetooth與Zigbee于真實環境采集的數據進行實驗。Bluetooth接口是較常用的通信接口，Zigbee雖然不是智能終端的標準配置，但由于它通信連接耗時更短（毫秒級），通信耗能更少等特點，從而具有良好的應用前景。這兩種短距通信接口的物理特性使其采集的數據可以較準確地刻畫移動P2P社會網絡的網絡情形，且這兩種通信接口是移動P2P社會網絡消息傳輸較為理想的選擇，具有較大的應用前景。

本文實驗所用的數據集具體為：（1）記錄2009年Sigcomm會議期間，100個持有HTC s620手機的用戶利用Bluetooth接口相遇的數據；（2）記錄2008年在圣安德魯斯大學校園內27名攜帶傳感器的人員在79天內通過Zigbee接口相遇的信息。兩組數據利用兩種不同的通信接口，分別展示了會議場景及校園場景這兩種不同的數據采集環境的不同網絡特性。針對這兩種具有差別的數據集進行實驗，可驗證本文方法具有普遍適用性。表1列出了實驗數據的基本信息。

4.2不同節點的消息傳播效率

網絡中不同個體的社會屬性決定了其對消息具有不同的傳播能力。本文提出了傳播實時消息的關鍵節點發現方法，旨在找到并利用這些關鍵節點提升網絡的消息傳播效率。為驗證這一目的，首先利用本文方法針對各個數據集分別找到消息傳播時關鍵程度最強與最弱的兩個節點，之后分別將這兩個節點作為消息傳播的源節點，在網絡中進行洪泛（flooding）。由于在移動P2P社會網絡中節點間是間歇性連通的，洪泛方式因具有冗余分發等特性，使其對動態網絡具有較好的自適應性，可以比較準確地刻畫基于通路的消息分發，故本實驗選取洪泛方式進行消息傳播。另外，研究工作[20]表明：2-copy（對同一消息而言，節點對其至多轉發2次）與無限副本洪泛方式的網絡覆蓋速率幾近相同，本實驗利用2-copy洪泛方式來降低消息傳播過程中的網絡開銷。為了使實驗結果更加直觀，本實驗計算出網絡覆蓋率的平均情況，與特定節點為消息源時的網絡覆蓋率進行對比。從圖2給出的實驗結果可看出：利用本文方法選出的關鍵程度最強的節點作為消息源頭進行消息傳播的速率明顯是最快速的。該實驗結果清晰表明，利用本文提出的方法作為傳播實時消息的關鍵節點發現方法，可以提升網絡的消息覆蓋速率。網絡消息覆蓋速率提升，表示實時性消息可快速地被傳遞給網絡中的各個節點。

Table 1　 Dataset description表1　數據集信息

Fig.2　 Comparison of message coverage圖2　網絡消息覆蓋速率對比

4.3路徑因子β對節點傳播能力排名的影響

本實驗針對路徑因子β對節點關鍵程度排名的影響進行討論。β用于對具有不同長度的動態通路進行衰減，使得“短動態通路對計算節點傳播能力的貢獻度較大，長動態通路對計算結果的貢獻度較小”。在實際中，一方面可根據網絡的動態程度，另一方面可根據需要傳播的消息的具體特性，按照經驗值設定β的具體取值。本實驗中，針對各個數據集隨機選取網絡中的某一節點作為觀測節點，考察β分別取（0.1，0.3，0.5）時，該節點在網絡中關鍵程度的排名變化情況。如前文所述，時間間隔的選取問題仍是未有定論的問題。進行相關實驗時，首先根據數據集的網絡特性，按照已有研究[9]對時間間隔的設置方法，將Sigcomm的時間間隔設為4.08 h，Sassy的時間間隔設為1 d。另外本節將時間衰減因子取0，表示此實驗暫不考慮時間因素，只考察路徑因子β對節點傳播能力排名的影響。本實驗隨機選擇節點（Sigcomm中選中節點15，Sassy中選中節點5），應用本文方法計算節點的消息傳播能力排名。實驗結果如圖3所示，橫坐標表示各個快照的產生時間，縱坐標表示節點在該時刻的關鍵程度（消息傳播能力）排名，隨著β取值變小，節點關鍵程度排名變化更加劇烈，并最終趨于平穩。這是由于本文方法考慮了節點可產生的所有長度的動態通路，并且當β取值變大時，不同長度動態通路之間的貢獻度差異會縮小，當β取值變小時，不同長度動態通路之間的貢獻度差異會變大。當β取值變小時，節點關鍵程度的計算結果會受到較大的影響，最終導致節點關鍵程度排名變化較劇烈，并且當時間累積到一定程度時，節點的排名受歷史相遇記錄的影響而趨于平穩。

Fig.3　 Impact on node rank of different β values圖3　 β對節點關鍵程度排名的影響

4.4時間因子α對節點傳播能力排名的影響

本實驗考察增加時間因素后，時間衰減因子α對節點關鍵程度排名的影響。為保持一致性，本實驗利用前一實驗針對各數據集隨機選出的節點繼續進行觀測（Sigcomm中選中節點15，Sassy中選中節點5）。從之前實驗的結果可以看出，當不考慮時間因素時，β取值較大，節點的排名變化較不明顯。因此本實驗中將β在各個數據集均設為0.5，α在每個數據集中分別取（0.1，0.5，1.0）觀測節點關鍵程度排名的變化趨勢。實驗結果如圖4所示，當α取值越大時，隨著時間的推進，節點關鍵程度排名變化越劇烈。這是因為e-αΔtk可作為消息在tk時刻的重要性衡量因子，Δtk越小，說明該消息（影響）離現在時刻越近，重要程度越大，對計算結果的貢獻度越大。Δtk越大，說明該消息（影響）離現在時刻越遠，重要程度越小，對計算結果的貢獻度越小。α取值大小直接影響衰減的快慢，α越大，衰減速率越快，節點關鍵程度變化越劇烈，最終導致節點關鍵程度排名變化越劇烈。與β考慮所有長度的動態通路不同，α考慮快照之間的“年齡差”集合{Δtk}的元素數目較少，這導致具有不同“年齡差”的消息的權重對計算結果都有較直接影響，若想突出具有某一“年齡差”的消息的貢獻度，需要設置合適的時間因素衰減因子的取值。

4.5網絡動態性對節點傳播能力的影響

網絡的動態性來源于節點間連邊不斷地建立與消失，導致網絡的拓撲連通性不斷變化，并對節點的影響力大小具有影響，更進一步，會影響節點在網絡中的關鍵程度。直觀上，當網絡連通性較低時，節點的影響力普遍較小。最極端情況是網絡中節點間不存在連邊，此時節點的影響力為0；當網絡連通性較強時，節點的影響力也會提升。最極端情況是網絡為完全連通狀態，節點到其他任意節點都存在長度為1的路徑，節點的影響力此時達到最大值。本實驗用于觀測網絡動態性影響節點關鍵程度排名的具體表現形式。為便于觀測結果，引用前面實驗的結論，在實驗過程中將α和β均取0.5，用于降低計算結果的波動，從數據集中重新隨機選擇節點進行觀測（Sigcomm中選中節點32，Sassy中選中節點12）。實驗結果如圖5所示，當該節點較活躍，與其相關的相遇記錄總量快速增長時，節點的關鍵程度排名也會快速增長，當與其相關的相遇記錄總量保持不變或增長較慢時，節點的關鍵程度排名也會相應降低，并且節點的關鍵程度排名的變化相對于網絡的拓撲變化具有一定的滯后性。這是由于在當前快照中計算節點影響力時，其結果是由新產生的拓撲信息和所有的歷史信息綜合計算出來的，即新產生的拓撲信息一般不會直接決定最終的計算結果。因此當網絡的拓撲變化積累到一定程度時，節點關鍵程度排名才會受到較明顯的變化，即產生了圖5所示的節點關鍵程度排名的滯后變化性。

Fig.5　 Contact density v.s. node rank圖5　網絡動態性對節點關鍵程度排名的影響

4.6預測節點的傳播與獲取消息的能力

式（5）的迭代形式使得本文方法可以基于當前快照的計算結果（歷史信息）對后一快照中的節點傳播或獲取實時性消息的能力進行一定程度上的預測。而時間衰減因子α的不同取值即是對歷史信息進行不同程度的處理——按照不同程度對歷史相遇記錄進行衰減。因此本節實驗研究時間衰減因子α對預測精度的影響。本實驗利用皮爾森相關系數作為預測結果的評判指標，計算出Qt+11與St+11，(Qt+1)T1與(St+1)T1的皮爾森相關系數，其中St+1是由式（2）計算出的在第t+1個快照中節點的影響力矩陣。皮爾森相關系數越大，說明利用本文方法預測出的結果越準確，相反，皮爾森相關系數越小，說明利用本文方法預測出的結果誤差越大。根據具體的網絡動態程度，按前面實驗的結果設置路徑因子β在兩個數據集內均為0.5，考察時間因子α對預測準確性的影響。實驗結果如圖6所示，在Sigcomm數據集中當α取值為2.0與1.7時，本文方法的預測準確性分別達到最高值68%與65%。在Sassy數據集中當α取值為1.4時，本文方法的預測準確性達到最高值90%。

Fig.6　 Impact of α on prediction accuracy圖6　 α對預測準確度的影響

4.7對衰減因子α與β的討論

衰減因子α與β在本文方法中根據消息效用的不同衰減特性對動態通路進行衰減，且衰減因子α 與β均具有彈性，可根據網絡狀況以及研究目標對衰減因子的具體取值進行調節。β針對不同長度的動態通路進行衰減，主要考慮了節點間可產生相互影響或可相互傳遞消息的難易程度。α針對不同快照產生的動態通路進行衰減，主要考慮了節點之間產生影響的先后關系或節點之間傳遞消息的實時性。可根據網絡的動態性程度或網絡的研究（觀測）目標設置這兩個因子的具體取值。例如，若實驗目的在于查看當網絡所處的環境壓力較大時節點傳播實時消息關鍵程度的排名情況，可將α設為較大的數值，β設為較小的數值。這是因為網絡所處環境壓力大時，節點之間通信較困難，節點通過長通路進行消息傳遞的可能性很小，“舊消息”傳遞到當前快照的可能性也較小，即更看重短步長動態通路以及“較新消息”對結果的影響，通過設置α和β的取值，起到調節步長和時間因素的衰減速率的目的，最終可突出短步長動態通路以及“新消息”的作用。

5　結束語

本文針對移動P2P社交網絡這類動態時變網絡，提出了一種傳播實時消息的關鍵節點發現方法。本文方法借助SNA方法將傳統的復雜網絡中基于靜態網絡的中心性指標分析方法擴展到時變動態網絡中，將傳統的通路概念延伸為動態通路概念。本文一方面參照靜態物理學中的“格林函數”公式為不同長度的動態通路設置衰減因子，另一方面考慮拓撲演化的時向性及消息的實時性，設置時間衰減因子對不同“年齡”的消息進行不同程度的衰減，最終以迭代方式計算出動態通路的加權和，得到傳播實時消息的關鍵節點評價函數。5組基于真實相遇數據的實驗在驗證本文方法正確性的同時，還表明了本文方法可在一定程度上對節點的消息傳播與獲取能力進行預測。

本文提出的傳播實時消息的關鍵節點發現方法，雖然在理論和實驗上均驗證是正確有效的，但仍有以下缺陷需要繼續完善：

（1）時間間隔的選取問題目前仍處在研究階段，時間間隔不限于本文所利用的“相等時間間隔”劃分形式，并且時間間隔選取的大小也會帶來很多問題。例如時間間隔劃分過大會使得快照內的相遇信息記錄不完整；時間間隔劃分過小會使得快照中存在過多的冗余相遇信息。本文按照數據的采集背景以及經驗值設置時間間隔是一種無奈的折中策略，進一步針對時間間隔選取進行研究是有必要且是十分重要的。

（2）衰減因子的取值問題。本文按照研究目標以及網絡狀況設置衰減因子，并通過實驗觀測了衰減因子對結果的影響，認為衰減因子應當存在取值的上下界或是針對不同網絡狀態有最優選擇，研究網絡狀況和衰減因子的取值關系是很有必要的。

（3）本文假設消息的生存期是無限大的，即不考慮節點會主動丟棄所攜帶消息的行為。不同網絡狀況下，消息生存期的設置方式不同，該項工作雖不與本文工作直接相關，但若考慮消息的生存期問題將有助于提升本文方法的普適性。

（4）選取合理的時間間隔以及運用合適的矩陣計算方法都會直接影響本文方法的復雜度。本文著重提出一種較新穎的在動態網絡中發現關鍵傳播節點的方法，故分析并進一步找到方法提升本文方法的算法效率是下一步的工作。

References:

[1] Spiliopoulou M. Evolution in social networks: a survey[M]// Social Network Data Analytics. Springer US, 2011: 149-175.

[2] Conti M, Giordano S, May M, et al. From opportunistic networks to opportunistic computing[J]. IEEE Communications Magazine, 2010, 48(9): 126-139.

[3] Chung K Y, Yoo J, Kim K J. Recent trends on mobile computing and future networks[J]. Personal and Ubiquitous Computing, 2014, 18(3): 489-491.

[4] Mota V F S, Cunha F D, Macedo D F, et al. Protocols, mobility models and tools in opportunistic networks: a survey[J]. Computer Communications, 2014, 48(8): 5519.

[5] Goyal E M, Chaudhary E M, Bharti E A. A survey of routing protocols for opportunistic mobile adhoc networks[J]. International Journal of Advanced Research in Computer Science, 2013, 4(9): 96-99.

[6] Ryan A R, Brian G, Jennifer N. Modeling dynamic behavior in large evolving graphs[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Italy, Feb 4-8, 2013. New York, USA:ACM, 2013: 667-676.

[7] Katz L. A new index derived from social metric data analysis[J]. Psychometrical, 1953, 18(1): 39-43.

[8] Freeman L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1979, 1(3): 215-239.

[9] Clauset A, Eagle N. Persistence and periodicity in a dynamic proximity network[C]//Proceedings of the DIMACS Workshop on Computational Methods for Dynamic Interaction Networks, 2007.

[10] Pirozmand P, Wu Guowei, Jedari B, et al. Human mobility in opportunistic networks: characteristics, models and prediction methods[J]. Journal of Network & Computer Applications, 2014, 42(3): 45-58.

[11] Wang Dashun, Pedreschi D, Song Chaoming, et al. Human mobility, social ties, and link prediction[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, USA, Aug 21-24, 2011. New York, USA:ACM, 2011: 1100-1108.

[12] Chao Fan, Zhang Hongqi, Du Xuehui, et al. Improvement of structured P2P routing algorithm based on NN-CHORD [C]//Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing, Wuhan, China, Sep 23-25, 2011. Piscataway, USA: IEEE, 2011: 1-5.

[13] Chandrasekaran V, Dantu R, Gupta N K, et al. Efficiency of social connection-based routing in P2P VoIP networks[C]// Proceedings of the 2nd International Conference on Communication Systems and Networks, Bangalore, Jan 5-9, 2010. Piscataway, USA: IEEE, 2010: 1-6.

[14] Newman M E J. Random graph as models of networks[M]// Handbook of Graphs and Networks: From the Genome to the Internet. [S.l.]: Wiley-VCH, 2005: 35-68.

[15] Rossi R A, Gallagher B, Neville J, et al. Modeling dynamic behavior in large evolving graphs[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Italy, Feb 4-8, 2013. New York, USA: ACM, 2013: 667-676.

[16] Yoneki E, Hui P, Crowcroft J. Wireless epidemic spread in dynamic human networks, bio- inspired computing and communication[C]//LNCS 5151: Proceedings of the 1st Workshop on Bio- Inspired Design of Networks, Cambridge, UK, Apr 2-5, 2007. Berlin, Heidelberg: Springer, 2007: 116-132.

[17] Grindrod P, Parson M C, Higham D J, et al. Communicability across evolving networks[J]. Physical Review E, 2011, 83 (4): 046120.

[18] Grindrod P, Higham D J. A matrix iteration for dynamic network summaries[J]. SIAM Review, 2013, 55(1): 118-128.

[19] A community resource for archiving wireless data[EB/OL]. [2015-08-06]. http://crawdad.cs.dartmouth.edu/.

[20] Cai Qingsong, Niu Jianwei, Liu Mingzhu. Method for iden

tifying node dissemination capability in opportunistic social networks[J]. Journal of Software, 2012, 23(S1): 49-58.

附中文參考文獻：

[20]蔡青松,牛建偉,劉明珠.一種評估機會社會網絡中節點消息傳播能力的方法[J].軟件學報, 2012, 23(S1): 49-58.

BAI Yuqing was born in 1991. He is an M.S. candidate at School of Computer and Information Engineering, Beijing Technology and Business University, and the student member of CCF. His research interests include mobile computing and social computing, etc.白宇清（1991—），男，北京工商大學計算機與信息工程學院碩士研究生，CCF學生會員，主要研究領域為移動計算，社會計算等。

LI Haijian was born in 1974. He received the M.S. degree from Renmin University of China in 2010. Now he is a lecturer at College of Mathematics, Physics and Information Engineering, Langfang Teachers University. His research interests include computing application and data mining, etc.李海健（1974—），男，2010年于中國人民大學獲得碩士學位，現為廊坊師范學院講師，主要研究領域為計算機應用，數據挖掘等。

CAI Qingsong was born in 1973. He received the Ph.D. degree from Beijing University of Aeronautics and Astronautics in 2005. Now he is an associate professor at School of Computer and Information Engineering, Beijing Technology and Business University, and the member of CCF. His research interests include mobile ad-hoc networks, wireless sensor networks, DTN/opportunistic networking and mobile social networks, etc.蔡青松（1973—），男，2005年于北京航空航天大學獲得博士學位，現為北京工商大學計算機與信息工程學院副教授，CCF會員，主要研究領域為移動自組網，無線傳感器網絡，DTN/機會網絡，移動社會網絡等。

Discovering Key Nodes in Mobile P2PSocial Networks?

BAI Yuqing1, LI Haijian2, CAI Qingsong1+
1. School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China
2. College of Mathematics, Physics and Information Engineering, Langfang Teachers University, Langfang, Hebei 065000, China
+ Corresponding author: E-mail: caiqs@btbu.edu.cn

BAI Yuqing, LI Haijian, CAI Qingsong. Discovering key nodes in mobile P2P social networks. Journal of Frontiers of Computer Science and Technology, 2016, 10(3): 350-362.

Abstract:Conventional methods of finding key nodes in a network are mainly based on the theory of static graph, and cannot be applied to dynamic settings where connections between nodes appear and disappear dynamically. This paper focuses on a dynamic and evolving network, called mobile peer-to-peer social network (MPPSN), and proposes an efficient method on it to quantitatively identify the key nodes in the network. By extending the classical concept of centrality to the dynamic MPPSNs and using two elastic attenuation factors to characterize the walklength fading effect and the freshness of a time-bound message, this paper precisely derives an iterative matrix function to compute the relative importance of a node in MPPSN. Extensive experiments based on two real Trace datasets are conducted, and the results show that the analytical model is not only effective at identifying the most effec-book=351,ebook=55tive node in disseminating or receiving the latest useful messages but can even predict the node’s future behaviors as well as the network evolution at a very high accuracy.

Key words:mobile peer-to-peer social network; time-bound message dissemination; centrality analysis method; dynamic walk

doi:10.3778/j.issn.1673-9418.1509044

文獻標志碼：A

中圖分類號：TP393