基于圖神經(jīng)網(wǎng)絡(luò)的機會網(wǎng)絡(luò)節(jié)點重要度評估方法

劉琳嵐 譚鎮(zhèn)陽 舒 堅

1(南昌航空大學信息工程學院 南昌 330063)

2(南昌航空大學軟件學院 南昌 330063)

(liulinlan@nchu.edu.cn)

機會網(wǎng)絡(luò)(opportunistic network, ON)[1]是一種不需要通信雙方的節(jié)點之間存在完整鏈路,利用節(jié)點移動帶來的間歇性連通機會實現(xiàn)通信的自組織動態(tài)網(wǎng)絡(luò).機會網(wǎng)絡(luò)的部分概念源于早期的延遲容忍網(wǎng)絡(luò)(delay tolerant network, DTN)研究,其主要的目標之一就是為了支持那些具有間歇性的連通、延時量大、錯誤率較高等特點的異構(gòu)網(wǎng)絡(luò)之間的互聯(lián)與相關(guān),如車載自組織網(wǎng)、移動數(shù)據(jù)分流、信息分享、移動計算等.機會網(wǎng)絡(luò)拓展了網(wǎng)絡(luò)通信的使用范圍,將成為未來泛在通信的重要組成部分[2].

機會網(wǎng)絡(luò)利用機會式的通信方式實現(xiàn)智能設(shè)備間的內(nèi)容、資源和服務(wù)的共享.正是這種機會式的通信方式導致了機會網(wǎng)絡(luò)具有明顯的動態(tài)性與時變性.因此,如何選擇最理想的轉(zhuǎn)發(fā)目標以及最理想的轉(zhuǎn)發(fā)時機成為機會網(wǎng)絡(luò)中數(shù)據(jù)傳輸機制關(guān)注的核心問題[3].對節(jié)點重要度的評估能夠輔助上層路由協(xié)議選取最佳轉(zhuǎn)發(fā)目標,從而提高整網(wǎng)的消息投遞率.

一個具有多個移動節(jié)點的機會網(wǎng)絡(luò)中,源節(jié)點A向目標節(jié)點B傳遞消息的過程如圖1所示.由于機會網(wǎng)絡(luò)節(jié)點間通信的頻繁連接和斷開,且移動節(jié)點的電池能量、內(nèi)存等資源相對受限,為了使源節(jié)點A的時效性消息能夠有效地投遞至目標節(jié)點B,應選擇重要度(即消息傳播能力)高的節(jié)點作為轉(zhuǎn)發(fā)目標,從而提高消息的投遞成功率.

針對機會網(wǎng)絡(luò)中通信節(jié)點位置的不確定性以及節(jié)點對連接的周期性導致其網(wǎng)絡(luò)結(jié)構(gòu)隨時間頻繁變化的特點,本文采用動態(tài)網(wǎng)絡(luò)嵌入方法將隨時間變化的動態(tài)網(wǎng)絡(luò)拓撲信息壓縮到特征空間中,以獲取網(wǎng)絡(luò)動態(tài)屬性特征,利用圖神經(jīng)網(wǎng)絡(luò)(graph neural network, GNN)建立網(wǎng)絡(luò)動態(tài)屬性特征與節(jié)點重要度的映射關(guān)系,實現(xiàn)對節(jié)點重要度的評估.本文的主要貢獻有3個方面：

1) 利用節(jié)點間的交互信息,通過聚合圖模型對機會網(wǎng)絡(luò)進行建模.針對機會網(wǎng)絡(luò)動態(tài)性與時變性的特點,將時序上連續(xù)的機會網(wǎng)絡(luò)按照時間片切分為離散的機會網(wǎng)絡(luò)單元,在機會網(wǎng)絡(luò)單元上建立聚合圖模型,確定圖模型中連邊的權(quán)重以構(gòu)建網(wǎng)絡(luò)屬性矩陣,表征機會網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息.

2) 提出一種適用于機會網(wǎng)絡(luò)的動態(tài)網(wǎng)絡(luò)嵌入方法.采用類增量學習的方式,根據(jù)輸入的網(wǎng)絡(luò)屬性矩陣生成節(jié)點的嵌入表示.提取機會網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息與時序變化信息,將其壓縮表示為由節(jié)點動態(tài)屬性嵌入向量組成的網(wǎng)絡(luò)動態(tài)屬性特征矩陣.

3) 提出基于圖神經(jīng)網(wǎng)絡(luò)的機會網(wǎng)絡(luò)節(jié)點重要度評估模型.通過節(jié)點之間相互關(guān)系對節(jié)點動態(tài)屬性嵌入向量進行更新,實現(xiàn)節(jié)點鄰域信息的融合,建立節(jié)點動態(tài)屬性嵌入向量與節(jié)點重要度之間的映射關(guān)系,評估機會網(wǎng)絡(luò)節(jié)點的重要度.

1 相關(guān)研究

近年來,評估節(jié)點重要度的方法可分為3類:基于局部指標的評估、基于全局指標的評估和基于混合指標的評估.

1.1 基于局部結(jié)構(gòu)的評估方法

網(wǎng)絡(luò)的拓撲結(jié)構(gòu)在很大程度上能夠決定一個節(jié)點在網(wǎng)絡(luò)中的重要度.因此,依據(jù)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)設(shè)計節(jié)點的重要度排序指標,是一類對網(wǎng)絡(luò)節(jié)點重要度進行評估的重要方法.節(jié)點的重要度也稱為“中心性”,即網(wǎng)絡(luò)中節(jié)點的重要程度取決于該節(jié)點與其他節(jié)點的連接使其具有的顯著性[4].度中心性[4](degree centrality, DC)的基本思想可描述為網(wǎng)絡(luò)中節(jié)點的鄰居數(shù)量決定其節(jié)點本身的影響力大小.文獻[5]采用路徑流的方式對時序網(wǎng)絡(luò)建模,提出時序度中心性,將靜態(tài)網(wǎng)絡(luò)中的度中心性指標拓展到時序網(wǎng)絡(luò),考慮了節(jié)點度隨時間變化的波動,能夠有效評估動態(tài)網(wǎng)絡(luò)中的節(jié)點重要度.為進一步提高節(jié)點重要度評估的準確性,Ren等人[4]提出一種利用節(jié)點在網(wǎng)絡(luò)中半局部信息的節(jié)點重要度評估指標,簡稱半局部中心性(semi-local centrality, SLC),該指標通過計算網(wǎng)絡(luò)中節(jié)點的2層鄰居數(shù)量來表征節(jié)點的重要度,在損耗較少計算時間的前提下得到了較好的評估效果.度中心性與半局部中心性利用節(jié)點在網(wǎng)絡(luò)拓撲中的領(lǐng)域信息對節(jié)點的重要度進行評估,認為鄰域內(nèi)節(jié)點數(shù)目相同的節(jié)點其重要程度也相同.

1.2 基于全局結(jié)構(gòu)的評估方法

