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

1.北京工商大學(xué)計算機(jī)與信息工程學(xué)院，北京1000482.廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，河北廊坊065000

ISSN 1673-9418 CODEN JKYTA8

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

?

移動P2P社會網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法*

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

1.北京工商大學(xué)計算機(jī)與信息工程學(xué)院，北京100048
2.廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，河北廊坊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 (國家自然科學(xué)基金); 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 (北京工商大學(xué)國有資產(chǎn)管理協(xié)同創(chuàng)新中心項目).

Received 2015-09,Accepted 2015-11.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-12-03, http://www.cnki.net/kcms/detail/11.5602.TP.20151203.0922.004.html

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

1　引言

近年來，隨著具有短距無線通信能力（如Blue-Tooth、Wi-Fi、Zigbee等）的移動智能設(shè)備（諸如智能手機(jī)、PDA、可穿戴設(shè)備）的大規(guī)模普及，人們?nèi)粘Ｉ钪械南嘤鲂畔⒖梢詭捉暾赜涗浵聛恚@不僅促進(jìn)了傳統(tǒng)社會網(wǎng)絡(luò)[1]及機(jī)會網(wǎng)絡(luò)[2]在信息感知、處理和傳播等領(lǐng)域的研究，也使得對人的真實社交情形進(jìn)行更加深入的研究，以提出更加高效的消息傳播機(jī)制成為可能。

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

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

在已有的復(fù)雜網(wǎng)絡(luò)研究工作[7-8]中，學(xué)者借助社會網(wǎng)絡(luò)分析法（social network analysis，SNA）提出諸如Katz中心度、節(jié)點(diǎn)度中心性等測度，用于衡量節(jié)點(diǎn)在信息傳播過程中的重要性。但這些研究大多通過疊加歷史相遇數(shù)據(jù)將網(wǎng)絡(luò)抽象為一個靜態(tài)網(wǎng)絡(luò)來處理，因此這些方法未能完全體現(xiàn)網(wǎng)絡(luò)的重要特征——網(wǎng)絡(luò)動態(tài)性與時變演化性。實際場景中，由于人的頻繁社會活動使得節(jié)點(diǎn)之間的相遇關(guān)系隨時間不斷動態(tài)變化，利用疊加圖的方法會造成大量重要相遇信息的缺失，無法準(zhǔn)確刻畫網(wǎng)絡(luò)的演化過程。如圖1所示，隨著時間推移及網(wǎng)絡(luò)演化，從拓?fù)浣嵌葋砜?，?jié)點(diǎn)A或節(jié)點(diǎn)B都能夠?qū)⑾⒅鹛?、間接地傳遞給節(jié)點(diǎn)F，但是節(jié)點(diǎn)F卻不能將消息傳遞給節(jié)點(diǎn)A或節(jié)點(diǎn)B；而使用傳統(tǒng)的疊加圖刻畫網(wǎng)絡(luò)后，從其拓?fù)浣Y(jié)構(gòu)看，節(jié)點(diǎn)A或節(jié)點(diǎn)B與節(jié)點(diǎn)F間均存在可達(dá)路徑，表示節(jié)點(diǎn)A或節(jié)點(diǎn)B與節(jié)點(diǎn)F均可進(jìn)行雙向信息傳遞。出現(xiàn)這種錯誤是由于疊加圖中未能體現(xiàn)網(wǎng)絡(luò)演化的時向性。

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

移動P2P社會網(wǎng)絡(luò)是網(wǎng)絡(luò)拓?fù)潆S時間不斷變化的時變動態(tài)網(wǎng)絡(luò)，為準(zhǔn)確刻畫其拓?fù)溲莼^程，本文利用時間演化圖模型（time evolving graph，TEG）對其進(jìn)行建模分析。TEG模型將動態(tài)演化的網(wǎng)絡(luò)抽象為隨時間不斷變化的一系列拓?fù)淇煺招蛄?，每個快照刻畫一個時間間隔內(nèi)的網(wǎng)絡(luò)狀態(tài)。需要說明的是，快照間時間間隔的選取方法是目前仍無定論的問題[9]，本文一方面根據(jù)經(jīng)驗值，一方面根據(jù)具體的網(wǎng)絡(luò)情景選取相應(yīng)的時間單位進(jìn)行拓?fù)淇煺盏膭澐帧?/p>

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

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

2　相關(guān)研究工作與現(xiàn)狀

