基于高階信息的網絡相似性比較方法*

陳浩宇 徐濤 劉闖 張子柯 詹秀秀3)?

1) (杭州師范大學復雜科學研究中心,杭州 311121)

2) (浙江大學數字溝通研究中心,杭州 310058)

3) (浙江大學傳媒與國際文化學院,杭州 310058)

1 引言

大多數實際的復雜系統都可以表示成復雜網絡,從細菌、細胞和蛋白質系統,到人類關系網絡,甚至再到大型的互聯網和萬維網[1,2].近年來,研究各種復雜網絡結構的相似性已經成為一個流行且跨學科的主題,目前在社會科學[3]、醫學[4]、生物學[5]和計算機科學[6]等領域得到了廣泛應用.比較網絡之間的相似性在當今社會發展中扮演著不可或缺的角色[7–11].例如,在醫學領域[12],研究人員可以利用基因網絡比較不同組織之間的相似性,以此發現與疾病相關的基因和信號通路;在生物領域[13],通過相似性方法來比較不同生物體或不同條件下的蛋白質相互作用網絡,可以發現共享的功能模塊以及關鍵的蛋白質節點;在社交領域[14],利用相似性比較不同社交網絡中的社區結構,從而揭示社區的劃分和特征.

網絡比較問題最初源于圖同構[15,16]問題,也被稱為圖匹配[17]或網絡對齊[18],其研究的本質在于判斷兩個圖中的節點集是否存在一對一映射的關系[19,20].通過比較網絡的結構拓撲性質來量化網絡之間的異同性,例如邊密度、度分布和節點距離分布[21]等較為簡單的拓撲結構特征,或者網絡社區結構[22]、光譜熵[23,24]等更為復雜的拓撲結構特征[25–27].例如,Koutra 等[28]提出了一種基于Matusita 距離來度量網絡節點親和力矩陣之間的相似度方法;De Domenico 和Biamonte[29]提出了一套基于譜熵的網絡比較信息理論工具;Schieber 等[30]通過考慮節點之間的最短路徑距離的概率分布,高效量化了網絡之間的差異;Chen 等[31]提出了一種基于節點可通信性序列和譜熵的比較方法;Liu 等[32]提出了基于遺傳算法和模型選擇的機器學習的網絡比較方法.這些方法的基本思想都是選取網絡特定的拓撲性質,并選擇特定的熵度量來比較網絡的異同[33].然而,單獨選取特定的拓撲性質無法充分捕獲網絡的全局結構信息.因此,我們引進了網絡節點的高階聚類系數,并通過構建節點的高階聚類系數分布和最短路徑分布,再基于兩個分布之間的Jensen-Shannon 散度[34]來度量網絡節點連通異質性.該方法在綜合考慮網絡全局性質重要性的同時,也兼顧了網絡局部的拓撲結構的影響.

本文的其余部分結構如下: 第2 節介紹本文用到的相關概念,提出基于高階信息的網絡相似性比較方法,并且介紹網絡比較的常見基線算法;第3節是實驗部分,分別在人工合成網絡和真實網絡上評估了此方法;第4 節是總結與展望,并為今后的網絡比較工作提供了全新思路.

2 基于高階信息的網絡相似性方法

2.1 基本定義

符號定義為了方便討論,將網絡統一記為G=(V,E),節點集合V和邊集合E分別表示為V={v1,v2,···,vN},E={ek=(vi,vj),k=1,···,M|vi,vj∈V},其中N和M分別表示網絡G中節點和邊的數量.根據網絡中節點與邊的隸屬關系,構建鄰接矩陣AN×N,具體而言,當節點vi和節點vj有連邊時,Aij的值為1;否則為0.此外,構建網絡中節點的鄰居集Q={q1,q2,···,qN},其中qi為節點vi的鄰居集合,|qi| 為節點vi的鄰居個數.

2.2 高階聚類系數

