1006大設(shè)計翻譯版小世界網(wǎng)絡(luò)中復(fù)雜傳播和路由

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

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

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

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

3u→vuv歸一化因子Z的值不同，下面列出歸一化因子的值以及對應(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時復(fù)雜時間的下界，首先需要下面這條引理 引理4.1：在無向Kleinberg小世界網(wǎng)絡(luò)中選定三個節(jié)點x,y,z（三個節(jié)點可以相同），節(jié)點z同時與x和y通過邊相連的概率Pr(x z,y≥1 z)不超過14p(x,z)p(y,z 證明最開始假設(shè)節(jié)點x,y,z都是不同的。為了計算概率Pr(x ≥→要把事件 z, z}拆分成四個較小的事件的并。通過布爾不等式 ≤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→因為節(jié)點x,y,z是固定的節(jié)點，他們彼此之間發(fā)出的弱連接是互相獨立的。于是有如下概率的等式Pr(x→z,y→z)=Pr(x→z,z→y)=Pr(z→x,y→z)（但Pr(z→x,z→y)和他們不同，因為兩條弱連接都是從z發(fā)出的。下面以計算Pr(xzyz的值作為代表，Pr(xzzy)Pr(zxyz的計算方法和結(jié)果是一樣的，此處就不再列出節(jié)點x發(fā)出兩條弱連接，每一條都會以p(xz)的概率指向節(jié)點z，所以Pr(xz)≤2p(xz)。因為節(jié)點x發(fā)出的弱連接與節(jié)點y{x→z{y→z也是獨立的。因此Pr(x→zy→z)=Pr(x→zPr(y→z)4p(x,z)p(y,z)2Pr(z→xz→y){z→xz→y}拆分成兩個事件。第一個事件是z用第一條弱連接指向x，用第二條弱連接指向y。第二個事件是zxy{zx{zy是獨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，這是因為弱連接不會指向自x=y的情況，{x≥1zy≥1zxz之間至少有兩條弱連{x≥2z}xz2Pr(x≥2z)≤(4)p(xz 證明(定理4.1(1))首先證明，V中存在被與B0的兩條弱連接（弱連接可以來自B0，也可以來自z）相連的點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)。因為α1/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時，網(wǎng)絡(luò)中存在與B0通過兩條弱連接相連的概率很小。在這個條件下，B0外有節(jié)點被之前復(fù)雜都很慢。這是因為節(jié)點被只能通過（1）僅靠強(qiáng)連接，（2）強(qiáng)連接和弱連接的結(jié)合。不管怎樣都需要一條強(qiáng)連接的幫助才能新的節(jié)點，而強(qiáng)連接的長度不超過2。所以在時間i，被的節(jié)點集合Si最多只能那些距離Si曼哈頓距離不超過2的節(jié)點。因此有很高的概率在復(fù)雜的開始階段，于cnδ時，Si每一步最多把半徑增加2的概率至少為1?O(n?ε)。而僅僅集合B0需要的時間就至少為2

=

4)，因此復(fù)雜的時間以1? )的概率至少 1 對于期望時間的下界，需要更精確的計算才能得到。由于在α<2時，模型的歸一化因子為Z=(?/2)。因此存在一個常數(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的概率 時間至少為

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

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)時，歸一化因子為Z= )。令δBi2(4.3)74

2(

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

O(n5γ

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

c1c

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

5對于復(fù)

l1?2α

∫nx1?2αdx∫

(√n)2?2α

l?2α

∫nx?2αdx∫

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

∑n?1l1?2α+∑

∑√n?1?2 l745 2l

(n1?α

≤7·2cλ ·β

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

令λ

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

的概率，時間大于12)5n1 25cβ這也就是說，復(fù)雜時間的期望為?(n5)。這樣就得到了對于α∈[1/5,1/2)2α的范圍，α12α>3λξ發(fā)生的概率的常數(shù)值，然后就可以給出期望時間的下界。因此本小節(jié)在接下來的部分略過了期望時間的證明，而僅提供高概率下界的證明。21α1/2時，令δ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?ε)，因此可以得知對于α=1/2復(fù)雜時間?(n5c2α(1/21時，令δ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?α+對于α∈(1/2,4/5]，本文取γ=1?ε.因此1?Pr(ξ)≤O(1)+ 4?α+n 5對α∈(1/2,4/5]的Kleinberg小世界網(wǎng)絡(luò)以1?O(n?ε)的概率時間為?(n1?ε)5 至于α∈(4/5,1)時，取γ=2?α?ε?？梢缘玫绞录蔚母怕??Pr(ξ)= O1)=O(n?ε)。此

時間高概率

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

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

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

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

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

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

1c1是一個稍后會定義的常數(shù)。χ0cn1/4?1步，當(dāng)前已的節(jié)點集合到目標(biāo)t的距離每一步最多減少n4。接下來本文會證明當(dāng)Kleinberg小世界模型的參數(shù)α=2時，Pr(χ)是一個很高的概率，10 引理5.1：對于α=2的有向Kleinberg小世界網(wǎng)絡(luò)，給定節(jié)點{s1,s2}和最遠(yuǎn)的目t（|s1t|=√n）c∈(01)2-復(fù)雜路由的過程中有0 Pr(?0≤i<cn4,di?1?di≤n4)≥1?O(logn證明令ui為當(dāng)前已節(jié)點結(jié)合和的節(jié)點中距離目標(biāo)t最近的節(jié)點，即ui=argminx{d(xt)|x∈Si∪E(Si)}didi=|uit|ui?1是集合E(Si?1)∪Si?1與目標(biāo)t曼哈頓距離最小的節(jié)點，而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é)點），同時是si在第i步變成了狀態(tài)導(dǎo)致ui變成狀態(tài)（ui恰好在第i步被，這正是因為si被感染了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的情況因為d(S0td?1，所以是u0∈E(S0引起d?1d0之間的差距，11本文稱那些被集Si?{si}發(fā)出弱連接指向的節(jié)點集合Xi。很顯然根據(jù)上面的第3ui∈Xiidi?1?din4diui一定被si發(fā)出的一條長度至少為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é)點v發(fā)出的弱連接相關(guān)。因此事件{(Xi=C)∧(si=v)}和事件11{?x∈Cv→x|vx|>n4}互相獨立，這就是公式第三行等號的來源。對于節(jié)點x n|vx|n4Pr(v→x|vx|>n4)0；否則的話，Pr(v→x|vx|>n4)≤2p(v,x)≤2Z12·1./4這是公式第四行到第五行“≤”的原因。把這個不等式帶入引理的(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所述，對于α=2的情況，在最初的cn4步中，已節(jié)1 tn4cn4tlog1?O(1)α=2Kleinberglog11 cn4·(1?O(logn))=?(n4)α∈[02)時，類比于引理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ù)雜路由時間的下界對于分散式的路由選擇算法依然成立，這里本文提供了α=2情況的證明。A為所有的確定性分散式路由算法的集合，G為所有可能的基于α=2的leinbg小世界網(wǎng)絡(luò)的集合，πl(wèi)einbgGT(G)A∈AG∈G隨機(jī)算法是在確定性算法上的一個分布，我們只需要證明對于任意的在確定性算法集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。對于任意固定的小世界網(wǎng)絡(luò)G∈G2loga（Markov’sinequalityPr(|X|≥a)≤E|X)）a?G∈G,Pr(T(A,G)≥cn1/4)≤EA～μ(T(A, 1

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