基于深度遷移的有向加權(quán)網(wǎng)絡(luò)節(jié)點重疊檢測

王小紅,劉 琴

(青海民族大學(xué)計算機學(xué)院,青海 西寧 810000)

1 引言

隨著通信技術(shù)和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,有向加權(quán)作為眾多網(wǎng)絡(luò)表達形式中的一種,網(wǎng)絡(luò)內(nèi)部節(jié)點分布規(guī)律性較強,但由于眾多節(jié)點的加權(quán)項一致,通過權(quán)值部署很容易出現(xiàn)節(jié)點重疊現(xiàn)象。隨著節(jié)點的不斷堆積,網(wǎng)路規(guī)模逐漸擴大,數(shù)據(jù)量不斷增加,節(jié)點間的關(guān)系也越來越復(fù)雜難以分辨,分布混亂,久而久之形成更為繁雜的網(wǎng)絡(luò),影響運行效率。近年來,這種節(jié)點重疊現(xiàn)象引起了計算機、互聯(lián)網(wǎng)以及電子信息技術(shù)等各個鄰域的重視。

文獻[1]提出一種基于密度峰值和社區(qū)歸屬度的節(jié)點重疊檢測算法。利用佩奇排名算法對網(wǎng)絡(luò)節(jié)點的影響力降序排列,挑選序列值相同的節(jié)點進行標記劃分,找出相同序列值內(nèi)密度值和社區(qū)歸屬度一致的數(shù)據(jù)節(jié)點,判定為重疊點。該方法通過降序排列、標記劃分再到歸屬度和密度值的判定,對于數(shù)量較大的節(jié)點來說,整個過程復(fù)雜度過高、耗用較大、實用性不強;文獻[2]采用粗糙?；瘷z測網(wǎng)絡(luò)嵌入式重疊節(jié)點,描述網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)、特征等屬性,對相似性較高的節(jié)點進行空間映射,明確節(jié)點間重疊關(guān)系。該方法沒有考慮到噪聲干擾的問題,重疊映射的誤差較大

綜合上述問題,本文對有向加權(quán)網(wǎng)絡(luò)中的節(jié)點進行分區(qū)檢測,首先,利用深度遷移算法計算聚合度、分離度,獲得網(wǎng)絡(luò)重疊社區(qū)的中心度值,挑選中心度最高的數(shù)據(jù)節(jié)點作為社區(qū)中心,計算中心節(jié)點在各個社區(qū)的隸屬度,歸屬度最高的社區(qū)即為重疊社區(qū),根據(jù)重疊原理,該社區(qū)內(nèi)一定存在重疊節(jié)點。分別對賦予重疊社區(qū)中相鄰節(jié)點和節(jié)點數(shù)據(jù)邊賦予不同權(quán)重,根據(jù)權(quán)重值求得重疊度。通過預(yù)先判定重疊社區(qū)可降低后續(xù)檢測可能受到的外界干擾,對不同的節(jié)點都能實現(xiàn)精準檢測。

2 基于深度遷移的有向加權(quán)網(wǎng)絡(luò)中心節(jié)點確定

從概率論的角度來看,深度遷移是不斷學(xué)習(xí)不斷獲取信息的過程,應(yīng)用在重疊檢測中,可通過上一遷移任務(wù)重疊節(jié)點信息來獲取下一任務(wù)重疊節(jié)點信息。一般情況下,深度學(xué)習(xí)[3]只涉及兩個域:一個是節(jié)點源域,用E={X,P(X)}表示,其中,X為節(jié)點的特征空間,P(X)表示邊緣節(jié)點[4]的概率分布,X=X1,X1,…,Xm∈X;另一個為目標域,用F={X,P(X)}表示,遷移任務(wù)可以用HT表示。遷移學(xué)習(xí)的目的是在每一個遷移任務(wù)中捕捉到關(guān)鍵信息,通過節(jié)點源域遷移任務(wù)[5],學(xué)習(xí)預(yù)測目標域中重疊的相關(guān)知識。