在現(xiàn)實世界中的諸多網(wǎng)絡(luò)中,存在著一些鄰居數(shù)目很少但重要程度卻不容小覷的節(jié)點,這類節(jié)點的重要性往往不能采用傳統(tǒng)的局部結(jié)構(gòu)評估方法度量.因此,基于全局結(jié)構(gòu)的評估方法應運而生.接近中心性(closeness centrality, CC)[4]指標通過計算節(jié)點與網(wǎng)絡(luò)中其他所有節(jié)點的平均距離來衡量該節(jié)點在網(wǎng)絡(luò)全局結(jié)構(gòu)上的影響力,從而消除特殊位置對的節(jié)點重要度評估的干擾.

Katz中心性[4]指標在接近中心性的基礎(chǔ)上進行改進,不僅考慮了節(jié)點對之間的最短路徑,還考慮了它們之間的其他非最短路徑.介數(shù)中心性(between-ness centrality, BC)[4]刻畫了節(jié)點對在網(wǎng)絡(luò)中沿最短路徑傳輸?shù)木W(wǎng)絡(luò)流的控制力.文獻[6]基于靜態(tài)網(wǎng)絡(luò)中的CC以及BC,提出了時效介數(shù)(temporal betweenness, TB)中心性指標評估時效網(wǎng)絡(luò)中節(jié)點重要程度,TB不僅考慮了經(jīng)過節(jié)點的最短路徑的數(shù)目,還考慮了最短路徑上節(jié)點對于消息的保持時間,從而綜合計算得到時序介數(shù)中心性的值,對節(jié)點重要度進行評估.

針對局部性指標僅僅只考察節(jié)點的局部特性而忽略節(jié)點在網(wǎng)絡(luò)中位置的問題,Kitsak等人[7]提出k-殼分解法(k-shell decomposition),該方法首先利用節(jié)點位于網(wǎng)絡(luò)中的位置,將外層節(jié)點層層剝?nèi)?認為處于內(nèi)層的節(jié)點其重要程度也越高.針對k-殼粒度粗的問題,學者們提出了一系列關(guān)于k-殼分解法的改進方法,如將節(jié)點進行預分類的層次k-殼分解法(hierarchicalk-shell decomposition)[8]、使用迭代因子進一步細化分解粒度的迭代因子k-殼分解法(k-shell iteration factor)[9]等.基于全局結(jié)構(gòu)的評估方法能夠考慮網(wǎng)絡(luò)的結(jié)構(gòu)信息,對網(wǎng)絡(luò)中的節(jié)點重要性評判更加準確,但基于全局結(jié)構(gòu)的方法時間復雜度較高,在大型網(wǎng)絡(luò)和動態(tài)網(wǎng)絡(luò)中的應用受到限制.

1.3 基于混合結(jié)構(gòu)的評估方法

研究人員結(jié)合前2類指標的優(yōu)點提出了基于混合指標的節(jié)點重要度評估方法.Zareie等人[10]結(jié)合節(jié)點的鄰居信息、影響力范圍以及范圍內(nèi)的影響力強度提出了多樣性強度中心性(diversity strength centrality, DSC)指標對節(jié)點的重要度做出評估.文獻[11]綜合考慮節(jié)點的拓撲結(jié)構(gòu)、動力學特征,采用時序游走得到節(jié)點的路徑信息,并定義了傳播中心性和接收溝通性指標.文獻[12]對傳統(tǒng)的h-index指標進行改進,考慮了傳統(tǒng)h-index未考慮的全局性信息,提出了擴展的h-index(extended h-index, EH)指標.文獻[13]提出一種快速的混合指標評估方法,通過計算網(wǎng)絡(luò)中節(jié)點的簡單指標(DC、聚類系數(shù)、k-shell)與復雜指標(CC、BC、網(wǎng)絡(luò)效率)構(gòu)建知識庫,利用層次分析法將復雜指標進行融合得到重要度指標,再通過最小二乘支持向量機找到簡單指標與重要度指標的映射關(guān)系.文獻[14]采用4種傳統(tǒng)的中心性指標對多層網(wǎng)絡(luò)中不同網(wǎng)絡(luò)層節(jié)點的中心性和權(quán)威性進行量化,得到一個4維張量,通過張量計算將網(wǎng)絡(luò)中所有節(jié)點和層的信息結(jié)合起來,得到張量奇異向量中心性指標評估多層網(wǎng)絡(luò)中節(jié)點的重要性.

近年來,研究人員從數(shù)據(jù)挖掘的角度,利用機器學習算法對網(wǎng)絡(luò)中的節(jié)點重要度進行評估.文獻[15]利用網(wǎng)絡(luò)嵌入技術(shù)提取電力網(wǎng)絡(luò)的網(wǎng)絡(luò)信息,結(jié)合節(jié)點本身的屬性信息,利用支持向量回歸機對電力網(wǎng)絡(luò)的節(jié)點重要度進行評估.

上述研究為解決機會網(wǎng)絡(luò)節(jié)點重要度評估問題提供了豐富的思路和解決方案,但多數(shù)方法是針對拓撲結(jié)構(gòu)變化緩慢的社交網(wǎng)絡(luò)所設(shè)計[16-21],無法直接應用于機會網(wǎng)絡(luò).本文針對機會網(wǎng)絡(luò)的動態(tài)性與時變性特點,對機會網(wǎng)絡(luò)進行切片處理,將切片后的網(wǎng)絡(luò)快照表示為機會網(wǎng)絡(luò)單元,通過對機會網(wǎng)絡(luò)單元建立圖模型,確定圖模型中節(jié)點間連邊的權(quán)值構(gòu)建網(wǎng)絡(luò)屬性矩陣,表征網(wǎng)絡(luò)拓撲信息;采用基于自編碼器結(jié)構(gòu)的動態(tài)網(wǎng)絡(luò)嵌入方法,將網(wǎng)絡(luò)屬性矩陣作為輸入,從網(wǎng)絡(luò)的時序變化信息以及拓撲結(jié)構(gòu)信息2個方面獲取機會網(wǎng)絡(luò)的網(wǎng)絡(luò)動態(tài)屬性特征;引入圖神經(jīng)網(wǎng)絡(luò)構(gòu)建節(jié)點重要度評估模型,實現(xiàn)節(jié)點間鄰域信息的融合,從而建立網(wǎng)絡(luò)動態(tài)屬性特征與節(jié)點重要度的映射關(guān)系,對機會網(wǎng)絡(luò)節(jié)點的重要度進行評估.

2 網(wǎng)絡(luò)拓撲信息的表征

本文將連續(xù)的機會網(wǎng)絡(luò)數(shù)據(jù)按照時間切片劃分為離散的機會網(wǎng)絡(luò)單元,建立機會網(wǎng)絡(luò)單元對應的圖模型以構(gòu)建機會網(wǎng)絡(luò)單元的帶權(quán)鄰接矩陣(本文稱網(wǎng)絡(luò)屬性矩陣),將多個網(wǎng)絡(luò)屬性矩陣組成的張量作為動態(tài)網(wǎng)絡(luò)嵌入模型的輸入,以進一步提取網(wǎng)絡(luò)信息.

2.1 機會網(wǎng)絡(luò)數(shù)據(jù)的轉(zhuǎn)化

本文主要研究機會網(wǎng)絡(luò)中的便攜設(shè)備交換網(wǎng)絡(luò)(pocket switched network, PSN),其數(shù)據(jù)集的數(shù)據(jù)格式如圖2所示：

