[29]Maximizing the spread of influence through a social network

《[29]Maximizing the spread of influence through a social network》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、MaximizingtheSpreadofInfluencethroughaSocialNetworkyzDavidKempeJonKleinbergEv´aTardosDept.ofComputerScienceDept.ofComputerScienceDept.ofComputerScienceCornellUniversity,IthacaNYCornellUniversity,IthacaNYCornellUniversity,IthacaNYkempe@cs.cornell.edukleinber@cs.cornell.edueva@cs.cor

2、nell.eduABSTRACTKeywordsModelsfortheprocessesbywhichideasandinfluencepropagateapproximationalgorithms,socialnetworks,viralmarketing,throughasocialnetworkhavebeenstudiedinanumberofdo-diffusionofinnovationsmains,includingthediffusionofmedicalandtechnologicalinnova-tions,thesuddenandwi

3、despreadadoptionofvariousstrategiesin1.INTRODUCTIONgame-theoreticsettings,andtheeffectsof“wordofmouth”intheAsocialnetwork—thegraphofrelationshipsandinteractionspromotionofnewproducts.Recently,motivatedbythedesignofwithinagroupofindividuals—playsafundamentalroleasaviralmarketingstra

4、tegies,DomingosandRichardsonposedafun-mediumforthespreadofinformation,ideas,andinfluenceamongdamentalalgorithmicproblemforsuchsocialnetworkprocesses:itsmembers.Anideaorinnovationwillappear—forexample,theifwecantrytoconvinceasubsetofindividualstoadoptanewuseofcellphonesamongcollegest

5、udents,theadoptionofanewproductorinnovation,andthegoalistotriggeralargecascadeofdrugwithinthemedicalprofession,ortheriseofapoliticalmove-furtheradoptions,whichsetofindividualsshouldwetarget?mentinanunstablesociety—anditcaneitherdieoutquicklyWeconsiderthisprobleminseveralofthemostwi

6、delystudiedormakesignificantinroadsintothepopulation.Ifwewanttoun-modelsinsocialnetworkanalysis.Theoptimizationproblemofderstandtheextenttowhichsuchideasareadopted,itcanbeim-selectingthemostinfluentialnodesisNP-hardhere,andwepro-portanttounderstandhowthedynamicsofadoptionarelikelytov

7、idethefirstprovableapproximationguaranteesforefficientalgo-unfoldwithintheunderlyingsocialnetwork:theextenttowhichrithms.Usingananalysisframeworkbasedonsubmodularfunc-peoplearelikelytobeaffectedbydecisionsoftheirfriendsandtions,weshowthatanaturalgreedystrategyobtainsasolutionthatcoll

8、eagues,ortheextenttowhich“