聚類系數是一種描述網絡拓撲結構的指標,它反映了節點周圍鄰居之間相互連接的緊密程度,且可以衡量網絡中節點的聚集程度.然而,在真實網絡中,由于節點間最短路徑長度較短且聚類系數較大,且這樣的局部特征不能充分描述節點周圍鄰居之間的高階聯系,往往導致無法捕捉網絡中局部拓撲結構性質的差異.為了解決這個問題,本文引入了一種更高階的聚類系數定義[35],在標準聚類系數的基礎上進行了擴展.

傳統標準聚類系數只考慮三角形子圖的數量來度量網絡中節點的聚集程度,而高階聚類系數則進一步考慮了更高階的子圖,從而能夠更準確地刻畫節點鄰居間的聯系,捕捉到網絡中的更復雜的拓撲結構.它能幫助我們理解網絡的聚集性和功能模塊,從而提高網絡的魯棒性和可靠性,這對于研究網絡的演化過程具有重要意義.例如,在分析社會團體網絡時,有利于發現更為復雜的關聯模式,揭示群體內部的交互模式和組織形式[36].

首先定義Ei(x) 為網絡中去除vi以及對應的連邊后vi的鄰居中距離為x的節點對的數量.因此,si(x) 定義為去除節點vi之后,其鄰居之間距離為x的節點對的比例,表達式為

本文 稱si(x) 為 關于節點vi的x-階聚類系數,根據x數值的改變,可以定義任意階聚類系數.因此,對于網絡中的所有節點可以構建一個完整的網絡節點高階聚類系數分布矩陣S={S1,S2,···,SN}.具體來說,節點vi的聚類系數分布為Si={si(x)|1 ≤x≤N-1}.由于在計算節點vi的聚類系數分布時會在網絡中移除該節點,因此新生成的網絡直徑最大可能值為N-2 .其中si(x)(1 ≤x≤N-2) 為節點vi的x-階聚類系數值,而Si的最后一列值si(N-1) 為節點vi的鄰居之間不存在路徑的節點對的比例.

圖1 給出了高階聚類系數的一個例子,其中圖 1(a)是一個由7 個節點構成的小網絡,在此網絡中去除節點v1及其相應的連邊后可得到圖1(b).計算圖1(b)中節點v1的鄰居之間的距離可得矩陣,如圖1(c)所示,例如節點v2和節點v6之間的距離為3.由圖1(c)的距離矩陣可以進一步計算節點v1的距離分布,結果如圖1(d)所示,即階數為1 的聚類系數為s1(1)=0.4,階數為2 的聚類系數為s1(2)=0.3,以此類推,階數為5 的聚類系數為s1(5)=0 .值得注意的是,因為節點v1的每兩個鄰居間都存在路徑,因此階數為6 的聚類系數s1(6)=0.

圖1 網絡高階聚類系數計算示意圖 (a)節點 v1 及它的鄰居形成的網絡;(b)去除節點 v1 后的網絡;(c)圖1(b)所示網絡 中節 點 v1 的鄰 居之間的距 離矩陣;(d)節點 v1 的 高階聚類系數分布Fig.1.Illustration of the calculation of the higher-order clustering coefficient: (a) A network formed by nodev1 and its neighbors;(b) network after removing node v1 ;(c) distance matrix between neighbors of node v1 in the network shown in panel (b);(d) the higher-order clustering coefficient distribution of node v1 .

2.3 基于高階信息的網絡相似性算法

首先定義節點的距離分布,即一個網絡節點間距離分布矩陣由P={P1,P2,···,PN}表示,每個節 點vi的距離分布向量 為Pi={pi(x)|1 ≤x≤d+1},其中pi(x) 表示與節點vi距離為x的節點的比例,而pi(d+1) 則表示與節點vi不存在路徑的節點的比例,d為網絡直徑.

