亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2010-02-27 05:53:30莊天舒
        長春大學(xué)學(xué)報 2010年10期
        關(guān)鍵詞:特征測量

        莊天舒

        (長春大學(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.

        猜你喜歡
        特征測量
        抓住特征巧觀察
        新型冠狀病毒及其流行病學(xué)特征認識
        如何表達“特征”
        把握四個“三” 測量變簡單
        不忠誠的四個特征
        滑動摩擦力的測量和計算
        滑動摩擦力的測量與計算
        測量的樂趣
        抓住特征巧觀察
        測量
        国产精品美女主播一区二区| 国产亚洲欧美成人久久片| 99成人无码精品视频| 人妖与人妖免费黄色片| 黄色av一区二区在线观看| 人妻久久久一区二区三区| 国产草草视频| 亚洲精彩视频一区二区| 亚洲一区二区三区偷拍女| 日韩精品久久久久久久电影蜜臀| 人妻在卧室被老板疯狂进入国产| 国产精品美女久久久久浪潮AVⅤ| 一区二区三区日本高清| 欧美性猛交xxxx三人| 亚洲爆乳无码专区| 91久久精品一二三区蜜桃| 久草视频这里只有精品| 亚洲熟妇久久国产精品| 亚洲国产精品自拍一区| 亚洲视频在线视频在线视频 | 日本少妇爽的大叫高潮了| 漂亮人妻被强了中文字幕| 欧美乱人伦人妻中文字幕| 国产亚洲欧美日韩综合一区在线观看| 亚洲素人日韩av中文字幕| 精品国产亚洲av麻豆| 鲁鲁鲁爽爽爽在线视频观看| 偷亚洲偷国产欧美高清| 日本成人中文字幕亚洲一区 | 国产免费一区二区三区在线观看| 久久精品夜色噜噜亚洲a∨| 搡老熟女老女人一区二区| 香蕉亚洲欧洲在线一区| av在线天堂国产一区| 欧美日韩国产码高清综合人成| 亚洲AV无码一区二区三区天堂网 | 亚洲一区二区三区在线| 精品国产亚洲亚洲国产| 亚洲国产激情一区二区三区| 人妻少妇看A偷人无码电影| 亚洲精品久久区二区三区蜜桃臀 |