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

1.北京工商大學(xué)計(jì)算機(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

?

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

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

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

1　引言

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

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

移動(dòng)P2P社會(huì)網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一種，一方面該類網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目眾多，另一方面該類網(wǎng)絡(luò)節(jié)點(diǎn)因具有復(fù)雜的社會(huì)屬性而使節(jié)點(diǎn)的移動(dòng)模式復(fù)雜多變，最終導(dǎo)致節(jié)點(diǎn)具有較強(qiáng)的動(dòng)態(tài)性。在移動(dòng)P2P社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)間幾乎不存在完整的端到端路徑，節(jié)點(diǎn)不依靠固定的基礎(chǔ)設(shè)施，采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸模式，利用智能設(shè)備的短距通信接口以自組織的方式與其他設(shè)備發(fā)生相遇而交換信息。由于節(jié)點(diǎn)在各自的社會(huì)性上存在差異，導(dǎo)致節(jié)點(diǎn)的移動(dòng)性不同并有不同的相遇模式，最終使不同節(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é)者借助社會(huì)網(wǎng)絡(luò)分析法（social network analysis，SNA）提出諸如Katz中心度、節(jié)點(diǎn)度中心性等測(cè)度，用于衡量節(jié)點(diǎn)在信息傳播過程中的重要性。但這些研究大多通過疊加歷史相遇數(shù)據(jù)將網(wǎng)絡(luò)抽象為一個(gè)靜態(tài)網(wǎng)絡(luò)來處理，因此這些方法未能完全體現(xiàn)網(wǎng)絡(luò)的重要特征——網(wǎng)絡(luò)動(dòng)態(tài)性與時(shí)變演化性。實(shí)際場(chǎng)景中，由于人的頻繁社會(huì)活動(dòng)使得節(jié)點(diǎn)之間的相遇關(guān)系隨時(shí)間不斷動(dòng)態(tài)變化，利用疊加圖的方法會(huì)造成大量重要相遇信息的缺失，無法準(zhǔn)確刻畫網(wǎng)絡(luò)的演化過程。如圖1所示，隨著時(shí)間推移及網(wǎng)絡(luò)演化，從拓?fù)浣嵌葋砜?，?jié)點(diǎn)A或節(jié)點(diǎn)B都能夠?qū)⑾⒅鹛亍㈤g接地傳遞給節(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)這種錯(cuò)誤是由于疊加圖中未能體現(xiàn)網(wǎng)絡(luò)演化的時(shí)向性。

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

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

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

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

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

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

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

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

3　系統(tǒng)建模

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

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

本文利用通路而不是“路徑”或“最短路徑”進(jìn)行計(jì)算是因?yàn)橐苿?dòng)P2P社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)因其載體的社會(huì)性而具有高度動(dòng)態(tài)性，節(jié)點(diǎn)間幾乎不存在完整端到端路徑，并且難以長(zhǎng)時(shí)間維持通信鏈路的穩(wěn)定。節(jié)點(diǎn)采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸模式，而每個(gè)節(jié)點(diǎn)一般只在一定時(shí)長(zhǎng)的消息生存期內(nèi)攜帶該消息，故節(jié)點(diǎn)會(huì)充分利用每次的相遇機(jī)會(huì)進(jìn)行最大功率的信息傳輸來保證將更多的消息傳遞出去。這種數(shù)據(jù)傳輸模式必然導(dǎo)致消息在傳遞過程中會(huì)經(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})的通路表示為一個(gè)頂點(diǎn)與邊交替出現(xiàn)的序列，即若節(jié)點(diǎn)i、j之間存在vie1v1e2…ewvj這樣一個(gè)序列，則表示節(jié)點(diǎn)i、j之間存在一條通路。

引理1若鄰接矩陣Α的w (w∈Z+)次冪為Αw，其i、j位置為k（即(Αw)ij=k），表示節(jié)點(diǎn)i、j之間長(zhǎng)度為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)對(duì)網(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)對(duì)于消息傳播的關(guān)鍵程度越大。節(jié)點(diǎn)間產(chǎn)生聯(lián)系以及節(jié)點(diǎn)間進(jìn)行消息傳遞的過程均是沿節(jié)點(diǎn)間的通路發(fā)生的，通路長(zhǎng)度越長(zhǎng)，節(jié)點(diǎn)之間產(chǎn)生聯(lián)系或進(jìn)行消息傳遞途經(jīng)的節(jié)點(diǎn)越多，產(chǎn)生影響或完成消息傳遞的難度越大。故本文按照“長(zhǎng)步長(zhǎng)通路衰減更多，短步長(zhǎng)通路衰減較少”的原則對(duì)不同長(zhǎng)度的通路設(shè)置不同權(quán)重。本文使用n×n維矩陣S表示節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中的其余節(jié)點(diǎn)的影響力矩陣，Sij表示節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的影響力大小。Sij的值越大，節(jié)點(diǎn)i對(duì)節(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ì)算方法及上述衰減原則可得到下式：進(jìn)而使用S1、(S)1分別表示傳播、獲取消息的關(guān)鍵程度。

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

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

t+1t+1T

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

+I)-I，展開后

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

+e-αΔt2eβA1

+eβA2

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

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

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

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

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

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

4　實(shí)驗(yàn)驗(yàn)證

4.1實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.7對(duì)衰減因子α與β的討論

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

5　結(jié)束語

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

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

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

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

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

（4）選取合理的時(shí)間間隔以及運(yùn)用合適的矩陣計(jì)算方法都會(huì)直接影響本文方法的復(fù)雜度。本文著重提出一種較新穎的在動(dòng)態(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]蔡青松,牛建偉,劉明珠.一種評(píng)估機(jī)會(huì)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)消息傳播能力的方法[J].軟件學(xué)報(bào), 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ì)算機(jī)與信息工程學(xué)院碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)橐苿?dòng)計(jì)算，社會(huì)計(jì)算等。

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.李海?。?974—），男，2010年于中國人民大學(xué)獲得碩士學(xué)位，現(xiàn)為廊坊師范學(xué)院講師，主要研究領(lǐng)域?yàn)橛?jì)算機(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ì)算機(jī)與信息工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)橐苿?dòng)自組網(wǎng)，無線傳感器網(wǎng)絡(luò)，DTN/機(jī)會(huì)網(wǎng)絡(luò)，移動(dòng)社會(huì)網(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

中圖分類號(hào)：TP393