在進行節(jié)點重疊檢測前,需要在眾多節(jié)點中挑選中心節(jié)點,最簡單的選擇方法就是按照節(jié)點度的排列順序選擇最大的那一個。但該方法存在過大誤差,因為節(jié)點度最大節(jié)點占比權(quán)重不一定是最大的,在有向加權(quán)網(wǎng)絡(luò)中,權(quán)重值較大的節(jié)點才是核心,與剩余節(jié)點之間存在緊密聯(lián)系。通過中心點與節(jié)點之間的關(guān)聯(lián),查找重疊度較高的節(jié)點,降低誤判。本文通過節(jié)點內(nèi)部的分散度和聚合度兩項指標,選取中心點,過程如下:

1)節(jié)點聚合度Ii:是指節(jié)點i與相鄰節(jié)點之間的最大相似度[6]乘積,用于描述節(jié)點之間的聚合關(guān)系,表達形式為:

(1)

2)節(jié)點分離度[7]Ji:是指節(jié)點i與相鄰節(jié)點之間最大相似度的乘積倒數(shù),用于描述節(jié)點間的分離程度,表達形式為:

(2)

3)節(jié)點中心度Ki:是指網(wǎng)絡(luò)節(jié)點聚合度Ii與分離度Ji數(shù)值的乘積,表達形式為

Ki=Ii×Ji

(3)

節(jié)點的中心度值Ki越大,表示成為社區(qū)中心的可能性越大。

3 包含重疊節(jié)點的重疊社區(qū)檢測

在實際的有向加權(quán)網(wǎng)絡(luò)中,由于節(jié)點會受到興趣偏好、特征屬性、區(qū)域位置、密度以及橫縱向維度等多種因素的干擾,很有可能出現(xiàn)多個節(jié)點社區(qū)。因此,要想提高重疊節(jié)點檢測的準確性,需要對網(wǎng)絡(luò)中各個社區(qū)分別進行重疊度檢測。

3.1 重疊社區(qū)隸屬度計算

計算重疊社區(qū)的隸屬度函數(shù)[8]mf(·),mf(·)∈[0,1]。給定一個初始社區(qū)為Aa,該社區(qū)的隸屬度函數(shù)值mf(Aa)越大,代表節(jié)點屬于該社區(qū)的概率越高。由于網(wǎng)絡(luò)中各個社區(qū)內(nèi)部數(shù)據(jù)存在緊密相連關(guān)系,社區(qū)外部的數(shù)據(jù)存在稀疏關(guān)系[9]。計算mf(·)與節(jié)點之間的連接關(guān)系,表達公式如下

(4)

(5)

(6)

式中,Ni∈Aa表示節(jié)點i在社區(qū)Aa內(nèi)相遇的個數(shù);Aa表示社區(qū)內(nèi)全部節(jié)點數(shù)量;ωi表示節(jié)點權(quán)重;ξ表示相遇次數(shù)[10]。當相遇次數(shù)ξ=0時,相遇個數(shù)Ni∈Aa=0,ξ值越大,相遇個數(shù)Ni∈Aa自然會越大,該節(jié)點屬于社區(qū)的概率越高。

3.2 節(jié)點歸屬度計算

通過上述過程判定出節(jié)點的隸屬度關(guān)系,計算待檢測社區(qū)的重疊度。節(jié)點除了對自身所屬的社區(qū)隸屬度較高外,還可能對其它社區(qū)的隸屬度也較高,出現(xiàn)這種現(xiàn)象會影響檢測的精度。為了能精準檢測發(fā)生重疊的社區(qū),計算數(shù)據(jù)對每個社區(qū)的歸屬度值[11]emf(Aa)為

(7)

式中,emfi(Aa)表示初始社區(qū)對外部節(jié)點的歸屬度值,將emf(Aa)和emfi(Aa)進行比較,即可得到重疊社區(qū)為