節點vi的高階聚類系數分布和距離分布分別考慮了vi的鄰居之間的聚集程度以及vi與網絡中其他節點的距離遠近,以下綜合這兩種分布來定義網絡的相似性算法.首先,因為d+1 ≤N,可以將距離分布Pi通過補零的方式變成一個N-1 階向量.然后定義網絡G的高階信息分布Ti={γSi,(1-γ)Pi},且Ti的維數為 1×(2N-2),其中γ∈[0,1],可以調節Si和Pi在Ti中所占的比例,γ越大,表示分布里面更注重高階聚類系數信息,如果γ趨于0 表示更注重距離信息.

給定網絡G以及其上的高階信息分布T,根據Jensen-Shannon 散度來定義網絡節點散度NND(network node dispersion):

式中J(T1,T2,···,TN) 表示N個節點分布的Jensen-Shannon 散度,其表達式為

其中ti(j) 是高階信息分布Ti的第j列的具體數值;而μj為N個節點分布第j維的平均值,其表達式為網絡 NND 衡量了網絡節點連通異質性的大小,其值越大表示網絡中節點連通異質性越大,反之亦然.

網絡之間的相似性給定網絡G和G′,可以使用以下公式來計算兩者在結構上的相似性DHC(G,G′),表達式為

網絡結構相似性DHC由兩個部分組成.第1 部分考慮了網絡中節點的平均連通性,其中J(μG,μG′)表示兩個網絡的平均距離分布的Jensen-Shannon散度,μG={μj|(1 ≤j≤2N-2)},它包含了基于節點高階聚類系數和節點間距離分布的信息,從而捕捉了網絡的全局結構性質;第2 部分考慮了節點之間的異質性,即網絡中局部的結構性質.其中參數β 用于調節它們的權重.如果兩個網絡之間的DHC值越小,說明它們的結構相似性越大;反之,DHC值越大,說明它們的結構相似性越小.

圖2 給出一種基于高階信息的網絡相似性比較方法計算流程圖,用于比較網絡G和G′.圖 2(a)展示了網絡G和G′的結構,其中G是一個全連通網絡,而G′是一個含有一個孤立節點的網絡.通過以下步驟計算這兩個網絡之間的相似性,具體過程如圖2(b)和圖2(c)所示: 首先,計算節點的高階聚類系數分布和節點的距離分布;然后,根據(2)式和(5)式計算兩個網絡之間的相似性.最終,得到網絡G和G′之間的DHC值為0.39.

圖2 基于高階信息的網絡比較方法計算流程示意圖 (a)給定兩個擁有 11 個節點的網絡G 和 G′ ,其中G 有 14 條邊,G′ 有12 條邊;(b)如何計算基于高階信息的網絡相似性的示例,包含了節點高階聚類系數分布和節點距離分布;(c)網絡相似值的計算,其中β=0.5Fig.2.Schematic diagram of calculation flow of network comparison method based on high-order information: (a) Given two networks G and G′ with 11 nodes,G has 14 edges and G′ has 12 edges;(b) an illustration of how to compute the network similarity based on higher-order information,including the distribution of node higher-order clustering coefficients and node distance distribution;(c) calculation of the network similarity value DHC ,where β=0.5 .

2.4 基線算法

基于距離分布的網絡相似性方法[30]

根據上述節點vi的距離分布Pi={pi(x)},由距離分布和Jensen-Shannon 散度定義兩個網絡G,G′的相似性比較算法:

DSP共基于3 個距離的概率分布,第1 項表示以平均距離分布(即μG和μG′)為特征的差異性,第2項表示網絡節點分散度的差異性,第3 項則是網絡α-中心性分布的差異,且Gc是G的補圖.這里

式中,J(P1,···,PN) 是N個節點距離分布的Jensen-Shannon 散度;w1,w2,w3和α 是可調參數,且滿足w1+w2+w3=1 .本文設置權重w1=w2=0.45 和w3=0.1 來進行網絡相似性比較.