Fig. 1 Schematic diagram of opportunistic network communication圖1 機會網(wǎng)絡(luò)通信示意圖

Fig. 2 Data format圖2 數(shù)據(jù)格式

Fig. 3 Evolution process of opportunistic network topology圖3 機會網(wǎng)絡(luò)拓撲的演化過程

Fig. 4 The effective records in each opportunistic network unit of MIT under different slice time length圖4 不同切片時長下MIT各機會網(wǎng)絡(luò)單元內(nèi)有效記錄

Fig. 5 The effective records in each opportunistic network unit of Haggle under different slice time length圖5 不同切片時長下Haggle各機會網(wǎng)絡(luò)單元內(nèi)有效記錄

Fig. 6 The effective records in each opportunistic network unit of Asturias-er under different slice time length圖6 不同切片時長下Asturias-er各機會網(wǎng)絡(luò)單元內(nèi)有效記錄

Fig. 8 Node importance evaluation model based on GNN圖8 基于GNN的節(jié)點重要度評估模型

Fig. 9 Influence of Δt on NDCG@10 of MIT圖9 MIT數(shù)據(jù)集上Δt對NDCG@10的影響

Fig. 10 Influence of Δt on NDCG@10 of Haggle圖10 Haggle數(shù)據(jù)集上Δt對NDCG@10的影響

Fig. 11 Influence of Δt on NDCG@10 of Asturias-er圖11 Asturias-er數(shù)據(jù)集上Δt對NDCG@10的影響

Fig. 12 Comparison of network message propagation rate圖12 網(wǎng)絡(luò)消息傳播速率對比

Fig. 13 Comparison of network message coverage圖13 網(wǎng)絡(luò)消息覆蓋范圍對比

Fig. 14 Comparison of different methods top1～5 under MIT圖14 MIT下不同方法top1～5對比

Fig. 15 Comparison of different methods top1～5 under Haggle圖15 Haggle下不同方法top1～5對比

Fig. 16 Comparison of different methods top1～5 under Asturias-er圖16 Asturias-er下不同方法top1～5對比

利用原始數(shù)據(jù)中節(jié)點對的連接情況,計算節(jié)點對之間的連接持續(xù)時長以及連接次數(shù).具體地,節(jié)點對[1,3]在第1秒連接類型為“up”,在第3秒的連接類型為“down”,則連接時長為3-1=2 s,節(jié)點對[1,3]在整個原始數(shù)據(jù)中的up,down狀態(tài)成對存在的次數(shù)為12次,則節(jié)點對[1,3]的連接次數(shù)為12次.

2.2 機會網(wǎng)絡(luò)單元的切分

根據(jù)機會網(wǎng)絡(luò)的動態(tài)性與時變性,將連續(xù)的原始數(shù)據(jù)集按照時間片切分為離散的機會網(wǎng)絡(luò)單元.原始的機會網(wǎng)絡(luò)表示為G,按照時間片進行切分可將連續(xù)的機會網(wǎng)絡(luò)表示為由一系列機會網(wǎng)絡(luò)單元組成的有序集合G={G1,G2,…,GN}.其中,N=T/Δt為機會網(wǎng)絡(luò)單元的數(shù)量,T為整個機會網(wǎng)絡(luò)數(shù)據(jù)集持續(xù)時長,Δt為機會網(wǎng)絡(luò)單元切片時長,G1表示初始機會網(wǎng)絡(luò)單元,G2表示間隔一個切片時長的機會網(wǎng)絡(luò)單元,依此類推,GN為最后一個機會網(wǎng)絡(luò)單元,以MIT數(shù)據(jù)集為例,將其網(wǎng)絡(luò)拓撲結(jié)構(gòu)可視化后,其演化過程如圖3所示.對機會網(wǎng)絡(luò)單元建立對應的聚合圖模型,使用Gt={Vt,Et,Wt}表示第t(t=1,2,…,N)個機會網(wǎng)絡(luò)單元的聚合圖,Vt表示在第t個機會網(wǎng)絡(luò)單元上的節(jié)點集合,Et表示在第t個機會網(wǎng)絡(luò)單元上邊的集合,Wt表示第t個機會網(wǎng)絡(luò)單元上對應邊上的權(quán)值的集合.

機會網(wǎng)絡(luò)單元切片時長Δt的長短直接關(guān)系到網(wǎng)絡(luò)拓撲信息的表征能力.針對該問題,文獻[22]對具有代表性的機會網(wǎng)絡(luò)數(shù)據(jù)集進行統(tǒng)計分析,從機會網(wǎng)絡(luò)的持續(xù)性與周期性2個角度,提出了基于鄰接相關(guān)系數(shù)、聚類系數(shù)和節(jié)點平均度確定切片時長的方法.借鑒該方法,一方面考慮到切片時長Δt太短導致機會網(wǎng)絡(luò)單元拓撲圖過于稀疏,無法準確描述機會網(wǎng)絡(luò)中節(jié)點間的連接情況,另一方面考慮切片時長Δt太長導致機會網(wǎng)絡(luò)單元內(nèi)拓撲圖過于密集、節(jié)點間連接頻繁,導致無法準確區(qū)分節(jié)點重要度的情況.本文對所使用的3個數(shù)據(jù)集按照不同切片時長進行切片得到機會網(wǎng)絡(luò)單元,分別統(tǒng)計每個機會網(wǎng)絡(luò)單元內(nèi)有效記錄的次數(shù),其結(jié)果如圖4～6所示.

按照Δt∈{0.5 d,1 d,10 d,30 d}對MIT數(shù)據(jù)集進行切片,分別統(tǒng)計每個機會網(wǎng)絡(luò)單元內(nèi)的有效記錄情況.由圖4可知,當Δt=0.5 d和Δt=1 d時,有效記錄次數(shù)呈現(xiàn)明顯的波動性,大多數(shù)機會網(wǎng)絡(luò)單元內(nèi)的有效記錄次數(shù)非常少,導致網(wǎng)絡(luò)拓撲結(jié)構(gòu)過于稀疏,節(jié)點大多處于未連接狀態(tài),因此無法獲取有效的拓撲信息.當Δt=30 d時,有效記錄次數(shù)均大于20 000條,大部分節(jié)點間都發(fā)生頻繁的連接,導致網(wǎng)絡(luò)拓撲過于密集,無法通過拓撲結(jié)構(gòu)信息區(qū)分節(jié)點的重要度.因此,采用Δt=10 d作為MIT數(shù)據(jù)集的候選切片時長,通過實驗確定最終切片時長.

按照Δt∈{0.5 h,1 h,4 h,8 h}對Haggle數(shù)據(jù)集進行切分統(tǒng)計各機會網(wǎng)絡(luò)單元內(nèi)的有效記錄情況.由圖5可知,當切片時長Δt=0.5 h與Δt=1 h時,有效記錄數(shù)呈明顯的波動性,且大多數(shù)機會網(wǎng)絡(luò)單元內(nèi)不存在有效的連接,導致機會網(wǎng)絡(luò)單元形成的網(wǎng)絡(luò)拓撲中絕大部分節(jié)點處于孤立狀態(tài),網(wǎng)絡(luò)拓撲極為稀疏,無法通過網(wǎng)絡(luò)的拓撲連接情況對節(jié)點的重要度進行評估.當切片時長為Δt=8 h時,有效連接數(shù)量的均值大于25 000條,大部分節(jié)點頻繁連接,導致網(wǎng)絡(luò)拓撲過于密集,無法通過拓撲結(jié)構(gòu)信息對不同節(jié)點的重要度做出評估.因此,將有效記錄數(shù)量過于稀疏或密集的時間切片長度剔除,采用Δt=4 h作為Haggle的候選切片時長,通過實驗確定最終切片時長.