(8)

式中,Remf(Aa),emfi(Aa)表示檢測出的重疊社區(qū)節(jié)點集合;if表示社區(qū)內(nèi)存在節(jié)點數(shù)據(jù);none表示社區(qū)內(nèi)不存在節(jié)點數(shù)據(jù)。

采用上述方法對有向加權(quán)網(wǎng)絡(luò)節(jié)點社區(qū)進行重疊檢測,可初步判定節(jié)點是否屬于重疊社區(qū)中,在一定程度上提高了檢測的精準性。

4 不同類型節(jié)點重疊檢測算法

4.1 節(jié)點權(quán)重

本文通過賦予重疊社區(qū)內(nèi)所有節(jié)點同等權(quán)重方式,對邊緣節(jié)點和共鄰節(jié)點進行重疊檢測。

設(shè)權(quán)重值集合為G2=(C2,V2,B2),?α∈C2,?β∈V2,其中,C2表示邊緣節(jié)點集合的權(quán)重值,?α∈C2;V2表示共鄰節(jié)點集合的權(quán)重值,?β∈V2;B2表示剩余節(jié)點集合。將節(jié)點α和β的權(quán)重值定義為,與其相鄰的所有節(jié)點權(quán)重和D(x),公式為

(9)

式中,α,β∈φ(x)*表示與節(jié)點相鄰的所有節(jié)點集合;?α,β表示節(jié)點α和β的定義值。

節(jié)點的權(quán)重值可以描述檢測節(jié)點周圍數(shù)據(jù)的連接關(guān)系[12],以圖1、2給出的有向和無向加權(quán)網(wǎng)絡(luò)[13]為例,節(jié)點4的權(quán)重計算為:D(4)=0.7+0.5+0.6=1.8;節(jié)點6的權(quán)重計算為:D(6)=0.3+0.2+0.2+0.4=1.1。

圖1 無向加權(quán)網(wǎng)絡(luò)示意

圖2 有向加權(quán)網(wǎng)絡(luò)示意

4.2 共鄰節(jié)點重疊度檢測

通過權(quán)重賦值概念,給定重疊社區(qū)內(nèi)兩個相近的點為α′、β′,用φα′、φβ′表示兩個節(jié)點之間的重疊度,根據(jù)權(quán)重定義,兩點之間的鄰域重疊比Hφα′φβ′為

(10)

式中,?α′β′表示相鄰數(shù)量,等式分子的值越小代表相鄰節(jié)點的重疊比越大,連接程度越強,重疊概率越高。

(11)

式中,ξ表示數(shù)據(jù)邊的權(quán)重度量[14,15],當數(shù)據(jù)邊之間存在連接時,等式值越大代表數(shù)據(jù)邊之間連接的緊密度越高,反之則為越差。以這種方法取得的重疊度值,較為準確,誤差小。

5 仿真研究

5.1 仿真設(shè)置

本文仿真在One NET(Opportunistic Networks Environ-ment全國物聯(lián)網(wǎng)開放平臺)上進行,該平臺是由移動公司開發(fā)的Paas(Platform as a Servic物聯(lián)網(wǎng)開放終端),具有數(shù)據(jù)覆蓋面廣、儲存量大的優(yōu)勢。為了能驗證本文算法對有向加權(quán)網(wǎng)絡(luò)節(jié)點重疊檢測的效果,與基于社區(qū)歸屬度的重疊節(jié)點檢測算法、基于網(wǎng)絡(luò)嵌入重疊節(jié)點檢測算法進行對比分析。檢測指標分別為:平均檢出率Fd、平均負載程度FOB,其中,平均檢出率Fd驗證正確檢測到重疊節(jié)點占全部節(jié)點的比例值;平均負載程度FOB驗證算法每檢測到一個重疊節(jié)點,相應(yīng)付出的成本,Fd、FOB的計算公式如下

(12)

(13)