移動P2P社會網(wǎng)絡(luò)由機(jī)會網(wǎng)絡(luò)和社交網(wǎng)絡(luò)結(jié)合而產(chǎn)生，是具有顯著的拓?fù)鋭討B(tài)性和演化性的一類復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)領(lǐng)域已有的研究工作[10-11]等用于研究人的移動性問題?；谶@些工作，文獻(xiàn)[12-13]提出了基于節(jié)點(diǎn)不同連接機(jī)制的機(jī)會消息傳遞方法。但是由于人移動性具有不可預(yù)知性使得網(wǎng)絡(luò)呈高度動態(tài)性，在移動P2P社會網(wǎng)絡(luò)中研究拓?fù)溲莼?guī)律以及發(fā)現(xiàn)消息傳播的關(guān)鍵節(jié)點(diǎn)成為一類極具挑戰(zhàn)性的問題。隨著針對該領(lǐng)域研究的增多，準(zhǔn)確刻畫網(wǎng)絡(luò)形態(tài)的問題受到更多的關(guān)注。文獻(xiàn)[14]提出了隨機(jī)圖的概念，然而由于隨機(jī)圖的邊獨(dú)立性，使其不能很好地應(yīng)用于動態(tài)網(wǎng)絡(luò)分析。而文獻(xiàn)[15]提出的時間演化圖模型則受到普遍的關(guān)注。該模型不同于靜態(tài)圖論與隨機(jī)圖，向網(wǎng)絡(luò)中引入時間因素，將動態(tài)演化的網(wǎng)絡(luò)沿時間方向刻畫為離散的拓?fù)淇煺招蛄?。該模型可用于在相鄰快照間研究拓?fù)溲莼匦?，并可在單一快照?nèi)研究節(jié)點(diǎn)的空間拓?fù)潢P(guān)系。

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

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

3　系統(tǒng)建模

3.1靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性

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

本文利用通路而不是“路徑”或“最短路徑”進(jìn)行計算是因為移動P2P社會網(wǎng)絡(luò)中的節(jié)點(diǎn)因其載體的社會性而具有高度動態(tài)性，節(jié)點(diǎn)間幾乎不存在完整端到端路徑，并且難以長時間維持通信鏈路的穩(wěn)定。節(jié)點(diǎn)采用“存儲-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸模式，而每個節(jié)點(diǎn)一般只在一定時長的消息生存期內(nèi)攜帶該消息，故節(jié)點(diǎn)會充分利用每次的相遇機(jī)會進(jìn)行最大功率的信息傳輸來保證將更多的消息傳遞出去。這種數(shù)據(jù)傳輸模式必然導(dǎo)致消息在傳遞過程中會經(jīng)過重復(fù)的節(jié)點(diǎn)或重復(fù)的邊?！奥窂健被颉白疃搪窂健本淮嬖谥貜?fù)的邊或點(diǎn)，而通路卻可以正確刻畫這種消息傳遞路徑?，F(xiàn)給出靜態(tài)網(wǎng)絡(luò)中通路的定義。

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

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

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

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

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

t+1t+1T

3.2動態(tài)演化網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性刻畫

移動P2P社會網(wǎng)絡(luò)是動態(tài)性極強(qiáng)的一類網(wǎng)絡(luò)，節(jié)點(diǎn)的社會性移動使節(jié)點(diǎn)之間的連邊在不斷產(chǎn)生和消失。為最大程度捕捉網(wǎng)絡(luò)的動態(tài)演化性，本文利用時間演化圖模型對該類時變網(wǎng)絡(luò)進(jìn)行建模和分析，使用中心性指標(biāo)作為判斷節(jié)點(diǎn)關(guān)鍵程度的依據(jù)，并將傳統(tǒng)的基于通路的中心性計算方法擴(kuò)展到時變網(wǎng)絡(luò)中。此處首先給出時間演化圖的定義。

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

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

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