按照Δt∈{6 h,24 h,48 h,96 h}對Asturias-er數(shù)據(jù)集進行切片,分別統(tǒng)計每個機會網(wǎng)絡(luò)單元內(nèi)的有效記錄情況.由圖6可知,當Δt=6 h和Δt=24 h時,得到的有效記錄次數(shù)呈現(xiàn)明顯的波動性,機會網(wǎng)絡(luò)單元內(nèi)大多數(shù)機會網(wǎng)絡(luò)單元網(wǎng)絡(luò)拓撲結(jié)構(gòu)過于稀疏,節(jié)點大多屬于未連接狀態(tài),因此無法獲取有效的拓撲信息.當Δt=96 h,機會網(wǎng)絡(luò)單元內(nèi)的有效記錄次數(shù)均大于60 000條,節(jié)點間連接頻繁,無法通過拓撲結(jié)構(gòu)信息區(qū)分節(jié)點的重要度.因此,采用Δt=48 h作為Asturias-er數(shù)據(jù)集的候選切片時長,通過實驗確定最終切片時長.

2.3 網(wǎng)絡(luò)屬性矩陣的構(gòu)建

按照切片時長將連續(xù)的機會網(wǎng)絡(luò)切分為離散的機會網(wǎng)絡(luò)單元并建立相應的圖模型.考慮到機會網(wǎng)絡(luò)中的通信是以人攜帶智能手機、藍牙通信設(shè)備進行數(shù)據(jù)交換,人具有社會性,相互通信的持續(xù)時長的頻繁程度取決于通信雙方的親密程度.因此,為了準確描述機會網(wǎng)絡(luò)中節(jié)點間的關(guān)系,本文采用節(jié)點間的連接次數(shù)以及連接持續(xù)時長表征節(jié)點間連邊的權(quán)重.具體地,在機會網(wǎng)絡(luò)單元Gt=(Vt,Et,Wt)中邊的權(quán)值Wt可表示為該機會網(wǎng)絡(luò)單元內(nèi)存在連接的節(jié)點間的連接次數(shù)與連接持續(xù)時長之積

(1)

依據(jù)機會網(wǎng)絡(luò)單元的拓撲狀態(tài)來構(gòu)建相應的帶權(quán)鄰接矩陣(本文稱為網(wǎng)絡(luò)屬性矩陣)為

(2)

3 節(jié)點重要度評估

本文以網(wǎng)絡(luò)屬性矩陣作為動態(tài)網(wǎng)絡(luò)嵌入模型的輸入,利用動態(tài)網(wǎng)絡(luò)嵌入方法將機會網(wǎng)絡(luò)單元之間的時序變化信息以及拓撲結(jié)構(gòu)信息壓縮到特征空間中以獲取網(wǎng)絡(luò)動態(tài)屬性特征,并以節(jié)點動態(tài)屬性特征向量的形式表示.之后,利用圖神經(jīng)網(wǎng)絡(luò)構(gòu)建節(jié)點重要度評估模型,建立節(jié)點動態(tài)屬性特征與節(jié)點重要度的映射關(guān)系,從而對節(jié)點重要度進行評估.

3.1 動態(tài)網(wǎng)絡(luò)嵌入模型的構(gòu)建

本文采用基于自編碼器的動態(tài)網(wǎng)絡(luò)嵌入模型提取網(wǎng)絡(luò)動態(tài)屬性特征.本節(jié)在介紹模型結(jié)構(gòu)的基礎(chǔ)上,從時序信息的提取和拓撲結(jié)構(gòu)信息的提取闡述模型的實現(xiàn).

3.1.1 模型結(jié)構(gòu)

自編碼器模型可以通過一系列非線性映射操作將網(wǎng)絡(luò)的原始特征映射到一個低維的特征空間中。模型的目的是盡可能地使得原始特征和重構(gòu)特征保持相似性,從而達到在降維和嵌入過程中降低網(wǎng)絡(luò)信息的損失.基于此,本文采用基于自編碼器的動態(tài)網(wǎng)絡(luò)嵌入模型提取網(wǎng)絡(luò)動態(tài)屬性特征.將機會網(wǎng)絡(luò)對應的多個網(wǎng)絡(luò)屬性矩陣作為輸入,每個網(wǎng)絡(luò)屬性矩陣都要經(jīng)過一系列的解碼和編碼操作,同時為了提取機會網(wǎng)絡(luò)的時序變化信息以及拓撲結(jié)構(gòu)信息,增加了編碼階段對原始特征整合的隱藏層和解碼階段對嵌入特征分解的隱藏層,最終得到由節(jié)點動態(tài)屬性嵌入向量組成的網(wǎng)絡(luò)動態(tài)屬性嵌入矩陣作為模型的輸出.動態(tài)網(wǎng)絡(luò)嵌入模型的結(jié)構(gòu)如圖7所示.

模型包括編碼與解碼2部分：1)編碼部分的作用是將原始特征向量映射到嵌入空間中;2)解碼部分恢復嵌入向量到重構(gòu)空間中.

在編碼部分,xi代表節(jié)點的原始特征,即機會網(wǎng)絡(luò)單元中節(jié)點i的屬性向量mi,yi為編碼器部分隱藏層的潛在特征,在嵌入空間中的編碼結(jié)果表示為hi∈F(F為節(jié)點嵌入維數(shù)),這些變量之間的關(guān)系為

(3)

(4)

(5)

在解碼部分,輸入為動態(tài)屬性嵌入向量hi∈F,輸出為重構(gòu)向量表示隱藏層的潛在特征,這些變量間的關(guān)系為

(6)

(7)

(8)

最終,將機會網(wǎng)絡(luò)對應的多個網(wǎng)絡(luò)屬性矩陣M=(M1,M2,…,MN)作為自編碼器輸入,經(jīng)過若干層的編碼和解碼操作,得到由節(jié)點動態(tài)屬性嵌入向量組成的網(wǎng)絡(luò)動態(tài)屬性嵌入矩陣H=(h1,h2,…,hn)∈n×F作為模型的輸出.

3.1.2 時序變化信息的提取

為了提取整個時序序列上機會網(wǎng)絡(luò)單元間的時序變化信息,采用類增量學習式的策略,在訓練的過程中充分利用歷史的訓練結(jié)果.讓時刻τ網(wǎng)絡(luò)單元對應的嵌入模型繼承時刻τ-1網(wǎng)絡(luò)單元訓練好的參數(shù),對第t個機會網(wǎng)絡(luò)單元的網(wǎng)絡(luò)信息進行迭代訓練,得到新的模型參數(shù)θt.進一步地,在經(jīng)過有限個該過程的迭代實現(xiàn)整個時序序列上時序信息的提取.采用該策略：其一加快了整個動態(tài)網(wǎng)絡(luò)嵌入模型的訓練收斂速度,使之更貼合機會網(wǎng)絡(luò)的時變特性；其二確保最終得到的節(jié)點動態(tài)嵌入矩陣H=(h1,h2,…,hn)能夠有效表征整個時序序列上網(wǎng)絡(luò)的時序變化信息.

