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

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

3 問(wèn)題定義及方法描述

3.1 問(wèn)題定義

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

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

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

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

其中，分母為標(biāo)準(zhǔn)化項(xiàng)，表示在兩個(gè)網(wǎng)絡(luò)中取較小的特征值平方和。

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

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

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

3.2 方法描述

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

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

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

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

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

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

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

其中，當(dāng)m=1時(shí)，

結(jié)合式（2），此時(shí)的標(biāo)準(zhǔn)化譜距離定義如下：

此時(shí)的相似性定義如下：

3.2.3 算法描述

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

算法1基于矩陣擾動(dòng)計(jì)算特征值

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

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

輸出：相似度矩陣sim。

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

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

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

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

4.2 對(duì)比方法

4.2.1 標(biāo)準(zhǔn)化譜距離

標(biāo)準(zhǔn)化譜距離的定義如第3章中式（2）所示。

4.2.2 JS散度

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

4.2.3 Deltacon

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

4.3 實(shí)驗(yàn)設(shè)置

4.3.1 狀態(tài)劃分實(shí)驗(yàn)

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

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

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

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

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

Fig.2 Experimental flow chart圖2 實(shí)驗(yàn)流程圖

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

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

對(duì)互信息標(biāo)準(zhǔn)化得到NMI的定義如下：

4.3.2 性能驗(yàn)證實(shí)驗(yàn)

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

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 狀態(tài)劃分實(shí)驗(yàn)

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

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

4.4.2 性能驗(yàn)證實(shí)驗(yàn)

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

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é)束語(yǔ)

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

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