式中,Ms表示正確檢測到節(jié)點的數(shù)量;MOC表示出現(xiàn)重疊現(xiàn)象節(jié)點的初始值;M2表示節(jié)點的全部數(shù)量。仿真參數(shù)如表1所示。

表1 仿真參數(shù)

5.2 檢測效果對比

三種方法的平均檢出率、平均負載程度指標測試結(jié)果如圖3、4所示。

圖3 平均檢出率對比曲線

從圖3中可以看出,隨著節(jié)點數(shù)量的不斷增加,所提方法的平均檢測率曲線屬于一種穩(wěn)中略降的變化趨勢,另外兩種方法曲線是劇烈下降趨勢。這是因為節(jié)點數(shù)量上漲打破了原本節(jié)點之間的信息串聯(lián)規(guī)律,使得節(jié)點關(guān)系變得復(fù)雜,節(jié)點間的區(qū)分度變小,難以檢測,導(dǎo)致平均檢測率下降。而本文沒有受到過多影響是因為,預(yù)先劃分了節(jié)點的重疊社區(qū),對社區(qū)內(nèi)中心節(jié)點及邊緣節(jié)點采取不同的檢測手段,來降低因目標不明確或定位模糊帶來的影響。

從圖4中可以看出,在3000檢測點,本文方法平均負載程度比傳統(tǒng)方法要小約0.25左右,曲線的變動幅度不大。其中,基于社區(qū)歸屬度方法檢測耗用代價過高,是因為沒有深度挖掘重疊節(jié)點的信息特征,在分步檢測時,不能根據(jù)節(jié)點間的特征關(guān)聯(lián)快速查找到與其相關(guān)的節(jié)點,需要重復(fù)尋找耗用大;而基于網(wǎng)絡(luò)嵌入重疊算法不能明確節(jié)點的關(guān)鍵特征,例如:密度、大小等,目標過于分散,誤檢率過高,導(dǎo)致需要頻繁二次檢測,代價成本過高,負載率上升。

圖4 平均負載程度對比曲線

5.3 檢測時間對比

重疊檢測時間實驗結(jié)果如圖5所示。

圖5 算法耗用時間曲線對比

從圖5中可以看出,本文算法耗用時間曲線處于較為平穩(wěn)增長趨勢,無論是從整體還是浮動細節(jié)變化來看都要優(yōu)于另外兩種方法。這是因為,本文方法對數(shù)據(jù)類型進行了詳細的劃分,根據(jù)數(shù)據(jù)的不同屬性給出不同的重疊檢測方法,做到了對應(yīng)的檢測,不僅可以保證檢測準確性,也降低了誤檢的可能,沒有額外的時間耗用;而另外兩種方法采用的檢測模式較為單一,不預(yù)先對數(shù)據(jù)劃分,直接從整體出發(fā)進行重疊檢測,初始檢測的時間耗用相對較少,但由于單一的模型存在過多誤差,導(dǎo)致誤檢率及漏檢率高,需要重新檢測計算,反倒增加了時間耗用。

6 結(jié)論

實現(xiàn)重疊節(jié)點的精準檢測對提高有向加權(quán)網(wǎng)絡(luò)運行效率具有非常重要的作用,本文提出了結(jié)合深度遷移學(xué)習(xí)的檢測算法。通過節(jié)點聚合度和節(jié)點分離度得到社區(qū)中的中心節(jié)點,利用中心節(jié)點關(guān)聯(lián)度較高的特性,求得與其隸屬度最高的社區(qū),判定社區(qū)為重疊社區(qū)。采用重疊度權(quán)重計算法得到相鄰節(jié)點和邊緣節(jié)點的重疊度,完成精準檢測。相比普通算法,所提方法對不同節(jié)點實現(xiàn)了對應(yīng)檢測,一步步獲取節(jié)點之間的關(guān)鍵連接關(guān)系,檢測精度高,時間耗用量小,邏輯表達明確,計算步驟簡單易實現(xiàn)。