大規(guī)模動態(tài)網(wǎng)絡(luò)的相似性度量方法研究*

王 佳，武志昊，趙苡積，林友芳

北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044

1 引言

近年來，復(fù)雜網(wǎng)絡(luò)已成為多學(xué)科交叉的熱點研究領(lǐng)域之一，有很多學(xué)者進行了大量深入的研究。復(fù)雜網(wǎng)絡(luò)（以下簡稱為網(wǎng)絡(luò)）通常由節(jié)點和節(jié)點之間的連邊組成，其中節(jié)點表示真實網(wǎng)絡(luò)中的個體，節(jié)點之間的連邊表示個體之間存在的聯(lián)系。網(wǎng)絡(luò)結(jié)構(gòu)相似性計算作為復(fù)雜網(wǎng)絡(luò)中的一個研究方向，在許多網(wǎng)絡(luò)分析應(yīng)用如異常檢測、狀態(tài)劃分中起著重要的作用。目前大多數(shù)研究僅針對靜態(tài)網(wǎng)絡(luò)，但在實際場景下，網(wǎng)絡(luò)的結(jié)構(gòu)往往會隨著時間的推移而發(fā)生改變，如何衡量動態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)相似性是計算機科學(xué)領(lǐng)域的一個急需解決的問題。

目前，已經(jīng)有多種靜態(tài)網(wǎng)絡(luò)相似性度量方法被提出，這些方法通常從宏觀和微觀兩個角度衡量網(wǎng)絡(luò)的差異。微觀方法[1-2]通常根據(jù)網(wǎng)絡(luò)的細節(jié)信息（如重疊的節(jié)點或邊的數(shù)量）差異來衡量網(wǎng)絡(luò)之間的相似程度，這類方法僅關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)的細節(jié)信息，而忽略了網(wǎng)絡(luò)中豐富的宏觀信息，如社團結(jié)構(gòu)。宏觀方法[3-4]則關(guān)注整體網(wǎng)絡(luò)結(jié)構(gòu)的變化，細微的網(wǎng)絡(luò)變化不會對整體相似性產(chǎn)生較大影響。受到廣泛關(guān)注的譜距離[3]就是一種典型的宏觀方法，該方法雖然有不錯的效果，但是它的計算復(fù)雜度為Ο(n3)，很難應(yīng)用在快速變化的大型動態(tài)網(wǎng)絡(luò)中。為了解決在大型動態(tài)網(wǎng)絡(luò)中計算成本高的問題，本文引入矩陣擾動理論[5]，結(jié)合網(wǎng)絡(luò)擾動提出了一種快速衡量網(wǎng)絡(luò)相似性的方法。具體來說，本文方法根據(jù)初始網(wǎng)絡(luò)快照的特征值和特征值對應(yīng)的特征向量估算后續(xù)網(wǎng)絡(luò)快照的特征值，不需要在每個網(wǎng)絡(luò)快照上重新計算特征值，將計算復(fù)雜度降低至線性復(fù)雜度。

本文其余部分的結(jié)構(gòu)安排如下：第2章介紹網(wǎng)絡(luò)相似性研究領(lǐng)域的相關(guān)工作；第3章介紹基本概念的定義和方法描述；第4 章進行實驗介紹及結(jié)果分析；第5章給出全文的總結(jié)及展望。

2 相關(guān)工作

目前已經(jīng)被提出的網(wǎng)絡(luò)相似性度量方法大致可以按微觀和宏觀角度分為兩類。微觀方法，如圖編輯距離[1]和DELTACON[2]主要關(guān)注的是網(wǎng)絡(luò)的細節(jié)差異。網(wǎng)絡(luò)編輯距離定義為將一個網(wǎng)絡(luò)轉(zhuǎn)變?yōu)榱硪粋€網(wǎng)絡(luò)所需的編輯次數(shù)，在動態(tài)網(wǎng)絡(luò)中可以理解為邊的變化數(shù)量。DELTACON使用置信度傳播算法將網(wǎng)絡(luò)表示為節(jié)點間的親密度矩陣，然后計算矩陣間的距離進而得到網(wǎng)絡(luò)的相似性。

