基于復(fù)雜網(wǎng)絡(luò)理論的Internet拓?fù)涔?jié)點(diǎn)特征分析

莊天舒

(長(zhǎng)春大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130022)

0 引言

Internet作為人類(lèi)社會(huì)信息化的標(biāo)志，雖然由人類(lèi)親自創(chuàng)造，但人們對(duì)其內(nèi)在特征尚未充分了解。一個(gè)例子就是IP級(jí)拓?fù)?，即以轉(zhuǎn)發(fā)路徑上每跳IP地址為頂點(diǎn)，相鄰跳為邊的圖。復(fù)雜網(wǎng)絡(luò)理論是基于圖論和統(tǒng)計(jì)物理的一門(mén)交叉學(xué)科，正是研究網(wǎng)絡(luò)拓?fù)涞囊粋€(gè)有力工具。本文基于復(fù)雜網(wǎng)絡(luò)理論對(duì)實(shí)際測(cè)量的IP級(jí)拓?fù)溥M(jìn)行特征分析。

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

1.1 基本概念

一個(gè)網(wǎng)絡(luò)拓?fù)淇梢员硎緸橐环鶊DG，定義為一個(gè)N個(gè)頂點(diǎn)(或節(jié)點(diǎn))的集合N(G)和一個(gè)M條邊(鏈接)的集合E(G)。每個(gè)頂點(diǎn)可以由一個(gè)整數(shù)值i=1，2，…，N來(lái)表示;邊表示為一個(gè)對(duì)(i，j)，即頂點(diǎn)i和頂點(diǎn)j相連。G是簡(jiǎn)單的，不含自環(huán)和重邊。G可以表示為一個(gè)鄰接矩陣A，元素aij=1，若(i，j)∈E(G);否則aij=0。頂點(diǎn)i的鄰域?yàn)閚(i)，即與i相連的頂點(diǎn)集合。

頂點(diǎn)i的度(degree)，ki，是與其相連邊的數(shù)量，即集合n(i)的勢(shì)|n(i)|(在物理學(xué)文獻(xiàn)中，這個(gè)量稱(chēng)為“連通性”(connectivity)［2］)

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

度是頂點(diǎn)的重要特征［4］，基于頂點(diǎn)度，會(huì)得到許多網(wǎng)絡(luò)測(cè)度。最簡(jiǎn)單的是最大度(maximum degree):

一個(gè)網(wǎng)絡(luò)的平均度是網(wǎng)絡(luò)中所有頂點(diǎn)的ki的平均值

不同頂點(diǎn)度之間的相關(guān)性，在許多網(wǎng)絡(luò)結(jié)構(gòu)和動(dòng)力學(xué)屬性中扮演重要角色［5］。最自然的方式是考察一條邊所連兩個(gè)頂點(diǎn)間的相關(guān)性。該相關(guān)性可由聯(lián)合度分布P(k，k')，即任意一條邊的兩端分別是一個(gè)度k頂點(diǎn)和一個(gè)度k'頂點(diǎn)的概率，來(lái)描述。

另一個(gè)刻畫(huà)頂點(diǎn)度之間依賴(lài)的方法是一個(gè)度k頂點(diǎn)的任意鄰居具有度k'的條件概率［6，7］，

注意∑k'P(k'|k)=1。對(duì)于無(wú)向圖，P(k，k')=P(k'，k)且 k'P(k|k')P(k')=kP(k'|k)P(k)。P(k，k')和P(k|k')形式化地描述頂點(diǎn)度分布，但是難以對(duì)之進(jìn)行實(shí)驗(yàn)評(píng)價(jià)。特別是重尾分布，它是有限網(wǎng)絡(luò)規(guī)模和少量頂點(diǎn)具有高度的結(jié)果。為處理此問(wèn)題，可以計(jì)算一個(gè)給定度k的頂點(diǎn)最近和(average degree of the nearest neighbors)［8］，

若無(wú)相關(guān)性，knn(k)獨(dú)立于k，knn(k)=＜k2＞/＜k＞。若knn(k)是k的遞增函數(shù)，高度頂點(diǎn)趨向于與高度頂點(diǎn)相連，則網(wǎng)絡(luò)是相配的(assortative)，而當(dāng)knn(k)是k的遞減函數(shù)時(shí)，高度頂點(diǎn)趨向于連接低度頂點(diǎn)，則網(wǎng)絡(luò)稱(chēng)作非相配的(disassortative)［9］。一個(gè)確定度相關(guān)性的方法是使用邊兩端的度的Pearson相關(guān)系數(shù)［13］:

若A＞0，則網(wǎng)絡(luò)是相配的;若A＜0，則網(wǎng)絡(luò)是非相配的;若A=0，則頂點(diǎn)度間不相關(guān).

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

特征化三階環(huán)出現(xiàn)的方法之一是使用聚集系數(shù)(clustering coefficient)。兩個(gè)不同的聚集系數(shù)被頻繁使用。首先是傳遞性(transitivity)［3］，其基于如下定義:

這里，NV是網(wǎng)絡(luò)中三角的數(shù)量，N3是連通三元組的數(shù)量。因數(shù)3是因?yàn)槊總€(gè)三角可以看作三個(gè)不同的連通三元組，從而保證0≤C≤1。