3.1.3 拓撲結(jié)構(gòu)信息的提取

為了使節(jié)點動態(tài)屬性嵌入向量更準確地表征網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息,構(gòu)建相應的損失函數(shù).通過不斷最小化機會網(wǎng)絡(luò)中節(jié)點的屬性向量與重構(gòu)向量之間的編碼損失,使得節(jié)點動態(tài)嵌入向量能夠從局部結(jié)構(gòu)以及全局結(jié)構(gòu)上表征節(jié)點在網(wǎng)絡(luò)中的拓撲信息.

(9)

(10)

加入L1正則項,輔助模型產(chǎn)生稀疏矩陣,得到:

(11)

得到模型的損失函數(shù)為

L=Lglob+αLloc+βL1.

(12)

3.2 節(jié)點重要度評估模型的構(gòu)建

利用GNN對圖數(shù)據(jù)強大的特征自動化提取能力,避免傳統(tǒng)方法人工構(gòu)建網(wǎng)絡(luò)中節(jié)點重要度特征.通過動態(tài)網(wǎng)絡(luò)嵌入模型得到的節(jié)點動態(tài)屬性嵌入向量組成的網(wǎng)絡(luò)動態(tài)屬性特征矩陣作為重要度評估模型的輸入,以構(gòu)建節(jié)點動態(tài)屬性嵌入向量與節(jié)點重要度之間的映射關(guān)系.節(jié)點重要度評估模型如圖8所示：

3.2.1 圖神經(jīng)網(wǎng)絡(luò)的確定

考慮到機會網(wǎng)絡(luò)相鄰節(jié)點間的重要度存在相互影響的情況,且節(jié)點間通信次數(shù)與通信時長會直接影響到節(jié)點間重要度的傳遞.為了有效地提取節(jié)點間重要度的相互影響關(guān)系,構(gòu)建圖神經(jīng)網(wǎng)絡(luò)將節(jié)點的動態(tài)屬性嵌入向量按照節(jié)點間關(guān)系進行加權(quán)聚合,實現(xiàn)節(jié)點間鄰域信息的融合.文獻[24]提出了一種基于圖數(shù)據(jù)的自注意力方法實現(xiàn)了一種根據(jù)節(jié)點間的關(guān)聯(lián)關(guān)系對相鄰節(jié)點進行卷積操作的圖注意力網(wǎng)絡(luò)(graph attention network, GAT).引入該方法中所提出的GAT構(gòu)建節(jié)點重要度評估模型.

3.2.2 注意力因子的構(gòu)造

根據(jù)文獻[24]所提出的圖注意力網(wǎng)絡(luò),首先將節(jié)點動態(tài)屬性嵌入矩陣H=(h1,h2,…,hn)作為圖注意力網(wǎng)絡(luò)的輸入,其中,hi∈F,n為節(jié)點總數(shù),F為節(jié)點動態(tài)屬性嵌入向量的維數(shù).使用F′表示經(jīng)過圖注意力網(wǎng)絡(luò)的輸出,F′為更新后的節(jié)點動態(tài)屬性嵌入向量維數(shù).對于節(jié)點動態(tài)屬性嵌入向量hi,首先通過一個節(jié)點共享的特征轉(zhuǎn)換矩陣W∈F×F′進行線性變換,再通過注意力機制a∈2F′計算節(jié)點間的注意力系數(shù),此后通過softmax函數(shù)對節(jié)點與其鄰居的注意力系數(shù)進行歸一化操作得到節(jié)點間的注意力因子,最后利用注意力因子對節(jié)點的動態(tài)屬性嵌入向量進行加權(quán)求和,得到融合了領(lǐng)域信息的新的節(jié)點動態(tài)屬性嵌入矩陣具體地,相鄰節(jié)點對(i,j)之間的注意力系數(shù)為

eij=a(Whi,Whj),

(13)

其中,a為單層前饋神經(jīng)網(wǎng)絡(luò)實現(xiàn)的注意力函數(shù),通過a計算相鄰節(jié)點間的注意力系數(shù)eij,該系數(shù)表征了節(jié)點j與節(jié)點i的動態(tài)屬性嵌入向量之間關(guān)聯(lián)關(guān)系.

進一步地,為了方便計算節(jié)點i與其鄰居節(jié)點之間的注意力系數(shù),利用softmax函數(shù)對其進行歸一化,得到相鄰節(jié)點對(i,j)之間的注意力因子:

(14)

其中,Ni表示節(jié)點i的鄰居節(jié)點集合,即機會網(wǎng)絡(luò)中與節(jié)點i存在通信關(guān)系的節(jié)點集合.通過αij計算節(jié)點對(i,j)的動態(tài)屬性嵌入向量的線性組合,從而對節(jié)點i的動態(tài)屬性嵌入向量進行更新:

(15)

為了提高模型的性能,引入多頭注意力機制:

(16)

本文實驗采用LeakyReLU(leak系數(shù)設(shè)置為0.01)作為注意力機制的非線性激活函數(shù).根據(jù)文獻[24],多頭注意力機制的頭數(shù)設(shè)置為4.

3.2.3 損失函數(shù)

構(gòu)建基于均方誤差(mean squared error, MSE)的監(jiān)督損失函數(shù)：

(17)

其中,N為樣本總數(shù),sn為節(jié)點n通過模型得到節(jié)點重要度分數(shù)評估值,gn為節(jié)點n的重要度分數(shù)真實值.MSE越小,模型的評估值與真實值的差異越小,對節(jié)點重要度評估越準確.

4 實驗結(jié)果及分析

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

本文實驗在CRAWDAD[25]提供的稀疏型機會網(wǎng)絡(luò)、密集型機會網(wǎng)絡(luò)以及大型機會網(wǎng)絡(luò)的真實數(shù)據(jù)集上進行.3個數(shù)據(jù)集的主要信息如表1所示：

Table 1 Trace Data Information表1 Trace數(shù)據(jù)信息

1) MIT reality數(shù)據(jù)集.記錄了100個攜帶Nokia 6600手機的用戶自2004-10—2005-05共246 d,利用藍牙接口相遇的數(shù)據(jù)(300 s采集1次).

2) Haggle項目數(shù)據(jù)集.收集了Infocom2006年會98位參會人員3 d攜帶藍牙接口相遇的數(shù)據(jù)(120 s采集1次).

3) Asturias-er數(shù)據(jù)集.記錄了229臺車載無線通信設(shè)備或GPS設(shè)備在2011-10—2012-10期間生成的數(shù)據(jù)(30 s采集1次).