以上方法僅關(guān)注網(wǎng)絡(luò)的細節(jié)差異而忽視了網(wǎng)絡(luò)中豐富的宏觀信息，而宏觀信息往往能更完整地反映網(wǎng)絡(luò)整體的結(jié)構(gòu)差異，因此本文更關(guān)注的是宏觀方法。例如，Rossi等人[4]提出了一種通過連續(xù)時間的量子游走演化來度量相似性的方法，該方法將兩個網(wǎng)絡(luò)之間的相似性定義為網(wǎng)絡(luò)所對應(yīng)的密度矩陣之間的Jensen-Shannon 距離。Domenico 等人[6]將該Jensen-Shannon距離應(yīng)用于層次約減任務(wù)中，通過計算動態(tài)網(wǎng)絡(luò)快照之間的相似性將網(wǎng)絡(luò)層數(shù)約減到最小。實驗結(jié)果表明該方法可以將網(wǎng)絡(luò)層數(shù)約減至原來的75%，但該方法也需要計算網(wǎng)絡(luò)的特征值，導(dǎo)致計算復(fù)雜度高。Wilson 等人[7]依據(jù)譜特征可以用于表征網(wǎng)絡(luò)的屬性和提取網(wǎng)絡(luò)的結(jié)構(gòu)信息的特點，提出譜特征可用于解決網(wǎng)絡(luò)的相似性問題。Masuda等人[8]將該方法應(yīng)用于狀態(tài)檢測任務(wù)中，實驗結(jié)果表明該方法可以有效區(qū)分網(wǎng)絡(luò)中的不同狀態(tài)，但該方法僅適用于小型網(wǎng)絡(luò)。Chen等人[9]引入矩陣擾動理論，通過跟蹤特征值的變化來快速計算網(wǎng)絡(luò)中的某些屬性，如網(wǎng)絡(luò)中的三角形數(shù)量。與該方法不同的是，本文側(cè)重于估算網(wǎng)絡(luò)快照間的特征值差量。

通過譜距離衡量網(wǎng)絡(luò)相似性雖然有效，但是存在計算復(fù)雜度高的缺點。一方面，目前通過迭代算法進行優(yōu)化最好情況下可以將復(fù)雜度降為Ο(n2)[10]，但對于計算大型動態(tài)網(wǎng)絡(luò)的相似性而言復(fù)雜度仍然很高。另一方面，計算網(wǎng)絡(luò)的全部特征值是不必要的，在大多數(shù)應(yīng)用中僅需前k個特征值即可[9]。為了解決計算問題，本文引入矩陣擾動理論，將其與網(wǎng)絡(luò)擾動理論相結(jié)合提出了一種快速衡量大型動態(tài)網(wǎng)絡(luò)相似性的方法。

3 問題定義及方法描述

3.1 問題定義

定義1（動態(tài)網(wǎng)絡(luò)）單個網(wǎng)絡(luò)快照定義為一個二元組G=(V,E)，其中集合V={v1,v2,…,vN}稱為節(jié)點集，集合E={e1,e2,…,eH}稱為邊集。網(wǎng)絡(luò)可以用鄰接矩陣A來表示，矩陣中的元素值為1表示節(jié)點之間有連邊，值為0 表示節(jié)點之間無連邊。如圖1 所示，動態(tài)網(wǎng)絡(luò)是隨著時間變化的網(wǎng)絡(luò)集合。假設(shè)動態(tài)網(wǎng)絡(luò)的時間跨度為[0,m]，按照一定的時間間隔將整個時序網(wǎng)絡(luò)劃分為T個時間窗口，那么動態(tài)網(wǎng)絡(luò)就是T個網(wǎng)絡(luò)的序列，即ζ={G1,G2,…,GT}。假設(shè)ζ中的每個網(wǎng)絡(luò)Gi都有相同的節(jié)點集合V，即另外，本文中只討論無向網(wǎng)絡(luò)，但本文提出的方法可以推廣到其他類型的網(wǎng)絡(luò)中。

Fig.1 Dynamic network diagram圖1 動態(tài)網(wǎng)絡(luò)示意圖

定義2（矩陣特征值）設(shè)A∈Cn×n，如果存在λ∈C和非零向量x∈Cn，使得Ax=λx成立，則稱λ是A的一個特征值，x為A的屬于特征值λ的特征向量。其中A的所有特征值的集合稱為A的譜，記作λ(A)。

