莊天舒
(長春大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,吉林 長春 130022)
Internet作為人類社會信息化的標(biāo)志,雖然由人類親自創(chuàng)造,但人們對其內(nèi)在特征尚未充分了解。一個例子就是IP級拓撲,即以轉(zhuǎn)發(fā)路徑上每跳IP地址為頂點,相鄰跳為邊的圖。復(fù)雜網(wǎng)絡(luò)理論是基于圖論和統(tǒng)計物理的一門交叉學(xué)科,正是研究網(wǎng)絡(luò)拓撲的一個有力工具。本文基于復(fù)雜網(wǎng)絡(luò)理論對實際測量的IP級拓撲進行特征分析。
一個網(wǎng)絡(luò)拓撲可以表示為一幅圖G,定義為一個N個頂點(或節(jié)點)的集合N(G)和一個M條邊(鏈接)的集合E(G)。每個頂點可以由一個整數(shù)值i=1,2,…,N來表示;邊表示為一個對(i,j),即頂點i和頂點j相連。G是簡單的,不含自環(huán)和重邊。G可以表示為一個鄰接矩陣A,元素aij=1,若(i,j)∈E(G);否則aij=0。頂點i的鄰域為n(i),即與i相連的頂點集合。
頂點i的度(degree),ki,是與其相連邊的數(shù)量,即集合n(i)的勢|n(i)|(在物理學(xué)文獻中,這個量稱為“連通性”(connectivity)[2])
度是頂點的重要特征[4],基于頂點度,會得到許多網(wǎng)絡(luò)測度。最簡單的是最大度(maximum degree):
一個網(wǎng)絡(luò)的平均度是網(wǎng)絡(luò)中所有頂點的ki的平均值
不同頂點度之間的相關(guān)性,在許多網(wǎng)絡(luò)結(jié)構(gòu)和動力學(xué)屬性中扮演重要角色[5]。最自然的方式是考察一條邊所連兩個頂點間的相關(guān)性。該相關(guān)性可由聯(lián)合度分布P(k,k'),即任意一條邊的兩端分別是一個度k頂點和一個度k'頂點的概率,來描述。
另一個刻畫頂點度之間依賴的方法是一個度k頂點的任意鄰居具有度k'的條件概率[6,7],
注意∑k'P(k'|k)=1。對于無向圖,P(k,k')=P(k',k)且 k'P(k|k')P(k')=kP(k'|k)P(k)。P(k,k')和P(k|k')形式化地描述頂點度分布,但是難以對之進行實驗評價。特別是重尾分布,它是有限網(wǎng)絡(luò)規(guī)模和少量頂點具有高度的結(jié)果。為處理此問題,可以計算一個給定度k的頂點最近和(average degree of the nearest neighbors)[8],
若無相關(guān)性,knn(k)獨立于k,knn(k)=<k2>/<k>。若knn(k)是k的遞增函數(shù),高度頂點趨向于與高度頂點相連,則網(wǎng)絡(luò)是相配的(assortative),而當(dāng)knn(k)是k的遞減函數(shù)時,高度頂點趨向于連接低度頂點,則網(wǎng)絡(luò)稱作非相配的(disassortative)[9]。一個確定度相關(guān)性的方法是使用邊兩端的度的Pearson相關(guān)系數(shù)[13]:
若A>0,則網(wǎng)絡(luò)是相配的;若A<0,則網(wǎng)絡(luò)是非相配的;若A=0,則頂點度間不相關(guān).
特征化三階環(huán)出現(xiàn)的方法之一是使用聚集系數(shù)(clustering coefficient)。兩個不同的聚集系數(shù)被頻繁使用。首先是傳遞性(transitivity)[3],其基于如下定義:
這里,NV是網(wǎng)絡(luò)中三角的數(shù)量,N3是連通三元組的數(shù)量。因數(shù)3是因為每個三角可以看作三個不同的連通三元組,從而保證0≤C≤1。
一個三角是一個彼此相連的三頂點集合;一個連通三元組是連通的三頂點集合,即兩個頂點與另一個頂點(中心點)鄰接。所以,有
這里,aij是鄰接矩陣A中元素,對所有不同頂點i,j和k的三元組只求和一次。
另一個是聚集系數(shù)<c>,其中定義一個給定頂點i的聚集系數(shù)[1]:
這里,NV(i)是頂點i所在三角數(shù)量,N3(i)是以i為中心的三元組數(shù)量:
截至2004年8月31日,中國IPv4地址空間約為218K個/24前綴,自治域約180個,在Internet中分別約占4%和0.8%。覆蓋中國網(wǎng)絡(luò)的測量實踐主要包括:
目前活躍的DIMES項目[11],在當(dāng)時的測量資源仍然有限,而且志愿主機測量能力遠不及專用監(jiān)測點。例如,就其測得的中國部分而言,只發(fā)現(xiàn)了41條邊。
CAIDA分布于全球的25個skitter監(jiān)測點使用相同目標(biāo)集,目標(biāo)數(shù)約2.20M,落入中國網(wǎng)絡(luò)的目標(biāo)約29K。收集21個監(jiān)測點上一個測量周期的數(shù)據(jù),將此圖命名為“SKTP”,提取屬于中國網(wǎng)絡(luò)的部分,命名為“SKCN”。
哈爾濱工業(yè)大學(xué)開發(fā)了一個測量工具fastrace,并將其安置于全國12個省會城市的監(jiān)測點上。對中國IP級網(wǎng)絡(luò)實施測量,各監(jiān)測點使用不同目標(biāo)集,平均目標(biāo)數(shù)為1.28M,無重復(fù)目標(biāo)數(shù)達5.03M,獲得的圖命名為“FTCN”。
提取在2004年12月19~21日間的測量結(jié)果,對匿名節(jié)點和私有IP地址全部刪除而不做推測。將FTCN和SKCN合并拓撲命名為“CNTP”。這四幅拓撲圖在本研究中的角色為:SKTP—完整性較低的Internet拓撲;SKCN,F(xiàn)TCN,CNTP—完整性較低,較高,最高的中國拓撲。另外,2005年5月,Zhou等[11]從國內(nèi)6個監(jiān)測點測量7.4K個目標(biāo),但其目的是發(fā)現(xiàn)AS級拓撲,而沒有發(fā)布IP級拓撲數(shù)據(jù)。
通過計算得到四幅拓撲的特征,列于表1。度分布服從冪律P(k)~k-γ[12]。四幅拓撲的冪律指數(shù)γ≈2.3驚人的一致。對于度的最大值,平均值及最小值比例,度分布冪律網(wǎng)絡(luò)中,max{k}~N1/(γ-1)[10],四幅拓撲的差異說明了這種規(guī)模關(guān)聯(lián)性。四幅拓撲都具有略微的非相配性,A<0,即低度頂點傾向與高度頂點相連。
對于平均聚集系數(shù)<c>及其替代傳遞性C。理論上,BA網(wǎng)絡(luò)中<c>~N-0.75,隨機網(wǎng)絡(luò)中<c>=<k>/N,小世界網(wǎng)絡(luò)中<c>與<k>相關(guān),可達3/4[10]。從實際情況看,IP級拓撲的<c>并非如BA網(wǎng)絡(luò)那樣絕對與規(guī)模相關(guān),也比隨機網(wǎng)絡(luò)中的高,但不及小世界網(wǎng)絡(luò)的。也就是說,IP級拓撲的<c>是與N和<k>相關(guān),而且略有小世界特征。
表1 所發(fā)現(xiàn)拓撲的特征
本文提取了實測的Internet的IP級拓撲中蘊含的若干復(fù)雜網(wǎng)絡(luò)特征,證明Internet拓撲節(jié)點度服從冪律,具有非相配性,以及小世界網(wǎng)絡(luò)的高聚集性。
[1]Watts D J,Strogatz S H.Collective dynamics of'small-world'networks[J].Nature,1998,393(6684):440 - 442.
[2]Dorogovtsev S N,Mendes J F F.Evolution of networks[J].Advances in Physics,2002,51:1079 -1187.
[3]Newman M E J.Scientific collaboration networks:I.Network construction and fundamental results[J].Physical Review E,2001,64(01):016131.
[4]Dorogovtsev N,Mendes J F F,The shortest path to complex networks.arXiv:cond-mat/0404593.2004.
[5]Maslov S,Sneppen K.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910 -913.
[6]Bogu M,Pastor-Satorras R.Epidemic spreading in correlated complex networks[J].Physical Review E,2002,66(04):047104.
[7]Bogu M,Pastor-Satorras R,Vespignani A.Statistical mechanics of complex networks[J].In:Lecture and notes in physics.2003.127.
[8]Pastor-Satorras R,V zquez A,Vespignani A.Dynamical and correlation properties of the Internet[J].Physical Review Letters,2001,87(25):258701.
[9]Newman M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.
[10]Albert R,Barab si A-L.Statistical mechanics of complex networks[J].Reviews of Modern Physics,2002,74(1):47.
[11]Shavitt Y,Shir E.Dimes:Let the internet measure itself[J].SIGCOMM Computer Communication Review,2005,35(5):71 -74.
[12]Faloutsos M,F(xiàn)aloutsos P,F(xiàn)aloutsos C.On power-law relationships of the Internet topology[J].SIGCOMM Computer Communication Review,1999,29(4):251 -262.
[13]Newman M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.