1006大設計翻譯版小世界網絡中復雜傳播和路由

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

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

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

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

3u→vuv歸一化因子Z的值不同，下面列出歸一化因子的值以及對應的概率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時復雜時間的下界，首先需要下面這條引理 引理4.1：在無向Kleinberg小世界網絡中選定三個節(jié)點x,y,z（三個節(jié)點可以相同），節(jié)點z同時與x和y通過邊相連的概率Pr(x z,y≥1 z)不超過14p(x,z)p(y,z 證明最開始假設節(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é)點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小世界網絡，當模型參數α<1/5時，網絡中存在與B0通過兩條弱連接相連的概率很小。在這個條件下，B0外有節(jié)點被之前復雜都很慢。這是因為節(jié)點被只能通過（1）僅靠強連接，（2）強連接和弱連接的結合。不管怎樣都需要一條強連接的幫助才能新的節(jié)點，而強連接的長度不超過2。所以在時間i，被的節(jié)點集合Si最多只能那些距離Si曼哈頓距離不超過2的節(jié)點。因此有很高的概率在復雜的開始階段，于cnδ時，Si每一步最多把半徑增加2的概率至少為1?O(n?ε)。而僅僅集合B0需要的時間就至少為2

=

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

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

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

c1c

)，2-復雜在第

5對于復

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，這是比較小的常數。因此以1?

的概率，時間大于12)5n1 25cβ這也就是說，復雜時間的期望為?(n5)。這樣就得到了對于α∈[1/5,1/2)2α的范圍，α12α>3λξ發(fā)生的概率的常數值，然后就可以給出期望時間的下界。因此本小節(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復雜時間?(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小世界網絡以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-復雜的時間以高概率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?ε)，從而以很高的概率通過復雜整個網所需要的步數至少為?(n )5α(3+∞Zδ0，而不能再設置δ=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依然成立。于是可以得到關于事件ξ概率的不等式1Pr(ξ)≤On3)=O(n?ε)。因此本文可以2-復雜以1α 2 ?(n2α)步才能整個網絡結合關于α所有范圍的結論，本文得到了在α∈[02)α∈(3+∞)時無向Kleinberg小世界網絡中復雜時間的高概率下界和期望時間的下界對于k-復雜，本文可以得到時間上類似的下界。在這種情況下，我們需要調整Kleinberg小世界模型的參數來保證復雜可以通過強連接進行下去。我們取p=q=k，同時初始的節(jié)點為k個網格上連續(xù)的節(jié)點。用上一節(jié)類似的方法我們可以得到k-復雜的結果，在這里我們只給出結論。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有一點需要注意到復雜結果尚不明確的α范圍是(2,2k+2]，這說明隨著k的增0k=1依然成立，k=1的情況對應著簡單傳染病模型，這個時候時間為網絡的直徑。在k=1時，本文的結果在α<2沒有太大意義，但是在α>4時時間有多項式的下界，這和小世界網絡直徑[14]的結果比較類似。k本章主要研究了Kleinberg小世界網絡中復雜傳染病的。首先給出了復雜傳染的主要結論，然后用列出了兩種不同的證明方法，給出了復雜結論的完整理論證明。最后把結論擴展到k-復雜并給出了一般性的結論。Kleinberg小世界網絡中復雜路由的研究，網絡模型的設定Kleinberg最初提出分散式路由時的網絡模型一致[8]。正如和第二章描述的，本章考慮節(jié)點u只能激活自己有向邊指向的節(jié)點（出鄰居）的分散式路由方式。只有當一個節(jié)點u被k個節(jié)點發(fā)出的有向邊指向時，u才會被變成狀態(tài)。對于強連接，仍然認為它們是無向的或者雙向的。在每一個時間步驟，我們僅有知道被節(jié)點和被節(jié)點的強連接和弱連接，而對于未節(jié)點的弱連接算法一無所知。這樣可以在證明中使用延遲選擇原則[23]，和[8]在證明分散式路由中使用的原則一樣。這意味著節(jié)點u的弱連接只有在u被時才被選取，進而算法才知道u的弱連接。最初的節(jié)點kKleinbergpq=kk-復雜路由最終可以目標節(jié)點t。接下來給出復雜路由的主要結論。 我們考慮一個2-復雜路由的任務，起始給定一對相鄰的節(jié)點S0={s1, 0和s2的曼哈頓距離為1）目標是通過分散式路由到達目標節(jié)點t。在本文中，我們0論t距 節(jié)點最遠的情況，也就是s1與t的曼哈頓距離為Θ(√)。從已 節(jié)點集合中選擇哪個節(jié)點來是由路由選擇算法決定的，一個比較特殊的路由選擇策略在經的點選擇離標t哈頓離小的點這被稱貪由算法。本章的結果對于任何分散式路由選擇算法都成立，甚至是隨機算法。下面是有關路由時間的下界的結果。定理5.1：對于任意的分散式路由策略（算法），甚至是隨機的策略，對于任意的比ε>0Kleinberg小世界網絡中，2-復雜路由的路由時間有下面依賴于Kleinberg小世界模型參數α的下界： 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小世界網絡中普通路由策略的的性能，然后把結果推廣到每一步可以多個節(jié)點的復雜路由。首先考慮確定性的路由算法，在本節(jié)的最后，我們會證明本章的下界對于隨機的α=2時路由時間的證明。設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。設事件χ為χ={?0≤i<cn4,

1c1是一個稍后會定義的常數。χ0cn1/4?1步，當前已的節(jié)點集合到目標t的距離每一步最多減少n4。接下來本文會證明當Kleinberg小世界模型的參數α=2時，Pr(χ)是一個很高的概率，10 引理5.1：對于α=2的有向Kleinberg小世界網絡，給定節(jié)點{s1,s2}和最遠的目t（|s1t|=√n）c∈(01)2-復雜路由的過程中有0 Pr(?0≤i<cn4,di?1?di≤n4)≥1?O(logn證明令ui為當前已節(jié)點結合和的節(jié)點中距離目標t最近的節(jié)點，即ui=argminx{d(xt)|x∈Si∪E(Si)}didi=|uit|ui?1是集合E(Si?1)∪Si?1與目標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)導致ui變成狀態(tài)（ui恰好在第i步被，這正是因為si被感染了di|uit|=di|siui|≥|sit|?|uit|di?1?di。所以有了下面的結如果在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。很顯然根據上面的第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由分散式路由的性質可以知道，事件{(Xi=C)∧(si=v)}僅依賴于Si?{si}和集合Sisi}vSi?{si}{?x∈Cv→x|vx|>n4}又僅與固定節(jié)點v發(fā)出的弱連接相關。因此事件{(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然后選取合適的常數cα>2α>Pr(?0≤i<cnα?2ε, –d≤n1+ε)≥1?

1O(n?ε)cnα?2εt有關復雜路由時間的下界對于分散式的路由選擇算法依然成立，這里本文提供了α=2情況的證明。A為所有的確定性分散式路由算法的集合，G為所有可能的基于α=2的leinbg小世界網絡的集合，πl(wèi)einbgGT(G)A∈AG∈G隨機算法是在確定性算法上的一個分布，我們只需要證明對于任意的在確定性算法集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。對于任意固定的小世界網絡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的元素出現的概率至少為1。2Pr(T(A,G)<c

=1.5c2

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