基于深度遷移的有向加權網絡節點重疊檢測

王小紅,劉 琴

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

1 引言

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

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

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

2 基于深度遷移的有向加權網絡中心節點確定

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

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

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

(1)

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

(2)

3)節點中心度Ki:是指網絡節點聚合度Ii與分離度Ji數值的乘積,表達形式為

Ki=Ii×Ji

(3)

節點的中心度值Ki越大,表示成為社區中心的可能性越大。

3 包含重疊節點的重疊社區檢測

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

3.1 重疊社區隸屬度計算

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

(4)

(5)

(6)

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

3.2 節點歸屬度計算

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

(7)

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

(8)

式中,Remf(Aa),emfi(Aa)表示檢測出的重疊社區節點集合;if表示社區內存在節點數據;none表示社區內不存在節點數據。

采用上述方法對有向加權網絡節點社區進行重疊檢測,可初步判定節點是否屬于重疊社區中,在一定程度上提高了檢測的精準性。

4 不同類型節點重疊檢測算法

4.1 節點權重

本文通過賦予重疊社區內所有節點同等權重方式,對邊緣節點和共鄰節點進行重疊檢測。

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

(9)

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

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

圖1 無向加權網絡示意

圖2 有向加權網絡示意

4.2 共鄰節點重疊度檢測

通過權重賦值概念,給定重疊社區內兩個相近的點為α′、β′,用φα′、φβ′表示兩個節點之間的重疊度,根據權重定義,兩點之間的鄰域重疊比Hφα′φβ′為

(10)

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

(11)

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

5 仿真研究

5.1 仿真設置

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

(12)

(13)

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

表1 仿真參數

5.2 檢測效果對比

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

圖3 平均檢出率對比曲線

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

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

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

5.3 檢測時間對比

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

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

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

6 結論

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