基于可通信性序列熵的網絡相似性方法[31]

通過構造網絡可通信性矩陣C來測量節點之間的通信能力,其定義如下:

其中Cij表示為節點vi和vj之間的可通信性,它反映了網絡中節點之間的信息傳遞能力.假設L={L1,L2,···,LM}是標準化的可通信性序列,其中

(1 ≤y≤M,1 ≤i≤j≤N和M=N(N+1)/2),L序列的香農熵H(L) 定義如下:

給定兩個網絡G和G′,歸一化可通信性序列分別由LG和給出.按升序對中的值進行排序,并獲得新的可通信序列為.因此,基于可通信性序列熵的網絡相似性被定義為DC(G,G′):

基于拉普拉斯特征值的網絡相似性方法[37]

該方法通過構造網絡拉普拉斯矩陣,并利用鄰接矩陣和度矩陣的特征值計算得到光譜距離.通過比較網絡的光譜距離差異性,該方法能夠更全面地表示網絡的拓撲結構,從而選擇更具穩定性的比較方式.基于拉普拉斯特征值的網絡相似性被定義為DM(G,G′):

其中λ 和λ′分別為兩個網絡中拉普拉斯矩陣的特征值.

3 實 驗

3.1 人工合成網絡比較

為了驗證本文提出的方法在量化網絡相似性方面的能力,進行了參數β 和γ的敏感性分析,旨在展示基于高階信息的網絡比較方法的魯棒性.在實驗中選擇用WS 網絡和BA 網絡來測試方法的魯棒性,其中網絡的平均度均為10.WS 網絡中選取重連概率為p=0.3,而BA 網絡中選取每一步的加邊數m=5 .圖3(a)和圖3(c)中的每一個點分別表示N=1000 的WS 網絡與N= [1500,5000],間隔為500 的WS 網絡相似性值 (DHC),不同參數β 和γ的取值分別對應不同顏色的曲線.圖3(b)和圖3(d)對相同規模的BA 網絡進行了類似的分析.由圖3(a)—(d)可以看出,WS (或BA)網絡與節點數相差小的網絡相似性更大,且β (或γ)并不會影響曲線的趨勢.此外,圖3(a)和圖3(b)顯示β 的值越大網絡差異性就越明顯,因此在后續的所有實驗分析中將β 設置為1.從圖3(c)和圖3(d)可以觀察到,兩種不同人工合成網絡下當γ=0.7時(即在高階信息分布中較注重高階聚類系數的拓撲信息),得到的相似性效果最為顯著.因此后續的所有實驗分析都將γ設置為0.7.

圖3 人工合成網絡下(WS,BA)的參數敏感性分析 (a)不同參數β 下 N=1000 的WS 網絡與 N=[1500,5000],間隔為500,重連概 率 p=0.3 的WS 網絡之 間的相 似性;(b)不同 參數β 下 N=1000 的BA 網絡與 N=[1500,5000],間 隔為500 的BA 網絡之間的相似性,其中每個BA 網絡每一步加邊數 m=5 ;(c)不同參數γ 下WS 網絡之間的相似性,參數與(a)圖一樣;(d)不同參數γ 下BA 網絡之間的相似性,參數與(b)圖一樣.所有的結果均基于100 次實驗的平均值Fig.3.Parameter sensitivity analysis of synthetic networks generated by the WS and BA model: (a) Similarity between the WS network of N=1000 and the WS networks of N=[1500,5000] with the interval is 500 under different parameters β,where the probability of rewiring p=0.3 ;(b) similarity between the BA network of N=1000 and the BA networks ofN=[1500,5000]with an interval of 500 under different parameters β,where each BA network adds edges at each step with number of m=5 ;(c) similarity between WS networks under different parameters γ,the parameters are the same as with those in panel (a);(d) similarity between BA networks under different parameters γ,the parameters are the same as those in panel (b).All results are based on an average of 100 realizations.

