资源描述：
《book2010-Structure and Dynamics of Informatio》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、StructureandDynamicsofInformationinNetworksDavidKempeDepartmentofComputerScienceUniversityofSouthernCaliforniaSeptember24,20102PrefaceThepresentnotesarederivedfromacoursetaughtattheUniversityofSouthernCalifornia.Thefocusofthecourseisonthemathematicalandalgorithmictheo
2、ryunderpinningtheconnectionsbetweennetworksandinformation.Theseconnectionstaketwopredominantforms:•Networkstructureitselfencodesalotofinformation.Forinstance,friendshipsbetweenindividualsletusdrawinferencesaboutsharedinterestsorotherattributes(location,gender,etc.).Si
3、milarly,hyperlinksbetweendocumentsindicatesimilartopics,butcanalsobeinterestedasendorsements,andthushintatquality.Thelistofscenariosinwhichnetworkstructurehelpsusinterpretinformationaboutindividualnodescontinuesbeyondthislist,andwillbeexploredinmoredetailthroughoutthe
4、senotes.•Networksalsoplayacrucialroleindisseminatingorgatheringinformation.Thisappliesbothtosocialnetworks,inwhichcommunicationbetweenindividualshappensnaturally,andcomputernetworks,whicharedesignedexplicitlytofacilitatetheexchangeofinformationanddistributedcomputatio
5、ns.Wewilldrawanalogiesbetweenthetwotypesofnetworks,andinvestigatethemathematicalunder-pinningsofthediffusionofinformationovernetworksinthelaterchaptersofthesenotes.Thesenotesaredesignedtoaccompanyaone-semestergraduate-levelcourseincomputerscience.Weassumeasolidmathemat
6、icalbackground,andfamiliaritywithbasicalgorithmictechniques,includingflowsandcuts;thenecessarytopicsarecoveredintextbooksbyKleinbergandTardos[217]andCormenetal.[99].Inparticular,wewillassumefamiliaritywithLinearProgramming(see,e.g.,[86,196])andtheconceptofapproximation
7、algorithms[175,321],aswellaswithbasicnotionsofrandomizationinalgorithms[253,261].Abasicunderstandingofgraphtheoryisalsorequired(see,e.g.,[49,114]).0.1FurtherReadingSeveralrecentbookscovertopicsoverlappingwiththecontentofthesenotes.“TheStructureandDynamicsofNetworks”[2
8、72]byNewman,Barab´asiandWattscollectsanumberofrecentpapersonnetworkanalysisandepidemicprocessesonnetworks,predominantlywitha