一個(gè)三角是一個(gè)彼此相連的三頂點(diǎn)集合;一個(gè)連通三元組是連通的三頂點(diǎn)集合，即兩個(gè)頂點(diǎn)與另一個(gè)頂點(diǎn)(中心點(diǎn))鄰接。所以，有

這里，aij是鄰接矩陣A中元素，對(duì)所有不同頂點(diǎn)i，j和k的三元組只求和一次。

另一個(gè)是聚集系數(shù)＜c＞，其中定義一個(gè)給定頂點(diǎn)i的聚集系數(shù)［1］:

這里，NV(i)是頂點(diǎn)i所在三角數(shù)量，N3(i)是以i為中心的三元組數(shù)量:

2 拓?fù)錅y(cè)量實(shí)驗(yàn)

截至2004年8月31日，中國(guó)IPv4地址空間約為218K個(gè)/24前綴，自治域約180個(gè)，在Internet中分別約占4%和0.8%。覆蓋中國(guó)網(wǎng)絡(luò)的測(cè)量實(shí)踐主要包括:

目前活躍的DIMES項(xiàng)目［11］，在當(dāng)時(shí)的測(cè)量資源仍然有限，而且志愿主機(jī)測(cè)量能力遠(yuǎn)不及專(zhuān)用監(jiān)測(cè)點(diǎn)。例如，就其測(cè)得的中國(guó)部分而言，只發(fā)現(xiàn)了41條邊。

CAIDA分布于全球的25個(gè)skitter監(jiān)測(cè)點(diǎn)使用相同目標(biāo)集，目標(biāo)數(shù)約2.20M，落入中國(guó)網(wǎng)絡(luò)的目標(biāo)約29K。收集21個(gè)監(jiān)測(cè)點(diǎn)上一個(gè)測(cè)量周期的數(shù)據(jù)，將此圖命名為“SKTP”，提取屬于中國(guó)網(wǎng)絡(luò)的部分，命名為“SKCN”。

哈爾濱工業(yè)大學(xué)開(kāi)發(fā)了一個(gè)測(cè)量工具fastrace，并將其安置于全國(guó)12個(gè)省會(huì)城市的監(jiān)測(cè)點(diǎn)上。對(duì)中國(guó)IP級(jí)網(wǎng)絡(luò)實(shí)施測(cè)量，各監(jiān)測(cè)點(diǎn)使用不同目標(biāo)集，平均目標(biāo)數(shù)為1.28M，無(wú)重復(fù)目標(biāo)數(shù)達(dá)5.03M，獲得的圖命名為“FTCN”。

提取在2004年12月19～21日間的測(cè)量結(jié)果，對(duì)匿名節(jié)點(diǎn)和私有IP地址全部刪除而不做推測(cè)。將FTCN和SKCN合并拓?fù)涿麨椤癈NTP”。這四幅拓?fù)鋱D在本研究中的角色為:SKTP—完整性較低的Internet拓?fù)?SKCN，F(xiàn)TCN，CNTP—完整性較低，較高，最高的中國(guó)拓?fù)洹Ａ硗猓?005年5月，Zhou等［11］從國(guó)內(nèi)6個(gè)監(jiān)測(cè)點(diǎn)測(cè)量7.4K個(gè)目標(biāo)，但其目的是發(fā)現(xiàn)AS級(jí)拓?fù)?，而沒(méi)有發(fā)布IP級(jí)拓?fù)鋽?shù)據(jù)。

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

通過(guò)計(jì)算得到四幅拓?fù)涞奶卣?，列于?。度分布服從冪律P(k)～k－γ［12］。四幅拓?fù)涞膬缏芍笖?shù)γ≈2.3驚人的一致。對(duì)于度的最大值，平均值及最小值比例，度分布冪律網(wǎng)絡(luò)中，max{k}～N1/(γ－1)［10］，四幅拓?fù)涞牟町愓f(shuō)明了這種規(guī)模關(guān)聯(lián)性。四幅拓?fù)涠季哂新晕⒌姆窍嗯湫?，A＜0，即低度頂點(diǎn)傾向與高度頂點(diǎn)相連。

對(duì)于平均聚集系數(shù)＜c＞及其替代傳遞性C。理論上，BA網(wǎng)絡(luò)中＜c＞～N－0.75，隨機(jī)網(wǎng)絡(luò)中＜c＞=＜k＞/N，小世界網(wǎng)絡(luò)中＜c＞與＜k＞相關(guān)，可達(dá)3/4［10］。從實(shí)際情況看，IP級(jí)拓?fù)涞模糲＞并非如BA網(wǎng)絡(luò)那樣絕對(duì)與規(guī)模相關(guān)，也比隨機(jī)網(wǎng)絡(luò)中的高，但不及小世界網(wǎng)絡(luò)的。也就是說(shuō)，IP級(jí)拓?fù)涞模糲＞是與N和＜k＞相關(guān)，而且略有小世界特征。

表1 所發(fā)現(xiàn)拓?fù)涞奶卣?/p>

4 結(jié)語(yǔ)

本文提取了實(shí)測(cè)的Internet的IP級(jí)拓?fù)渲刑N(yùn)含的若干復(fù)雜網(wǎng)絡(luò)特征，證明Internet拓?fù)涔?jié)點(diǎn)度服從冪律，具有非相配性，以及小世界網(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.