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

        ?

        復(fù)雜網(wǎng)絡(luò)的度分布及其算法

        2018-06-04 03:41:54王桂山任學(xué)藻西南科技大學(xué)許凡河南理工大學(xué)
        數(shù)碼世界 2018年5期
        關(guān)鍵詞:標(biāo)度度數(shù)方程

        王桂山 任學(xué)藻 西南科技大學(xué) 許凡 河南理工大學(xué)

        自然界中存在的大量復(fù)雜系統(tǒng)都可以通過形形色色的網(wǎng)絡(luò)加以描述一個(gè)典型的網(wǎng)絡(luò)是由許多節(jié)點(diǎn)與連接兩個(gè)節(jié)點(diǎn)之間的一些邊組成的,其中節(jié)點(diǎn)用來代表真實(shí)系統(tǒng)中不同的個(gè)體,而邊則用來表示個(gè)體之間的關(guān)系,通常是當(dāng)兩個(gè)節(jié)點(diǎn)之間具有某種特定的關(guān)系時(shí)連一條邊,反之則不連邊有邊相連的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中被看作是相鄰的。

        一網(wǎng)絡(luò)的發(fā)展大致經(jīng)歷了規(guī)則網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)三個(gè)階段。

        第一階段規(guī)則網(wǎng)絡(luò)的理論:圖論的發(fā)展始于18世紀(jì)偉大的數(shù)學(xué)家Euler對(duì)著名的柯尼斯堡(konigsberg)七橋問題的研究。開創(chuàng)了數(shù)學(xué)分支圖論的研究,研究表明規(guī)則網(wǎng)絡(luò)具有較大的聚類系數(shù)和較大的平均最短路徑長度,其所有的節(jié)點(diǎn)都有相同的度,節(jié)點(diǎn)度分布為

        第二階段隨機(jī)網(wǎng)絡(luò)階段理論:如果節(jié)點(diǎn)之間不按確定的規(guī)則連接,而是以一定的概率隨機(jī)連接,所得到的網(wǎng)絡(luò)就是隨機(jī)網(wǎng)絡(luò)。20世紀(jì)60年代,兩個(gè)著名的匈牙利數(shù)學(xué)家Erdo和Renyi提出的ER隨機(jī)網(wǎng)絡(luò)模型,開創(chuàng)了隨機(jī)網(wǎng)絡(luò)的研究的新局面。隨機(jī)網(wǎng)絡(luò)具有較小的聚類系數(shù)和較小的平均最短路徑長度,節(jié)點(diǎn)度分布為泊松分布。

        第三階段復(fù)雜網(wǎng)絡(luò)理論:在世紀(jì)之交,隨著計(jì)算機(jī)技術(shù)的高度發(fā)展、計(jì)算機(jī)運(yùn)算能力的不斷提高,人們擁有了各種的數(shù)據(jù)庫,因此對(duì)大規(guī)模的網(wǎng)絡(luò)進(jìn)行實(shí)證研究有了可能,復(fù)雜網(wǎng)絡(luò)科學(xué)取得了突破性的進(jìn)展。問題的起因可追溯到20世紀(jì)60年代,美國心理學(xué)家曾做過一個(gè)所謂‘六度分割’(six degree of separation)實(shí)驗(yàn)。已有的規(guī)則網(wǎng)絡(luò)和ER隨機(jī)網(wǎng)絡(luò)都無法解釋這種“小世界現(xiàn)象”。

        1998年Watts和Strogata提出了小世界網(wǎng)絡(luò)模型,說明了少量的隨機(jī)捷徑(Random shortcuts)會(huì)改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),從而涌現(xiàn)出“小世界效應(yīng)”,小世界網(wǎng)絡(luò)模型介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間,具有較大的聚類系數(shù)和短平均路徑長度,節(jié)點(diǎn)度分布為泊松分布,比規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)更能模擬真實(shí)網(wǎng)絡(luò)的特性。

        1999年的Barabasi和Albert在研究萬維網(wǎng)時(shí)發(fā)現(xiàn),萬維網(wǎng)的度分布不像隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)那種具有對(duì)稱的泊松分布,而是偏倚的冪律分布,在該網(wǎng)絡(luò)中,大多數(shù)節(jié)點(diǎn)僅有少量的連線,而少數(shù)節(jié)點(diǎn)擁有大量的連線。為此提出了無標(biāo)度(Scale-free)網(wǎng)絡(luò)模型,揭示了增長和擇優(yōu)機(jī)制在復(fù)雜網(wǎng)絡(luò)自組織演化過程中的普遍性和冪律的重要性。無標(biāo)度網(wǎng)絡(luò)中的節(jié)點(diǎn)具有很強(qiáng)的異質(zhì)性,不同度的節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性不同。例如:在城市交通網(wǎng)絡(luò)中,度分布表示城市之間的航線的多少和重要程度,度越大的城市,其重要性也越大;在社會(huì)網(wǎng)絡(luò)中,度可以表示個(gè)體的作用力和影響度,一個(gè)節(jié)點(diǎn)的度越大,一般表示在整個(gè)網(wǎng)絡(luò)中的作用和影響越大,反之亦然。

        復(fù)雜網(wǎng)絡(luò)可以描述自然界和人類社會(huì)中大量的復(fù)雜系統(tǒng),一個(gè)典型的網(wǎng)絡(luò)是有許多節(jié)點(diǎn)和一些連接節(jié)點(diǎn)間的邊組成,其中節(jié)點(diǎn)代表真實(shí)系統(tǒng)中不同的個(gè)體,二邊則表示個(gè)體之間的關(guān)系。例如上面提到的交通網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)代表一個(gè)城市,每條邊表示兩個(gè)城市間有一條航線。目前復(fù)雜網(wǎng)絡(luò)的研究主要為:社會(huì)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。

        復(fù)雜網(wǎng)絡(luò)在社會(huì)網(wǎng)絡(luò)中的應(yīng)用十分廣泛,社會(huì)網(wǎng)絡(luò)是指社會(huì)個(gè)體成員之間因?yàn)榛?dòng)而形成的相對(duì)穩(wěn)定的關(guān)系體系,社會(huì)網(wǎng)絡(luò)關(guān)注的是人們之間的互動(dòng)和聯(lián)系,社會(huì)互動(dòng)影響到人們的社會(huì)行為。社會(huì)網(wǎng)絡(luò)研究如個(gè)人間的朋友關(guān)系,公司商業(yè)伙伴關(guān)系,電影演員合作網(wǎng)絡(luò),性接觸網(wǎng)絡(luò),科學(xué)家合作網(wǎng)絡(luò)等。目前,復(fù)雜網(wǎng)絡(luò)研究主題主要包括:復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì),復(fù)雜網(wǎng)絡(luò)的生成機(jī)制,復(fù)雜網(wǎng)絡(luò)的演化的統(tǒng)計(jì)規(guī)律,復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)穩(wěn)定性,復(fù)雜網(wǎng)絡(luò)上的傳播機(jī)理與動(dòng)力學(xué)特性,復(fù)雜網(wǎng)絡(luò)中的搜索,復(fù)雜網(wǎng)絡(luò)中的同步與控制以及把網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與具體系統(tǒng)結(jié)合起來。

        分析復(fù)雜網(wǎng)路在隨機(jī)和惡意攻擊下的魯棒性。對(duì)于隨機(jī)網(wǎng)絡(luò)而言網(wǎng)絡(luò)中的節(jié)點(diǎn)是同質(zhì)的,即網(wǎng)絡(luò)中所有的節(jié)點(diǎn)幾乎具有相同的度數(shù)。而無標(biāo)度網(wǎng)絡(luò)具有很強(qiáng)的異質(zhì)性,網(wǎng)絡(luò)中大部分節(jié)點(diǎn)具有較小的度只有少量的節(jié)點(diǎn)具有較大的度,當(dāng)隨機(jī)刪除一小部分節(jié)點(diǎn)時(shí),隨機(jī)網(wǎng)絡(luò)的直徑隨著刪除節(jié)點(diǎn)的多少單調(diào)增加,而無標(biāo)度網(wǎng)絡(luò)的直徑幾乎不變。

        度分布是復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要的統(tǒng)計(jì)量,節(jié)點(diǎn)度數(shù)反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性,度數(shù)越大的節(jié)點(diǎn)在網(wǎng)絡(luò)中有越多的鄰居節(jié)點(diǎn),它的變化對(duì)網(wǎng)絡(luò)的影響越大,反之亦然。網(wǎng)絡(luò)度分布描述了網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布情況,具有指數(shù)型度分布的網(wǎng)絡(luò)中節(jié)點(diǎn)是同質(zhì)的,這樣的網(wǎng)絡(luò)對(duì)惡意攻擊具有很強(qiáng)的魯棒性;具有冪律度分布的網(wǎng)路中節(jié)點(diǎn)是異質(zhì)的,網(wǎng)絡(luò)中大部分節(jié)點(diǎn)具有很小的度數(shù),但也存在極少數(shù)量的節(jié)點(diǎn)度很大,這樣的網(wǎng)絡(luò)對(duì)于隨機(jī)攻擊具有強(qiáng)的韌魯棒性,但對(duì)于惡意攻擊卻很脆弱,下面系統(tǒng)分析網(wǎng)絡(luò)度分布的方法:

        平均場(chǎng)方法:Barabasi等人分析BA模型的度分布提出了平均場(chǎng)方法(mean-fild approach)。具體計(jì)算步驟如下:令表示節(jié)點(diǎn)i(在第i時(shí)刻加入到網(wǎng)絡(luò)的節(jié)點(diǎn))在時(shí)刻 時(shí)的度數(shù),對(duì)于BA模型,在t時(shí)刻網(wǎng)絡(luò)共增加了m條連線,每條連線連接網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn),此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)之和.根據(jù)連續(xù)性理論,把看做連續(xù)動(dòng)力學(xué)函數(shù),則滿足如下的動(dòng)力學(xué)方程

        上述方程有如下的解:由于計(jì)算網(wǎng)絡(luò)的度分布需要隨機(jī)選擇一個(gè)節(jié)點(diǎn),所以中的i必須看成隨機(jī)變量,由于節(jié)點(diǎn)是隨機(jī)選擇的,因此i在所有節(jié)點(diǎn)中服從均勻分布,又初始網(wǎng)絡(luò)中含有個(gè)節(jié)點(diǎn),從而通過

        可得:對(duì)k求導(dǎo)即可得到表示在時(shí)刻t度數(shù)為k的節(jié)點(diǎn)所占的比例:

        當(dāng)時(shí),網(wǎng)絡(luò)的穩(wěn)態(tài)度分布為:其中,為標(biāo)度指數(shù)。

        率方程方法:

        Krapivsky等人在分析網(wǎng)絡(luò)度分布的時(shí)候提出了率方程方法(rate-equation approach),求解過程:令表示在t時(shí)刻網(wǎng)絡(luò)中度數(shù)為k的節(jié)點(diǎn)總數(shù),對(duì)于BA模型根據(jù)連續(xù)性理論,現(xiàn)在考慮節(jié)點(diǎn)數(shù)的變化率,對(duì)于原來度數(shù)為的節(jié)點(diǎn)由于與新節(jié)點(diǎn)相連度數(shù)變?yōu)閗,需要算入;對(duì)于原來度數(shù)為k的節(jié)點(diǎn),由于增加了連線度數(shù)變?yōu)椋枰懦?;?duì)于新節(jié)點(diǎn),它的度數(shù)度數(shù)恰好為m,若k=m,則需要保留。節(jié)點(diǎn)i與新加入的節(jié)點(diǎn)相連的概率為可得到關(guān)于率方程由大數(shù)定律得結(jié)合上式可表示為:此方程式是一個(gè)關(guān)于一階差分方程,解此方程可以得到:通過率方程方法得到BA模型的度分布服從指數(shù)為3的冪律分布,這個(gè)結(jié)果和平均場(chǎng)方法所得結(jié)果一致。

        主方程方法:

        Dorogovtsev等人提出了主方程方法(master-equation approach).主方程方法求解度分布的步驟如下:對(duì)于固定的t,第i時(shí)刻加入到網(wǎng)絡(luò)中的節(jié)點(diǎn)i的度數(shù)是一個(gè)隨機(jī)變量,現(xiàn)在令對(duì)于BA模型,新節(jié)點(diǎn)加入到網(wǎng)絡(luò)時(shí)選擇舊節(jié)點(diǎn)i并與之相連的概率時(shí)得到下面的主方程:

        這個(gè)方程的邊界條件:對(duì)于BA模型,結(jié)合上式可以化簡為:這是一個(gè)一階差分方程,解此差分方程:

        通過主方程方法可得BA模型是度分布服從指數(shù)為3的冪律分布的無標(biāo)度網(wǎng)絡(luò)。

        鞅方法:

        Bollobas等人用鞅方法嚴(yán)格證明了LCD模型度分布的存在性并求出了度分布的表達(dá)式,對(duì)于LCD模型,首先證明了當(dāng)然后定義一個(gè)鞅

        根據(jù)Azuma-Hoeffding不等式,對(duì)于每個(gè)d有:

        當(dāng)時(shí),有

        BA模型的度分布另外一個(gè)求解方法,具體思路如下:首先令然后證明定義得

        在BA模型中,對(duì)于每一個(gè)固定的t為一個(gè)隨機(jī)變量,對(duì)于變動(dòng)的t為一非齊次馬氏鏈,馬氏鏈的狀態(tài)轉(zhuǎn)移概率為

        應(yīng)用馬氏鏈理論的首達(dá)概率及其方法和技巧,對(duì)節(jié)點(diǎn)度分布得出如下

        最后給出網(wǎng)絡(luò)度分布的精確、解析表達(dá)式如下:

        本文章馬氏鏈方法在求解復(fù)雜網(wǎng)絡(luò)度分布中,具有很好的普適性,對(duì)增長網(wǎng)絡(luò)和演化網(wǎng)絡(luò)的度分布進(jìn)行了系統(tǒng)的分析,在對(duì)增長網(wǎng)絡(luò)和演化網(wǎng)絡(luò)的度分布問題給出了較為統(tǒng)一的答案。

        [1]李彥.復(fù)雜網(wǎng)絡(luò)研究概述[J].科學(xué)與財(cái)富,2012(10):35-35.

        [2]葉笛.基于復(fù)雜網(wǎng)絡(luò)視角的供應(yīng)鏈網(wǎng)絡(luò)研究[J].現(xiàn)代管理科學(xué),2011(8):111-113.

        [3]趙京勝,孫宇航.基于復(fù)雜網(wǎng)絡(luò)理論的校友網(wǎng)絡(luò)研究[J].信息技術(shù)與信息化,2014(2):121-126.

        [4]莊天舒.基于復(fù)雜網(wǎng)絡(luò)理論的Internet拓?fù)涔?jié)點(diǎn)特征分析[J].長春大學(xué)學(xué)報(bào),2010, 20(10):30-32.

        [5]趙山春.基于復(fù)雜網(wǎng)絡(luò)理論的城市公交網(wǎng)絡(luò)可靠性研究[J].中國安全科學(xué)學(xué)報(bào),2013, 23(4):108-112.

        [6]胡海波.復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究[D]. 西安理工大學(xué), 2006.

        [7]姚紅光,朱麗萍.基于仿真分析的中國航空網(wǎng)絡(luò)魯棒性研究[J]. 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 2012, 36(1):42-46.

        [8]蔣國平,宋玉蓉,鞏永旺.基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的病毒傳播研究綜述[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 32(5):1-6.

        [9]黃瑋強(qiáng),姚爽, 莊新田.基于復(fù)雜社會(huì)網(wǎng)絡(luò)的創(chuàng)新擴(kuò)散多智能體仿真研究[J].科學(xué)學(xué)研究,2013, 31(2):310-320.

        [10]王甲生,吳曉平,陳永強(qiáng),加權(quán)無標(biāo)度網(wǎng)絡(luò)級(jí)聯(lián)抗毀性研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2013,10(2):13-19.

        猜你喜歡
        標(biāo)度度數(shù)方程
        層次分析法中兩種標(biāo)度的對(duì)比分析
        方程的再認(rèn)識(shí)
        眼鏡的度數(shù)是如何得出的
        方程(組)的由來
        圖形中角的度數(shù)
        圓的方程
        隱形眼鏡度數(shù)換算
        加權(quán)無標(biāo)度網(wǎng)絡(luò)上SIRS 類傳播模型研究
        創(chuàng)新孵化網(wǎng)絡(luò)演化無標(biāo)度特征仿真分析
        基于標(biāo)度自由演化網(wǎng)絡(luò)在不同攻擊下的拓?fù)湫再|(zhì)
        亚洲第一页视频在线观看| 伊人色综合久久天天人手人停| 五月天无码| 国产专区亚洲专区久久| 厨房人妻hd中文字幕| 国产精品无码a∨精品影院| 亚洲AV永久青草无码性色av| 中文字幕中文字幕人妻黑丝| 亚洲男人天堂一区二区| 亚洲成av人在线观看天堂无码| 午夜毛片午夜女人喷潮视频| av免费一区在线播放| 亚洲中文字幕久久精品品| 亚洲伊人色欲综合网| 国产成人美女AV| 日韩视频午夜在线观看| 亚洲av不卡无码国产| 欧美日韩一区二区三区自拍| 欧美日韩中文字幕日韩欧美| 在线国产丝袜自拍观看| 国产精品久久久久精品一区二区| 少妇太爽了在线观看| 亚洲精品一区二区三区播放| av天堂手机免费在线| 无码国产精品一区二区免费式直播| 久草视频这里有精品| 日韩人妻免费一区二区三区| 红桃av一区二区三区在线无码av| 内射无码专区久久亚洲| 精品无人区无码乱码大片国产| 国产精品一二三区亚洲| 久久久久人妻一区精品| 免费人成黄页在线观看视频国产| 日韩av中文字幕亚洲天| 欧美又大粗又爽又黄大片视频| 水蜜桃亚洲一二三四在线| 亚洲一区精品中文字幕| 一区二区三区日韩亚洲中文视频| 国产午夜精品一区二区三区嫩草| 日韩欧美在线播放视频| 国产人妖在线观看一区二区三区|