在移動P2P社會網(wǎng)絡(luò)中，因為節(jié)點(diǎn)采取“存儲-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸模式，所以節(jié)點(diǎn)間不僅在同一拓?fù)淇煺諆?nèi)會產(chǎn)生聯(lián)系，也可以跨拓?fù)淇煺债a(chǎn)生聯(lián)系。如圖1所示，節(jié)點(diǎn)B在前兩個時間快照內(nèi)沒有與節(jié)點(diǎn)F發(fā)生直接接觸，但是節(jié)點(diǎn)B在T1時刻將消息傳給節(jié)點(diǎn)C，由節(jié)點(diǎn)C攜帶節(jié)點(diǎn)B的消息在T2時刻和節(jié)點(diǎn)F發(fā)生相遇時，將節(jié)點(diǎn)B的消息傳給節(jié)點(diǎn)F。即通過節(jié)點(diǎn)C，節(jié)點(diǎn)B與節(jié)點(diǎn)F間完成了消息傳遞，或說通過節(jié)點(diǎn)C，節(jié)點(diǎn)F受到了節(jié)點(diǎn)B的間接影響，而節(jié)點(diǎn)B和節(jié)點(diǎn)C間在T1時刻產(chǎn)生了直接影響。節(jié)點(diǎn)之間的直接影響沿空間維度上的通路傳遞，間接影響沿時間維度上的通路傳遞。將空間維度和時間維度上產(chǎn)生的通路統(tǒng)稱為動態(tài)通路，并將其明確地分為相對應(yīng)的兩類：空間通路與時間通路?？臻g通路是在某單一靜態(tài)快照中形成的通路，而時間通路由若干個連續(xù)（亦可不連續(xù)）快照的通路組成。

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

式（3）展開為式（4）后不難發(fā)現(xiàn)，式（3）考慮了所有的動態(tài)通路組合：（1）在同一拓?fù)淇煺諆?nèi)起始和終止的所有長度的通路；（2）不同拓?fù)淇煺諆?nèi)起始和終止的所有長度的通路。在同一拓?fù)淇煺諆?nèi)長度為w的通路按照βww!的方式衰減，利用不同拓?fù)淇煺胀瓿傻拈L度為w的通路按照βw(l1!l2!…lr!)的方式衰減，其中w=l1+l2+…+lr表示跨越了r個拓?fù)淇煺胀瓿闪碎L度為w的通路，并在第r個拓?fù)淇煺罩型瓿闪藈中的lr步。

3.3動態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)對時效性消息的傳播能力度量

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

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

綜合考慮上述問題，本文使用節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力大?。ü?jié)點(diǎn)中心性指標(biāo)）作為評判節(jié)點(diǎn)關(guān)鍵程度的評價指標(biāo)，提出傳播實時消息的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)的迭代計算公式：

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社會網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力矩陣，第k個拓?fù)淇煺站W(wǎng)絡(luò)對應(yīng)的鄰接矩陣表示為Αk。本文對時間因素按照自然指數(shù)方式進(jìn)行衰減，設(shè)置時間衰減因子α，且α可根據(jù)網(wǎng)絡(luò)的實際情形對衰減程度進(jìn)行調(diào)節(jié)。利用e-αΔt對不同靜態(tài)快照中的通路按照快照產(chǎn)生的先后順序進(jìn)行衰減，并保證同一個靜態(tài)快照中不同長度的空間通路在時間維度上的衰減程度相同。另外，Qt+11、(Qt+1)T1分別表示節(jié)點(diǎn)傳播、獲取實時性消息的關(guān)鍵程度。

下文給出式（5）能夠正確計算移動P2P社會網(wǎng)絡(luò)中節(jié)點(diǎn)之間影響力的說明，并利用數(shù)學(xué)歸納法證明其正確性。

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

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

+I)-I，展開后

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

+e-αΔt2eβA1

+eβA2

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

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

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

公式中第一部分表示延續(xù)k=s時的情況，并在第s+2個拓?fù)淇煺沼智斑M(jìn)了m（m≥0，m=0時表示節(jié)點(diǎn)將信息傳給自己）步新形成的動態(tài)通路加權(quán)和；第二部分表示截止到第s+1個拓?fù)淇煺眨谥叭我煌負(fù)淇煺罩衅鹗疾⒃谥笕我煌負(fù)淇煺罩薪K止的所有長度的時間通路的加權(quán)和；第三部分表示在第s+2個拓?fù)淇煺掌鹗疾⒃谠摽煺罩薪K止的所有長度的空間通路的加權(quán)和。進(jìn)一步化簡可得：

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

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

4　實驗驗證

4.1實驗數(shù)據(jù)

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

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

4.2不同節(jié)點(diǎn)的消息傳播效率

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

Table 1　 Dataset description表1　數(shù)據(jù)集信息

Fig.2　 Comparison of message coverage圖2　網(wǎng)絡(luò)消息覆蓋速率對比

