本我，本及其研究工作是由在導(dǎo)師指導(dǎo)下獨(dú)立完成的，在完成時(shí)所利用的一切資料均已考文獻(xiàn)中列出。作者：201406TheDiffusionandRoutingofComplexContagioninKleinberg’sSmall-WorldNetworks QiangLi Recentstudieshavesuggestedthatsmall-worldphenomenonispervasiveinrealnetworks,includingsocialnetworks.Diseases,informationandrumorscouldspreadfastinsocialnet-worksexhibitingsmallworldproperty,whichhaveattractedwideacademicattention.Deeplyunderstandingthepropagationmechanismsofsocialnetworksaswellascontrollingdiseasespread,guidingpublicopinionandmarketingstrategyhave eheatedresearchtopics.Manyrecentworksthatinvolvemanyfieldsfocusedontheinfluenceizationinsocialnetworksandinformationpropagationmodel.Complexcontagionreferstothepropagationmechanisminanetworkwhereeachnodeisactivatedonlyafterk≥2neighborsofthenodeareactivated.Simplecontagion,suchasinformationand,couldspreadthroughasinglecontact,whilecomplexcontagionrequiresmultipleactivation.InKleinberg’ssmall-worldnetworkmodel,strongtiesaremodeledasde-terministicedgesintheunderlyingbasegridandweaktiesaremodeledasrandomedgescon-nectingremotenodes.Theprobabilityofconnectinganodeuwithnodevthroughaweaktieisproportionalto1/|uv|α,where|uv|isthegriddistancebetweenuandvandα≥0istheparame-terofthemodel.Recentresearchshowsthatwhileweaktiescangreatlyspeedupthediffusionofsimplecontagion,theyarenotaseffectiveinthespreadofcomplexcontagion.Firstly,thispaperstudiesthediffusionofcomplexcontagion(orcomplexdiffusion)inKleinberg’ssmall-worldnetworks.Accordingtotheprobabilitydistributionofweakties,theauthortativelyysesthediffusiontimedependingontheparameteroftheparameterofthenetworkmodel.Specifically,theauthorshowsthatforα<2orα>3,thediffusiontimeislowerboundedbyapolynomialinn(thenumberofnodesinthenetwork),whichaddressesanopenproblemleftlastyear.Secondly,thispaperinvestigatesanewpropagationphenomenonclosertodecentralizedroutingproposedbyKleinberg,whichiscalledtheroutingofcomplexcontagion(orcomplexrouting).MeanwhilethepaperstudiescomplexroutinginKleinberg’ssmall-worldnetworksandprovesthatroutingtimeislowerboundbyapolynomialinnforallrangeofα.Finally,throughcomparingtheresultsofdiffusionandroutingofbothsimplecontagionTheresultsalsoprovidetheoreticalsupporttotheargumentthatcomplexcontagionismuchhardertopropagatethansimplecontagion.:Computationalsocialscience,complexcontagion,diffusion,decentralizedrout-ing,small-worldnetworks,socialnetworks 1緒論11.1研究背景11.1.1小世界現(xiàn)象和六度分割理論 11.1.2強(qiáng)連接和弱連接 21.1.3小世界網(wǎng)絡(luò)的建模 21.2研究意義 31.3國(guó)內(nèi)外研究現(xiàn)狀 41.3.1簡(jiǎn)單傳染病和復(fù)雜傳染病模型 41.3.2Kleinberg模型的直徑 51.3.3其他相關(guān)工作 51.4研究目標(biāo)與內(nèi)容 61.5課題來(lái)源 71.6的組織結(jié)構(gòu) 72相關(guān)技術(shù)綜述 92.1Kleinberg小世界模型 92.2復(fù)雜傳染病模型 92.3復(fù)雜傳染病的 2.4復(fù)雜傳染病的路由 2.5蒙特卡洛模擬 2.6本章小結(jié) 3蒙特卡洛模擬及實(shí)驗(yàn)結(jié)果分析 3.1實(shí)驗(yàn)設(shè)計(jì) 3.2實(shí)驗(yàn)環(huán)境 3.3實(shí)驗(yàn)?zāi)康? 3.4實(shí)驗(yàn)步驟 3.5實(shí)驗(yàn)結(jié)果及分析 3.6本章小結(jié) 4復(fù)雜的研究 復(fù)雜的主要結(jié) 分析與證明 定理4.1(1)的證 證明方法框架 4.2.3定理4.1(2),(3),(4)的證明 4.3討論和擴(kuò)展 4.4本章小結(jié) 5復(fù)雜路由的研究 5.1復(fù)雜路由的結(jié)論 5.2分析與證明 5.3討論和擴(kuò)展 5.4本章小結(jié) 6總結(jié)與展望 6.1工作總結(jié) 6.2工作展望 致謝 參考文獻(xiàn) 社會(huì)網(wǎng)絡(luò)（Soilntwork）是由許多節(jié)點(diǎn)構(gòu)成的一種社會(huì)結(jié)構(gòu)。節(jié)點(diǎn)通常是組織或個(gè)人，節(jié)點(diǎn)之間的連接代表網(wǎng)絡(luò)中之間的社會(huì)關(guān)系。社會(huì)關(guān)系可以是親朋好友這種很親密的關(guān)系，也可以是偶然相識(shí)的泛泛之交。這些社會(huì)關(guān)系，把社會(huì)網(wǎng)絡(luò)上分散獨(dú)立的連接起來(lái)，組成一個(gè)整體。社會(huì)網(wǎng)絡(luò)也被認(rèn)為是疾病、信息和行為的媒介。社會(huì)學(xué)家研究社會(huì)網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)上的已經(jīng)有幾十年了，很多研究成果對(duì)于社會(huì)科學(xué)、經(jīng)濟(jì)學(xué)和計(jì)算機(jī)科學(xué)的交叉領(lǐng)域有很大的啟示。這也不斷激勵(lì)著科學(xué)家們?nèi)?duì)社會(huì)網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)上的傳播建模。從圖論的角度來(lái)看，小世界網(wǎng)絡(luò)就是一個(gè)由大量節(jié)點(diǎn)構(gòu)成的圖，其中大部分節(jié)點(diǎn)之間的路徑長(zhǎng)度遠(yuǎn)小于圖點(diǎn)數(shù)量。經(jīng)常地，兩個(gè)陌生人在交談后發(fā)現(xiàn)有一個(gè)共同的朋友，互相不認(rèn)識(shí)的人也許通過(guò)自己的可以很快建立聯(lián)系。那么人們所處的社會(huì)網(wǎng)絡(luò)是不是小世界網(wǎng)絡(luò)呢？二十世紀(jì)60年代，哈佛大會(huì)心理學(xué)家斯坦利?米爾格倫Staleyilgram）做了鎖信實(shí)驗(yàn)1]。他將一些信件交給自愿的參加者，要求他們通過(guò)自己的朋友將信傳到信封上指明的收信人手里。參與者們并不知道這個(gè)收信人詳細(xì)資料，而是只知道收信人的基本信息，如所在的城市和職業(yè)。每個(gè)收到信件的人都被要求把信件轉(zhuǎn)發(fā)給他們的朋友來(lái)盡可能地去把信件傳遞給指定的收件人。他發(fā)現(xiàn)，29464封最終送到了目標(biāo)人物手中。在成功傳遞的信件中，平均只需要56次轉(zhuǎn)發(fā)，就能夠到達(dá)目標(biāo)。這個(gè)實(shí)驗(yàn)表明，的任意兩個(gè)人之間的“距離”是6。這就是著名的“六度分隔”理論（ixDrsofSprtin。盡管他的實(shí)驗(yàn)有不少缺陷，但這個(gè)現(xiàn)象引起了學(xué)界的注意。ilrm除了社會(huì)網(wǎng)絡(luò)以外，小世界現(xiàn)象在自然形成的或者工業(yè)推動(dòng)產(chǎn)生的網(wǎng)絡(luò)中都是很如.線蟲(chóng)的神經(jīng)網(wǎng)絡(luò)和西部的電力網(wǎng)2]，網(wǎng)中的超所構(gòu)成的網(wǎng)絡(luò)也具有小世界現(xiàn)象3]。?格拉諾維特（rkrnovttr）4,5]強(qiáng)連接和弱連接。強(qiáng)連接（Strongti）指非常親密的關(guān)系，例如家人、摯友等。而且這些關(guān)系需要付出一定的時(shí)間和經(jīng)歷，需要用心去呵護(hù)。而相對(duì)于強(qiáng)連接，人們還維持著一些更廣泛的社會(huì)關(guān)系，不需要投入太多心思，例如偶然結(jié)識(shí)的新朋友、遠(yuǎn)處的同學(xué)，這些關(guān)系被稱為弱連接（kti。Granovetter通過(guò)調(diào)研麻省牛頓鎮(zhèn)的居民如何找工作來(lái)探索社會(huì)網(wǎng)絡(luò)[5]，得到了一個(gè)令人驚訝的結(jié)論。被的人中，大部分都是通過(guò)自己的人脈來(lái)找到現(xiàn)在的工作但是比較有趣的是這些人脈大部分都不是最親密的那些朋友，這被稱為弱連接的力量[4]（Thernthofwkti。這也許是因?yàn)橐粋€(gè)人的比較親密的朋友他們可能本來(lái)已經(jīng)是朋友，這些社會(huì)關(guān)系比較冗余，對(duì)于信息的遠(yuǎn)距離傳遞幫助沒(méi)有那么大。而少數(shù)的弱連接，卻可以幫助信息傳遞很遠(yuǎn)，對(duì)于社會(huì)網(wǎng)絡(luò)中信息的有很大的幫助。社會(huì)網(wǎng)絡(luò)小世界現(xiàn)象的發(fā)現(xiàn)和弱連接理論的提出引起了學(xué)術(shù)界的關(guān)注，許多工作開(kāi)始專注于小世界網(wǎng)絡(luò)的建模。ttsStrotz首先提出了基于圓環(huán)的小世界網(wǎng)絡(luò)模型2]，模型按照如下步驟構(gòu)造。2kk是一個(gè)較小的常數(shù)，這些邊被3p的概率重新選擇邊的終點(diǎn)，終點(diǎn)是完全隨機(jī)地從V中選擇的，重新連接的邊被稱作弱連接。這樣就完成了小世界網(wǎng)絡(luò)的建立。他們還提出了小世界網(wǎng)絡(luò)的應(yīng)該具有的兩個(gè)特性：直徑較小（Shortdiamter）和系數(shù)較大（Highluteringoficit。直徑較小是因?yàn)樾∈澜缇W(wǎng)絡(luò)中兩個(gè)不認(rèn)識(shí)的可以找到一條較短的連接兩個(gè)人的路徑，這首先要求網(wǎng)絡(luò)中任意兩點(diǎn)之間存在比較短的路徑。系數(shù)是一個(gè)節(jié)點(diǎn)的鄰接點(diǎn)之間相互連接的程度，真實(shí)社會(huì)網(wǎng)絡(luò)中，一個(gè)人的朋友之間一般都會(huì)相互認(rèn)識(shí)，這說(shuō)明社會(huì)網(wǎng)絡(luò)的聚集系數(shù)也比較大。之前的研究[6一般設(shè)定每個(gè)人都完全隨機(jī)地從所有人選擇一些人作為自己的朋友，而且相識(shí)關(guān)系是對(duì)稱的。這樣構(gòu)成的網(wǎng)絡(luò)是一個(gè)隨機(jī)圖，而且的確有比較小的直徑[7]。但是過(guò)于隨機(jī)的網(wǎng)絡(luò)導(dǎo)致這個(gè)網(wǎng)絡(luò)的系數(shù)比較小，這不符合社會(huì)網(wǎng)絡(luò)的特而，如果一個(gè)網(wǎng)絡(luò)的系數(shù)比較大，例如一個(gè)二維網(wǎng)格，這個(gè)網(wǎng)絡(luò)的直徑會(huì)較大，沒(méi)有小世界現(xiàn)象的存在。tts和Srogtz這個(gè)模型是介于兩個(gè)之間的模型，同時(shí)具有較小的直徑和較大的系數(shù)。這個(gè)模型是一個(gè)圓環(huán)框架和隨機(jī)圖的疊加，圓環(huán)作為模型的底層結(jié)構(gòu)（Undrlyngtutr，而隨機(jī)圖代表網(wǎng)絡(luò)中少量的弱連接。這樣疊加圖的模型恰好同時(shí)保持了圓環(huán)較大的系數(shù)和隨機(jī)圖較小直徑的優(yōu)點(diǎn)。由于系數(shù)較大，信息在一個(gè)的群體中通過(guò)強(qiáng)連接可以很快。而為數(shù)不多的弱連接可以把消息傳遞到很遠(yuǎn)的群體，進(jìn)而消息可以在整個(gè)網(wǎng)絡(luò)中很快。KleinbergWattsStrogatz的模型[8]，也是基于由強(qiáng)連接構(gòu)成的框架和隨機(jī)圖的弱連接疊加而成。Kleinberg的小世界網(wǎng)絡(luò)的框架是一個(gè)二維的網(wǎng)格，網(wǎng)格上的邊代uv為終點(diǎn)的1/|uv|α|uv|uv之間的網(wǎng)格距離，α是小世界模型的參數(shù)（Clusteringexponent。Kleinberg證明了當(dāng)且僅當(dāng)α等于網(wǎng)格的維度（這里是2）當(dāng)前節(jié)點(diǎn)會(huì)選擇距離目標(biāo)網(wǎng)格距離最近的節(jié)點(diǎn)來(lái)傳遞消息。α=2的小世界網(wǎng)絡(luò)中分散式路由的效率在數(shù)量級(jí)上符合Milgram的實(shí)驗(yàn)結(jié)果。然而在α不等于網(wǎng)格的維度時(shí)，Newan和Watts小世界模型[9]恰好是Kleinberg的模型在α=0的一維形式。在α<2時(shí)，弱連接的分布比較隨機(jī)，相對(duì)來(lái)說(shuō)會(huì)更易于連接到相距較遠(yuǎn)的點(diǎn)。但是弱連接分布的過(guò)于隨機(jī)化導(dǎo)致在分散式路由算法執(zhí)行時(shí)，不知道應(yīng)該把消息傳遞給哪一個(gè)聯(lián)系人，不能保證路由算法的高效率。隨著α的增大，uα>2時(shí)，節(jié)點(diǎn)弱連接的分布就過(guò)于集中，系數(shù)較大。因此即使有弱連接的幫助，分散式算法也不能有效的找到目標(biāo)。而在α=2這個(gè)位置，弱連接不會(huì)過(guò)于集中，同時(shí)也具有一定的地理依賴性，弱連接的隨機(jī)性在本文中，我們使用的就是Kleinberg的小世界模型（Kleinberg’ssmall-worldnetworkmodel）。現(xiàn)實(shí)中大量的網(wǎng)絡(luò)都具有小世界現(xiàn)象，從互聯(lián)網(wǎng)到網(wǎng)，從神經(jīng)網(wǎng)絡(luò)到電力傳力。但是同時(shí)，過(guò)于網(wǎng)絡(luò)化的社會(huì)有時(shí)也會(huì)帶來(lái)。例如傳染病的爆發(fā)，到處肆虐的計(jì)算機(jī)，的擴(kuò)散，網(wǎng)絡(luò)的小世界性質(zhì)為這些有害信息的提供了良好的條件。同時(shí)網(wǎng)絡(luò)點(diǎn)的互相影響也會(huì)因其，例如電力網(wǎng)絡(luò)的癱瘓。人們必須了解傳些的發(fā)生。對(duì)于社會(huì)網(wǎng)絡(luò)復(fù)雜傳染病和路由的研究可以幫助理解小世界網(wǎng)絡(luò)的結(jié)構(gòu)和復(fù)雜速度的關(guān)系，對(duì)于疾病預(yù)防和控制有一定的幫助。復(fù)雜路由的Granovetter在1978年的另一篇文章[10]中提出了有閾值的傳染模型用來(lái)描述、創(chuàng)意和行為等的，這些往往需要接受者投入一定的成本。在這個(gè)傳染模型中，社會(huì)網(wǎng)絡(luò)中的只有在他的疾病鄰居的數(shù)量超過(guò)一定閾值的時(shí)候才會(huì)被傳染。Kempe2003年提出了線性閾值，固定閾值和通用閾值等模型[11]，這與我們研究的復(fù)雜傳染病模型直接相關(guān)在近期的工作中，CentolaMacy把閾值傳染模型歸類為簡(jiǎn)單傳染病模型和復(fù)雜傳染病模型[12]。簡(jiǎn)單傳染病對(duì)應(yīng)于網(wǎng)絡(luò)中所有節(jié)點(diǎn)閾值均為1的閾值傳染模型，這就意味著當(dāng)一個(gè)節(jié)點(diǎn)在有一個(gè)被的鄰居的時(shí)候他就會(huì)被。簡(jiǎn)單傳染病模型在現(xiàn)實(shí)生活中可以看作流感或者八卦的，因?yàn)槿藗冊(cè)诮佑|到消息源或者傳染源后很容易。而另方面復(fù)雜病對(duì)應(yīng)閾值至為2的閾值傳染模型。因此只有在他的一定數(shù)量的鄰居都被的時(shí)候才會(huì)被。對(duì)應(yīng)到實(shí)際的社會(huì)網(wǎng)絡(luò)，復(fù)雜傳染病模型地描述的是那些有一定代價(jià)的決定的，譬如一款新產(chǎn)品、采納一個(gè)有風(fēng)險(xiǎn)的建議。一款新式的上市后，一個(gè)人往往會(huì)在很多同學(xué)和同事都了該款手機(jī)后才會(huì)動(dòng)心，新的上映也是如此。需要在接收到來(lái)自足夠多獨(dú)立的建議后才能說(shuō)服自己作出決定。ntola和y進(jìn)一步弱連接盡管在社會(huì)網(wǎng)絡(luò)中對(duì)于信息的長(zhǎng)距離傳輸有很大幫助，但是對(duì)于復(fù)雜傳染的幫助比較小。這是因?yàn)閷?duì)于社會(huì)網(wǎng)絡(luò)中的復(fù)雜傳染病模型，只有在不同區(qū)域之間形成較長(zhǎng)和較寬的由弱連接組成的橋梁時(shí)，信息才能較快的。這對(duì)于隨機(jī)性比較大的而數(shù)量較少弱連接來(lái)說(shuō)是很難形成的。Kleinberg模型的直在2000年Kleinberg提出了一個(gè)小世界模型并討論了在這個(gè)模型上分散式路由的效率。但是他只是討論了路由算法的效率，并沒(méi)有去分析網(wǎng)絡(luò)的直徑。Nguyen和 在最近的工作中討論了當(dāng)模型參數(shù)0≤α≤2時(shí)Kleinberg模型的直徑[13]。他們的結(jié)果是0≤α≤2的Kleinberg網(wǎng)絡(luò)模型的直徑為Θ(logn)，n是網(wǎng)絡(luò)點(diǎn)的個(gè)數(shù)。而在每個(gè)節(jié)點(diǎn)的度為常數(shù)時(shí)，一個(gè)網(wǎng)絡(luò)直徑的期望也是?(logn)，這說(shuō)明Kleinberg模型的直徑的確很小，在0≤α<2時(shí)分散式路由的效率較低不是因?yàn)榫W(wǎng)絡(luò)兩個(gè)節(jié)點(diǎn)之間不果把時(shí)間看成離散的時(shí)間點(diǎn)，是指給定了節(jié)點(diǎn)后，在每一個(gè)時(shí)間點(diǎn)，在傳染模型下當(dāng)前所有可以被的節(jié)點(diǎn)都會(huì)被。而路由則是在每個(gè)時(shí)間點(diǎn)，從當(dāng)前可以的節(jié)點(diǎn)集合中，根據(jù)路由算法僅選擇一個(gè)節(jié)點(diǎn)。一個(gè)網(wǎng)絡(luò)的直徑恰好和速度對(duì)應(yīng)著，從這我們就知道了對(duì)于同一個(gè)網(wǎng)絡(luò)，速度和路由速度可能相差很大（nNguyenMar2<α<4時(shí)，Kleinberg基于二維網(wǎng)格的模型也O(logβn)形式的直徑，βn無(wú)關(guān)的常數(shù)[14]α4的時(shí)候，Kleinberg模型的直徑就變成了多項(xiàng)式形式，出現(xiàn)了從對(duì)數(shù)到多項(xiàng)式的相變現(xiàn)象。1受到有關(guān)復(fù)雜傳染模型工作的啟發(fā)，Ghasemiesfeh等人首次給出了小世界模型中復(fù)雜傳染的理論分析[15]。他們研究了k-復(fù)雜傳染病的（簡(jiǎn)稱k-復(fù)雜，在這個(gè)設(shè)置下網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的閾值為k，也就是說(shuō)節(jié)點(diǎn)在有k個(gè)被鄰居時(shí)就立即會(huì)被。他們研究了時(shí)間，也就是給定k個(gè)通過(guò)強(qiáng)連接相連的節(jié)點(diǎn)后，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都被所需要的時(shí)間。他們的主要結(jié)果是在k=2對(duì)于基于二維網(wǎng)格的Kleinberg2以內(nèi)的點(diǎn)會(huì)被強(qiáng)連接相連。這時(shí)，時(shí)間具有上界O(log3.5n)，n仍然指小世界網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)。同時(shí)也給出了基于一維圓環(huán)-Watts模型[9]α=0條件下的Kleinberg模型。這時(shí)弱連接是完全均勻分布的，而此時(shí)時(shí)間具有下界?(n3)。1自從上文提到的Watts-Strogatz模型[2]和Kleinberg模型[8]被提出后，還有其他很多小世界模型的擴(kuò)展和變種被研究過(guò)。在2001年Kleinberg又提出了基于樹(shù)狀結(jié)構(gòu)的小世界模型，樹(shù)的葉子代表社會(huì)網(wǎng)絡(luò)中的 Θ(log2n)時(shí)，貪心路由算法可以很快地找到目標(biāo)。FraigniaudGiakkoupisKleinberg的小世界模型和冪律分布（Powerlaw）結(jié)合起來(lái)[16]，即每個(gè)節(jié)點(diǎn)發(fā)出的弱連接數(shù)目遵從冪律分布。同時(shí)他們也在Kmpe提出了最大化的問(wèn)題之后11,18]，一系列后續(xù)問(wèn)題都在研究在隨模型給定限額budgt后，如何找到使社會(huì)網(wǎng)絡(luò)中最終被影響的節(jié)點(diǎn)最多的budgt個(gè)P問(wèn)，最近工作在研究比高效的啟式法。陳衛(wèi)等人提供了一個(gè)可以在大規(guī)模網(wǎng)絡(luò)運(yùn)行的最大化算法19,20]，在有較高的效率的同時(shí)也可以輸出不錯(cuò)的結(jié)果。與此同時(shí)陳寧證明了在一個(gè)所有節(jié)點(diǎn)都有固定閾值的網(wǎng)絡(luò)中，近似算法很難找到可以影響到所有節(jié)點(diǎn)的最小節(jié)點(diǎn)集合21]，也就是說(shuō)很難給出一個(gè)多項(xiàng)式對(duì)數(shù)近似比（Polyogrthmicftor）現(xiàn)有的有關(guān)小世界網(wǎng)絡(luò)的分析大多是關(guān)于簡(jiǎn)單傳染病的和路由，去年Ghasemiesfeh等人給出了第一份有關(guān)復(fù)雜傳染病的的理論分析[15]。本文進(jìn)一步給出Kleinberg模型下復(fù)雜傳染病的理論上的分析，提升時(shí)間的下界，解決Ghasemiesfeh等人留下的開(kāi)放性問(wèn)題。同時(shí)在準(zhǔn)備研究一種新的消息行為，復(fù)雜傳染病的路Kleinberg的分散式路由，而在本文關(guān)注的是復(fù)雜傳染病上的分散式路由。最后對(duì)比簡(jiǎn)單，簡(jiǎn)單路由，復(fù)雜和復(fù)雜路由的效率。Kleinberg小世界網(wǎng)絡(luò)，在生成的小世界網(wǎng)絡(luò)上估計(jì)簡(jiǎn)單傳染病的時(shí)間和路由時(shí)間以及復(fù)雜傳染病的時(shí)間，然后分析實(shí)驗(yàn)第二，給出復(fù)雜傳染病的理論上的分析。在2013年Ghasemiesfeh等人第一次給出了復(fù)雜傳染病模型下信息速度的研究。他們同時(shí)也證明了在小世界模型的參數(shù)α為網(wǎng)格維度時(shí)，復(fù)雜的速度很快，是網(wǎng)絡(luò)點(diǎn)數(shù)量的多項(xiàng)式對(duì)數(shù)級(jí)下界。本文主要關(guān)注對(duì)于二維網(wǎng)格模型，當(dāng)α不為2時(shí)，復(fù)雜時(shí)間的下界，嘗試Kleinberg的分散式路由算法的結(jié)果，當(dāng)且僅當(dāng)在α等于2時(shí)，復(fù)雜時(shí)間較短，當(dāng)α不為2時(shí)，可以給出節(jié)點(diǎn)數(shù)量多項(xiàng)式形式簡(jiǎn)單傳染病的由（Klinbeg的貪心路由簡(jiǎn)單染病（網(wǎng)絡(luò)的直）和復(fù)傳染病的時(shí)間上下界。但是復(fù)雜傳染病的路由一直沒(méi)有人進(jìn)行相關(guān)研究。相比于簡(jiǎn)單傳染病的路由，復(fù)雜傳染病的路由需要的弱連接來(lái)支持。復(fù)雜路由所需要的時(shí)間必然要比簡(jiǎn)單路由，但是仍然希望看到類似于簡(jiǎn)單路由的在α等于網(wǎng)格維度時(shí)具有最高的效率。在文中也會(huì)去尋找對(duì)于復(fù)雜傳染病的比較高效的路由算法。復(fù)雜路由在現(xiàn)實(shí)生活中類似于一群人在不斷的擴(kuò)大自己陣營(yíng)的同時(shí)去影響另一個(gè)人。復(fù)雜路由的研究對(duì)于社交上主動(dòng)交友方面也有一定的幫助22]，和等社交上通過(guò)添加一些中間好友來(lái)增加目標(biāo)接受自己好友請(qǐng)求的概率。第四，分析對(duì)比簡(jiǎn)單路由、簡(jiǎn)單、復(fù)雜路由和復(fù)雜的結(jié)果，研究時(shí)間和路由時(shí)間與模型參數(shù)α的關(guān)系，同時(shí)深入探討復(fù)雜傳染與簡(jiǎn)單傳染的內(nèi)在區(qū)別。本畢業(yè)設(shè)計(jì)課題來(lái)源于與微軟亞洲的陳衛(wèi)研究員和計(jì)算所的孫曉明老師、張家琳老師合作完成的“TheDiffusionandRoutingofComplexContagioninKleinberg’sSmall-WorldNetworks”。究Klnbg小世界網(wǎng)絡(luò)中復(fù)雜傳染病的時(shí)間和路由時(shí)間，首先分析了小世界模型的特性，包括已有的關(guān)于簡(jiǎn)單（直徑）和簡(jiǎn)單路由的結(jié)論。然后，對(duì)相關(guān)小世界模型和復(fù)雜傳染病模型的定義做出詳細(xì)論述。其次，給出了有關(guān)小世界網(wǎng)絡(luò)上和路由的蒙特卡洛模擬實(shí)驗(yàn)的完整過(guò)程，包括設(shè)計(jì)、步驟和結(jié)果分析等。接下來(lái)給出有關(guān)復(fù)雜和復(fù)雜的主要結(jié)論以及完整證明。最后給出本文結(jié)論和已有結(jié)論的分析對(duì)比。最后把結(jié)論擴(kuò)展到k-復(fù)雜并與簡(jiǎn)單進(jìn)行比較。給出復(fù)雜路由的結(jié)論及完整的證明過(guò)程，然后探討一步允許m個(gè)節(jié)點(diǎn)的復(fù)雜在最后的總結(jié)與展望中，首先整體給出了文章的結(jié)論，然后對(duì)比本文結(jié)果和已有結(jié)果，深入討論了復(fù)雜和簡(jiǎn)單的內(nèi)在差別。然后已有工作的不足，并對(duì)下一步的工作進(jìn)行展望。Klinbeg小世界網(wǎng)絡(luò)的精確定義，包括強(qiáng)連接和弱連接的生成方式。同時(shí)也介紹文中用到的簡(jiǎn)單傳染病和復(fù)雜傳染病模型以及兩種信息擴(kuò)散的方式：和路由。最后介紹在模擬小世界網(wǎng)絡(luò)上的和路由時(shí)采用的蒙特卡洛模擬技術(shù)。Kleinberg小世界模KleinbergnV生成的隨機(jī)圖。n n n個(gè)節(jié)點(diǎn)的位置都是對(duì)稱的。網(wǎng)格上兩個(gè)節(jié)點(diǎn)u和v之間的曼哈頓距離（Manhattandistance）|uv|uv的最短路徑的長(zhǎng)度。這個(gè)隨機(jī)圖上有兩種類型的邊：強(qiáng)連接和弱連接pp1是一個(gè)模型的常數(shù)。弱連接指連接節(jié)點(diǎn)uvuq條互相獨(dú)立的弱連接邊，uiv||α，0是小世界模型的參數(shù)。我們用1/|uv|α乘以歸一化因子Z=1/∑|uv|?α（在環(huán)形網(wǎng)格上，這個(gè)值意的節(jié)u∈V都相等），這樣就得到了弱連接的概率分布函數(shù)。Kleinberg描述的網(wǎng)絡(luò)模型[8]中，u到v之間的弱連接被認(rèn)為是有向邊，這樣的網(wǎng)絡(luò)被稱為有向Kleinberg小世界網(wǎng)絡(luò)模型。而有些研究工作[15]中弱連接被認(rèn)為是無(wú)向的，這樣的網(wǎng)絡(luò)被稱為無(wú)Kleinberg小世界網(wǎng)絡(luò)模型。兩個(gè)模型在本文中都被討論了，在分析復(fù)雜傳染病的傳Kleinberg小世界網(wǎng)絡(luò)模型。分析復(fù)雜傳染病的路由時(shí)，我們使用有向Kleinberg小世界網(wǎng)絡(luò)模型。本文用傳染病去模擬信息、疾病和想法在網(wǎng)絡(luò)中的擴(kuò)散。網(wǎng)絡(luò)中的節(jié)點(diǎn)都有三種狀態(tài)：未（inactive、（exposed）和已（activated。節(jié)點(diǎn)可以從未狀態(tài)轉(zhuǎn)變?yōu)闋顟B(tài)，然后再進(jìn)入狀態(tài)，但是不能反方向轉(zhuǎn)變，例如不能從已感染的狀態(tài)變成未狀態(tài)。傳染病傳染的過(guò)程可以用離散的時(shí)間步驟012來(lái)描述。如果一個(gè)節(jié)點(diǎn)ut?1時(shí)間有至少k個(gè)已經(jīng)的鄰居節(jié)點(diǎn)（在有向圖中指有k個(gè)已節(jié)點(diǎn)發(fā)出的有u，的節(jié)點(diǎn)可以立即或者在后續(xù)時(shí)間步驟中轉(zhuǎn)變?yōu)闋顟B(tài)，這取決于消息擴(kuò)散的方式。簡(jiǎn)單傳染病指k=1的傳染病，也就是說(shuō)u的一個(gè)已的鄰居就可以讓u變?yōu)楦腥緺顟B(tài)（有可能u。而復(fù)雜傳染病則較難傳染，因?yàn)閺?fù)雜傳染病的閾值k≥2，要一個(gè)新的節(jié)點(diǎn)，至少需要兩個(gè)已的鄰居節(jié)點(diǎn)。閾值k≥2的傳染病稱為k-復(fù)雜所有狀態(tài)的節(jié)點(diǎn)在同一時(shí)間會(huì)被立即。在研究k-復(fù)雜時(shí)，為了保證網(wǎng)絡(luò)中所有節(jié)點(diǎn)都會(huì)被，最初選取在網(wǎng)絡(luò)上k個(gè)連續(xù)的節(jié)點(diǎn)設(shè)為狀態(tài)，這些節(jié)點(diǎn)被稱作節(jié)點(diǎn)。為了方便，本文設(shè)置p=q=kukuk以內(nèi)的節(jié)點(diǎn)建立強(qiáng)連接。當(dāng)p=k時(shí)，k-復(fù)雜僅僅通過(guò)強(qiáng)連接也可以整個(gè)網(wǎng)絡(luò)，q=k也本文主要研究傳染病多快把整個(gè)網(wǎng)絡(luò)都傳染，這個(gè)可以用時(shí)間來(lái)描述，而在網(wǎng)絡(luò)中的強(qiáng)連接和弱連接都固定后時(shí)間是定值。時(shí)間是指從k個(gè)節(jié)點(diǎn)開(kāi)本文進(jìn)一步研究了一種比較像分散式路由[8]的擴(kuò)散方式，我們稱之為復(fù) 在復(fù)雜路由中，最初會(huì)選擇一個(gè)節(jié)點(diǎn)t作為目標(biāo)，同時(shí)也有k個(gè)節(jié)點(diǎn)（和復(fù)雜設(shè)定一致。復(fù)雜路由的任務(wù)是盡染到目標(biāo)節(jié)點(diǎn)t，不同于復(fù)雜的是，每一個(gè)時(shí)間步驟中所有被的節(jié)點(diǎn)不會(huì)被立即。每一步，我們只能從狀態(tài)的節(jié)點(diǎn)集合中選擇一個(gè)節(jié)點(diǎn)來(lái)。選擇節(jié)點(diǎn)的策略稱為路由策略。更進(jìn)一步，當(dāng)在時(shí)間i選擇了節(jié)點(diǎn)u去時(shí)，算法僅僅知道已節(jié)點(diǎn)集合的所有鄰居（在有向圖中是已漸的擴(kuò)大自己的，拉攏他們認(rèn)為可以對(duì)勸說(shuō)目標(biāo)有幫助的人入伙，最終影響到目標(biāo)。 一定的代價(jià)，在每一步只能選擇拉攏一個(gè)人。注意到如果把k-復(fù)雜傳染病用簡(jiǎn)單傳染病替代，并且要求下一個(gè)被的節(jié)點(diǎn)是節(jié)點(diǎn)的鄰居，這就是Kleinberg研究為了研究路由找到目標(biāo)的速度，本文定義路由時(shí)間為通過(guò)路由方式距離節(jié)點(diǎn)曼哈頓距離最遠(yuǎn)的目標(biāo)節(jié)點(diǎn)t所需要的步驟。蒙特卡洛模擬（onterloimulaton，也稱統(tǒng)計(jì)模擬方法，是二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明，而被一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)（或更常見(jiàn)的偽隨機(jī)數(shù)）來(lái)解決很多計(jì)算問(wèn)題的方法，與此對(duì)應(yīng)的是確定性算法。有些問(wèn)題很難直接求解，例如一些期望、積分等，直接求出精確解可能時(shí)間復(fù)雜度很大。這時(shí)我們就可以采用蒙特卡洛模擬。主要有兩部分工作：例如在分析復(fù)雜時(shí)間的期望時(shí)，直接根據(jù)小世界網(wǎng)絡(luò)中弱連接的分布函數(shù)求出時(shí)間的期望比較難。可以根據(jù)弱連接的概率分布函數(shù)來(lái)生成弱連接，在給定的生成的小世界網(wǎng)絡(luò)中，可以計(jì)算出復(fù)雜的時(shí)間，這一步就是產(chǎn)生符合概率分布的隨量。做大量的獨(dú)立重復(fù)的生成小世界網(wǎng)絡(luò)的實(shí)驗(yàn)，利用實(shí)驗(yàn)中記錄的時(shí)間的平均時(shí)間作為時(shí)間的期望。這一步是通過(guò)統(tǒng)計(jì)得到數(shù)值解。本章主要介紹了本文使用的Kleinberg小世界模型以及傳染病模型和路由等概念，并給出了精確的數(shù)學(xué)定義，同時(shí)提到了蒙特卡洛模擬。2.1節(jié)介紹了Kleinberg的小世界模型，主要分析了弱連接的生成方式。2.2節(jié)介紹了復(fù)雜傳染病模型，終點(diǎn)介紹閾值和節(jié)點(diǎn)的三種狀態(tài)。2.3節(jié)介紹了復(fù)雜傳染病的，2.4節(jié)介紹了復(fù)雜傳染病的路由并與簡(jiǎn)單路由做了一些對(duì)比。2.5得出時(shí)間和路由時(shí)間與網(wǎng)絡(luò)大小以及Kleinberg小世界模型參數(shù)α的關(guān)系，有利于α=2時(shí)路由時(shí)間首先需要生成Kleinberg的小世界網(wǎng)絡(luò)，這就需要設(shè)計(jì)如何和生成一個(gè)規(guī)模較大的隨機(jī)圖。與此同時(shí)，需要考慮如何生成遵從逆α次方分布的弱連接。比較好的是，二維網(wǎng)格上的節(jié)點(diǎn)都是的，每個(gè)節(jié)點(diǎn)的弱連接的分布都是一 1uv為終點(diǎn)的概率 w