本文采用Pycharm對機會網(wǎng)絡(luò)數(shù)據(jù)集進行分析、處理,將其轉(zhuǎn)化為網(wǎng)絡(luò)屬性矩陣.采用Keras框架作為動態(tài)網(wǎng)絡(luò)嵌入模型以及節(jié)點重要度評估模型的訓練工具.利用Python圖形庫Matplotlib對實驗數(shù)據(jù)以及實驗結(jié)果進行可視化.采用Gephi網(wǎng)絡(luò)分析工具對機會網(wǎng)絡(luò)數(shù)據(jù)集進行統(tǒng)計分析與可視化.

4.2 評價方法

采用SI(susceptible infected)，SIR(susceptible infected recovered)傳播模型評價和比較本文所提出的節(jié)點重要度評估方法;采用NDCG@10(nor-malized discounted cumulative gain)對節(jié)點重要度排序列表的質(zhì)量進行評價.

1) 基于傳播模型的評價

通常認為,機會網(wǎng)絡(luò)這類以消息傳遞為主的網(wǎng)絡(luò)中,節(jié)點的重要度體現(xiàn)于節(jié)點在網(wǎng)絡(luò)中對消息的傳播能力[26].因此采用基于信息傳播模型的評價方法對節(jié)點在網(wǎng)絡(luò)中信息傳遞的重要度進行評價.利用SI與SIR感染模型[26]中網(wǎng)絡(luò)感染節(jié)點總數(shù)來衡量節(jié)點的重要度,SI感染模型將網(wǎng)絡(luò)中的節(jié)點分為2種狀態(tài),分別為易感染態(tài)和感染態(tài),其中易感染態(tài)表示節(jié)點還未被感染疾病,但由于節(jié)點間的接觸會被其他節(jié)點感染,感染態(tài)表示已經(jīng)感染疾病的節(jié)點,易感態(tài)節(jié)點在被感染節(jié)點感染后無法被恢復.SIR模型則多出一種狀態(tài)為免疫態(tài),感染節(jié)點以恢復率恢復為免疫態(tài).假設(shè)初始時刻t0將總節(jié)點數(shù)為n的未感染網(wǎng)絡(luò)中i0個節(jié)點設(shè)置為感染源,剩余n-i個節(jié)點為未感染節(jié)點,感染概率為p.那么在時刻i感染節(jié)點總數(shù)為

(18)

具體地,在實驗中,通過本文方法得到所有節(jié)點的重要度,并按照重要度大小對節(jié)點進行排序,得到排序列表中重要度排名靠前的節(jié)點作為傳播模型的感染源,利用SI和SIR感染模型比較在同一時間內(nèi)感染節(jié)點的數(shù)量.采用SI模型評價本文方法的合理性,采用SIR比較本文方法和其他方法.

2) 基于相關(guān)性的評價

歸一化折扣累計增益(normalized discounted cumulative gain,NDCG)常用于評價排序列表的質(zhì)量.該指標的取值范圍為[0,1],值越大,說明給定的排序列表與理想排序列表越接近,即說明節(jié)點重要度評估方法越優(yōu).給定一個按照節(jié)點重要度分數(shù)的排序列表,排序列表中排名前k位的折扣累計增益為

(19)

其中,ri為排序列表中位于第i位節(jié)點的重要度分數(shù),考慮到理想排序列表(即按照節(jié)點真實重要度分數(shù)得到的排序列表)中前k位的理想折扣累計增益(IDCG@k),進行歸一化操作得到歸一化折扣累計增益為

(20)

4.3 實驗參數(shù)設(shè)置

實驗參數(shù)設(shè)置包括機會網(wǎng)絡(luò)單元切片時長Δt的設(shè)置和動態(tài)網(wǎng)絡(luò)嵌入模型中超參數(shù)的設(shè)置.

1) 機會網(wǎng)絡(luò)單元切片時長Δt

考慮機會網(wǎng)絡(luò)數(shù)據(jù)集持續(xù)性與周期性[27],確定MIT，Haggle，Asturias-er的候選切片時長分別為10 d,4 h,48 h.以候選切片時長為基準，按照Δt∈{8 d,9 d,10 d,11 d,12 d},在MIT數(shù)據(jù)集上,根據(jù)Δt對排序質(zhì)量NDCG@10的影響,最終確定切片時長，實驗結(jié)果如圖9所示.其中Δt=11 d時NDCG@10取值最優(yōu).因此,本文選取機會網(wǎng)絡(luò)單元切片時長Δt=11 d作為MIT的切片時長.

以候選切片時長Δt=2 h為基準,按照Δt∈{2 h,3 h,4 h,5 h,6 h},在Haggle數(shù)據(jù)集上,根據(jù)Δt對排序質(zhì)量NDCG@10的影響,最終確定切片時長.實驗結(jié)果如圖10所示.其中Δt=3 h時NDCG@10取值最優(yōu).因此,本文選取Δt=3 h作為Haggle的切片時長.

以候選切片時長Δt=48 h為基準,按照Δt∈{36 h,42 h,48 h,54 h,60 h},在Asturias-er數(shù)據(jù)集上,根據(jù)Δt對排序質(zhì)量NDCG@10的影響,最終確定切片時長.實驗結(jié)果如圖11所示.其中Δt=48 h時NDCG@10取值最優(yōu).因此,本文選取Δt=48 h為Asturias-er的切片時長.

2) 動態(tài)網(wǎng)絡(luò)嵌入模型的超參數(shù)

在基于自編碼器的動態(tài)網(wǎng)絡(luò)嵌入模型中,超參數(shù)的具體配置為:網(wǎng)絡(luò)嵌入的最佳網(wǎng)絡(luò)嵌入維數(shù)與網(wǎng)絡(luò)的規(guī)模和密度相關(guān)[27],考慮到所選機會網(wǎng)絡(luò)數(shù)據(jù)集的規(guī)模(節(jié)點數(shù)目均小于300)以及機會網(wǎng)絡(luò)的稀疏性(網(wǎng)絡(luò)密度較小),將MIT，Haggle，Asturias-er的網(wǎng)絡(luò)嵌入維數(shù)設(shè)置為F=32；考慮到網(wǎng)絡(luò)中節(jié)點的全局結(jié)構(gòu)相較于局部結(jié)構(gòu)更能反映節(jié)點在網(wǎng)絡(luò)中的重要程度[28]且正則項主要是輔助模型的訓練,故設(shè)置式(12)中的α=10-5,β=10-4.采用Adam學習算法對自編碼器進行訓練,迭代次數(shù)設(shè)置為200,編碼器與解碼器隱藏層數(shù)量均為4,每層的神經(jīng)元數(shù)量分別為n,84,64,32(n為網(wǎng)絡(luò)節(jié)點數(shù)量),學習率參數(shù)設(shè)置為0.001.

4.4 實驗結(jié)果

實驗分為2個部分：1)通過信息傳播模型評價節(jié)點在機會網(wǎng)絡(luò)中的消息傳播能力;2)通過相關(guān)性分析,利用NDCG@10衡量本文方法與其他方法所得到的節(jié)點重要度排序列表的質(zhì)量.

1) 節(jié)點在機會網(wǎng)絡(luò)中的消息傳播能力

