莊天舒

(長春大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130022)

0 引言

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級拓撲進行特征分析。

1 復(fù)雜網(wǎng)絡(luò)節(jié)點特征

1.1 基本概念

一個網(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］)

1.2 度與相關(guān)特征

度是頂點的重要特征［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).

1.3 聚集系數(shù)(Clustering Coefficients)

特征化三階環(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ù)量:

2 拓撲測量實驗

截至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ù)。

3 復(fù)雜網(wǎng)絡(luò)特征比較分析

通過計算得到四幅拓撲的特征，列于表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)拓撲的特征

4 結(jié)語

本文提取了實測的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.