genrecnnchina

1EarlywarninganalysisforsocialdiffusioneventsRichardColbaugh1andKristinGlass21AnalyticsandCryptographyDepartment,SandiaNationalLaboratories,Albuquerque,USA2CyberResearchandEducationDepartment,SandiaNationalLaboratories,Albuquerque,USARC:colbaugh@comcast.
netKG:kglass609@comcast.
net(correspondingauthor)Abstract--Thereisconsiderableinterestindevelopingpredictivecapabilitiesforsocialdiffusionprocesses,forinstancetopermitearlyidentificationofemergingcontentioussituations,rapiddetectionofdiseaseoutbreaks,oraccurateforecastingoftheultimatereachofpotentially"viral"ideasorbehaviors.
Thispaperproposesanewap-proachtothispredictiveanalyticsproblem,inwhichanalysisofmeso-scalenetworkdynamicsisleveragedtogen-erateusefulpredictionsforcomplexsocialphenomena.
Webeginbyderivingastochastichybriddynamicalsystems(S-HDS)modelfordiffusionprocessestakingplaceoversocialnetworkswithrealistictopologies;thismodelingapproachisinspiredbyrecentworkinbiologydemonstratingthatS-HDSofferausefulmathematicalformalismwithwhichtorepresentcomplex,multi-scalebiologicalnetworkdynamics.
WethenperformformalstochasticreachabilityanalysiswiththisS-HDSmodelandconcludethattheoutcomesofsocialdiffusionprocessesmayde-pendcruciallyuponthewaytheearlydynamicsoftheprocessinteractswiththeunderlyingnetwork'scommunitystructureandcore-peripherystructure.
Thistheoreticalfindingprovidesthefoundationsfordevelopingamachinelearningalgorithmthatenablesaccurateearlywarninganalysisforsocialdiffusionevents.
Theutilityofthewarningalgorithm,andthepowerofnetwork-basedpredictivemetrics,aredemonstratedthroughanempiricalinvestigationofthepropagationofpolitical"memes"oversocialmedianetworks.
Additionally,weillustratethepotentialoftheapproachforsecurityinformaticsapplicationsthroughcasestudiesinvolvingearlywarninganalysisoflarge-scaleprotestseventsandpolitically-motivatedcyberattacks.
Keywords:socialdynamics,predictiveanalysis,earlywarning,protestandmobilization,cybersecurity,securityinformatics.
1.
IntroductionUnderstandingthewayinformation,behaviors,innovations,anddiseasespropagateoversocialnetworksisofgreatimportanceinawidevarietyofdomains[e.
g.
,1-4],includingnationalsecurity[e.
g.
,5-13].
Ofparticularinterestarepredictivecapabilitiesforsocialdiffusion,forinstancetoenableearlywarningcon-cerningtheemergenceofaviolentconflictoroutbreakofanepidemic.
Asaconsequence,vastresourcesaredevotedtothetaskofpredictingtheoutcomesofdiffusionprocesses,butthequalityofsuchpredic-tionsisoftenpoor.
Itistemptingtoconcludethattheproblemisoneofinsufficientinformation.
Clearlydiffusionphenomenawhich"goviral"arequalitativelydifferentfromthosethatdon'tortheywouldn'tbesodominant,theconventionalwisdomgoes,soinordertomakegoodpredictionswemustcollectenoughdatatoallowthesecrucialdifferencestobeidentified.
Recentresearchcallsintoquestionthisintuitivelyplausiblepremiseand,indeed,indicatesthatintui-tioncanbeanunreliableguidetoconstructingsuccessfulpredictionmethods.
Forexample,studiesofthepredictabilityofpopularcultureindicatethattheintrinsicattributescommonlybelievedtobeimportantwhenassessingthelikelihoodofadoptionofculturalproducts,suchasthequalityoftheproductitself,donotpossessmuchpredictivepower[14-16].
Thisresearchoffersevidencethat,whenindividualsarein-fluencedbytheactionsofothers,itmaynotbepossibletoobtainreliablepredictionsusingmethodswhichfocusonintrinsicsalone;instead,itmaybenecessarytoincorporateaspectsofsocialinfluenceintothepredictionprocess.
Veryrecentlyahandfulofinvestigationshaveshownthevalueofconsidering2evensimpleandindirectmeasuresofsocialinfluence,suchasearlysocialmedia"buzz",whenformingpredictions.
Thisworkhasproducedusefulpredictionalgorithmsforanarrayofsocialphenomena,in-cludingmarkets[16-21],politicalandsocialmovements[17,22],mobilizationandprotestbehavior[23,24],epidemics[17,25],socialmediadynamics[26,27],andtheevolutionofcyberthreats[28].
Recognizingtheimportanceofaccountingforsocialinfluence,thispaperproposesapredictivemethodologywhichexplicitlyconsidersthewayindividualsinfluenceoneanotherthroughtheirsocialnetworks.
Itisexpectedthatpredictionalgorithmswhicharebased,inpart,onnetworkdynamicsmetricswilloutperformexistingmethodsandbeapplicabletoawiderrangeofdiffusionsystems.
Webeginbydevelopingastochastichybriddynamicalsystems(S-HDS)modelfordiffusionprocessestakingplaceoversocialnetworkswithrealistictopologies.
Thismodelingapproachisinspiredbyrecentworkinbiol-ogydemonstratingthatS-HDSofferausefulmathematicalformalismwithwhichtorepresentmulti-scalebiologicalnetworkdynamics[29-33].
AnS-HDSisafeedbackinterconnectionofadiscrete-statestochas-ticprocess,suchasaMarkovchain,withafamilyofcontinuous-statestochasticdynamicalsystems[34].
Combiningdiscreteandcontinuousdynamicsinthiswayprovidesarigorous,expressive,andcomputa-tionally-tractableframeworkformodelingthedynamicsofthecomplex,highly-evolvednetworksthatareubiquitousinbiologicalsystems[35],andweshowinthispaperthattheS-HDSframeworkisalsowell-suitedtothetaskofmodelingthenetworkdynamicswhichunderliesocialdiffusion.
WiththeS-HDSmodelinhand,wethenperformformalstochasticreachabilityanalysisandcon-cludethattheoutcomesofsocialdiffusionprocessesmaydependcruciallyuponthewaytheearlydy-namicsoftheprocesspropagateswithrespecttotheunderlyingnetwork's1.
)communitystructure,thatis,denselyconnectedgroupingsofindividualswhichhaveonlyrelativelyfewlinkstoothergroups[36],and2.
)core-peripherystructure,reflectingthepresenceofasmallgroupof"core"individualsthataredenselyconnectedtoeachotherandarealsoclosetotheremainderofthenetwork[36].
Thistheoreticalfindingleadstotheidentificationofnovelmetricsforthecommunityandcore-peripherydynamicswhichshouldbeusefulearlyindicatorsofwhichdiffusioneventswillpropagatewidely,ultimatelyaffectingasubstantialportionofthepopulationofinterest,andwhichwillnot.
Predictionisaccomplishedwithamachinelearningalgorithm[37]whichisbased,inpart,onthesenetworkdynamicsmetrics.
Thepapermakesthreemaincontributions.
First,wepresentanewS-HDS-basedframeworkformodelingsocialdiffusiononnetworksofreal-worldscaleandcomplexity,enablingthesedynamicstobeappropriatelyrepresentedasmulti-scalephenomena.
Second,weformulatepredictiveanalysisproblemsasquestionsconcerningthereachabilityofdiffusionevents,andpresentanovel"altitudefunction"meth-odforassessingreachabilitywithoutsimulatingsystemtrajectories.
Thealtitudefunctiontechniqueisbothmathematicallyrigorousandcomputationallytractable,therebypermittingthederivationofprova-bly-correctassessmentsforcomplex,large-scalesystems.
Third,theS-HDSmodelandaltitudefunctionanalyticsareusedtocharacterizetheimportanceofmeso-scalenetworkfeatures,specificallynetworkcommunityandcore-peripherystructures,forunderstandingdiffusionprocessesandpredictingtheirfates.
Thischaracterization,inturn,formsthefoundationfordevelopinganewmachinelearning-basedclassifi-cationalgorithmwhichemploysthesenetworkdynamicsfeaturesforaccurateearlywarninganalysis.
Additionally,weevaluatetheefficacyofthisearlywarningalgorithmthroughthreeempiricalcasestud-iesinvestigating:1.
)thepropagationofpolitical"memes"[38]oversocialmedianetworks,2.
)warninganalysisforlarge-scalemobilizationandprotestevents,and3.
)earlywarningforpolitically-motivatedcyberattacks.
Theseempiricalstudiesillustratetheeffectivenessoftheproposedearlywarningmethod-ologyanddemonstratethesignificantpredictivepowerofmeso-scalenetworkmetricsforsocialdiffusion3processes.
Moreover,theresultsindicatethattheproposedalgorithmprovidesareadily-implementableWeb-basedtoolforearlywarninganalysisforimportantclassesofsecurity-relevantdiffusionevents.
2.
EarlyWarningMethodologyThissectionbeginsbydefiningtheclassofearlywarningproblemsofinterest,thenpresentsabrief,in-tuitivesummaryoftheproposedsocialdiffusionmodelingandpredictiveanalysisprocedure,andfinallydescribestheearlywarningindicatorsidentifiedthroughthisanalyticprocedureandthewarningalgo-rithmthatisderivedbasedontheseresults.
AdetailedmathematicalpresentationofthemodelingandanalysismethodsisprovidedinAppendicesOneandTwo.
2.
1ProblemFormulationTheobjectiveofthispaperistodevelopascientifically-rigorous,practically-implementablemethodologyforperformingearlywarninganalysisforsocialdiffusionevents.
Roughlyspeaking,wesupposethatsome"triggeringevent"hastakenplaceorcontentiousissueisemerging,andwewishtodetermine,asearlyaspossible,whetherthiseventorissuewillultimatelygeneratealarge,self-sustainingreaction,in-volvingthediffusionofdiscussionsandactionsthroughasubstantialsegmentofapopulation,orwillinsteadquicklydissipate.
Anillustrativeexampleofthebasicideaisprovidedbythecontrastingreactionsto1.
)thepublicationinSeptember2005ofcartoonsdepictingMohammadintheDanishnewspaperJyllands-Posten,and2.
)thelecturegivenbyPopeBenedictXVIinSeptember2006quotingcontroversialmaterialconcerningIslam.
Whileeacheventappearedattheoutsettohavethepotentialtotriggersignifi-cantprotests,the"Danishcartoons"incidentultimatelyledtosubstantialMuslimmobilization,includingmassiveprotestsandconsiderableviolence,whileoutragetriggeredbythepopelecturequicklysubsidedwithessentiallynoviolence.
Itwouldobviouslybeveryusefultohavethecapabilitytodistinguishthesetwotypesofreactionasearlyintheeventlifecycleaspossible.
Inordertostatetheearlywarningproblemmoreprecisely,wemakeafewassumptions:Wesupposethatthetriggeringeventoremergingsituationisgiven.
Notethatthisisoftenthecaseinnationalsecuritysettings,andthatadditionallythereexisttechniquesfordiscoveringsucheventsorissuesinanautomatedorsemi-automatedmanner[e.
g.
,24,27].
Itisassumedthatdataareavailablewhichprovideaviewoftheearlyreactionofarelevantpopula-tiontothetriggerorissueofinterest.
Thesedatacanbeonlyindirectlyrelatedtotheevent;forexam-ple,inthispapertheprimarydatasourceissocialmediadiscussions(e.
g.
,blogposts)whiletheeventsofinterestare"real-world"activitiessuchasprotests.
Itisexpectedthatthe"customer"fortheanalysisprovidesatleastqualitativedefinitionsofthepopu-lationofinterestandthescaleofreactionforwhichawarningisdesired.
Thus,forinstance,intheexampleabove,itmightbeofinteresttoanticipateMuslimreactiontothetriggeringincident,andtoobtainawarningalertifthereactionislikelytoeventuallyincludeself-sustaining,violentprotests.
Weformulatetheearlywarningproblemasaclassificationtask.
Morespecifically,givenatrigger-ingincident,oneormoreinformationsourceswhichreflect(perhapsindirectly)thereactiontothistriggerbyapopulationofinterest(e.
g.
,socialmediadiscussions,intelligencereporting),andadefinitionforwhatconstitutesan"alarming"reaction,thegoalistodesignaclassifierwhichaccuratelypredicts,asearlyaspossible,whetherornotreactiontotheeventwillultimatelybecomealarming.
NotethatamoremathematicallyprecisestatementofthiswarningproblemisgiveninAppendixTwo.
Observethatthis4typeofwarninganalysisisbothimportantinapplicationsand"easier"toaccomplishthanmorestandardpredictionorforecastinggoals.
Consider,asafamiliarnon-securityexample,thecaseofmoviesuccess.
Itisshownin[14-16]thatitislikelytobeimpossibletopredictmovierevenues,evenveryroughly,basedontheintrinsicinformationavailableconcerningthemovieexante(e.
g.
,personnel,genre,criticreviews).
However,wehavedemonstratedthatitispossibletoidentifyearlyindicatorsofmoviesuccess,suchastemporalpatternsinpre-release"buzz",andtousetheseindicatorstoaccuratelypredictultimateboxof-ficerevenues[39].
Recentresearchindicatesthatthisresultholdsmoregenerally,sothatitmaybemorescientifically-sensibleinmanydomainstopursueearlywarningratherthanexantepredictiongoals[14-28].
2.
2S-HDSSocialDiffusionModelInsocialdiffusion,individualsareaffectedbywhatothersdo.
Thisiseasytovisualizeinthecaseofdis-easetransmission,withinfectionsbeingpassedfrompersontoperson.
Information,innovations,behav-iors,andsooncanalsopropagatethroughapopulation,asindividualsbecomeawareofanewpieceofinformationoranactivityandarepersuadedofitsrelevanceandutilitythroughtheirsocialandinfor-mationnetworks.
Thedynamicsofsocialdiffusioncanthereforedependuponthetopologicalfeaturesofthepertinentnetworks,suchasthepresenceofhighlyconnectedblogsinasocialmedianetwork(see,e.
g.
,[4]).
Indeed,socialscientistshavedevelopedextensivetheoriesexplainingtheroleofsocialnet-worksinthedynamicsofsocialdiffusionandmobilization(seethebooks[2-4]andthereferencesthere-in,andalsoAppendixOne,fordiscussionsofthiswork).
Thisdependencesuggeststhat,inordertoun-derstandthepredictabilityofsocialdiffusionphenomenaandinparticulartoidentifyfeatureswhichpos-sesspredictivepower,itisnecessarytoconducttheanalysisusingsocialandinformationnetworkmodelswithrealistictopologies.
Thesocialdiffusionmodelsexaminedinthisstudypossessnetworkswiththreetopologicalproper-tiesthatareubiquitousinreal-worldsocialandinformationnetworksandwhichhavethepotentialtoim-pactdiffusiondynamics[36]:transitivity–thepropertythatthenetworkneighborsofagivenindividualhaveaheightenedproba-bilityofbeingconnectedtooneanother;communitystructure–thepresenceofdenselyconnectedgroupingsofindividualswhichhaveonlyrelativelyfewlinkstoothergroups;core-peripherystructure–thepresenceofasmallgroupof"core"individualswhicharedenselycon-nectedtoeachotherandarealsoclosetotheotherindividualsinthenetwork.
Additionally,wepermitournetworkmodelstopossessright-skeweddegreedistributions,inwhichmostindividualshaveonlyafewnetworkneighborswhileafewindividualshaveagreatmanyneigh-bors,assuchnetworksarecommoninonlinesettings.
Themannerinwhichthecommunitiesandthecore-peripheryarearrangedwillbesaidtodefinethenetwork'smeso-scalestructure.
Forconvenienceofexposition,thesubsetsofindividualsspecifiedbyapartitioningofthenetworkintocommunitiesandintoacoreandperipherywillsometimesbereferredtoasthepartitionelements,andthecollectionofthese(communityandcore-periphery)subsetswillbecalledthenetworkpartition.
Inordertodealeffectivelywithnetworkspossessingrealistictopologies,andinparticulartorepre-sentandanalyzethewaysocialdynamicsisaffectedbythemeso-scalestructure,wemodelsocialdiffu-sioninamannerwhichexplicitlyseparatestheindividual,or"micro",dynamicsfromthecollectivedy-namics.
Morespecifically,weadoptamulti-scalemodelingframeworkconsistingofthreenetworkscales:5amicro-scale,formodelingthebehaviorofindividuals;ameso-scale,whichrepresentstheinteractiondynamicsofindividualswithinthesamenetworkparti-tionelement(communityorcore/periphery);amacro-scale,whichcharacterizestheinteractionbetweenpartitionelements.
Themicro-scalequantifiesthewayindividualscombinetheirowninherentpreferencesorattributeswiththeinfluencesofotherstoarriveattheirchosencoursesofaction.
ItisshowninAppendixOnethatseparatingthemicro-scaledynamicsfromthemeso-andmacro-scaleactivitypermitsthedependenceofthisdecision-makingprocessonthesocialnetworktobecharacterizedinasurprisinglystraightforwardway.
Themeso-andmacro-scalecomponentsoftheproposedmodelingframeworktogetherquantifythewaythedecision-makingprocessesofindividualsinteracttoproducecollectivebehavioratthepopulationlevel.
Theroleofthemeso-scalemodelistoquantifyandilluminatethemannerinwhichbehaviorswith-ineachnetworkpartitionelement(communities,coreorperiphery),whilethemacro-scalemodelcapturestheinteractionsbetweentheseelements.
Theprimaryassumptionsarethatinteractionsbetweenindividu-alsbelongingtothesamenetworkpartitionelementcanbemodeledmoresimplythanthosebetweenin-dividualsfromdistinctpartitionelements,andthatthelatterinteractionsareconstrainedbythe"meta-network"whichdefinesthedependenciesbetweenthepartitionelements.
Thisperspectiveoffersanumberofadvantages.
Forexample,atthemicro-scaleitispossibletouni-fybehaviorswhichappeardifferentphenomenologicallybutactuallypossessequivalentdynamics.
WeshowinAppendixOnethatthesocialdynamicsassociatedwithclassical"utility-maximizing"behaviorandthosearisingfromindividualsattemptingtoinferinformationbyobservingtheactionsofotherscanberepresentedwiththesamemicro-scalemodel.
Additionally,separatingtheindividualandcollectivedynamicssupportsefficientandflexiblemodelbuildingandsimplifiestheprocessofestimatingmodelcomponentsfromempiricaldata[39].
Dividingthecollectivedynamicsintomeso-andmacro-scalesalsoprovidesamathematically-tractable,sociologically-sensiblemeansofrepresentingcomplexsocialnet-workdynamics.
Forinstance,becausenetworkcommunitiesaretopologicalstructurescorrespondingtolocalizedsocialsettingsintherealworld,determinedbyworkplace,family,physicalneighborhood,andsoon,itisnaturalbothmathematicallyandsociologicallytomodeltheinteractionsofindividualswithincommunitiesasqualitativelydifferent(e.
g.
,morefrequentandhomogeneous)thanthosebetweencom-munities.
Developingamathematically-rigorous,expressive,scalable,andcomputationally-tractableframe-workwithinwhichmulti-scalesocialnetworkdiffusionmodelscanbeconstructedis,ofcourse,achal-lengingundertaking.
Recentworkinsystemsbiologyhasdemonstratedthatstochastichybriddynamicalsystems(S-HDS)provideausefulmathematicalformalismwithwhichtorepresentbiologicalnetworkdynamicsthatpossessmultipletemporalandspatialscales[29-33].
AnS-HDSisafeedbackinterconnec-tionofadiscrete-statestochasticprocess,suchasaMarkovchain,withafamilyofcontinuous-statesto-chasticdynamicalsystems[34].
Thusthediscretesystemdynamicsdependsonthecontinuoussystemstate,perhapsbecausedifferentregionsofthecontinuousstatespaceareassociatedwithdifferentmatri-cesofMarkovstatetransitionprobabilities,andtheparticularcontinuoussystemwhichis"active"atagiventimedependsonthediscretesystemstate.
Combiningdiscreteandcontinuousdynamicsinthiswayprovidesaneffectiveframeworkformodelingthedynamicsofthecomplex,highly-evolvednetworksthatareubiquitousinbiologicalsystems[35].
Forexample,therigorousyettractableintegrationofswitchingbehaviorwithcontinuousdynamicsenabledbytheS-HDSmodelallowsaccurateandefficientrepresen-tationofbiologicalphenomenaevolvingoverdisparatetemporalscales[29-31]andspatialscales[32,33].
6Inspiredbythiswork,inthispaperweapplytheS-HDSframeworktosocialdiffusiondynamicsevolvingovermultiplenetworkscales.
AppendixOneprovidesadetaileddiscussionoftheproposedS-HDSsocialdiffusionmodelanddemonstratestheeffectivenesswithwhichthisformalismcapturesmulti-scalenetworkdynamics.
AsanintuitiveillustrationofthewayS-HDSenablecomplexnetworkphenom-enatobeefficientlyrepresented,considerthetaskofmodelingdiffusiononanetworkthatpossessescommunitystructure.
AsshowninFigure1,thisdiffusionconsistsoftwocomponents:1.
)intra-communitydynamics,involvingfrequentinteractionsbetweenindividualswithinthesamecommunityandtheresultinggradualchangeintheconcentrationsof"infected"(red)individuals,and2.
)inter-communitydynamics,inwhichthe"infection"jumpsfromonecommunitytoanother,forinstancebe-causeaninfectedindividual"visits"anewcommunity.
S-HDSmodelsofferanaturalframeworkforrep-resentingthesedynamics,withtheS-HDScontinuoussystemmodelingtheintra-communitydynamics(e.
g.
,viastochasticdifferentialequations),thediscretesystemcapturingtheinter-communitydynamics(e.
g.
,usingaMarkovchain),andtheinterplaybetweenthesedynamicsbeingrepresentedbytheS-HDSfeedbackstructure.
AdetaileddescriptionofthemannerinwhichS-HDSmodelscanbeusedtocapturesocialdiffusiononnetworkswithrealistictopologiesisgiveninAppendixOne.
Figure1.
ModelingdiffusiononnetworkswithcommunitystructureviaS-HDS.
Thecartoonattopleftdepictsanetworkwiththreecommunities.
Thecartoonatrightillustratesdiffusionwithinacom-munitykandbetweencommunitiesiandj.
TheschematicatbottomleftshowsthebasicS-HDSfeed-backstructure;thediscreteandcontinuoussystemsinthisframeworkmodeltheinter-communityandintra-communitydiffusiondynamics,respectively.
discretesystemcontinuoussysteminputsinputsmodeoutputsdiscretesystemcontinuoussysteminputsinputsmodeoutputsdiscretesystemcontinuoussysteminputsinputsmodeoutputsinter-communitydynamicsintra-communitydynamicsijkinter-communitydynamicsinter-communitydynamicsinter-communitydynamicsintra-communitydynamicsintra-communitydynamicsijkijk72.
3PredictabilityAssessmentOnehallmarkofsocialdiffusionprocessesistheirostensibleunpredictability:phenomenafromhitsandflopsinculturalmarketstofinancialsystembubblesandcrashestopoliticalupheavalsappearresistanttopredictiveanalysis(althoughthereisnoshortageofexpostexplanationsfortheiroccurrence!
).
Itisnotdifficulttogainanintuitiveunderstandingofthebasisforthisunpredictability.
Individualpreferencesandsusceptibilitiesaremappedtocollectiveoutcomesthroughanintricate,dynamicalprocessinwhichpeoplereactindividuallytoanenvironmentconsistinglargelyofotherswhoarereactinglikewise.
Be-causeofthisfeedbackdynamics,thecollectiveoutcomecanbequitedifferentfromoneimpliedbyasimpleaggregationofindividualpreferences;standardpredictionmethods,whichtypicallyarebasedonsuchaggregationideas,donotcapturethesedynamicsandthereforeareoftenunsuccessful.
Thissectionprovidesabrief,intuitiveintroductiontoasystematicapproachtoassessingthepredict-abilityofsocialdiffusionprocessesandidentifyingprocessobservableswhichhaveexploitablepredictivepower(seeAppendixTwo,andalso[17,39],forthemathematicaldetails).
Considerasimplemodelforproductadoption,inwhichindividualscombinetheirownpreferencesandopinionsregardingtheavaila-bleoptionswiththeirobservationsoftheactionsofotherstoarriveattheirdecisionsaboutwhichproducttoadopt.
Asdiscussedabove,itcanbequitedifficulttodeterminewhichcharacteristicsoftheprocessbywhichadoptiondecisionspropagate,ifany,arepredictiveofthingslikethespeedorultimatereachofthepropagation[15-17].
InAppendixTwoweproposeamathematicallyrigorousapproachtopredictabilityassessmentwhich,amongotherthings,permitsidentificationoffeaturesofsocialdynamicswhichshouldhavepredictivepower.
Wenowsummarizethisassessmentmethodology.
Thebasicideabehindtheproposedapproachtopredictabilityanalysisissimpleandnatural:weas-sesspredictabilitybyansweringquestionsaboutthereachabilityofdiffusionevents.
Toobtainamathe-maticalformulationofthisstrategy,thebehavioraboutwhichpredictionsaretobemadeisusedtodefinethesystemstatespacesubsetsofinterest(SSI),whiletheparticularsetofcandidatemeasurablesunderconsiderationallowsidentificationofthecandidatestartingset(CSS),thatis,thesetofstatesandsystemparametervalueswhichrepresentinitializationsthatareconsistentwith,andequivalentunder,thepre-sumedobservationalcapability.
Asasimpleexample,consideranonlinemarketwithtwoproducts,AandB,andsupposethesystemstatevariablesconsistofthecurrentmarketshareforA,ms(A),andtherateofchangeofthismarketshare,r(A)(ms(B)andr(B)arenotindependentstatevariablesbecausems(A)+ms(B)=1andr(A)+r(B)=0);lettheparametersbetheadvertisingbudgetsfortheproducts,bud(A)andbud(B).
TheproducerofitemAmightfinditusefultodefinetheSSItoreflectmarketsharedominancebyA,thatis,thesubsetofthetwo-dimensionalstatespacewherems(A)exceedsaspecifiedthreshold(andr(A)cantakeanyvalue).
IfonlymarketshareandadvertisingbudgetscanbemeasuredthentheCSSistheone-dimensionalsubsetofstate-parameterspaceconsistingoftheinitialmagnitudesforms(A),bud(A),andbud(B),withr(A)unspecified(theone-dimensional"uncertainty"intheCSSreflectsthefactthatr(A)isnotmeasurable).
Roughlyspeaking,theproposedapproachtopredictabilityassessmentinvolvesdetermininghowprobableitistoreachtheSSIfromaCSSanddecidingifthesereachabilitypropertiesarecompatiblewiththepredictiongoals.
Ifasystem'sreachabilitycharacteristicsareincompatiblewiththegivenpredic-tionquestion–if,say,"hit"and"flop"statesintheonlinemarketexamplearebothfairlylikelytobereachedfromtheCSS–thenthesituationisdeemedunpredictable.
Thissetuppermitstheidentificationofcandidatepredictivemeasurables:thesearethemeasurablestatesand/orparametersforwhichpredict-abilityismostsensitive(seeAppendixTwo).
Continuingwiththeonlinemarketexample,iftrajectorieswithpositiveearlymarketshareratesr(A)aremuchmorelikelytoyieldmarketsharedominanceforA8thanaretrajectorieswithnegativeearlyr(A),thenthesituationisunpredictable(becausetheoutcomedependssensitivelyonr(A)andthisquantityisnotmeasured).
Moreover,thisanalysissuggeststhatmar-ketsharerateislikelytopossesspredictivepower,soitmaybepossibletoincreasepredictabilitybyadd-ingthecapacitytomeasurethisquantity.
AkeyelementofthisapproachtopredictabilityassessmentistheproposedmethodofestimatingtheprobabilityofreachingtheSSIfromaCSS.
NotethatinatypicalassessmentsuchestimatesmustbecomputedforseveralCSSinordertoadequatelyexplorethespaceofcandidatepredictivefeatures,sothatitiscrucialtoperformtheseestimatesefficiently.
InAppendixTwowedevelopan"altitudefunc-tion"approachtothisreachabilityproblem,inwhichweseekascalarfunctionofthesystemstatethatpermitsconclusionstobemaderegardingreachabilitywithoutcomputingsystemtrajectories.
Werefertotheseasaltitudefunctionstoprovideanintuitivesenseoftheiranalyticrole:ifsomemeasureof"alti-tude"islowontheCSSandhighonanSSI,andiftheexpectedrateofchangeofaltitudealongsystemtrajectoriesisnonincreasing,thenitisunlikelyfortrajectoriestoreachthisSSIfromtheCSS.
Moreover,thedifferenceinaltitudesbetweentheCSSandSSIgivesameasureoftheprobabilityofreachingthelatterfromtheformer.
Becausethereachprobabilityiscomputedforsetsofstateswithoutsimulatingsys-temtrajectories,thealtitudefunctionmethodoffersanextremelyefficientwaytoexplorethespaceofcandidatepredictivefeatures.
Wehaveappliedthepredictabilityassessmentmethodologysummarizedabovetothesocialdiffu-sionpredictionproblem,andwenowsummarizethemainconclusionsofthisstudy;amorecompletedis-cussionofthisinvestigationisgiveninAppendixTwo.
Theanalysisusesthemathematicallyrigorouspredictabilityassessmentproceduresummarizedabove,incombinationwithempirically-groundedS-HDSmodelsforsocialdynamics,tocharacterizethepredictabilityofsocialdiffusiononnetworkswithrealisticdegreedistributions,transitivity,communitystructure,andcore-peripherystructure.
Themainfindingofthestudy,fromtheperspectiveofthepresentpaper,isthatthepredictabilityofthesediffusionmodelsdependscruciallyuponsocialandinformationnetworktopology,andinparticularonthecommu-nityandcore-peripherystructuresofthesenetworks.
Inordertodescribethesetheoreticalresultsmorequantitativelyandleveragethemforprediction,itisnecessarytospecifymathematicaldefinitionsfornetworkcommunitiesandcore-peripherystructure.
Thereexistseveralqualitativeandquantitativedefinitionsfortheconceptofcommunitystructureinnet-works.
Hereweadoptthemodularity-baseddefinitionproposedin[40],wherebyagoodpartitioningofanetwork'sverticesintocommunitiesisoneforwhichthenumberofedgesbetweenputativecommunitiesissmallerthanwouldbeexpectedinarandompartitioning.
Tobeconcrete,amodularity-basedpartition-ingofanetworkintotwocommunitiesmaximizesthemodularityQ,definedasQ=sTBs/4m,wheremisthetotalnumberofedgesinthenetwork,thepartitionisspecifiedwiththeelementsofvectorsbysettingsi=1ifvertexibelongstocommunity1andsi=1ifitbelongstocommunity2,andthema-trixBhaselementsBij=Aijkikj/2m,withAijandkidenotingthenetworkadjacencymatrixanddegreeofvertexi,respectively.
Partitionsofthenetworkintomorethantwocommunitiescanbeconstructedrecursively[40].
Notethatmodularity-basedcommunitypartitionscanbeefficientlycomputedforlargesocialnetworks,andcanbeconstructedevenwithincompletenetworktopologydata[39].
Withthisdefinitioninhand,weareinapositiontopresentthefirstcandidatepredictivefeaturenominatedbythetheoreticalpredictabilityassessment:thepresenceofearlydiffusionactivityinnumer-ousdistinctnetworkcommunitiesshouldbeareliablepredictorthattheultimatereachofthediffusion9willbelarge(seeAppendixTwo).
Inwhatfollows,propagationdynamicswhichpossessthischaracteris-ticwillbesaidtoexhibitsignificantearlydispersionacrossnetworkcommunities.
Notethatthismeasureshouldbemorepredictivethantheearlyvolumeofdiffusionactivity(thelatterhasrecentlybecomeafairlystandardmeasure[e.
g.
,19,20]).
AcartoonillustratingthebasicideabehindthisresultisgiveninFigure2.
Analogouslytothesituationwithnetworkcommunities,thereexistsawiderangeofqualitativeandquantitativedescriptionsofthecore-peripherystructurefoundinreal-worldnetworks.
Hereweadoptthecharacterizationofnetworkcore-peripherywhichresultsfromk-shelldecomposition,awell-establishedtechniqueingraphtheorythatissummarizedin,forinstance,[41].
Topartitionanetworkintoitsk-shells,onefirstremovesallverticeswithdegreeone,repeatingthisstepifnecessaryuntilallremainingverticeshavedegreetwoorhigher;theremovedverticesconstitutethe1-shell.
Continuinginthesameway,allverticeswithdegreetwo(orless)arerecursivelyremoved,creatingthe2-shell.
Thisprocessisrepeateduntilallverticeshavebeenassignedtoak-shell.
Theshellwiththehighestindex,thekmax-shell,isdeemedtobethecoreofthenetwork.
Giventhisdefinition,weareinapositiontoreportthesecondcandidatepredictivefeaturenominat-edbyourtheoreticalpredictabilityassessment:earlydiffusionactivitywithinthenetworkkmax-shellshouldbeareliablepredictorthattheultimatereachofthediffusionwillbesignificant(seeAppendixTwo).
Inparticular,thismeasureshouldbemorepredictivethantheearlyvolumeofdiffusionactivity.
AnintuitiveillustrationofthisresultisdepictedinFigure3.
Figure2.
Earlydispersionacrosscommunitiesispredictive.
Thecartoonillustratesthepredic-tivefeatureassociatedwithcommunitystructure:socialdiffusioninitiatedwithfive"seed"indi-vidualsismuchmorelikelytopropagatewidelyiftheseseedsaredispersedacrossthreecom-munities(left)ratherthanconcentratedwithinasinglecommunity(right).
NotethatinAppendixTwothisresultisestablishedfornetworksofrealisticscaleandnotsimplyfor"toy"networksliketheoneshownhere.
102.
4EarlyWarningMethodWearenowinapositiontopresentanearlywarningmethodwhichiscapableofaccuratelypredicting,veryearlyinthelifecycleofadiffusionprocessofinterest,whetherornottheprocesswillpropagatewidely.
Weadoptamachinelearning-basedclassificationapproachtothisproblem:givenatriggeringincident,oneormoreinformationsourceswhichreflectthereactiontothistriggerbyapopulationofin-terest,andadefinitionforwhatconstitutesan"alarming"reaction,thegoalistolearnclassifierthataccu-ratelypredicts,asearlyaspossible,whetherornotreactiontotheeventwillultimatelybecomealarming.
TheclassifierusedintheempiricalstudiesdescribedinthispaperistheAvatarensemblesofdecisiontrees(A-EDT)algorithm[42].
Otherclassificationalgorithmwerealsoexploredtoallowtherobustnessoftheproposedearlywarningapproachtobeevaluated,andthesealternativemethodsproducedqualita-tivelysimilarresults[39].
PredictionaccuracyinalltestsisestimatedusingstandardN-foldcross-validation,inwhichthesetofdiffusioneventsofinterestisrandomlypartitionedintoNsubsetsofequalsize,andtheA-EDTalgorithmissuccessively"trained"onN1ofthesubsetsand"tested"ontheheld-outsubsetinsuchawaythateachoftheNsubsetsisusedasthetestsetexactlyonce.
Akeyaspectoftheproposedapproachtoearlywarninganalysisisdeterminingwhichcharacteristicsofthesocialdiffusioneventofinterest,ifany,possessexploitablepredictivepower.
Weconsiderthreeclassesoffeatures:intrinsics-basedfeatures–measuresoftheinherentpropertiesandattributesofthe"object"beingdiffused;simpledynamics-basedfeatures–metricswhichcapturingsimplepropertiesofthediffusiondynam-ics,suchastheearlyextentofthediffusionandtherateatwhichthediffusionispropagating;networkdynamics-basedfeatures–measuresthatcharacterizethewaytheearlydiffusionisprogress-ingrelativetotopologicalpropertiesoftheunderlyingsocialandinformationnetworks(e.
g.
,commu-nitystructure).
Figure3.
Earlydiffusionwithinthecoreispredictive.
Thecartoonillustratesthepredictivefeatureassociatedwithk-shellstructure:socialdiffusioninitiatedwiththree"seed"individualsismuchmorelikelytopropagatewidelyiftheseseedsresidewithinthenetwork'score(left)ratherthanatitsperiphery(right).
NotethatinAppendixTwothisresultisestablishedfornetworksofrealisticscaleandnotsimplyfor"toy"networksliketheoneshownhere.
11Consider,asanillustrativeexample,thediffusionof"memes",thatis,shorttextualphraseswhichpropagaterelativelyunchangedonline(e.
g.
,'lipstickonapig').
Supposeitisofinteresttopredictwhichmemeswill"goviral",appearinginthousandsofblogposts,andwhichwillnot.
Inthiscase,intrinsic-basedfeaturescouldincludelanguagemeasures,suchasthesentimentoremotionexpressedinthetextsurroundingthememesinblogpostsornewsarticles.
Simpledynamics-basedfeaturesformemesmightmeasurethecumulativenumberofpostsorarticlesmentioningthememeofinterestatsomeearlytimeτandtherateatwhichthisvolumeisincreasing.
Networkdynamics-basedfeaturesmightcountthecumu-lativenumberofnetworkcommunitiesinabloggraphGBthatcontainatleastonepostwhichmentionsthememebytimeτandthenumberofblogsinthekmax-shellofGBthat,bytimeτ,containatleastonepostmentioningthememe.
Alternatively,inthecaseofanepidemic,theintrinsic-basedfeaturescouldincludetheinfectivityofthepathogen,simpledynamics-basedfeaturesmightcapturethenumberofindi-vidualsinfectedbythediseaseintheearlystagesoftheoutbreak,andnetworkdynamics-basedfeaturescouldincludemetricsthatcharacterizethewaytheepidemicisprogressingoverthecommunitiesofrele-vantsocialandtransportationnetworks.
Theproposedapproachtoearlywarninganalysisistocollectfeaturesfromtheseclassesfortheeventofinterest,inputthefeaturevaluestothe(trained)A-EDTclassifier,andthenruntheclassifiertogeneratethewarningprediction(i.
e.
,aforecastthattheeventisexpectedtobecome'alarming'orremain'notalarming').
Inthealgorithmpresentedbelowthisprocedureinspecifiedingeneralterms;morespe-cificinstantiationsoftheprocedurearepresentedinthediscussionsofthethreecasestudiesinSection3.
Inwhatfollowsitisassumedthattheprimarysourceofinformationconcerningtheeventofinterestissocialmedia,asthatisemergingasaveryusefuldatasourceforpredictiveanalysis[e.
g.
,17-24,26,27].
However,theanalyticprocessisquitesimilarwhenotherdatasources(e.
g.
,intelligencereporting)areemployed[24].
Thuswehavethefollowingearlywarningalgorithm:AlgorithmEWGiven:atriggeringincident,adefinitionforwhatconstitutesan'alarming'reaction,andasetofsocialmediasites(e.
g.
,blogs)Bwhicharerelevanttoearlywarningtask.
Initialization:traintheA-EDTclassifieronasetofeventswhicharequalitativelysimilartothetriggeringeventofinterestandarelabeledas'alarming'or'notalarming'accordingtothedefinitiongivenabove(seethecasestudydiscussionsforadditionaldetailsonthistrainingprocess).
Procedure:1.
AssemblealexiconofkeywordsLthatpertaintothetriggeringeventunderstudy.
2.
ConductasequenceofbloggraphcrawlsandconstructatimeseriesofbloggraphsGB(t).
ForthelexiconLandeachtimeperiodt,labeleachbloginGB(t)as'active'ifitcontainsapostmentioninganyofthekeywordsinLand'inactive'otherwise.
3.
FormtheunionGB=∪tGB(t),partitionGBintonetworkcommunitiesandintok-shells,andmapthepartitionelementstructureofGBbacktoeachofthegraphsGB(t).
4.
Computethevaluesofappropriatemeasuresfortheintrinsics,simpledynamics,andnetworkdynam-icsfeaturesforeachofthegraphsGB(t).
5.
ApplytheA-EDTclassifiertotheavailabletimeseriesoffeatures,thatis,thefeaturesobtainedfromthesequenceofbloggraphs{GB(t0),…,GB(tp)},wheret0andtparethetriggeringeventtimeandpre-senttime,respectively.
Issueanearlywarningalertiftheclassifieroutputis'alarming'.
Wenowofferadditionaldetailsconcerningthisprocedure;moreapplication-specificdiscussionsofthemethodologyareprovidedinthecasestudiesinSection3.
IdentifyingappropriatekeywordsinStep112canbeaccomplishedwiththehelpofsubjectmatterexpertsandalsothroughvariousautomatedmeans(e.
g.
,viamemeanalysis[38,27]).
Step2isbynowstandard,andvarioustoolsexistwhichcanperformthesetasks[e.
g.
,43].
InStep3,blognetworkcommunitiesareidentifiedwithamodularity-basedcom-munityextractionalgorithmappliedtothebloggraph[40],whilethedecompositionofthegraphintoitsk-shellsisachievedthroughstandardmethods[41].
Theparticularchoicesofmetricsfortheintrinsics,simpledynamics,andnetworkdynamicsfeaturescomputedinStep4tendtobeproblemspecific,andtypicalexamplesaregiveninthecasestudiesbelow.
Itisworthnoting,however,thatwehavefounditusefulinarangeofapplicationstoquantifythedispersionofactivityoverthecommunitiesofGB(t)usingablogentropymeasureBE:BE(t)=Σifi(t)log(fi(t)),wherefi(t)isthefractionoftotalpostscontainingoneormorekeywordsandmadeduringintervaltwhichoccurincommunityi.
Finally,inStep5thefeaturevaluesobtainedinStep4serveasinputstotheA-EDTclassifierandtheoutputisusedtodecidewhetheranalertshouldbeissued.
3.
CaseStudiesThissectionappliesAlgorithmEWtothreeearlywarningcasestudiesinvolvingsocialphenomenathathaveprovedtobebothpracticallyimportantandchallengingtoanalyze:1.
)diffusionofinformationthroughsocialmedia,2.
)mobilization/protesteventsresponseto"triggering"incidents,and3.
)plan-ning/coordination/executionofpolitically-motivatedcyberattacks.
3.
1CaseStudyOne:MemeDiffusionThegoalofthiscasestudyistoapplyAlgorithmEWtothetaskofpredictingwhetherornotagiven"meme",thatis,ashorttextualphrasewhichpropagatesrelativelyunchangedonline,will"goviral".
Ourmainsourceofdataonmemedynamicsisthepubliclyavailabledatasetsarchivedathttp://memetracker.
org[44]bytheauthorsof[38].
Briefly,thearchive[44]containstimeseriesdatacharacterizingthediffusionof~70000memesthroughsocialmediaandotheronlinesitesduringthefivemonthperiodbetween1Augustand31December2008.
WeareinterestedinusingAlgorithmEWtodis-tinguishsuccessfulandunsuccessfulmemesearlyintheirlifecycle.
Moreprecisely,thetaskofinterestistoclassifymemesintotwogroups–thosewhichwillultimatelybesuccessful(acquiremorethanSposts)andthosethatwillbeunsuccessful(attractfewerthanUposts)–veryearlyinthememelifecycle.
TosupportanempiricalevaluationoftheutilityofAlgorithmEWforthisproblems,wedownloadedfrom[44]thetimeseriesdataforslightlymorethan70000memes.
Thesedatacontain,foreachmemeM,asequenceofpairs(t1,URL1)M,(t2,URL2)M,…,(tT,URLT)M,wheretkisthetimeofappearanceofthekthblogpostornewsarticlethatcontainsatleastonementionofmemeM,URLkistheURLoftheblogornewssiteonwhichthatpost/articlewaspublished,andTisthetotalnumberofpoststhatmentionmemeM.
Fromthissetoftimeserieswerandomlyselected100"successful"memetrajectories,definedasthosecorrespondingtomemeswhichattractedatleast1000postsduringtheirlifetimes,and100"un-successful"memetrajectories,definedasthosewhosememesacquirednomorethan100totalposts.
Itisworthnotingthat,inassemblingthedatain[44],allmemeswhichreceivedfewerthan15totalpostsweredeleted,andthat~50%oftheremainingmemeshavebi,suchthatautilitymaximiz-ingagentwillchooseoption0ifsi0begivenforthemin-imumacceptablelevelofvariationinsystembehaviorrelativeto{Xs1,Xs2}.
ConsiderthefollowingDefinitionA2.
1:Asituationiseventualstate(ES)predictableif|γ1γ2|>δ,whereγ1andγ2aretheprobabilitiesofΣS-HDS,diffreachingXs1andXs2,respectively,andisESunpredictableotherwise.
NotethatinESpredictabilityproblemsitisexpectedthatthetwosets{Xs1,Xs2}representqualita-tivelydifferentsystembehaviors(e.
g.
,hitandflopinaculturalmarket),sothatiftheprobabilitiesofreachingeachfromX0*P0aresimilarthensystembehaviorisunpredictableinasensethatismeaningfulformanyapplications.
Otherusefulformsofpredictabilityaredefinedandinvestigatedin[39].
Thenotionofpredictabilityformsthebasisforourdefinitionofusefulmeasurables:DefinitionA2.
2:Letthecomponentsofthevectors(x0,p0)∈X0*P0whichcomprisetheCSSbedenot-edx0=[x01…x0n]Tandp0=[p01…p0p]T.
Themeasurableswithmostpredictivepowerarethosestatevariablesx0jand/orparametersp0kforwhichpredictabilityismostsensitive.
Intuitively,thosemeasurablesforwhichpredictabilityismostsensitivearelikelytobetheonesthatcanmostdramaticallyaffectthepredictabilityofagivenproblem.
Notethatwedonotspecifyaparticularmeasureofsensitivitytobeusedwhenidentifyingmeasurableswithmaximumpredictivepower,assuch32considerationsareordinarilyapplication-dependent(see[39]forsomeusefulspecifications).
DefinitionsA2.
1andA2.
2focusontheroleplayedbyinitialstatesinthepredictabilityofsocialprocesses.
Insomecasesitisusefultoexpandthisformulationtoallowconsiderationofstatesotherthaninitialstates.
Forinstance,weshowin[18]thatveryearlytimeseriesareoftenpredictiveforPEP,suggestingthatitcanbevaluabletoconsiderinitialstatetrajectorysegments,ratherthanjustinitialstates,whenassessingpredict-ability.
ThisextensioncanbenaturallyaccomplishedbyredefiningtheCSS,forinstancebyaugmentingthestatespaceXwithanexplicittimecoordinate[18].
Wenowturnourattentiontothe"earlywarning"problem.
DefinitionA2.
3:LettheeventofinterestbespecifiedintermsofΣS-HDS,diffreachingorescapingsomeSSIXs,andsupposeawarningsignalistobeissuedonlyiftheprobabilityofeventoccurrenceexceedssomespecifiedthresholdα.
ReachwarninganalysisinvolvesidentifyingastatesetXw,whereXsXwnecessarily,withthepropertythatifthesystemtrajectoryentersXwthentheprobabilitythatΣS-HDS,diffwilleventuallyreachXsisatleastα.
Analogously,escapewarninganalysisinvolvesidentifyingastatesetXw,whereX\XwXsnecessarily,withthepropertythatifthesystemtrajectoryentersXwthentheprobabilitythatΣS-HDS,diffwilleventuallyescapefromXsisatleastα.
A2.
2StochasticReachabilityAssessmentTheprevioussectionformulatespredictiveanalysisproblemsasreachabilityquestions.
Hereweshowthatthesereachabilityquestionscanbeaddressedthroughan"altitudefunction"analysis,inwhichweseekascalarfunctionofthesystemstatethatpermitsconclusionstobemaderegardingreachabilitywith-outcomputingsystemtrajectories.
Werefertotheseasaltitudefunctionstoprovideanintuitivesenseoftheiranalyticrole:ifsomemeasureof"altitude"islowontheCSSandhighonanSSI,andiftheex-pectedrateofchangeofaltitudealongsystemtrajectoriesisnonincreasing,thenitisunlikelyfortrajecto-riestoreachthisSSIfromtheCSS.
ConsidertheS-HDSsocialdiffusionmodelΣS-HDS,diffevolvingonaboundedstatespaceQ*X.
WequantifytheuncertaintyassociatedwithΣS-HDS,diffbyspecifyingboundsonthepossiblevaluesforsomesystemparametersandperturbationsandgivingprobabilisticdescriptionsforotheruncertainsystemele-mentsanddisturbances.
Giventhisrepresentation,itisnaturaltoseekaprobabilisticassessmentofsys-temreachability.
Webeginwithaninvestigationofprobabilisticreachabilityoninfinitetimehorizons.
Thefollowing"supermartingalelemma"isprovedin[53]andisinstrumentalinourdevelopment:LemmaSM:ConsiderastochasticprocessΣswithboundedstatespaceX,andletx(t)denotethe"stopped"processassociatedwithΣs(i.
e.
,x(t)isthetrajectoryofΣswhichstartsatx0andisstoppedifitencounterstheboundaryofX).
IfA(x(t))isanonnegativesupermartingalethenforanyx0andλ>0P{supA(x(t))≥λ|x(0)=x0}≤A(x0)/λ.
DenotebyX0XandXsXtheinitialstatesetandSSI,respectively,forthecontinuoussystemcomponentofΣS-HDS,diff,andassumethatXandtheparametersetParparebothbounded.
Thus,forinstance,theSSIisasubsetofthecontinuoussystemstatespaceXalone;thisistypicallythecaseinap-plicationsandiseasilyextendedifnecessary.
Wearenowinapositiontostateourfirststochasticreach-abilityresult:Theorem2:γisanupperboundontheprobabilityoftrajectoriesofΣS-HDS,diffreachingXsfromX0,whileremaininginQ*X,ifthereisafamilyofdifferentiablefunctions{Aq(x)}q∈QsuchthatAq(x)≤γx∈X0,q∈Q;33Aq(x)≥1x∈Xs,q∈Q;Aq(x)≥0x∈X,q∈Q;(Aq/x)(fq+Hqu)+(1/2)tr[GqT(2Aq/x2)Gq]+Σq′∈Qλqq′Aq′≤0x∈X,q∈Q,u∈U,p∈Par.
Proof:NotefirstthatBAq(x)=(Aq/x)(fq+Hqu)+(1/2)tr[GqT(2Aq/x2)Gq]+Σq′∈Qλqq′Aq′istheinfinitesimalgeneratorforΣS-HDS,diff,andthereforequantifiestheevolutionoftheexpectationofAq(x)[53,34].
Asaconsequence,thethirdandfourthconditionsofthetheoremimplythatA(q(t),x(t))isanonnegativesupermartingale[53].
Thus,fromLemmaSM,wecanconcludethatP{x(t)∈Xsforsomet}≤P{supA(q(t),x(t))≥1|x(0)=x0}≤A(q,x0)≤γx0∈X0,q∈Q,u∈U,p∈Par.
TheprecedingresultcharacterizesreachabilityofS-HDSoninfinitetimehorizons.
Insomesitua-tions,includingimportantapplicationsinvolvingsocialsystems,itisofinteresttostudysystembehavioronfinitetimehorizons.
Thefollowingresultisusefulforsuchanalysis:Theorem3:γisanupperboundontheprobabilityoftrajectoriesofΣS-HDS,diffreachingXsfromX0duringtimeinterval[0,T],whileremaininginQ*X,ifthereexistsafamilyofdifferentiablefunctions{Aq(x,t)}q∈QsuchthatAq(x,t)≤γ(x,t)∈X0*0,q∈Q;Aq(x,t)≥1(x,t)∈Xs*[0,T],q∈Q;Aq(x,t)≥0(x,t)∈X*+,q∈Q;BAq(x,t)≤0(x,t)∈X*+,q∈Q,u∈U,p∈Par.
Proof:TheprooffollowsimmediatelyfromthatofTheorem2onceitisobservedthatP{x(t)∈Xsforsomet∈[0,T]}=P{(x(t),t)∈Xs*[0,T]}.
TheideafortheproofofTheorem3wassuggestedin[54].
Havingformulatedpredictabilityassessmentforsocialprocessesintermsofsystemreachabilityandpresentedanewtheoreticalmethodologyforassessingreachability,wearenowinapositiontogiveourapproachtodecidingpredictability.
ObservefirstthatTheorems2and3areofdirectpracticalinterestonlyifitispossibletoefficientlycomputeatightprobabilityboundγandassociatedaltitudefunctionA(x)whichsatisfythetheoremconditions.
Towardthatend,observethatthetheoremsspecifyconvexconditionstobesatisfiedbyaltitudefunctions:ifA1andA2satisfythetheoremconditionsthenanycon-vexcombinationofA1andA2willalsosatisfytheconditions.
Thusthesearchforaltitudefunctionscanbeformulatedasaconvexprogrammingproblem[55].
Moreover,ifthesystemofinterestadmitsapoly-nomialdescription(e.
g.
,thesystemvectorandmatrixfieldsarepolynomials)andwesearchtopolynomi-alaltitudefunctions,thenthesearchcanbecarriedoutusingsum-of-squares(SOS)optimization[56].
SOSoptimizationisaconvexrelaxationframeworkbasedonSOSdecompositionoftherelevantpolynomialsandsemidefiniteprogramming.
SOSrelaxationinvolvesreplacingthenonnegativeandnonpositiveconditionstobesatisfiedbythealtitudefunctionswithSOSconditions.
Forexample,theconditionsforAq(x)giveninTheorem2canberelaxedasfollows:A(x)≤γx∈X0→γA(x)λ0T(x)g0(x)isSOSA(x)≥1x∈Xs→A(x)1λsT(x)gs(x)isSOSA(x)≥0x∈X→A(x)λX1T(x)gX1(x)isSOSBA(x)≤0x∈X,p∈Par→BA(x)λX2T(x)gX2(x)λPT(p)gP(p)isSOSwheretheentriesofthevectorfunctionsλ0,λs,λX1,λX2,λPareSOS,thevectorfunctionsg0,gs,gX1,gX2,gPsatisfyg()≥0(entry-wise)wheneverx∈Xorp∈Par,respectively,andweassume|Q|=1fornota-34tionalconvenience.
TheconditionsonAq(x,t)specifiedinTheorem3canberelaxedinexactlythesamemanner.
TherelaxedSOSconditionsareclearlysufficientandinpracticearetypicallynotoverly-conservative[56,39].
OncethesetofconditionstobesatisfiedbyA(x)arerelaxedinthisway,SOSprogrammingcanbeusedtocomputeγmin,theminimumvaluefortheprobabilityboundγ,andA(x),theassociatedaltitudefunctionwhichcertifiesthecorrectnessofthisbound.
SoftwareforsolvingSOSprogramsisavailableasthethird-partyMatlabtoolboxSOSTOOLS[56],andexampleSOSprogramsaregivenin[39].
Im-portantly,theapproachistractable:forfixedpolynomialdegrees,thecomputationalcomplexityoftheassociatedSOSprogramgrowspolynomiallyinthedimensionofthecontinuousstatespace,thecardi-nalityofthediscretestateset,andthedimensionoftheparameterspace.
Forcompleteness,weoutlineanalgorithmforcomputingthepair(γmin,A(x)):AlgorithmA2.
1:altitudefunctionsviaSOSprogramming(outline)1.
ParameterizeAasA(x)=Σkckak(x),where{a1,…,aB}aremonomialsuptoadesireddegreeboundand{c1,…,cB}areto-be-determinedcoefficients.
2.
RelaxallA(x)criteriaintherelevanttheoremtoSOSconditions.
3.
FormulateanSOSprogramwithdecisionvariablesγ,{c1,…,cB},wherethedesiredboundonalti-tudefunctionpolynomialdegreeisreflectedinthespecificationoftheset{c1,…,cB}.
Computetheminimumprobabilityboundγminandvaluesforthecoefficients{c1,…,cB}thatdefineA(x)usingSOSTOOLS.
Itisemphasizedthat,althoughthecomputationof(γmin,A(x))isperformednumerically,theresultingfunctionA(x)isguaranteedtosatisfytheconditionsoftherelevanttheoremandthereforerepresentsaproofofthecorrectnessoftheprobabilityupperboundγmin.
Notealsothattheprobabilityestimateisob-tainedwithoutcomputingsystemtrajectories,andisvalidforentiresetsofinitialstatesX0,parametervaluesPar,andexogenousinputsU.
Havinggivenamethodforefficientlycomputingpairs(γmin,A(x)),andtherebycharacterizingreach-ability,wearenowinapositiontosketchanalgorithmforassessingESpredictability:AlgorithmA2.
2:ESpredictability(outline)Given:socialdiffusionprocessofinterestisΣS-HDS,diff,CSS=X0*P0,SSI={Xs1,Xs2},andminimumacceptablelevelofvariation=δ.
Procedure:1.
compute(upperboundfor)probabilityγ1ofΣS-HDS,diffreachingXs1fromX0*P0;2.
compute(upperboundfor)probabilityγ2ofΣS-HDS,diffreachingXs2fromX0*P0;3.
if|γ1γ2|>δthenproblemisESpredictable,elseproblemisESunpredictable.
Note:γ1,γ2canbecomputedusingTheorem2(infinitetimehorizon)orTheorem3(finitetimehorizon)togetherwithAlgorithm3.
1andSOSTOOLS[56].
A2.
3ApplicationtoSocialDiffusionThetheoreticalframeworkdevelopedintheprecedingsectionsisnowused,incombinationwithempiri-cally-groundedmodelsforsocialdiffusion[e.
g.
,17,49-51],todemonstratethatpredictabilityofthisclassofdiffusionmodelsdependscruciallyuponnetworkcommunitystructure.
Weinvestigatethefollowingpredictabilityquestion:IsthediffusionofsocialmovementsandmobilizationsESpredictableand,ifso,whichmeasurablequantitieshavepredictivepowerWeadoptaspecificversionoftheS-HDSsocialdiffusionmodelproposedinDefinition2.
2:35ΣS-HDS,diff={Gsc,Q*X,{fq(x),Gq(x)}q∈Q,Par,W,{Q,Λ(x)}}wherethesocialnetworkcommunitygraphGscconsistsofKcommunities(so|Vsc|=K),connectedtogetherwithanErdos-Renyirandomgraphtopology,withcommunitysizedrawnfromapowerlawdistribu-tion[36];eachcontinuoussystemΣcs,q:dx=fq(x,p)dt+Gq(x,p)dw,q∈Q,isgivenbythemeso-scalesocialmovementmodelΣHorΣBwithappropriateparametervectorpandsystem"noise"w;thediscretesystem{Q,Λ(x)}isaMarkovchainthatdefinesinter-communityinteractionsinthemannerdescribedinDefinitionA1.
2.
AMatlabinstantiationofthisS-HDSdiffusionmodelisgivenin[39]andisavailableuponrequest.
Thebehaviorofthemodelcanbeshowntobeconsistentwithempiricalobservationsofseveralhistoricalsocialmovements(e.
g.
,variousmovementsinSweden)[39].
InordertoassessESpredictability,SSI={Xs1,Xs2}isdefinedsothatXs1,Xs2arestatesetscorre-spondingtoglobal(affectingasignificantfractionofthepopulation)andlocal(remainingconfinedtoasmallfractionofthepopulation)movementevents,respectively.
WethenemployAlgorithmA2.
2itera-tivelytosearchforadefinitionforCSS=X0*P0whichensuresthattheprobabilitiesofreachingXs1andXs2fromX0*P0aresufficientlydifferenttoyieldanESpredictablesituation.
WeusetwomodelsoftheformΣS-HDS,diffforthisanalysis,correspondingtothetwodefinitionsforthecontinuoussystemΣHandΣB.
EachmodeliscomposedofK=10communitiesconnectedtogetherwithanErdos-Renyirandomgraphtopology.
(UsingdifferentrealizationsoftheErdos-Renyirandomgraphdoesnotaffecttheconclusionsreportedbelow.
)ESpredictabilityanalysisyieldstwomainresults.
First,boththeintra-communityandinter-communitydynamicsexhibitthresholdbehavior:smallchangesineithertheintra-community"infectivi-ty"orinter-communityinteractionratearoundtheirthresholdvaluesleadtolargevariationsintheproba-bilitythatthemovementwillpropagate"globally".
Morequantitatively,forthediffusionmodelΣS-HDS,diffwithcontinuoussystemdynamicsΣH,thresholdbehaviorisobtainedwhenvarying1.
)thegeneralizedreproductionnumberR=β/δ2and2.
)therateλatwhichinter-communityinteractionsbetweenindivid-ualstakeplace.
Thusinorderforasocialmovementtopropagatetoasignificantfractionofthepopula-tion,thethresholdconditionsR≥1andλ≥λ0mustbesatisfiedsimultaneously.
AnanalogousconclusionholdswhenΣHisreplacedwiththediffusionmodelΣBintheS-HDSrepresentation.
Thisfindingisremi-niscentofandextendswell-knownresultsforepidemicthresholdsindiseasepropagationmodels[1].
ThisthresholdbehaviorisillustratedintheplotatthetoprightofFigure7,whichshowsthewayprobabilityofglobalpropagationincreaseswithinter-communityinteractionratewhentheintra-communitydiffusionissufficientlyinfective(i.
e.
,R≥1).
Theprobabilitieswhichmakeupthisplotrepre-sentsprovably-correct(upperbound)estimatescomputedusingTheorem2andAlgorithmA2.
1.
Asimi-larthresholdresponseisobservedwhenvaryingintra-communityinfectivityR,providedtheinter-communityinteractionratesatisfiesλ≥λ0.
Importantly,theinter-communityinteractionthresholdλ0isseentobequitesmall,indicatingthatevenafewlinksbetweennetworkcommunitiesenablesrapiddiffu-sionofthemovementtootherwisedisparateregionsofthesocialnetwork.
Thisresultsuggeststhatause-fulpredictorofmovementactivityinagivencommunityisthelevelofmovementactivityamongthatcommunity'sneighborsinGsc.
36ThesecondmainESpredictabilityresultcharacterizesthewayprobabilityofglobalpropagationvar-ieswiththenumberofnetworkcommunitiesacrosswhichafixedsetof"seed"movementmembersisdistributed.
Toquantifythisdependence,thesocialmovementmodelΣS-HDS,diffisinitializedsothatasmallfractionofindividualsinthepopulationaremovementmembersandtheremainderofthepopula-tionconsistssolelyofpotentialmembers.
Wethenvarythewaythisinitialseedsetofmovementmem-bersisdistributedacrosstheKnetworkcommunities,atoneextremeassigningallseedstothesamecommunityandattheotherspreadingtheseedsuniformlyoverallKcommunities.
Foreachdistributionofseedmovementmembers,theprobabilityofglobalmovementpropagationiscomputedusingTheorem2andAlgorithmA2.
1.
Otherthaninitializationstrategy,themodelisspecifiedexactlyasintheprecedinganalysis.
Figure7.
Sampleresultsfromsocialdiffusionpredictabilitystudy.
Cartoonattopleftillustratesthesetupfortheinter-communityinteractionstudy,highlightingtheparametervaluesR0=1andλ0whichquantifyintra-andinter-communitypropagationthresholds;plotattoprightshowsclassicthresholddependenceofglobalpropagationprobabilityoninter-communityinteractionintensityλ.
Plotsinbottomrowdepictthewayglobalpropagationprobabilityincreaseswiththenumberofcommunitiesacrosswhichafixedsetofinnovatingseedsaredistributed(plotsatleftandrightshowcascadeprob-abilitiesformulti-scalemodelspossessingΣHandΣBmeso-scaledynamics,respectively).
λ0R0λ0R0λ0R037TheresultsofthisportionoftheESpredictabilityassessmentaresummarizedinthetwoplotsatthebottomofFigure7.
Itisseenthatforbothchoicesofmeso-scalesocialmovementdynamics,ΣHandΣB,theprobabilityofglobalmovementpropagationincreasesapproximatelylinearlywiththenumberofnet-workcommunitiesacrosswhichthefixedsetofseedmembersisdistributed(herethenumberofinitialmembersissettoonepercentofthetotalpopulation).