2u[01p，然后在概率分布函數(shù)的數(shù)組上面進(jìn)行二分查找，找到值p對(duì)應(yīng)的數(shù)組下iv。則對(duì)于u的這條弱連接，終點(diǎn)即為下標(biāo)iv對(duì)應(yīng)的節(jié)點(diǎn)v。用上面的方法就可以生成對(duì)于一個(gè)節(jié)點(diǎn)u的弱連接，生成一張圖中所有節(jié)點(diǎn)的弱連接Kleinberg小世界網(wǎng)絡(luò)了。下面討論在生成的小世界網(wǎng)絡(luò)上的傳簡(jiǎn)單的過(guò)程就是廣度優(yōu)先搜索的過(guò)程，因此用廣度優(yōu)先搜索遍歷網(wǎng)絡(luò)，計(jì)算最后被遍歷的節(jié)點(diǎn)需要多少輪廣度搜索，這就是簡(jiǎn)單的步數(shù)。簡(jiǎn)單的步數(shù)是從節(jié)點(diǎn)到網(wǎng)絡(luò)中相距最遠(yuǎn)節(jié)點(diǎn)的路徑的長(zhǎng)度，也就對(duì)應(yīng)著網(wǎng)絡(luò)的直徑。對(duì)于復(fù)雜（考慮2-復(fù)雜，也比較類似，可以為每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)狀態(tài)，然后用類似廣1、生成Kleinberg小世界網(wǎng)絡(luò)，建立一個(gè)遍歷隊(duì)列，節(jié)點(diǎn)入隊(duì)。每個(gè)節(jié)點(diǎn)有個(gè)狀態(tài)變量state用來(lái)記錄已的鄰居節(jié)點(diǎn)的數(shù)量。初始狀態(tài)時(shí)所有節(jié)點(diǎn)的state都為0。節(jié)點(diǎn)用step變量記錄被的時(shí)間步驟，節(jié)點(diǎn)的step=1。2、隊(duì)頭出列，隊(duì)頭元素對(duì)應(yīng)的節(jié)點(diǎn)為u，對(duì)于u的每個(gè)沒(méi)有被的鄰居v，如vstate=0state=1vstate=1v入列，同時(shí)stepv=stepu+1，標(biāo)記v為被狀態(tài)這樣遍歷完整個(gè)網(wǎng)絡(luò)之后，最后一個(gè)出列的節(jié)點(diǎn)的step就可以看做時(shí)間。從復(fù)雜間，簡(jiǎn)單的模擬也類似。為了生成的小世界網(wǎng)絡(luò)，采用了鄰接鏈表的方法，比而簡(jiǎn)單路由的模擬則比較簡(jiǎn)單，因?yàn)槭欠稚⑹铰酚伤惴ǎ惴ú恢莱艘?、在網(wǎng)格上選取節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)t。設(shè)holder為當(dāng)前消息持有者，初始狀態(tài)holder=s。2、根據(jù)概率分布函數(shù)生成節(jié)點(diǎn)holder的弱連接，然后從holder的鄰居節(jié)點(diǎn)（通過(guò)強(qiáng)連接和弱連接相連的鄰居）中選擇距離t曼哈頓距離最近的節(jié)點(diǎn)v，令holder=v。2的執(zhí)行次數(shù)就是簡(jiǎn)單路由需要的步數(shù)。可以看到簡(jiǎn)單路由在模擬過(guò)程中，不需holdrhldr的弱連接即可。而簡(jiǎn)單路由的步數(shù)本來(lái)就比較少，所以模擬時(shí)只需要生成路由路徑上節(jié)點(diǎn)的弱連接，效率很高。這里還是做簡(jiǎn)要的介紹。選用微軟亞洲的服務(wù)器作為實(shí)驗(yàn)主機(jī)，相關(guān)參數(shù)如下硬件環(huán)CPU：In(R)Xeon(R)CPUE5330@2.40GHz(2processors16軟件環(huán)操作系統(tǒng)：WindowsServer2008R2IDE：VisualStudio繪圖工具：gnuplot nα?xí)r簡(jiǎn)單時(shí)間、簡(jiǎn)單路由時(shí)間和復(fù)雜時(shí)間的期望的數(shù)據(jù)。然后可視化數(shù)據(jù)，清晰地觀察n,α對(duì)時(shí)間和路由時(shí)間的影響，進(jìn)一步理解已有的成果，也幫助我們?nèi)ヮA(yù)測(cè)估計(jì)復(fù)雜的結(jié)論。對(duì)于每個(gè)n和α，進(jìn)行1萬(wàn)次模擬，統(tǒng)計(jì)平均結(jié)果，作為期望時(shí)間或者路由時(shí)718800和 、?108、9?102.5?180和3.6?910。復(fù)雜的效率較低，仍然采用比較小的網(wǎng)絡(luò)進(jìn)行模擬，網(wǎng)絡(luò)節(jié) 。網(wǎng)路節(jié)點(diǎn)選取的數(shù)量大致構(gòu)成以2理論分析，復(fù)雜模擬時(shí)α的取值范圍為[0,4]。模擬完成后會(huì)生成列表格式的數(shù)據(jù)，第一列為模型參數(shù)α的取值，第二列為網(wǎng)絡(luò)節(jié)點(diǎn)n的大小，第三列為模擬的時(shí)間或者路由時(shí)間。把分別對(duì)應(yīng)簡(jiǎn)單，簡(jiǎn)單路由和復(fù)雜的數(shù)據(jù)用gnuplot可視化。本節(jié)對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，結(jié)合可視化后的數(shù)據(jù)，深入理解簡(jiǎn)單、簡(jiǎn)單路由和復(fù)雜。首先是簡(jiǎn)單的時(shí)間隨網(wǎng)絡(luò)大小n和Kleinberg小世界模型參數(shù)α的變化曲線，如圖3.1所示。圖的橫坐標(biāo)為模型參數(shù)α的值，縱坐標(biāo)是簡(jiǎn)單所需要的步數(shù)。圖上的兩條曲線分別對(duì)應(yīng)著節(jié)點(diǎn)個(gè)數(shù)為718800和的小世界網(wǎng)絡(luò)的模擬情況。簡(jiǎn)單時(shí)間是用廣度優(yōu)先搜索來(lái)求出的，最后一個(gè)被的節(jié)點(diǎn)需要廣度優(yōu)先搜索的輪數(shù)被記為是簡(jiǎn)單時(shí)間。然后對(duì)于每個(gè)n和α模擬多次后結(jié)果取平均值得到期望的簡(jiǎn)單傳播時(shí)間。從圖3.1可以看出簡(jiǎn)單時(shí)間隨著網(wǎng)絡(luò)的增大也在增大，這是因?yàn)榫W(wǎng)絡(luò)的α∈[0,2]時(shí)具有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的直徑為Θ(logn)相符合。而簡(jiǎn)單時(shí)間隨著α的圖 簡(jiǎn)單時(shí)間隨n和α的變化曲減小也在減小。α越小，網(wǎng)絡(luò)中弱連接的分布就越隨機(jī)。隨著α的增大，弱連接的分布開(kāi)始趨于，網(wǎng)絡(luò)的直徑開(kāi)始增大。而在α=0時(shí)，網(wǎng)絡(luò)中的弱連接是均勻分布的，由隨機(jī)圖的理論[7]O(logn)。對(duì)簡(jiǎn)單圖像的分析也知道Kleinberg的小世界網(wǎng)絡(luò)的確直徑比較小，兩個(gè)點(diǎn)之間的確圖 簡(jiǎn)單路由時(shí)間隨n和α的變化曲3.2Kleinberg小世界模型的關(guān)系。圖的縱坐標(biāo)為簡(jiǎn)單路[02]α是在α=2的附近，簡(jiǎn)單路由的效率最高，但是和理論解釋的在α=2的點(diǎn)取得最小值nα2偏移。可以nα=2處取得最高的效率，這就和理論相符了。同時(shí)也可以看到，簡(jiǎn)單路由的效率的確很高，在36億個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，路由算法也可以1600步以內(nèi)找到目標(biāo)。隨著α的減小，路由的步數(shù)反而開(kāi)始增加，這和網(wǎng)絡(luò)直徑隨著α的減小而減小相反。這也說(shuō)明簡(jiǎn)單路由不僅僅是網(wǎng)絡(luò)中兩點(diǎn)之間存在比較短的路α較小時(shí)，網(wǎng)比簡(jiǎn)單和簡(jiǎn)單路由的速度。在網(wǎng)絡(luò)點(diǎn)個(gè)數(shù)是百萬(wàn)量級(jí)時(shí)，簡(jiǎn)單大約只需要十多步就可以整個(gè)網(wǎng)絡(luò)，而簡(jiǎn)單路由仍然需要大約100步才能找到目標(biāo)。這也說(shuō)圖 復(fù)雜時(shí)間隨n和α的變化曲圖3.3給出了復(fù)雜時(shí)間隨著網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)和模型參數(shù)α的變化關(guān)系。首先可以看到，復(fù)雜在α=2的附近時(shí)，時(shí)間最少。Kleinberg的分散式路由也是在α=2處取得最少的路由時(shí)間，所以我們期望在復(fù)雜也可以看到類似的結(jié)果。根據(jù)可視化的數(shù)據(jù)，復(fù)雜的確也是在α附近時(shí)時(shí)間最少。進(jìn)一步可以觀察在α>2時(shí)，時(shí)間明顯上升，和α≤2時(shí)的時(shí)間相差很大。去年的結(jié)果[15]顯示α=2時(shí)，復(fù)雜時(shí)間上界為O(log3.5n)。因?yàn)橛^察到復(fù)雜在α=2時(shí)效率最高的現(xiàn)象，后續(xù)工作地集中在給出其他α的取值時(shí)時(shí)間n的多項(xiàng)式的下界。Kleinberg小世界網(wǎng)絡(luò)上做的蒙特卡洛實(shí)驗(yàn)以及結(jié)果分析。3.1節(jié)介紹了實(shí)驗(yàn)的設(shè)計(jì)，簡(jiǎn)要的列出了模擬時(shí)采用的算法。3.2節(jié)介紹了服務(wù)器的配置，3.33.4節(jié)介紹了實(shí)驗(yàn)?zāi)康牡綄?shí)驗(yàn)步驟，包括參數(shù)的設(shè)置和網(wǎng)絡(luò)大小的選取。3.5節(jié)用圖表的形式展示了實(shí)驗(yàn)結(jié)果，并分析了實(shí)驗(yàn)圖像，探究了時(shí)間和網(wǎng)絡(luò)大小n以及模型參數(shù)α的關(guān)系。本章在第三章蒙特卡洛模擬實(shí)驗(yàn)的基礎(chǔ)上，給出復(fù)雜完整的理論上的分析。首先給出我們關(guān)于復(fù)雜的主要結(jié)論，然后根據(jù)不同的α的范圍，分別證明。]雜，并給出了期望時(shí)間的下界以及高概率下界（例如以很高的概率1?O(n?ε)時(shí)間大于這個(gè)下界。所有在無(wú)向Kleinberg小世界網(wǎng)絡(luò)中成立的下界在有向Kleinberg小世界網(wǎng)絡(luò)中依然成立，因?yàn)樵谌踹B接為有向邊的網(wǎng)絡(luò)中速度會(huì)比在連接無(wú)向的網(wǎng)絡(luò)中慢。在本文中，主要定理和分析都是基于2-復(fù)雜傳染病模型，探討Kleinbergk-復(fù)雜傳染病的時(shí)間具有依賴于Kleinberg小世界模型參數(shù)α的下界：

