Complex Graphs and Networks[2006] .pdf

《Complex Graphs and Networks[2006] .pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ComplexGraphsandNetworksFanChungUniversityofCaliforniaatSanDiegoLaJolla,California92093fan@ucsd.eduLinyuanLuUniversityofSouthCarolina,Columbia,SouthCarolina29208lu@math.sc.eduContentsPrefaceviiChapter1.GraphTheoryintheInformationAge11.1.Introduction11.2.Basicdenit

2、ions31.3.Degreesequencesandthepowerlaw61.4.Historyofthepowerlaw81.5.Examplesofpowerlawgraphs101.6.Anoutlineofthebook17Chapter2.OldandNewConcentrationInequalities212.1.Thebinomialdistributionanditsasymptoticbehavior212.2.GeneralChernoinequalities252.3.Moreconcentra

3、tioninequalities302.4.Aconcentrationinequalitywithalargeerrorestimate332.5.MartingalesandAzuma'sinequality352.6.Generalmartingaleinequalities382.7.SupermartingalesandSubmartingales412.8.Thedecisiontreeandrelaxedconcentrationinequalities46Chapter3.AGenerativeModel

4、t

5、hePreferentialAttachmentScheme553.1.Basicstepsofthepreferentialattachmentscheme553.2.Analyzingthepreferentialattachmentmodel563.3.Ausefullemmaforrigorousproofs593.4.Theperilofheuristicsviaanexampleofballs-and-bins603.5.Scale-freenetworks623.6.Thesharpconcentrationo

6、fpreferentialattachmentscheme643.7.Modelsfordirectedgraphs70Chapter4.DuplicationModelsforBiologicalNetworks754.1.Biologicalnetworks754.2.Theduplicationmodel764.3.Expecteddegreesofarandomgraphintheduplicationmodel774.4.Theconvergenceoftheexpecteddegrees794.5.Thegene

7、ratingfunctionsfortheexpecteddegrees834.6.Twoconcentrationresultsfortheduplicationmodel844.7.Powerlawdistributionofgeneralizedduplicationmodels89Chapter5.RandomGraphswithGivenExpectedDegrees915.1.TheErd}os-Renyimodel915.2.ThediameterofGn;p95iiiivCONTENTS5.3.Agener

8、alrandomgraphmodel975.4.Size,volumeandhigherordervolumes975.5.BasicpropertiesofG(w)1005.6.Neighborhoodexpansioninrandomgraphs1035.7.Arandompowerlawgraphmodel1075.8.Actualversusexpecteddegreesequence109Chapter6.TheRiseoftheGiantComponent1136.1.Nogiantcomponentifw<1?

9、1146.2.Isthereagiantcomponentif~w>1?1156.3.Nogiantcomponentif~w<1?1166.4.Existenceanduniquenessofthegiantcomponent1176.5.Alemmaonneighborhoodgrow