定義3（網(wǎng)絡(luò)譜距離）由定義2可知，將任意網(wǎng)絡(luò)表示為矩陣形式后可計算其矩陣的特征值。譜距離（spectral distance，SD）就是計算兩個不同網(wǎng)絡(luò)矩陣表示的特征值之間的距離。對于任意的矩陣表示，有以下兩種類型的譜距離，分別為譜距離和標準化譜距離。假設(shè)有兩個網(wǎng)絡(luò)Gm=(V,E)和Gn=(V,E′)，Gm與Gn之間的譜距離定義如下[11]：

其中，分母為標準化項，表示在兩個網(wǎng)絡(luò)中取較小的特征值平方和。

定義4（矩陣擾動）假設(shè)有兩個矩陣Xm和Xn，Xn可以看作是Xm經(jīng)過擾動得到的，擾動可以表示為ΔX=Xn-Xm。通過一階矩陣擾動理論[5]，利用Xm的特征值可近似得到Xn特征值，定義如下：

定義5（網(wǎng)絡(luò)擾動）假設(shè)有兩個網(wǎng)絡(luò)Gm=(V,E)和Gn=(V,E′)，那么Gn可以看作是Gm經(jīng)過一系列邊的擾動得到的。如果將網(wǎng)絡(luò)表示為鄰接矩陣Am和An，由定義4可知An可以看作是Am經(jīng)過擾動ΔA=An-Am得到的。

定義6（問題定義）針對動態(tài)網(wǎng)絡(luò)ζ={G1,G2,…,GT}中任意的兩個網(wǎng)絡(luò)快照Gm=(V,E)和Gn=(V,E′)，設(shè)計一種網(wǎng)絡(luò)相似性度量方法SpeedSim(Gm,Gn)∈[0,1]衡量兩個網(wǎng)絡(luò)快照的相似性。該方法應(yīng)滿足當且僅當Gm與Gn完全相同時值為1。

3.2 方法描述

將動態(tài)網(wǎng)絡(luò)ζ={G1,G2,…,GT}的各網(wǎng)絡(luò)快照表示為矩陣集合X={X1,X2,…,XT}，其中初始網(wǎng)絡(luò)快照也可表示為Xinit。將網(wǎng)絡(luò)擾動和矩陣擾動理論相結(jié)合，根據(jù)Xinit的特征值λinit和特征向量μinit快速更新得到后續(xù)網(wǎng)絡(luò)快照的特征值，通過計算譜距離得到動態(tài)網(wǎng)絡(luò)各網(wǎng)絡(luò)快照間的相似性。

一般而言，譜距離是基于兩個網(wǎng)絡(luò)矩陣表示的特征值之間的比較，例如鄰接矩陣或拉普拉斯矩陣[3]。由于在計算譜距離時拉普拉斯矩陣已被證明優(yōu)于鄰接矩陣，因此只考慮拉普拉斯矩陣的譜距離。首先，區(qū)分拉普拉斯矩陣和歸一化拉普拉斯矩陣[12]。拉普拉斯矩陣L=D-A，其中A是鄰接矩陣，D是對角矩陣，其對角線元素等于各節(jié)點的度。歸一化的拉普拉斯矩陣，其中I是單位矩陣。由于歸一化拉普拉斯矩陣的數(shù)值范圍為0～2，在數(shù)值計算方面更為穩(wěn)定，因此本文選用標準化的拉普拉斯矩陣表示。

3.2.1 動態(tài)網(wǎng)絡(luò)的特征值擾動

給定動態(tài)網(wǎng)絡(luò)ζ中初始網(wǎng)絡(luò)快照的矩陣表示Xinit和除初始網(wǎng)絡(luò)快照外t時刻網(wǎng)絡(luò)的矩陣表示Xt，那么t時刻的矩陣可以看作是初始時刻矩陣經(jīng)過擾動得到的，擾動可以表示為ΔXt=Xt-Xinit。通過一階矩陣擾動理論可得，使用Xinit的特征值λinit可近似得到Xt的特征值λinit，定義如下：

假設(shè)Xt被一組邊擾動，其中s是擾動矩陣ΔXt中的非零元素的數(shù)量。那么可被擴展為：

3.2.2 SpeedSim：動態(tài)網(wǎng)絡(luò)相似性度量方法