圖4 在由模型生成的人工網絡上(即ER,WS,BA 網絡)對比了提出的基于高階信息的網絡比較方法與其他基線方法在網絡相似性上的性能,其中網絡規模統一設置為N=1000 .在ER 模型中,通過重連概率p∈{0.1,0.3,0.5,0.7,0.9}構造網絡;在WS 模型中,通過相同重連概率構造網絡,且平均度均為10;在BA 模型中,通過每一步的加邊數m∈{2,3,4,5,6}構造網絡.圖4(a)—(d)給出了DHC,DSP,DC和DM等4 種方法在ER 網絡上的性能比較.直觀上來講,由相似重連概率生成的網絡的相似性會比較高,而重連概率相差較大的網絡的相似性差距較大.由結果可知,DHC能夠很好地展現這一結論,而DSP方法在p≤0.5 表現比較好,但是p≥0.5 的網絡之間的相似性差別不大.同樣,DC和DM分別 在p≥0.3 和p≥0.5 無法區分由 不同重連概率生成的網絡.此外,在WS 和BA 網絡上,基于高階信息的網絡比較方法DHC也能夠很好地區分不同參數生成的網絡,而DSP無法區分p≥0.5 的WS 網絡和m≥4 的BA 網絡.DC無法區 分p≥0.5 的WS 網絡和m≥3 的BA 網絡.雖然DM能夠區分不同概率p(或不同加邊數m)下的WS (或BA)網絡,但是其相似性的數值與直觀的理解是相反的.例如,在WS 網絡上,直觀上來講,p=0.1 的WS 網絡與p=0.5 的WS 網絡的相似性應該大于p=0.1 的WS 網絡與p=0.7 (或p=0.9)的WS 網絡的相似性,但DM給出的數值恰恰相反.此外,在BA 網絡上DM的性能與WS網絡相似.DHC和DSP相比,同時應用了節點的距離分布來比較網絡,不同的是DHC考慮了節點的高階聚類系數,這表明高階聚類系數這一拓撲性質能夠幫助比較不同結構的網絡.綜上所述,與其他方法相比,基于高階信息的網絡比較方法能夠很好地區分由不同參數生成的ER (或WS,BA)網絡.

圖4 四種相似性方法在人工合成網絡上的效果評估(網絡規模均為 N=1000) (a)—(d)不同重連概率p 下ER 模型生成的每對網 絡的相似性,其 中相似性方法分 別為 DHC ,DSP ,DC 以及 DM ;(e)—(h)不同重連概 率p,平均度為10 下WS 模型生成的每對 網絡的相似性,其中相似性方法分別為 DHC ,DSP ,DC 以及 DM ;(i)—(l)不 同加邊數 m ∈{2,3,4,5,6} 下BA 模 型生成的 每對網 絡的相似性,其中相似性方 法分別為 DHC ,DSP ,DC 以及 DM .所有的結果均基于100 次 實驗的平均值Fig.4.Effectiveness of four similarity methods in comparing synthetic networks.The network size is set to N=1000 : (a)–(d) Similarity between each pair of networks generated by the ER model under different rewiring probabilities p,where the network comparing methods are DHC ,DSP ,DC and DM ;(e)–(h) similarity between each pair of networks generated by the WS model with different rewiring probabilities p and an average degree of 10,where the network comparing methods are DHC ,DSP ,DC and DM ;(i)–(l) similarity between each pair of networks generated by the BA model under different edge numbersm ∈{2,3,4,5,6}added at each time step,where the similarity methods are DHC ,DSP ,DC and DM .All results are based on an average of 100 realizations.