機會網(wǎng)絡(luò)中節(jié)點的核心任務(wù)是消息的投遞,網(wǎng)絡(luò)中不同個體的社會屬性決定了其在網(wǎng)絡(luò)中對于消息的傳播能力,而在網(wǎng)絡(luò)中節(jié)點對消息的傳播能力可分為對消息的傳播速率和覆蓋范圍.本文提出的機會網(wǎng)絡(luò)節(jié)點重要度評估方法,目的是找到并利用消息傳播能力較高的節(jié)點以提高整個網(wǎng)絡(luò)的消息傳播效率.因此,本文通過實驗1驗證節(jié)點重要度高的節(jié)點對于消息的傳播速率影響,通過實驗2驗證節(jié)點重要度高的節(jié)點對于消息覆蓋范圍的影響.

實驗1.采用SI傳播模型考察本文方法得到的節(jié)點重要度列表中排名不同的節(jié)點的消息傳播速率,進而說明本文方法的有效性.為了直觀地展示網(wǎng)絡(luò)中不同節(jié)點的消息傳播速率,選取節(jié)點重要度排序列表中間隔相同的5個節(jié)點分別單獨作為消息源對比其消息傳播速率.若排名靠前的節(jié)點在消息的傳播速率(即圖12中曲線下的覆蓋面積)上要高于排名靠后的節(jié)點,則說明重要度高的節(jié)點能夠更快地使消息傳播到更多的節(jié)點上,進而驗證本文方法對節(jié)點重要度的評估是有效的.具體地,根據(jù)經(jīng)驗值設(shè)定SI傳播模型的傳播概率,觀察消息的傳播速率.圖12(a)為MIT數(shù)據(jù)集下,選取節(jié)點重要度排序列表中第1(即top節(jié)點)、第25、第50、第75以及最后1名(即bottom節(jié)點)的5個節(jié)點分別作為SI傳播模型的傳播源的消息傳播速率情況.從實驗結(jié)果可知,由于MIT數(shù)據(jù)集持續(xù)時間較長,且有效記錄數(shù)較少,導致網(wǎng)絡(luò)連接較為稀疏,將單一節(jié)點作為消息源時,消息能夠覆蓋全網(wǎng)85%左右,top節(jié)點的消息傳播速度明顯快于排名靠后的節(jié)點.從整體趨勢來看,排名靠前的節(jié)點其消息傳播速率上要快于排名靠后的節(jié)點,從逐個節(jié)點傳播情況來看,top節(jié)點的消息傳播速率明顯快于bottom節(jié)點,且節(jié)點重要度排序越靠后其消息覆蓋速率越低.圖12(b)為Haggle數(shù)據(jù)集下,同樣選取節(jié)點重要度排序列表中第1(top)、第25、第50、第75以及最后1名(bottom)的5個節(jié)點進行實驗比較不同節(jié)點的消息傳播速率.從實驗結(jié)果可知,相比于MIT而言,Haggle持續(xù)時間短且有效記錄數(shù)多,節(jié)點間連接較為密集,因此,消息能夠迅速覆蓋到整個網(wǎng)絡(luò).總體上來說,top節(jié)點的消息傳播速率均快于其他節(jié)點,且排名越靠后其消息傳播速率越慢,但由于Haggle數(shù)據(jù)集較MIT數(shù)據(jù)集更密集,使得網(wǎng)絡(luò)中節(jié)點的傳播速率總體上要更高,且top節(jié)點與bottom節(jié)點的差距較MIT也更小.圖12(c)為Asturias-er數(shù)據(jù)集下,選取節(jié)點重要度排序列表中第1(top)、第60、第120、第180以及最后1名(bottom)節(jié)點作為實驗對象考察其消息傳播速率.從實驗結(jié)果可知,由于Asturias-er節(jié)點數(shù)目多且持續(xù)時間長,不同節(jié)點間的消息傳播能力存在明顯差距.從整體上來說,排名越靠后的節(jié)點其在消息傳播速率以及消息覆蓋率上都明顯低于排名靠前的節(jié)點,且排名越靠后其差距越大,從節(jié)點層面上來說,top節(jié)點與bottom節(jié)點間無論是在消息覆蓋范圍和消息傳播速率上都有明顯的差距,top節(jié)點的消息覆蓋率能達到80%左右而bottom節(jié)點的消息覆蓋率不足20%,且在傳播過程中bottom消息傳播速率也要顯著慢于top節(jié)點.

綜上所述,在MIT，Haggle，Asturias-er數(shù)據(jù)集上,實驗結(jié)果表明按照本文方法得到的節(jié)點重要度由高向低將節(jié)點進行排序,等差選取5個節(jié)點單獨作為SI模型的傳播源時,排名靠前的節(jié)點消息傳播速率高于排名靠后的節(jié)點.因此,本文方法得到的節(jié)點重要度能夠準確地描述節(jié)點對于消息的傳播速率,也說明了本文方法是有效的.

實驗2.采用SIR模型比較本文方法和時效度(temporal degree, TD)方法[11]、時效介數(shù)(temporal betweenness, TB)方法[12]、時效PageRank(temporal PageRank, f-PageRank)方法[29]以及kshell-CN方法[30],驗證模型的正確性.具體地,選取時TD，TB，f-PageRank，kshell-CN以及本文方法(以下簡稱GNN)得到的節(jié)點重要度排序列表中排名前5的節(jié)點作為重要節(jié)點集合S,分別將不同方法得到的top1，top2，top3，top4，top5，S作為SIR傳播模型的傳播源,比較不同方法的消息覆蓋范圍.相同的傳播時間步下,消息覆蓋節(jié)點數(shù)越多,則說明節(jié)點重要度評估方法越準確.

表2～4分別給出了在MIT，Haggle，Asturias-er機會網(wǎng)絡(luò)數(shù)據(jù)集下由TD，TB，f-PageRank，kshell-CN，GNN節(jié)點重要度評估方法得到的排名top1～5節(jié)點以及由這些節(jié)點組成的重要節(jié)點集合S.

Table 2 MIT Node Importance Rank Table表2 MIT節(jié)點重要度排序表

Table 3 Haggle Node Importance Rank Table表3 Haggle節(jié)點重要度排序表

Table 4 Asturias-er Node Importance Rank Table表4 Asturias-er節(jié)點重要度排序表

首先,以S為傳播源考察3個數(shù)據(jù)集下消息覆蓋范圍結(jié)果,圖13為實驗結(jié)果.從圖13(a)中可以看出,由于MIT數(shù)據(jù)集屬于稀疏型機會網(wǎng)絡(luò),節(jié)點間連接頻率低,整體的消息覆蓋節(jié)點數(shù)較少,本文方法得到的重要節(jié)點集合S作為消息源時,網(wǎng)絡(luò)的消息覆蓋節(jié)點數(shù)要明顯高于TD，TB方法,略高于f-PageRank方法與kshell-CN方法.圖13(b)為Haggle數(shù)據(jù)集網(wǎng)絡(luò)消息覆蓋范圍結(jié)果,由于Haggle數(shù)據(jù)集屬于密集型機會網(wǎng)絡(luò),節(jié)點連接頻繁,即便在相同的傳播條件下,4種方法所得到的消息覆蓋范圍更廣.由本文方法得到的S作為消息源時,網(wǎng)絡(luò)的消息覆蓋率明顯高于TD方法,略高于TB，kshell-CN，f-PageRank方法.圖13(c)為Asturias-er數(shù)據(jù)集網(wǎng)絡(luò)消息覆蓋范圍,Asturias-er數(shù)據(jù)集持續(xù)時間長,且隨著時間的推移參與通信的節(jié)點數(shù)目也隨之增加.總體來說,以本文方法得到的重要節(jié)點集合S作為消息源時網(wǎng)絡(luò)的消息覆蓋范圍均高于其他方法.