動態(tài)網(wǎng)絡(luò)ζ={G1,G2,…,GT}，其中G1為初始網(wǎng)絡(luò)快照，其矩陣表示為Xinit。給定動態(tài)網(wǎng)絡(luò)ζ中任意兩個網(wǎng)絡(luò)快照Gm和Gn(1≤m,n≤T），網(wǎng)絡(luò)的矩陣表示Xm和Xn，由式（4）可得：

其中，當m=1時，

結(jié)合式（2），此時的標準化譜距離定義如下：

此時的相似性定義如下：

3.2.3 算法描述

將動態(tài)網(wǎng)絡(luò)ζ中的各網(wǎng)絡(luò)快照表示為歸一化拉普拉斯矩陣后得到集合X，使用譜分解方法計算初始網(wǎng)絡(luò)快照Xinit的特征值λinit和對應(yīng)的特征向量μinit，然后使用λinit快速更新得到后續(xù)網(wǎng)絡(luò)快照的特征值。最后通過計算各網(wǎng)絡(luò)快照間的譜距離dis得到動態(tài)網(wǎng)絡(luò)的相似度矩陣sim。算法1為基于矩陣擾動計算特征值的一般步驟。算法2 為基于特征值計算動態(tài)網(wǎng)絡(luò)相似性的一般步驟。

算法1基于矩陣擾動計算特征值

輸入：動態(tài)網(wǎng)絡(luò)的矩陣表示X1,X2,…,Xtmax，初始網(wǎng)絡(luò)快照的前k個特征值及其對應(yīng)的特征向量，其他網(wǎng)絡(luò)快照相對于初始網(wǎng)絡(luò)快照的一系列擾動矩陣

算法2基于特征值計算動態(tài)網(wǎng)絡(luò)相似性

輸出：相似度矩陣sim。

由于計算特征值是主要的時間消耗，并且算法2中基于算法1 得到的特征值計算相似性與一般的相似性度量算法步驟相同，因此重點分析算法1 的時間復(fù)雜度。假設(shè)T為動態(tài)網(wǎng)絡(luò)的時間跨度，s為中的平均擾動邊數(shù)，由步驟1到步驟6計算的時間復(fù)雜度為Ο(Tks)，更新的時間復(fù)雜度為Ο(T)，那么算法1的時間復(fù)雜度為Ο(Tks)。對于空間復(fù)雜度，需要花費Ο(Tk)存儲，Ο(s)存儲ΔXt，因此空間復(fù)雜度為Ο(Tk+s)。

4 實驗設(shè)計與結(jié)果分析

4.1 數(shù)據(jù)集

4.1.1 人工數(shù)據(jù)集

LFR benchmark[13]是目前最常用的一種能夠生成具有社區(qū)結(jié)構(gòu)的人工網(wǎng)絡(luò)生成模型。該生成模型的特點在于考慮了真實網(wǎng)絡(luò)的不均勻性。在生成網(wǎng)絡(luò)時假設(shè)節(jié)點度數(shù)分布與社區(qū)大小分布分別服從指數(shù)γ和α，節(jié)點的個數(shù)為N，節(jié)點的平均度為，節(jié)點的最大度為kmax。網(wǎng)絡(luò)中的邊使用混雜系數(shù)0≤μ≤1生成，即任意節(jié)點以(1-μ)的概率連接社區(qū)內(nèi)的節(jié)點，以μ的概率連接社區(qū)外部的節(jié)點，因此μ值越大社區(qū)結(jié)構(gòu)越難發(fā)現(xiàn)。

本文基于LFR benchmark 模型構(gòu)造人工數(shù)據(jù)集LFR-SPEED-Diff 和LFR-SPEED-Node，用于測試相似性方法的計算效率。LFR-SPEED-Diff參數(shù)設(shè)置如表1所示，以相同的LFR參數(shù)生成初始網(wǎng)絡(luò)快照。在每個初始網(wǎng)絡(luò)快照的基礎(chǔ)上分別以不同的隨機重連比率0.1、0.3、0.5、0.7 和0.9 改變網(wǎng)絡(luò)中的連邊得到新的網(wǎng)絡(luò)快照，最終得到5個變化的邊數(shù)量不同的動態(tài)網(wǎng)絡(luò)，每個動態(tài)網(wǎng)絡(luò)均包含10 個網(wǎng)絡(luò)快照。LFRSPEED-Node 參數(shù)設(shè)置如表2 所示，以不同的LFR 參數(shù)分別生成6 種不同參數(shù)下的初始網(wǎng)絡(luò)快照。在每個初始網(wǎng)絡(luò)快照的基礎(chǔ)上以隨機重連比率β=0.2 改變網(wǎng)絡(luò)中的連邊得到新的網(wǎng)絡(luò)快照，最終得到6個節(jié)點數(shù)量不同的動態(tài)網(wǎng)絡(luò)，每個動態(tài)網(wǎng)絡(luò)包含10 個網(wǎng)絡(luò)快照。

Table 1 Parameters table of LFR-SPEED-Diff表1 LFR-SPEED-Diff參數(shù)表

Table 2 Parameters table of LFR-SPEED-Node表2 LFR-SPEED-Node參數(shù)表

4.1.2 真實數(shù)據(jù)集

小學(xué)動態(tài)接觸網(wǎng)絡(luò)數(shù)據(jù)集（PRIMARY）[14]由SocioPatterns 協(xié)會收集。通過給小學(xué)中的學(xué)生和老師穿戴射頻識別裝置（radio frequency identification，RFID），每隔一段時間探測一次，如果他們之間的距離在1～1.5 m 內(nèi)會記錄下這條連邊。該動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集中共有242 個節(jié)點，分別為法國某小學(xué)來自10個不同班級的232名學(xué)生和10名老師。該數(shù)據(jù)集采集于2009年10月的連續(xù)兩天，第一天的時間跨度為8:45—17:20，第二天的時間跨度為8:30—17:05，每20 s 采集一次，共采集了3 100 片網(wǎng)絡(luò)。在實驗中為了保持兩天的時間跨度相同，將時間跨度統(tǒng)一設(shè)置為9:00—17:00。在該網(wǎng)絡(luò)中，學(xué)生有兩種不同的活動狀態(tài)，分別為上課狀態(tài)和午餐活動狀態(tài)，不同活動狀態(tài)所對應(yīng)的具體時間如表3所示，以此來驗證狀態(tài)劃分結(jié)果的準確率。

Table 3 Status verification information表3 狀態(tài)驗證信息

4.2 對比方法

4.2.1 標準化譜距離

標準化譜距離的定義如第3章中式（2）所示。

4.2.2 JS散度

JS 散度（Jensen-Shannon divergence）是一種基于熵的網(wǎng)絡(luò)相似性度量方法[4]。為了定義熵，首先通過來定義密度矩陣，其中β為在網(wǎng)絡(luò)上運行擴散過程的時間量的參數(shù)，ρ的特征值總和為1。馮諾依曼熵由定義，其中λi是ρ的第i個特征值。JS散度的定義如下：

4.2.3 Deltacon

Deltacon[2]是一種可擴展的網(wǎng)絡(luò)距離度量方法。假設(shè)有兩個網(wǎng)絡(luò)G=(V,E)和G′=(V,E′)，使用置信度傳播算法分別計算G和G′中任意節(jié)點之間的親和度，得到親和度矩陣W和W′。然后計算親和度矩陣W和W′之間的距離。Deltacon的定義如下：

4.3 實驗設(shè)置

4.3.1 狀態(tài)劃分實驗

自然界、社會和技術(shù)網(wǎng)絡(luò)中的許多時間演化系統(tǒng)都留下了它們之間相互作用的痕跡，這些相互作用形成了反映系統(tǒng)狀態(tài)的動態(tài)網(wǎng)絡(luò)[8]。本實驗通過將本文提出的SpeedSim 方法與層次聚類相結(jié)合，在真實數(shù)據(jù)集上檢測系統(tǒng)狀態(tài)來對這些系統(tǒng)進行粗略的描述。實驗流程如圖2所示。

（1）將動態(tài)網(wǎng)絡(luò)ζ按照時間粒度τ劃分為T個網(wǎng)絡(luò)快照，即ζ=(G1,G2,…,GT)，其中τ的選擇是任意的，并將動態(tài)網(wǎng)絡(luò)ζ表示為矩陣集合X=(X1,X2,…,XT)。本文中真實網(wǎng)絡(luò)的基本屬性如表4所示。

Table 4 Real network basic properties表4 真實網(wǎng)絡(luò)基本屬性

（2）計算動態(tài)網(wǎng)絡(luò)ζ中各網(wǎng)絡(luò)快照的特征值λ1,λ2,…,λk，其中k=50。根據(jù)特征值計算任意兩個網(wǎng)絡(luò)快照之間的距離構(gòu)成距離矩陣dis(Gm,Gn)，由距離矩陣可得到相似性矩陣sim(Gm,Gn)，其中1≤i,j≤T。

（3）應(yīng)用標準的層次聚類算法對網(wǎng)絡(luò)快照進行聚類，聚類結(jié)果即對應(yīng)于不同的狀態(tài)。在層次聚類算法中，選用Average-linkage 參數(shù)，即用平均距離定義兩個集合之間的距離。層次聚類的聚類個數(shù)由鄧恩指標（Dunn validity index）[15]確定，該指標用于確定最優(yōu)的聚類個數(shù)。定義如下：

Fig.2 Experimental flow chart圖2 實驗流程圖

（4）層次聚類的準確率用標準化互信息進行評價。標準化互信息[16]（normalized mutual information，NMI）是一種基于信息論的網(wǎng)絡(luò)劃分算法檢驗指標，可用于衡量兩種劃分之間的相似性，是社區(qū)發(fā)現(xiàn)的重要衡量指標。該指標也常用于評價一個聚類結(jié)果與標準聚類結(jié)果之間的相似性。NMI指標的值域是[0,1]，取值越高代表聚類結(jié)果越準確?；バ畔ⅲ╩utual information，MI）用來衡量兩種劃分的相關(guān)性大小。定義如下：

劃分X和劃分Y的信息熵定義如下：

對互信息標準化得到NMI的定義如下：

4.3.2 性能驗證實驗

為了驗證SpeedSim 方法的時間效率，本文使用人工數(shù)據(jù)集LFR-SPEED-Diff和LFR-SPEED-Node模擬大規(guī)模動態(tài)網(wǎng)絡(luò)，使用運算時間（單位：s）評價相似性方法的時間效率。

4.4 實驗結(jié)果

4.4.1 狀態(tài)劃分實驗

4 種相似性度量方法在小學(xué)動態(tài)接觸網(wǎng)絡(luò)上的狀態(tài)劃分結(jié)果如圖3～圖6 所示，從左至右分別為20 min、10 min 和5 min 時間粒度下的狀態(tài)劃分結(jié)果圖，每個結(jié)果圖均由相似性熱度圖和狀態(tài)轉(zhuǎn)換序列組成；相似性熱度圖中橫坐標和縱坐標均表示網(wǎng)絡(luò)快照編號，狀態(tài)轉(zhuǎn)換序列中橫坐標表示網(wǎng)絡(luò)快照編號，縱坐標表示不同狀態(tài)。狀態(tài)劃分的準確率如表5所示。本文提出的SpeedSim方法與標準化譜距離在三種時間粒度網(wǎng)絡(luò)下，均能自動發(fā)現(xiàn)網(wǎng)絡(luò)中的兩種不同狀態(tài)。由相似性熱度圖可以看出，本文方法及標準化譜距離計算得到的相似度大小在不同狀態(tài)下區(qū)分明顯。結(jié)合圖7 也可以看出本文方法可以清晰地將網(wǎng)絡(luò)快照劃分為兩類，即對應(yīng)于該網(wǎng)絡(luò)中的兩種狀態(tài)。觀察發(fā)現(xiàn)這兩種狀態(tài)與真實網(wǎng)絡(luò)中學(xué)生的上課與午餐活動狀態(tài)相匹配，這與使用圖形信號對同一真實數(shù)據(jù)集進行處理得出的分析結(jié)果是一致的[17]，表明SpeedSim 與標準化譜距離在狀態(tài)劃分任務(wù)中是有效的。

Fig.3 State division result graph of SpeedSim圖3 SpeedSim方法的狀態(tài)劃分結(jié)果圖

Fig.4 State division result graph of standard SD圖4 標準化譜距離方法的狀態(tài)劃分結(jié)果圖

Fig.5 State division result graph of JS圖5 JS散度方法的狀態(tài)劃分結(jié)果圖

Fig.6 State division result graph of Deltacon圖6 Deltacon方法的狀態(tài)劃分結(jié)果圖

Fig.7 State hierarchy clustering diagram of SpeedSim method圖7 SpeedSim方法的狀態(tài)層次聚類圖

如圖5 和圖6 所示，JS 散度和Deltacon 在三種時間粒度網(wǎng)絡(luò)下的相似性熱度圖沒有明顯的區(qū)分度，由狀態(tài)轉(zhuǎn)移序列也可看出這兩種方法無法區(qū)分真實數(shù)據(jù)集中的不同狀態(tài)。其中Deltacon 無法將狀態(tài)自動聚類成兩類，這可能是由于該方法逐對地比較兩個網(wǎng)絡(luò)中的節(jié)點親密度，這種比較過于細化。此外，由表5可以看到SpeedSim與標準化譜距離的劃分準確率均為1.00，而JS 散度和Deltacon 的準確率很低。該準確率結(jié)果與針對狀態(tài)劃分結(jié)果圖的分析結(jié)果是一致的。綜上所述，可以發(fā)現(xiàn)本文提出的SpeedSim方法雖然使用矩陣擾動理論更新得到前50個特征值來計算網(wǎng)絡(luò)的相似性，但并沒有因為提升了計算速度而降低狀態(tài)劃分的準確率。因此本文方法與譜距離相比具有明顯優(yōu)勢。

4.4.2 性能驗證實驗

在狀態(tài)劃分任務(wù)中，SpeedSim 和標準化譜距離的劃分準確率較高，在此進一步比較兩種方法的計算性能。本文提出的SpeedSim方法具有與變化的邊數(shù)量相關(guān)的線性復(fù)雜度，相較于譜距離與節(jié)點數(shù)量呈正比的平方階復(fù)雜度，計算效率大大提升。為了驗證該方法的計算效率，本文設(shè)計人工數(shù)據(jù)集LFRSPEED-Diff和LFR-SPEED-Node。由圖8可以看出，在節(jié)點數(shù)和邊數(shù)相同的情況下，隨著隨機重連比率β增大，即網(wǎng)絡(luò)中變化的邊數(shù)量增多，SpeedSim的計算時間也逐漸升高，并與網(wǎng)絡(luò)中變化的邊數(shù)量呈線性相關(guān)。如圖9 所示，隨著節(jié)點規(guī)模的增加，網(wǎng)絡(luò)中邊的數(shù)量成倍增長，網(wǎng)絡(luò)規(guī)模逐漸增大，計算時間也隨之升高。當N=100 000時，譜距離的計算效率明顯低于SpeedSim，不僅計算耗時而且內(nèi)存消耗也非常大；在節(jié)點數(shù)量達到150 000 時基本已經(jīng)達到了可計算網(wǎng)絡(luò)規(guī)模的臨界值。而本文提出的方法隨著網(wǎng)絡(luò)規(guī)模的逐漸增加，計算效率緩慢下降，且內(nèi)存開銷小，因此SpeedSim 方法的計算復(fù)雜度明顯低于標準化譜距離。

Fig.8 LFR-SPEED-Diff performance result graph圖8 LFR-SPEED-Diff性能結(jié)果圖

Fig.9 LFR-SPEED-Node performance result graph圖9 LFR-SPEED-Node性能結(jié)果圖

5 結(jié)束語

本文基于矩陣擾動理論提出了一種快速的動態(tài)網(wǎng)絡(luò)相似性度量算法，該方法通過跟蹤動態(tài)網(wǎng)絡(luò)的特征值變化計算動態(tài)網(wǎng)絡(luò)中各時間片網(wǎng)絡(luò)結(jié)構(gòu)的相似度。為了驗證本文方法的有效性，本文通過LFR基準模型生成了兩種人工數(shù)據(jù)集LFR-SPEED-Diff和LFR-SPEED-Node驗證該方法的性能，并將其應(yīng)用于狀態(tài)劃分任務(wù)中。在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗結(jié)果表明，本文提出的方法具有與變化的邊數(shù)量相關(guān)的線性復(fù)雜度，大大加快了計算速度，并且在狀態(tài)劃分任務(wù)中達到了和譜方法可比的準確率。

未來的研究需要在以下兩方面開展：（1）深入研究本文方法能夠揭示的網(wǎng)絡(luò)結(jié)構(gòu)特性。（2）將本文方法應(yīng)用于其他動態(tài)網(wǎng)絡(luò)任務(wù)中驗證其有效性。