圖5 給出了4 種由模型生成的人工合成網絡上的進一步研究,對比了提出的基于高階信息的網絡比較方法與其他基線方法在網絡相似性方面的表現.這4 種網絡分別是K-regular 網絡、WSC (通過1%重連邊的K-regular 網絡生成得到)、WSK(通過10%重連邊的K-regular 網絡生成得到)和BA 網絡(每一步的加邊數m=5),其中網絡規模統一設置為N=1000 ,|E|=5000,平均度為10.由4 種網絡的生成方式可知,K-regular 網絡與其他3 種網絡的相似性由高到低分別是WSC,WSK和BA,而本文提出的基于高階信息的方法DHC結果符合這一結論.此外,DHC在比較不同模型生成的網絡相似性方面表現出明顯的效果差異,并且具有較小的誤差范圍;而DSP方法在K-regular 網絡和WSC (WSK)、K-regular 網絡和BA 網絡比較中結果非常相近,表明該方法不能有效區分這些網絡之間的相似性;DC方法在4 種網絡比較上大體趨勢上正確,但總體效果不夠明顯;DM則在Kregular 網絡和WSC 網絡以及K-regular 網絡和WSK 網絡比較中得出的相似性與實際情況相反,且實驗結果存在較大的誤差和波動,缺乏穩定性.

圖5 分別使用 DHC ,DSP ,DC 和 DM 這4 種方法對4 種人工合成網絡(K-regular,WSC,WSK 和BA)進行相互比較.所有的結果均基于100 次實驗的平均值Fig.5.Comparison of the four synthetic networks,i.e.,Kregular,WSC,WSK,and BA,by using four methods of DHC,DSP ,DC and DM .All results are based on an average of 100 realizations.

3.2 真實網絡比較

進一步在來自多個領域的12 個真實網絡上評估了基于高階信息的網絡比較方法的有效性.這12 個真實數據集的具體描述如下: Chesapeake網絡是美國河口切薩皮克灣的中鹽營養網絡,節點表示一組生物體,例如浮游植物或纖毛蟲,邊表示碳交換;Windsurfers 網絡描述了1986 年秋季南加州風帆沖浪者之間的人際交往網絡;Contiguous網絡描述了美國的48 個相鄰州和哥倫比亞特區,邊表示兩個州共享邊界;Jazz 網絡是爵士音樂家之間的合作網絡;Infectious 網絡是2009 年在都柏林科學展覽館舉辦的“INFECTIOUS: STAY AWAY”展覽期間的一個面對面的接觸網絡;Yeast 和Metabolic 網絡分別是蛋白質相互作用網絡和線蟲的代謝網絡;Rovira 網絡是位于西班牙加泰羅尼亞南部塔拉戈納的Rovira i Virgili 大學的一個電子郵件通信網絡;Petsterc 和Petster 網絡描述了網站用戶之間的友誼和家庭聯系網絡;Irvine 網絡是加州大學Irvine 分校學生在線社區用戶之間的消息傳遞網絡;Pgp 網絡是一種基于Pretty Good Privacy (Pgp)算法的用戶交互網絡.表 1 展示了這些數據集的全部拓撲結構信息,包括了節點數N、邊數 (|E|)、平均度 (Ad)、平均路徑長度 (Avl)、網絡密度 (Ld)、聚類系數 (C) 和直徑 (d) .

表1 真實網絡的拓撲結構性質,其中N 為節點數,|E| 為邊數,Ad 為平均度,Avl 為平均路徑長度,Ld 為網絡密度,C 為聚類系數,d 為直徑Table 1. Topology properties of the real networks,where N is the number of nodes,|E| is the number of edges,Ad is the average degree,Avl is the average path length,Ld is the network link density,and C is the clustering coefficient,and d is the diameter.