?(n4)51對(duì)于α∈[1/5,4/5]， 時(shí)間是?(n1?ε)的概率至少為1?O(n?ε)，期望 間的下界為?(n5)。516)6)

對(duì)于α∈(3, ?(n2α 22-復(fù)雜傳染病模型，本文取網(wǎng)絡(luò)上曼哈頓距離為1的兩個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)，用S0={s1,s2}來(lái)表示這兩個(gè)節(jié)點(diǎn)。對(duì)于Kleinberg發(fā)出兩條弱連接（q=2）。注意到每個(gè)節(jié)點(diǎn)發(fā)出兩條弱連接，但是實(shí)際上可能與許多 用集合序列S0,S1,...,S?=V表示在復(fù)雜 過(guò)程中被 的節(jié)點(diǎn)集合序列，其中Si表示在時(shí)間步驟i時(shí)當(dāng)前的被的節(jié)點(diǎn)集合，?指所有節(jié)點(diǎn)即V被時(shí)的時(shí)間，也就是復(fù)雜傳播需要的時(shí)間。因此，Si的大小是遞增的，而且有S0?S1?···?S?。用Bi表示s1c(i1)nδ的“圓”中所有的節(jié)點(diǎn)（0出的。BiBi{x∈V||1x|≤(i1·c·nδ}i=01，δ0將要確定的非負(fù)參數(shù)，cc·nδ>2的常數(shù)。這樣，兩個(gè)相鄰的圓（Bi2|12|1S0?B001u2u

3u→vuv歸一化因子Z的值不同，下面列出歸一化因子的值以及對(duì)應(yīng)的概率p(u,v)。1、Z= 1),p(u,v)= ),α∈[0, 2、Z=Θ(1),p(u,v)= ),α=log |uv|2log3Z=Θ(1),p(uv)=Θ1),α∈(2定理4.11為了證明0≤α<1/5時(shí)復(fù)雜時(shí)間的下界，首先需要下面這條引理 引理4.1：在無(wú)向Kleinberg小世界網(wǎng)絡(luò)中選定三個(gè)節(jié)點(diǎn)x,y,z（三個(gè)節(jié)點(diǎn)可以相同），節(jié)點(diǎn)z同時(shí)與x和y通過(guò)邊相連的概率Pr(x z,y≥1 z)不超過(guò)14p(x,z)p(y,z 證明最開(kāi)始假設(shè)節(jié)點(diǎn)x,y,z都是不同的。為了計(jì)算概率Pr(x ≥→要把事件 z, z}拆分成四個(gè)較小的事件的并。通過(guò)布爾不等式 ≤Pr(≤Pr(xz,z,x→z,y→z)+≥1z,≥1z,x→z,z→ +←→z,y←→z,z→x,y→z)+Pr(x←→z,y←→z,z→x,z→≤Pr(x→z,y→z)+Pr(x→z,z→y)+Pr(z→x,y→z)+Pr(z→x,z→因?yàn)楣?jié)點(diǎn)x,y,z是固定的節(jié)點(diǎn)，他們彼此之間發(fā)出的弱連接是互相獨(dú)立的。于是有如下概率的等式Pr(x→z,y→z)=Pr(x→z,z→y)=Pr(z→x,y→z)（但Pr(z→x,z→y)和他們不同，因?yàn)閮蓷l弱連接都是從z發(fā)出的。下面以計(jì)算Pr(xzyz的值作為代表，Pr(xzzy)Pr(zxyz的計(jì)算方法和結(jié)果是一樣的，此處就不再列出節(jié)點(diǎn)x發(fā)出兩條弱連接，每一條都會(huì)以p(xz)的概率指向節(jié)點(diǎn)z，所以Pr(xz)≤2p(xz)。因?yàn)楣?jié)點(diǎn)x發(fā)出的弱連接與節(jié)點(diǎn)y{x→z{y→z也是獨(dú)立的。因此Pr(x→zy→z)=Pr(x→zPr(y→z)4p(x,z)p(y,z)2Pr(z→xz→y){z→xz→y}拆分成兩個(gè)事件。第一個(gè)事件是z用第一條弱連接指向x，用第二條弱連接指向y。第二個(gè)事件是zxy{zx{zy是獨(dú)Pr(z→x,z→y)≤p(z,x)p(z,y)+p(z,y)p(z,x)=2p(z,x)p(z,p(xz)=p(zx)p(yz)=p(zy)z被其(Pr (←→z,y←→z)≤14p(x,z)p(y, 注意到x=z或者y=z，Pr(x≥1zy≥1z)=0，這是因?yàn)槿踹B接不會(huì)指向自x=y的情況，{x≥1zy≥1zxz之間至少有兩條弱連{x≥2z}xz2Pr(x≥2z)≤(4)p(xz 證明(定理4.1(1))首先證明，V中存在被與B0的兩條弱連接（弱連接可以來(lái)自B0，也可以來(lái)自z）相連的點(diǎn)z的概率很低，即Pr(?z∈V,z≥2 B0)比較小。Pr(?z∈V,z =Pr(?z∈V,?x,y∈B,x,y,x

z,y≥1

Pr(x

z,y≥1

|V|·|B|2Pr(x z,y≥ 1≥→最后一步的不等式是|V|=n而且|0≤(2cnδ)2=4c2n2δ 從引理4.1，可以得到Pr(x≥1zy≥1z≤14p(xz)p(yz)。因?yàn)棣?/5，歸一化 ←→z,y←→z)≤

=4δ=1?α?ε4Pr(?z∈V,z≥2B)≤16c4n1+4δPr(x z,y z)=16c4n1+4δO(1)=←→ Pr(z∈Vz≥→B0)Kleinberg小世界網(wǎng)絡(luò)，當(dāng)模型參數(shù)α<1/5時(shí)，網(wǎng)絡(luò)中存在與B0通過(guò)兩條弱連接相連的概率很小。在這個(gè)條件下，B0外有節(jié)點(diǎn)被之前復(fù)雜都很慢。這是因?yàn)楣?jié)點(diǎn)被只能通過(guò)（1）僅靠強(qiáng)連接，（2）強(qiáng)連接和弱連接的結(jié)合。不管怎樣都需要一條強(qiáng)連接的幫助才能新的節(jié)點(diǎn)，而強(qiáng)連接的長(zhǎng)度不超過(guò)2。所以在時(shí)間i，被的節(jié)點(diǎn)集合Si最多只能那些距離Si曼哈頓距離不超過(guò)2的節(jié)點(diǎn)。因此有很高的概率在復(fù)雜的開(kāi)始階段，于cnδ時(shí)，Si每一步最多把半徑增加2的概率至少為1?O(n?ε)。而僅僅集合B0需要的時(shí)間就至少為2

=

4)，因此復(fù)雜的時(shí)間以1? )的概率至少 1 對(duì)于期望時(shí)間的下界，需要更精確的計(jì)算才能得到。由于在α<2時(shí)，模型的歸一化因子為Z=(?/2)。因此存在一個(gè)常數(shù)βZ≤β1c 1δ=1?αncnδ>2cδ4 cδZ(4.1≥

41+4δ 4(?z∈V,z←→B0)≤16c Pr(x←→z,y←→z)≤16c

≤8從上面關(guān)于概率的不等式可以得到：以至少1的概率 時(shí)間至少為

1?41? 么2-復(fù) 的期 時(shí)間為?(1·cn4+7·1)=?(n1?α) 這里α=0復(fù)雜時(shí)間的下界和Ghasemiesfeh等人給出的 -Watts模型中復(fù)雜時(shí)間的下界相符合[15]1。前面一節(jié)采用的證明方法對(duì)于比較大的模型參數(shù)α，例如α≥1就不合適了。這一小節(jié)提供了一個(gè)比較通用的證明方法來(lái)更好的研究復(fù)雜，同時(shí)在α≥1/5時(shí)也得到了比較高的下界。主要思路是用一個(gè)一個(gè)的“圓”來(lái)覆蓋住已的節(jié)點(diǎn)集合Sii<λnγ步中，Si?Biλ<12nγ≤1λnγcnδ≤√Bi?(nγ)2n為2-復(fù)雜時(shí)間的下界ξ1iλnγSiBi}ξ發(fā)生的概率很低，或者等價(jià)地說(shuō)概率1?Pr(ξ)非常小。這也就是說(shuō)，在開(kāi)始的cλnγ步中，每一步已cnδRl(s1)s1ls1l 0半徑的圓環(huán)的上的節(jié)點(diǎn)。不l≤|l(1≤4l0現(xiàn)在本文給出事件ξ概率的不等式。假設(shè)在第i步，有Si?1?Bi?1。如果節(jié)點(diǎn)z∈V?Bi想要被，z一定要通過(guò)兩條弱連接和Si?1相連。這是因?yàn)锽i間的距離c·nδ>2，不通過(guò)弱連接去的話，Si?1只能距離Si?1不超過(guò)2的節(jié)點(diǎn)。因此， 11 當(dāng)節(jié)點(diǎn)z<B被z< ≥→ 1?=Pr(?1≤i<λnγ,Si* ∑λnγ?1

?Bi?1,S

*=∑λnγ?1Pr(?z<B, ? ,z∈S

=∑λnγ?1Pr(?z<B, ? ,z2 ∑λnγ?1Pr(?z<B,z2

∑λnγ?1Pr(?z<B,?x,y∈ ,x,y,x z,y≥1

≤∑λnγ?1≤

Pr(x z,y V?Bi

z,y≥1

Pr(x←→z,y←→z)0 l=(i+1)·cnδ0

Pr(x←→z,y←→|xz|li·cnδ|yz|≥li·cnδ|xz||yz|曼哈頓 δPr(x←→z,y←→z)≤14p(x,z)p(y,z)

≤14Z(l?icn Pr(x1z,y≥→z)的∑√∑n 2

0z∈Rl(s1)Pr(x←→z,y←→00l(1·14Z2(l?0

4l·(l?l 56Z2∑√n?icnδ(l+icnδ)·l

2

l1?2α+

δ∑√n?icnδl?2)α α1?≤≤

nn

z∈Rl(s1)Pr(x←→z, ∑λnγ?1

|2·56Z2(∑√n?icnδl1?2α+icnδ∑√n?icnδ (λn(λnγ·16c4λ4n4γ+4δ·l1?2α+√·nδ∑)δδ≤

7·27c4λ5n5γ+4δZ2(∑√n?1l1?2α+cλnγ+δ∑√n?1 從第三行到第四行是|B1≤(2cinδ)2=4c2i2n2δ并且iλnγ定理4.12),(3),(4)本小節(jié)提供了定理.1余下部分的證明。證明的過(guò)程基于兩個(gè)級(jí)數(shù)（見(jiàn)下面）的累α對(duì)應(yīng)的級(jí)數(shù)不同的累加和，本文分別給出α∈[//)，α=/，α∈(1/2,4/5]，α∈(4/5,1)，α=1,α∈(1,2)和α∈(3,∞)的復(fù)雜時(shí)間的下界√δ

l·l?2α

∫√n

α∈[0,x1?2αdx O(log α=2?) α∈(1,O(n1 α∈[0,2

√δ

l?2α

∫n∫

x?2αdx O(log α= δ(1?2α)O(n α(1/2,證明(定理4.1(2),(3),(4))當(dāng)α∈[1/5,1/2)時(shí)，歸一化因子為Z= )。令δBi2(4.3)74

2(

γ+δ∑√n?1?21? ≤7·2cλ + ≤O(n5γ)·O(1)(O(n1?α)+nn/2?

O(n5γ

) 這里γ1?ελ=1，ε是一個(gè)比較小的正數(shù)。不難發(fā)γλ的取值 λnγcnδ<√nγλ的值后，1Pr(ξ)≤O(n?ε)，這樣就意味著有很高的概率1?O(n??)，在復(fù)雜最初λnγ?1步中每一步已節(jié)點(diǎn)集合Si的半徑都于(i+1)·cnδ。由于cλnγnδ<√， 的節(jié)點(diǎn)的集合在第λnγ?1步時(shí)仍然是全部= =

c1c

)，2-復(fù)雜在第

5對(duì)于復(fù)

l1?2α

∫nx1?2αdx∫

(√n)2?2α

l?2α

∫nx?2αdx∫

(√n)1?2α Z注意到對(duì)于歸一化因子，一定存在β 使 ZPr(ξ)1?≤7·

∑n?1l1?2α+∑

∑√n?1?2 l745 2l

(n1?α

≤7·2cλ ·β

77c4λ5n5γ+4δβ2·2 7cβ·n5γ

令λ

5，同時(shí)γ的取值為γ=.很顯然λnγ×cnδ 25cβ得到 Pr(ξ)≤7，這是比較小的常數(shù)。因此以1?

的概率，時(shí)間大于12)5n1 25cβ這也就是說(shuō)，復(fù)雜時(shí)間的期望為?(n5)。這樣就得到了對(duì)于α∈[1/5,1/2)2α的范圍，α12α>3λξ發(fā)生的概率的常數(shù)值，然后就可以給出期望時(shí)間的下界。因此本小節(jié)在接下來(lái)的部分略過(guò)了期望時(shí)間的證明，而僅提供高概率下界的證明。21α1/2時(shí)，令δ0，然后取γλγ=1?ε并且λ=1,因此得到 1? ≤7·27c4λ5n5γ+4δZ2(∑√n?1l1?2α+cλnγ+δ∑√n?1 ≤O(n5γ)·O(1

O(n1/2)+O(nγ)·O(log=O(n5γ)+O(n6γlogn 事件ξ發(fā)生的概率至少為1?O(n?ε)，因此可以得知對(duì)于α=1/2復(fù)雜時(shí)間?(n5c2α(1/21時(shí)，令δ0，λ=1。不(4.3變成c1? 7·27c4λ5n5γ+4δZ2(∑√n?1l1?2α+cλnγ+δ∑√n?1 (n≤O(n5γ)·O(n

O(n1?α)+ O(n5γ)·O(1)O(n1?α)+ ≤O(n+n2?α 4?α+對(duì)于α∈(1/2,4/5]，本文取γ=1?ε.因此1?Pr(ξ)≤O(1)+ 4?α+n 5對(duì)α∈(1/2,4/5]的Kleinberg小世界網(wǎng)絡(luò)以1?O(n?ε)的概率時(shí)間為?(n1?ε)5 至于α∈(4/5,1)時(shí)，取γ=2?α?ε。可以得到事件ξ的概率1?Pr(ξ)= O1)=O(n?ε)。此

時(shí)間高概率

1?5(2?α)+ 63α1δ0，γ=1?ε，λ=1。然后計(jì)算ξ發(fā)生的概率 1? 7·27c4λ5n5γ+4δZ2(∑√n?1l1?2α+cλnγ+δ∑√n?1 n O(n5γ)·O(1)O(logn)+O(nγ)·n=O(n5γlogn)+O(n6γ =于是可以得到對(duì)于2-復(fù)雜的時(shí)間以高概率1?O(n?ε)的下界?(n64α∈(12)時(shí)，1?2α?2α?1δ=0(4.4),(4.5)加和都為O(1)。然后取γ2?α?ε并且λ= 1? 7·(

∑n?1l1?2α+∑δ)

∑√n?1?2lln≤O(n5γ)·O(1)O(1)+n≤ n6γ≤ ≤事件ξ發(fā)生的概率為1?O(n?ε)，從而以很高的概率通過(guò)復(fù)雜整個(gè)網(wǎng)所需要的步數(shù)至少為?(n )5α(3+∞Zδ0，而不能再設(shè)置δ=0。1? ≤7·27c4λ5n5γ+4δZ2(∑√n?1l1?2α+cλnγ+δ∑√n?1l?2α) O(n5γ+4δ)O(nδ(2?2α))+O(nγ+δ)· ≤O(n(2α?2)δ+n(2α?1)δ)==O(n6γ+6δ

α 2 δ=3+εγ=1δ=α?3?ε，此時(shí)0<ε<α3。如果λ=1，那么λnγcnδ≤√n依然成立。于是可以得到關(guān)于事件ξ概率的不等式1Pr(ξ)≤On3)=O(n?ε)。因此本文可以2-復(fù)雜以1α 2 ?(n2α)步才能整個(gè)網(wǎng)絡(luò)結(jié)合關(guān)于α所有范圍的結(jié)論，本文得到了在α∈[02)α∈(3+∞)時(shí)無(wú)向Kleinberg小世界網(wǎng)絡(luò)中復(fù)雜時(shí)間的高概率下界和期望時(shí)間的下界對(duì)于k-復(fù)雜，本文可以得到時(shí)間上類似的下界。在這種情況下，我們需要調(diào)整Kleinberg小世界模型的參數(shù)來(lái)保證復(fù)雜可以通過(guò)強(qiáng)連接進(jìn)行下去。我們?nèi)=q=k，同時(shí)初始的節(jié)點(diǎn)為k個(gè)網(wǎng)格上連續(xù)的節(jié)點(diǎn)。用上一節(jié)類似的方法我們可以得到k-復(fù)雜的結(jié)果，在這里我們只給出結(jié)論。4.1ε>0p=q=kKleinberg α∈ 1 α∈ 1?O(n、對(duì) ，時(shí)間 的概率至少為?ε，期2(k?1) ))

2、對(duì)于α∈[2(k?1),2k 時(shí)間是?(nk?1?ε)的概率至少為1?O(n?ε)，期望k(2k+1)播時(shí)間的下界為?(n2k+1)3、對(duì)于α∈(2k, 時(shí)間是?(n(2?α)k?2ε)的概率至少為1?O(n?ε)，期

時(shí)間的下界為?(n4k+4)4、對(duì)于α∈(2k+2,+∞)，時(shí)間是?(nkα?2k?2?2ε)的概率至少為1?O(n?ε)，期望k

播時(shí)間的下界為?(n )k有一點(diǎn)需要注意到復(fù)雜結(jié)果尚不明確的α范圍是(2,2k+2]，這說(shuō)明隨著k的增0k=1依然成立，k=1的情況對(duì)應(yīng)著簡(jiǎn)單傳染病模型，這個(gè)時(shí)候時(shí)間為網(wǎng)絡(luò)的直徑。在k=1時(shí)，本文的結(jié)果在α<2沒(méi)有太大意義，但是在α>4時(shí)時(shí)間有多項(xiàng)式的下界，這和小世界網(wǎng)絡(luò)直徑[14]的結(jié)果比較類似。k本章主要研究了Kleinberg小世界網(wǎng)絡(luò)中復(fù)雜傳染病的。首先給出了復(fù)雜傳染的主要結(jié)論，然后用列出了兩種不同的證明方法，給出了復(fù)雜結(jié)論的完整理論證明。最后把結(jié)論擴(kuò)展到k-復(fù)雜并給出了一般性的結(jié)論。Kleinberg小世界網(wǎng)絡(luò)中復(fù)雜路由的研究，網(wǎng)絡(luò)模型的設(shè)定Kleinberg最初提出分散式路由時(shí)的網(wǎng)絡(luò)模型一致[8]。正如和第二章描述的，本章考慮節(jié)點(diǎn)u只能激活自己有向邊指向的節(jié)點(diǎn)（出鄰居）的分散式路由方式。只有當(dāng)一個(gè)節(jié)點(diǎn)u被k個(gè)節(jié)點(diǎn)發(fā)出的有向邊指向時(shí)，u才會(huì)被變成狀態(tài)。對(duì)于強(qiáng)連接，仍然認(rèn)為它們是無(wú)向的或者雙向的。在每一個(gè)時(shí)間步驟，我們僅有知道被節(jié)點(diǎn)和被節(jié)點(diǎn)的強(qiáng)連接和弱連接，而對(duì)于未節(jié)點(diǎn)的弱連接算法一無(wú)所知。這樣可以在證明中使用延遲選擇原則[23]，和[8]在證明分散式路由中使用的原則一樣。這意味著節(jié)點(diǎn)u的弱連接只有在u被時(shí)才被選取，進(jìn)而算法才知道u的弱連接。最初的節(jié)點(diǎn)kKleinbergpq=kk-復(fù)雜路由最終可以目標(biāo)節(jié)點(diǎn)t。接下來(lái)給出復(fù)雜路由的主要結(jié)論。 我們考慮一個(gè)2-復(fù)雜路由的任務(wù)，起始給定一對(duì)相鄰的節(jié)點(diǎn)S0={s1, 0和s2的曼哈頓距離為1）目標(biāo)是通過(guò)分散式路由到達(dá)目標(biāo)節(jié)點(diǎn)t。在本文中，我們0論t距 節(jié)點(diǎn)最遠(yuǎn)的情況，也就是s1與t的曼哈頓距離為Θ(√)。從已 節(jié)點(diǎn)集合中選擇哪個(gè)節(jié)點(diǎn)來(lái)是由路由選擇算法決定的，一個(gè)比較特殊的路由選擇策略在經(jīng)的點(diǎn)選擇離標(biāo)t哈頓離小的點(diǎn)這被稱貪由算法。本章的結(jié)果對(duì)于任何分散式路由選擇算法都成立，甚至是隨機(jī)算法。下面是有關(guān)路由時(shí)間的下界的結(jié)果。定理5.1：對(duì)于任意的分散式路由策略（算法），甚至是隨機(jī)的策略，對(duì)于任意的比ε>0Kleinberg小世界網(wǎng)絡(luò)中，2-復(fù)雜路由的路由時(shí)間有下面依賴于Kleinberg小世界模型參數(shù)α的下界： 1α∈[02)?(nα+2)1O(n?)1?(nα+2)12α=2時(shí)，路由時(shí)間是?(n1)的概率至少為1?O(1)，期望路由時(shí)間為41?(n4)1

log3α∈(2+∞)?(nα?2ε)1O(n?εα?(在本章的開(kāi)始首先給出一些定義。對(duì)于一個(gè)已感染節(jié)點(diǎn)集合S，定義集合E(S)為被已節(jié)點(diǎn)集合S的節(jié)點(diǎn)的集合，更精確的定義為E(S)={x<S|S有兩條有向邊指向x}E(S)Kleinberg小世界Kleinberg小世界網(wǎng)絡(luò)中普通路由策略的的性能，然后把結(jié)果推廣到每一步可以多個(gè)節(jié)點(diǎn)的復(fù)雜路由。首先考慮確定性的路由算法，在本節(jié)的最后，我們會(huì)證明本章的下界對(duì)于隨機(jī)的α=2時(shí)路由時(shí)間的證明。設(shè)S0,S1,···,S?為在路由過(guò)程中

被了，s?=t是最后一個(gè)被加入集合S?的節(jié)點(diǎn)。定義距離di=d(Si∪E(Si),t)，這里d(S,u)是指集合Sudid??1=d?=0 s2寫作s0，這樣可以說(shuō)si是在第i0 =|1|=√n因?yàn)閨s1t|=n1/2。設(shè)事件χ為χ={?0≤i<cn4,

1c1是一個(gè)稍后會(huì)定義的常數(shù)。χ0cn1/4?1步，當(dāng)前已的節(jié)點(diǎn)集合到目標(biāo)t的距離每一步最多減少n4。接下來(lái)本文會(huì)證明當(dāng)Kleinberg小世界模型的參數(shù)α=2時(shí)，Pr(χ)是一個(gè)很高的概率，10 引理5.1：對(duì)于α=2的有向Kleinberg小世界網(wǎng)絡(luò)，給定節(jié)點(diǎn){s1,s2}和最遠(yuǎn)的目t（|s1t|=√n）c∈(01)2-復(fù)雜路由的過(guò)程中有0 Pr(?0≤i<cn4,di?1?di≤n4)≥1?O(logn證明令ui為當(dāng)前已節(jié)點(diǎn)結(jié)合和的節(jié)點(diǎn)中距離目標(biāo)t最近的節(jié)點(diǎn)，即ui=argminx{d(xt)|x∈Si∪E(Si)}didi=|uit|ui?1是集合E(Si?1)∪Si?1與目標(biāo)t曼哈頓距離最小的節(jié)點(diǎn)，而si是從第i?1步的集合中選擇siE(Si?1)|sit||sit|≥|ui?1t|di?1。因此如果di?1?di>0uisisitdi?1。此外，還可以得知ui∈E(Si)?E(Si?1)（ui是在第i步剛剛變?yōu)闋顟B(tài)的節(jié)點(diǎn)），同時(shí)是si在第i步變成了狀態(tài)導(dǎo)致ui變成狀態(tài)（ui恰好在第i步被，這正是因?yàn)閟i被感染了di|uit|=di|siui|≥|sit|?|uit|di?1?di。所以有了下面的結(jié)如果在i1di?1din1/4，11|siui|>n412uisisiui的弱連接（|siui|比3、ui恰好在第i步變?yōu)闋顟B(tài)，因此集合Si?{si}中恰好存在一條弱連接指uii0的情況因?yàn)閐(S0td?1，所以是u0∈E(S0引起d?1d0之間的差距，11本文稱那些被集Si?{si}發(fā)出弱連接指向的節(jié)點(diǎn)集合Xi。很顯然根據(jù)上面的第3ui∈Xiidi?1?din4diui一定被si發(fā)出的一條長(zhǎng)度至少為n4的弱連接指向。由布爾不等式，得到11 1?Pr(?0≤i<cn4,di?1?di≤n4 =Pr(?0≤i<cn4,di?1?di>n4 ∑ Pr

–d>n cn4∑

( 41 cn4–1Pr(si→ui,|siui|>n4,ui∈X4≤∑cn14≤

1Pr(?x∈Xi,si→x,|six|>n41Si?{si}i12(i1)條弱連接。這意味2(i1)Si?{si}|Xi||Xi|≤2(i+1)Hi?2V2(i+1)Xisi1Pr(?x∈Xi,si→x,|six|>n41 11 1

v∈V

(Xi=C)∧(si=v)∧(?x∈C,v→x,|vx|>n4∑1 1

(Xi=C)∧(si=

Pr(?x∈C,v→x,|vx|>n4∑ ∑

)(Xi=C)∧(si=

x∈CPr(v→x,|vx|>n4∑ ∑

Pr(Xi=C)∧(si=

·|C|·2Z 2(i+1)

n1

Pr

=C)∧

=n1=2(i+1) Zn111由分散式路由的性質(zhì)可以知道，事件{(Xi=C)∧(si=v)}僅依賴于Si?{si}和集合Sisi}vSi?{si}{?x∈Cv→x|vx|>n4}又僅與固定節(jié)點(diǎn)v發(fā)出的弱連接相關(guān)。因此事件{(Xi=C)∧(si=v)}和事件11{?x∈Cv→x|vx|>n4}互相獨(dú)立，這就是公式第三行等號(hào)的來(lái)源。對(duì)于節(jié)點(diǎn)x n|vx|n4Pr(v→x|vx|>n4)0；否則的話，Pr(v→x|vx|>n4)≤2p(v,x)≤2Z12·1./4這是公式第四行到第五行“≤”的原因。把這個(gè)不等式帶入引理的(5.1)中:n 1?Pr(?0≤i<cn4,di?1?di≤n44 ∑cn1–1Pr?x∈X,4

→x,|sx|>n ∑

42(i+1)≤cn42(i+1)≤ cn4·2cn4·Θ(lognlog=O(1log111證明(定理5.1)正如引理5.1所述，對(duì)于α=2的情況，在最初的cn4步中，已節(jié)1 tn4cn4tlog1?O(1)α=2Kleinberglog11 cn4·(1?O(logn))=?(n4)α∈[02)時(shí)，類比于引理5.1ε> 1?Pr(?0≤i<cnα+2,di?1?di≤2n2(α+2) ∑

Pr(?x∈Xi,si→x,|six|>2n2(α+2) cnα+2?12(i+1)·Z·(2n2(α+2)

·2cnα

·O

=1?O(n?ε)?(n1?ε)ε=0然后選取合適的常數(shù)cα>2α>Pr(?0≤i<cnα?2ε, –d≤n1+ε)≥1?

1O(n?ε)cnα?2εt有關(guān)復(fù)雜路由時(shí)間的下界對(duì)于分散式的路由選擇算法依然成立，這里本文提供了α=2情況的證明。A為所有的確定性分散式路由算法的集合，G為所有可能的基于α=2的leinbg小世界網(wǎng)絡(luò)的集合，πl(wèi)einbgGT(G)A∈AG∈G隨機(jī)算法是在確定性算法上的一個(gè)分布，我們只需要證明對(duì)于任意的在確定性算法集A，Pr

(T(A,G))=?(n1/4))=1?O(1 logGπEA～μ(T(AGA遵從的分布μ。?A∈A,Pr(T(A,G)=?(n1/4))=1?Ac1c2>0

logn?A∈A,Pr(T(A,G)≥c1n1/4)≥1

lognA∈AAPr(T(A,G)≥cn1/4)≥1 c2

log

Pr

(T(A,G))

c1n1/4)≥1?3c2

logPr

(T(A,G))<c1n1/4)≥3c2 log2logG1?G為滿EA～μ(T(AG))<c1n1/4的所有小世界G的集合，于是可以得PrG～π(G∈G1)≥3c2。對(duì)于任意固定的小世界網(wǎng)絡(luò)G∈G2loga（Markov’sinequalityPr(|X|≥a)≤E|X)）a?G∈G,Pr(T(A,G)≥cn1/4)≤EA～μ(T(A, 1

因此對(duì)于任意的G1中的元素G，PrA～μ(T(AGc1n1/4≥1/2都成立，而G1的元素出現(xiàn)的概率至少為1。2Pr(T(A,G)<c

=1.5c2

≥2·log log這與不等式(5.3)相，假設(shè)不成立，等式(5.4)和等式(5.2)成立。因此在α=2時(shí)，對(duì)于任意的隨機(jī)路由算法A～μ，期望的復(fù)雜路由時(shí)間均有?(n1/4)的下界。用上一節(jié)的方法，可以得到k-復(fù)雜路由相同的下界。為了保證復(fù)雜路由能夠找到目標(biāo)，需要設(shè)置Kleinberg小世界網(wǎng)絡(luò)的參數(shù)為p=q=k，同時(shí)節(jié)點(diǎn)的個(gè)數(shù)為k。因?yàn)榻Y(jié)果和2-復(fù)雜路由一樣，這里就不在列出定理。接下來(lái)本文把結(jié)果擴(kuò)展到每一步允許多個(gè)（m個(gè)）節(jié)點(diǎn)的復(fù)雜路由。當(dāng)m=1時(shí)，這正是我們前一節(jié)在定理5.1m的大小時(shí)，復(fù)雜路由就演變?yōu)閺?fù)雜。m可以被看作是連結(jié)復(fù)雜路由和復(fù)雜的變量，本文嘗試去探索多大的m可以把復(fù)雜路由的時(shí)間拉低到復(fù)雜路由的水平。log中，每一步可以允許m個(gè)節(jié)點(diǎn)的k-復(fù)雜路由的路由時(shí)間有很高的概率1?O(1log路由時(shí)間為?(n1/4)，期望路由時(shí)間為?(n1/4) 證明設(shè)S為當(dāng)前已節(jié)點(diǎn)的集合。在下一步，通過(guò)S發(fā)出的有向邊我們最多可以m個(gè)節(jié)點(diǎn)。但是考慮一步只允許一個(gè)節(jié)點(diǎn)的復(fù)雜路由，如果一步只去一個(gè)節(jié)點(diǎn)，但是分成m步去。在每一步完成后，路由算法都會(huì)了解到新感染節(jié)點(diǎn)的有向邊，也就是有的機(jī)會(huì)去其他節(jié)點(diǎn)。不難看出每步一個(gè)節(jié)點(diǎn)分成m步去要比一步m個(gè)節(jié)點(diǎn)的路由更有效率。因此如果每步一個(gè)節(jié)點(diǎn)的復(fù)雜路由需要T個(gè)時(shí)間步驟來(lái)找到目標(biāo)，每步允許m個(gè)節(jié)點(diǎn)的復(fù)雜m路由至少也需要T才能完成。所以每步允許m個(gè)節(jié)點(diǎn)的復(fù)雜路由的路由時(shí)間m m·(1?Olognm)從上面這個(gè)定理可以得知為了得到路由時(shí)間為n的多項(xiàng)式對(duì)數(shù)級(jí)的復(fù)雜路由，每一步允許的節(jié)點(diǎn)個(gè)數(shù)m需要很大，至少為m=4n1/logO(1)n。Klinbeg小世界網(wǎng)絡(luò)中復(fù)雜路由的概念，并對(duì)這一信息擴(kuò)散現(xiàn)象進(jìn)行了研究。首先給出最簡(jiǎn)單的復(fù)雜路由的結(jié)論并給出了完整了理論證明，然后把結(jié)論擴(kuò)到k-復(fù)雜路由，并且建立起復(fù)雜路由和復(fù)雜的關(guān)系，研究了每步允許m個(gè)節(jié)點(diǎn)的復(fù)雜路由。本章總結(jié)了取得的主要結(jié)論和成果，然后與已有結(jié)果進(jìn)行對(duì)比。本文主要研Kleinberg小世界網(wǎng)絡(luò)中復(fù)雜傳染的現(xiàn)象，解決了去年遺留的開(kāi)放性問(wèn)題[15]。文中nKleinberg2的復(fù)雜傳染。首先，本文解決了[15]中有關(guān)復(fù)雜的問(wèn)題：對(duì)于α∈(0,2)的具有n 節(jié)點(diǎn)的小世界網(wǎng)絡(luò)，Ghasemiesfeh等人給出的時(shí)間的上界O(n5?2αlog2n)和下?(logn/loglogn)有指數(shù)量級(jí)的差距。本給出了α在區(qū)間(0,2)時(shí)時(shí)間多項(xiàng)式表 α[0,15[1,45(4,52(2,(3,4(4,簡(jiǎn)單（直徑Θ(logO(logβ??(nα?4?(n2?α6O(log2?(nα?2?(n41?(n5?(n6O(log3.5??(n2α1?(nα+21?(n4α?(n2(α+2)ε注2：“*”表示Mar 等人的結(jié)果[13]，“+”表示Nguyen等人的結(jié)果[14]，其中β=log2+1，“§”表示ε然后本文α>3時(shí)，復(fù)雜時(shí)間期望的下界為?(n2α)，（以很高的概1?O(n?ε)， 時(shí)間至少為?(nα?3?ε)α∈(02)的結(jié)果，可以看出對(duì)于α<2和α>3，時(shí)間均有n的多項(xiàng)式形式的下界（α∈(2,3]時(shí)的上下界仍然未知。定性地看，復(fù)雜表現(xiàn)出和Kleinberg分散式路由[8]相似的性質(zhì)（Kleinberg的分散式路由當(dāng)且僅當(dāng)在最佳點(diǎn)α=2n的多項(xiàng)式對(duì)數(shù)的上界。這里我們對(duì)比簡(jiǎn)單傳染病和復(fù)雜傳染病的結(jié)果。可以觀察到簡(jiǎn)單傳染病的比較像從一個(gè)節(jié)點(diǎn)開(kāi)始的廣度優(yōu)先搜索，因此簡(jiǎn)單時(shí)間對(duì)應(yīng)著網(wǎng)絡(luò)的直徑。近期的研究[13,14]當(dāng)α<4時(shí)，Kleinberg小世界網(wǎng)絡(luò)的直徑都是n的多項(xiàng)式對(duì)數(shù)級(jí)（見(jiàn)表格6.1的第二行。從這可以看出，從簡(jiǎn)單傳染病到復(fù)雜傳染病（k從1跳變到2），α∈[0,2)∪(3,4)時(shí)的時(shí)間完成了從n的多項(xiàng)式對(duì)數(shù)級(jí)到多項(xiàng)式級(jí)的巨大跳變，出現(xiàn)了相變現(xiàn)象。這暗示了對(duì)于通常的α（不包括最佳點(diǎn)α=2），復(fù)雜傳染病的要比簡(jiǎn)單傳染病的慢得多。接下來(lái)本文在復(fù)雜的基礎(chǔ)之上，進(jìn)一步研究了一種新的擴(kuò)散現(xiàn)象：復(fù)雜的路由，這