资源描述：
《spreading messages》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、TheoreticalComputerScience410(2009)27142724ContentslistsavailableatScienceDirectTheoreticalComputerSciencejournalhomepage:www.elsevier.com/locate/tcsI,IISpreadingmessagesChing-LuehChanga,Yuh-DauhLyuua,b,aDepartmentofComputerScienceandInformationEngineering,NationalTaiwanUniversi
2、ty,Taipei,TaiwanbDepartmentofFinance,NationalTaiwanUniversity,Taipei,TaiwanarticleinfoabstractArticlehistory:WemodelanetworkinwhichmessagesspreadbyasimpledirectedgraphGD.V;E/Received25September2008andafunctionVV!Nmappingeachv2VtoapositiveintegerlessthanorReceivedinrevisedform23Feb
3、ruary2009equaltotheindegreeofv.ThegraphGrepresentstheindividualsinthenetworkandAccepted19March2009thecommunicationchannelsbetweenthem.Anindividualv2VwillbeconvincedCommunicatedbyD.Pelegofamessagewhenatleast .v/ofitsin-neighborsareconvinced.Supposewearetoconvinceamessagetotheindivi
4、dualsbyfirstconvincingasubsetofindividuals,calledKeywords:theseeds,andthenletthemessagespread.Westudytheminimumnumbermin-seedIrreversibledynamoGlobalcascade.G; /ofseedsneededtoconvinceallindividualsattheend.Inparticular,weproveaTrustpropagationlowerboundonmin-seed.G; /andtheNP-com
5、pletenessofcomputingmin-seed.G; /.Wealsoanalyzethespecialcase,calledthestrict-majorityscenario,whereeachindividualisconvincedofamessagewhenmorethanhalfofitsin-neighborsareconvinced.Forthestrict-majorityscenario,weprovethreeresults.First,weshowthatwithhighprobabilityovertheErd®sRé
6、nyirandomgraphsG.n;p/,.minfn;1=pg/seedsareneededtoconvinceallindividualsattheend.Second,ifGD.V;E/isundirected,thenasetofsuniformlyrandomsamplesfromVconvincesnomorethananexpecteds.2jEjC2jVj/jVjindividualsattheend.Third,inadigraphGD.V;E/withapositiveminimumindegree,onecanfindinpolyn
7、omial(injVj)timeasetofatmost(23/27)jVjseedsconvincingallindividuals.'2009ElsevierB.V.Allrightsreserved.1.IntroductionEachindividualbelievestosomeextentwhatothersbelieve.Acommunicationchannelbetweentwoindividuals,ifitexists,iseitherbidirectionalorunidirectional.Supposethereisanimpo
8、rtantmessagethatwewantallindividu
