资源描述：
《书籍 2013 Random Graphs and Complex Networks》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、RandomGraphsandComplexNetworksRemcovanderHofstadDepartmentofMathematicsandComputerScienceEindhovenUniversityofTechnologyP.O.Box5135600MBEindhoven,TheNetherlandsrhofstad@win.tue.nlMarch20,2013PrefaceTheselecturenotesareintendedtobeusedformastercourses,wherethestudent
2、shavealimitedpriorknowledgeofspecialtopicsinprobability.Therefore,wehaveincludedmanyofthepreliminaries,suchasconvergenceofrandomvariables,probabilisticbounds,coupling,martingalesandbranchingprocesses.Thesenotesareaimedtobeself-contained,andtogivethereadersaninsighti
3、nthehistoryofthe eldofrandomgraphs.The eldofrandomgraphswasstartedin1959-1960byErd}osandRenyi,see[109,110,111,112].At rst,thestudyofrandomgraphswasusedtoprovedeterministicpropertiesofgraphs.Forexample,ifwecanshowthatarandomgraphhaswithapositiveprobabilityacertainpr
4、operty,thenagraphmustexistwiththisproperty.Themethodofprovingdeterministicstatementsusingprobabilisticargumentsiscalledtheprobabilisticmethod,andgoesbackalongway.SeeamongotherstheprefaceofastandardworkinrandomgraphsbyBollobas[52],ortheworkdevotedtoitTheProbabilisti
5、cMethod[14].Erd}oswasoneofthe rsttousethismethod,seee.g.,[107],whereitwasshownthattheRamseyk=2numberR(k)isatleast2.TheRamseynumberR(k)isthevaluenforwhichanygraphofsizeatleastnissuchthateitheritselforitscomplementcontainsacompletegraphofk=2sizeatleastk.Erd}osin[107]s
6、howsthatforn2,thefractionofgraphsforwhichthegraphoritscomplementcontainsacompletegraphofsizekisboundedby1=2,sothatk=2theremustbegraphsofsizen2forwhichthegraphnoritscomplementcontainsacompletegraphofsizek.TheinitialworkbyErd}osandRenyionrandomgraphshasincitedagrea
7、tamountofworkonthe eld.Seethestandardreferencesonthesubject[52]and[154]forthestateoftheart.Particularly[110]isahighlyimpressivepaper.Init,arathercompletepictureisgivenofthevariousphasetransitionsthatoccurontheErd}os-Renyirandomgraph.Aninterestingquoteappearingin[11
8、0,Page2-3]isthefollowing:Itseemstousworthwhiletoconsiderbesidesgraphsalsomorecomplexstruc-turesfromthesamepointofview,i.e.toinvestigateth