其次,逐一考察由不同方法得到的top1～5節(jié)點在SIR傳播模型下的消息覆蓋范圍.圖14～16分別為MIT，Haggle，Asturias-er數(shù)據(jù)集下,不同方法top1～5節(jié)點在SIR傳播模型下的消息覆蓋范圍對比圖.

圖14為MIT數(shù)據(jù)集下top1～5的對比結(jié)果.其中,圖14(a)是不同方法top1節(jié)點的對比情況,根據(jù)表2結(jié)果選取89，56，28號節(jié)點單獨作為SIR傳播模型的傳播源進行實驗,從圖14(a)中可知,89號節(jié)點優(yōu)于56號節(jié)點與28號節(jié)點.類似地,圖14(b)～(e)為按照表2結(jié)果分別比較top2～5不同方法得到的節(jié)點的消息覆蓋范圍.特別地,top4和top5節(jié)點集中在85和95號節(jié)點上,故圖14(d)和圖14(e)均為85號和95號節(jié)點的對比情況.從實驗結(jié)果可知,本文方法在top1，top3，top4，top5的評估更為準確.

圖15為Haggle數(shù)據(jù)集下top1～5的對比結(jié)果.其中,圖15(a)是不同方法top1節(jié)點的對比情況,根據(jù)表3的結(jié)果選取77，86，44號節(jié)點單獨作為SIR傳播模型的傳播源進行實驗,從圖15(a)中可知,77號節(jié)優(yōu)于86與44號節(jié)點.類似地,圖15(b)～(e)分別為top2～5不同方法得到的節(jié)點消息覆蓋范圍.從實驗結(jié)果可知,本文方法在top1～5的評估更為準確.

圖16為Asturias-er數(shù)據(jù)集下top1～5的對比結(jié)果.其中,圖16(a)和圖16(b)是不同方法top1與top2節(jié)點的對比情況,根據(jù)表4不同方法的評估結(jié)果中top1和top2的節(jié)點均是33號和158號節(jié)點,故選取33，158號節(jié)點單獨作為SIR傳播模型的傳播源進行實驗,從圖16(a)中可知,33號節(jié)點與158號節(jié)點消息覆蓋率基本一致,因此多種評估方法的top1與top2節(jié)點均是158號和33號節(jié)點.類似地,圖15(c)(d)(e)分別為top3～5不同方法得到的節(jié)點消息覆蓋范圍.從實驗結(jié)果可知,本文方法在top1，top2，top3，top4的評估更為準確.

綜上所述,在MIT，Haggle，Asturias-er數(shù)據(jù)集上,本文方法得到的top1～5節(jié)點以及由它們組成的重要節(jié)點集合S,在SIR傳播模型上的消息覆蓋率均高于TD方法、TB方法、f-PageRank方法以及kshell-CN方法.這是由于本文方法綜合考慮了節(jié)點的局部拓撲信息、全局拓撲信息、時序變化信息以及節(jié)點間重要度的相互影響關(guān)系,因此,能更加準確地識別出機會網(wǎng)絡(luò)中的重要節(jié)點.

2) 節(jié)點重要度排序列表的質(zhì)量

根據(jù)TD方法、TB方法、f-PageRank方法、kshell-CN方法及本文方法得到節(jié)點重要度的排序列表,將消息傳播模型的結(jié)果作為標準排序.分別計算不同網(wǎng)絡(luò)數(shù)據(jù)集中TD方法、TB方法、f-PageRank方法、kshell-CN方法以及本文方法的NDCG@10,排序質(zhì)量如表5所示:

Table 5 NDCG@10 of Three Datasets表5 3個數(shù)據(jù)集上的NDCG@10值

由表5可知,由于MIT數(shù)據(jù)集持續(xù)時間長,且有效記錄數(shù)較少,屬于稀疏性機會網(wǎng)絡(luò),采用TD與TB方法對節(jié)點重要度評估時,導致網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息以及時序變化信息不能被充分利用,本文方法在排序質(zhì)量上相較于TD方法與TB方法分別提高了22.2%與22.0%,相較于f-PageRank方法提高了7.1%.在Haggle數(shù)據(jù)集中,由于Haggle持續(xù)時間短,節(jié)點間通信頻繁,屬于密集型機會網(wǎng)絡(luò).隨著節(jié)點間的有效通信路徑增加,TB方法能夠更好地刻畫出節(jié)點對于網(wǎng)絡(luò)中有效通信路徑的控制力,因此,評估結(jié)果較TD更好.但相較本文方法,TB方法沒有考慮節(jié)點間重要度的相互影響,故評估效果低于本文方法.在Asturias-er數(shù)據(jù)集中,由于Asturias-er節(jié)點規(guī)模相較于其他2個數(shù)據(jù)集更大且數(shù)據(jù)集持續(xù)時間長,因此能夠獲取的網(wǎng)絡(luò)拓撲信息以及時序變化信息更加豐富,本文方法相較于其他方法能夠更有效地利用這些信息進行節(jié)點重要度的評估,故評估效果均高于其他方法.基于以上分析,本文所提出的方法能夠有效地對機會網(wǎng)絡(luò)中的節(jié)點重要度進行評估,且實驗結(jié)果表明本文方法在多個評價方法上優(yōu)于現(xiàn)有其他方法.

5 總 結(jié)

本文方法針對機會網(wǎng)絡(luò)的動態(tài)性與時變性,利用機會網(wǎng)絡(luò)數(shù)據(jù)的歷史連接信息有效地對機會網(wǎng)絡(luò)中節(jié)點的重要度進行評估,從而識別出機會網(wǎng)絡(luò)中消息傳播能力強的節(jié)點.實驗結(jié)果表明：本文方法能夠準確識別出在機會網(wǎng)絡(luò)中消息傳播能力強的節(jié)點,將這些節(jié)點作為消息的傳播源時,能提高消息覆蓋率和傳播速率.同時,在稀疏型機會網(wǎng)絡(luò)場景、密集型機會網(wǎng)絡(luò)場景以及大型機會網(wǎng)絡(luò)場景下,本文提出的基于GNN的機會網(wǎng)絡(luò)節(jié)點重要度評估方法,在SI，SIR和NDCG@10評價方法上優(yōu)于TD，TB，f-PageRank，kshell-CN.未來研究將進一步確定機會網(wǎng)絡(luò)單元的最佳切片時長以嘗試改善評估的效果.

作者貢獻聲明：劉琳嵐負責理論模型構(gòu)建、實驗方案設(shè)計和文章撰寫；譚鎮(zhèn)陽提出研究思路，負責實驗數(shù)據(jù)整理與分析、實驗結(jié)果可視化，撰寫初稿；舒堅參與了論文想法的討論，確定研究思路，對于實驗方案提出指導意見，審閱和完善論文內(nèi)容.