圖6 給出了12 個真實網絡與對應的零模型之間的相似性.對于一個特定的網絡,本文考慮了3 種不同的k階零模型,分別記作Dk1.0 ,Dk2.0 和Dk2.5[8].其中,零模型的k值表示網絡拓撲結構保留的程度.具體來說,當k=1.0 時,生成的網絡保留了原始網絡的度序列;當k= 2.0 時,在重連過程中保持了度序列和度相關性屬性不變;當k=2.5時,則保留了原始網絡的聚類譜屬性.也就是說,k越大保留的原始網絡的性質越多,即零模型與原始網絡越相近.如圖 6 所示,本文基于高階信息的網絡比較方法DHC在不同的網絡上比較了原始網絡與其零模型的相似性,結果表明隨著k值的增加,真實網絡與其隨機化網絡之間的相似性趨向于變大,即k越大表明隨機化后的網絡與原始網絡共享的拓撲屬性越多.這說明本文的方法能夠很好地區分原始網絡和零模型之間的不同.

圖6 真實網絡與其零模型生成的網絡相似性.考慮了具有不同k 值(1.0,2.0 和2.5)的 Dk 零模型,圖中的值表示DHC 的值的大小.所有的結果均基于100 次實驗的平均值Fig.6.Similarity between real networks and their null-models.We considered the Dk null model with different values k (1.0,2.0,and 2.5),and the values in the figure indicate the value of DHC .All results are based on an average of 100 realizations.

圖7 給出對真實網絡以及經過擾動后的網絡進行比較的過程.擾動的過程如下: 對于給定的網絡,隨機添加或刪除一定比例的邊f∈[-0.9,0.9],然后比較原網絡與擾動后網絡之間的相似性.其中,正值的f表示添加邊的過程,負值的f表示刪除邊的過程.直觀上來講,網絡擾動程度越大(|f|越大),原網絡與擾動后網絡的相似性就越小.實驗結果顯示DHC在刪邊和加邊的過程中都能保持良好的上升趨勢,即 |f| 越大,原網絡與擾動后的網絡相似性越小.相比之下,從圖7 可以看出,DSP,DC和DM這3 種方法只在刪邊時能較好地反映網絡結構變化,在添加邊時效果欠佳.例如,在網絡Chesapeake 上,隨著 |f| 的增大,DSP,DC和DM的值變化都很小,也就是說在這3 種方法下,無論增加多少邊,原網絡與增邊后的網絡相差不大,這與事實不符.此外,在其他網絡上,與DHC相比,這3 種方法都或多或少不能合理地表示出網絡的相似性.主要原因在于,DM主要依賴于鄰接矩陣和度矩陣,而忽略了高階結構信息;DSP則無法同時考慮網絡的全局結構特征和局部結構特征.綜合來說,基于高階信息的網絡比較方法DHC在網絡擾動中展現出良好的性能,能夠更全面地反映網絡的結構變化.

圖7 原始真實網絡和經過擾動后生成的網絡之間的相似性,其中f 的負值對應于給定比例的邊的隨機刪除過程,正值表示隨機增邊的過程.所有的結果均基于100 次實驗的平均值.Fig.7.Similarity between the original real network and the network after perturbation,where negative values of f correspond to the deletion of |f| fraction of edges and positive values of f indicate the addition of f fraction of edges.All results are based on an average of 100 realizations.

4 總結與展望

本文提出了一種利用基于高階信息的網絡相似性比較方法DHC,來彌補現有網絡相似性比較算法的不足.具體而言,首先計算每個節點的高階聚類系數分布和節點間距離分布,然后使用分布的Jensen-Shannon 散度來度量網絡距離分布的異質性,從而得到不同網絡之間的相似性.

DHC在不同人工合成網絡(ER,WS,BA)上均展示了良好的性能,并在12 個具有不同拓撲性質的真實網絡擾動上也保持了穩定性.此外,將該方法與網絡比較領域內一些具有代表性的基線算法(DSP,DC,DM)分別在人工合成網絡和真實網絡上進行了性能對比,也取得了令人滿意的結果.未來,我們也希望將其擴展到更多類型的網絡,如有向網絡[38]、超網絡[39]和時序網絡[40]等.