4.3路徑因子β對節(jié)點(diǎn)傳播能力排名的影響

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

Fig.3　 Impact on node rank of different β values圖3　 β對節(jié)點(diǎn)關(guān)鍵程度排名的影響

4.4時間因子α對節(jié)點(diǎn)傳播能力排名的影響

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

4.5網(wǎng)絡(luò)動態(tài)性對節(jié)點(diǎn)傳播能力的影響

網(wǎng)絡(luò)的動態(tài)性來源于節(jié)點(diǎn)間連邊不斷地建立與消失，導(dǎo)致網(wǎng)絡(luò)的拓?fù)溥B通性不斷變化，并對節(jié)點(diǎn)的影響力大小具有影響，更進(jìn)一步，會影響節(jié)點(diǎn)在網(wǎng)絡(luò)中的關(guān)鍵程度。直觀上，當(dāng)網(wǎng)絡(luò)連通性較低時，節(jié)點(diǎn)的影響力普遍較小。最極端情況是網(wǎng)絡(luò)中節(jié)點(diǎn)間不存在連邊，此時節(jié)點(diǎn)的影響力為0；當(dāng)網(wǎng)絡(luò)連通性較強(qiáng)時，節(jié)點(diǎn)的影響力也會提升。最極端情況是網(wǎng)絡(luò)為完全連通狀態(tài)，節(jié)點(diǎn)到其他任意節(jié)點(diǎn)都存在長度為1的路徑，節(jié)點(diǎn)的影響力此時達(dá)到最大值。本實驗用于觀測網(wǎng)絡(luò)動態(tài)性影響節(jié)點(diǎn)關(guān)鍵程度排名的具體表現(xiàn)形式。為便于觀測結(jié)果，引用前面實驗的結(jié)論，在實驗過程中將α和β均取0.5，用于降低計算結(jié)果的波動，從數(shù)據(jù)集中重新隨機(jī)選擇節(jié)點(diǎn)進(jìn)行觀測（Sigcomm中選中節(jié)點(diǎn)32，Sassy中選中節(jié)點(diǎn)12）。實驗結(jié)果如圖5所示，當(dāng)該節(jié)點(diǎn)較活躍，與其相關(guān)的相遇記錄總量快速增長時，節(jié)點(diǎn)的關(guān)鍵程度排名也會快速增長，當(dāng)與其相關(guān)的相遇記錄總量保持不變或增長較慢時，節(jié)點(diǎn)的關(guān)鍵程度排名也會相應(yīng)降低，并且節(jié)點(diǎn)的關(guān)鍵程度排名的變化相對于網(wǎng)絡(luò)的拓?fù)渥兓哂幸欢ǖ臏笮?。這是由于在當(dāng)前快照中計算節(jié)點(diǎn)影響力時，其結(jié)果是由新產(chǎn)生的拓?fù)湫畔⒑退械臍v史信息綜合計算出來的，即新產(chǎn)生的拓?fù)湫畔⒁话悴粫苯記Q定最終的計算結(jié)果。因此當(dāng)網(wǎng)絡(luò)的拓?fù)渥兓e累到一定程度時，節(jié)點(diǎn)關(guān)鍵程度排名才會受到較明顯的變化，即產(chǎn)生了圖5所示的節(jié)點(diǎn)關(guān)鍵程度排名的滯后變化性。

Fig.5　 Contact density v.s. node rank圖5　網(wǎng)絡(luò)動態(tài)性對節(jié)點(diǎn)關(guān)鍵程度排名的影響

4.6預(yù)測節(jié)點(diǎn)的傳播與獲取消息的能力

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

Fig.6　 Impact of α on prediction accuracy圖6　 α對預(yù)測準(zhǔn)確度的影響

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

衰減因子α與β在本文方法中根據(jù)消息效用的不同衰減特性對動態(tài)通路進(jìn)行衰減，且衰減因子α 與β均具有彈性，可根據(jù)網(wǎng)絡(luò)狀況以及研究目標(biāo)對衰減因子的具體取值進(jìn)行調(diào)節(jié)。β針對不同長度的動態(tài)通路進(jìn)行衰減，主要考慮了節(jié)點(diǎn)間可產(chǎn)生相互影響或可相互傳遞消息的難易程度。α針對不同快照產(chǎn)生的動態(tài)通路進(jìn)行衰減，主要考慮了節(jié)點(diǎn)之間產(chǎn)生影響的先后關(guān)系或節(jié)點(diǎn)之間傳遞消息的實時性。可根據(jù)網(wǎng)絡(luò)的動態(tài)性程度或網(wǎng)絡(luò)的研究（觀測）目標(biāo)設(shè)置這兩個因子的具體取值。例如，若實驗?zāi)康脑谟诓榭串?dāng)網(wǎng)絡(luò)所處的環(huán)境壓力較大時節(jié)點(diǎn)傳播實時消息關(guān)鍵程度的排名情況，可將α設(shè)為較大的數(shù)值，β設(shè)為較小的數(shù)值。這是因為網(wǎng)絡(luò)所處環(huán)境壓力大時，節(jié)點(diǎn)之間通信較困難，節(jié)點(diǎn)通過長通路進(jìn)行消息傳遞的可能性很小，“舊消息”傳遞到當(dāng)前快照的可能性也較小，即更看重短步長動態(tài)通路以及“較新消息”對結(jié)果的影響，通過設(shè)置α和β的取值，起到調(diào)節(jié)步長和時間因素的衰減速率的目的，最終可突出短步長動態(tài)通路以及“新消息”的作用。

5　結(jié)束語

本文針對移動P2P社交網(wǎng)絡(luò)這類動態(tài)時變網(wǎng)絡(luò)，提出了一種傳播實時消息的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法。本文方法借助SNA方法將傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)中基于靜態(tài)網(wǎng)絡(luò)的中心性指標(biāo)分析方法擴(kuò)展到時變動態(tài)網(wǎng)絡(luò)中，將傳統(tǒng)的通路概念延伸為動態(tài)通路概念。本文一方面參照靜態(tài)物理學(xué)中的“格林函數(shù)”公式為不同長度的動態(tài)通路設(shè)置衰減因子，另一方面考慮拓?fù)溲莼臅r向性及消息的實時性，設(shè)置時間衰減因子對不同“年齡”的消息進(jìn)行不同程度的衰減，最終以迭代方式計算出動態(tài)通路的加權(quán)和，得到傳播實時消息的關(guān)鍵節(jié)點(diǎn)評價函數(shù)。5組基于真實相遇數(shù)據(jù)的實驗在驗證本文方法正確性的同時，還表明了本文方法可在一定程度上對節(jié)點(diǎn)的消息傳播與獲取能力進(jìn)行預(yù)測。

本文提出的傳播實時消息的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)方法，雖然在理論和實驗上均驗證是正確有效的，但仍有以下缺陷需要繼續(xù)完善：

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

（2）衰減因子的取值問題。本文按照研究目標(biāo)以及網(wǎng)絡(luò)狀況設(shè)置衰減因子，并通過實驗觀測了衰減因子對結(jié)果的影響，認(rèn)為衰減因子應(yīng)當(dāng)存在取值的上下界或是針對不同網(wǎng)絡(luò)狀態(tài)有最優(yōu)選擇，研究網(wǎng)絡(luò)狀況和衰減因子的取值關(guān)系是很有必要的。

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

（4）選取合理的時間間隔以及運(yùn)用合適的矩陣計算方法都會直接影響本文方法的復(fù)雜度。本文著重提出一種較新穎的在動態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵傳播節(jié)點(diǎn)的方法，故分析并進(jìn)一步找到方法提升本文方法的算法效率是下一步的工作。

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.

附中文參考文獻(xiàn)：

[20]蔡青松,牛建偉,劉明珠.一種評估機(jī)會社會網(wǎng)絡(luò)中節(jié)點(diǎn)消息傳播能力的方法[J].軟件學(xué)報, 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—），男，北京工商大學(xué)計算機(jī)與信息工程學(xué)院碩士研究生，CCF學(xué)生會員，主要研究領(lǐng)域為移動計算，社會計算等。

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年于中國人民大學(xué)獲得碩士學(xué)位，現(xiàn)為廊坊師范學(xué)院講師，主要研究領(lǐng)域為計算機(jī)應(yīng)用，數(shù)據(jù)挖掘等。

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年于北京航空航天大學(xué)獲得博士學(xué)位，現(xiàn)為北京工商大學(xué)計算機(jī)與信息工程學(xué)院副教授，CCF會員，主要研究領(lǐng)域為移動自組網(wǎng)，無線傳感器網(wǎng)絡(luò)，DTN/機(jī)會網(wǎng)絡(luò)，移動社會網(wǎng)絡(luò)等。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP393