sociologicallycnnchina

RESEARCHOpenAccessEarlywarninganalysisforsocialdiffusioneventsRichardColbaugh1andKristinGlass2*AbstractThereisconsiderableinterestindevelopingpredictivecapabilitiesforsocialdiffusionprocesses,forinstancetopermitearlyidentificationofemergingcontentioussituations,rapiddetectionofdiseaseoutbreaks,oraccurateforecastingoftheultimatereachofpotentially"viral"ideasorbehaviors.
Thispaperproposesanewapproachtothispredictiveanalyticsproblem,inwhichanalysisofmeso-scalenetworkdynamicsisleveragedtogenerateusefulpredictionsforcomplexsocialphenomena.
Webeginbyderivingastochastichybriddynamicalsystems(S-HDS)modelfordiffusionprocessestakingplaceoversocialnetworkswithrealistictopologies;thismodelingapproachisinspiredbyrecentworkinbiologydemonstratingthatS-HDSofferausefulmathematicalformalismwithwhichtorepresentcomplex,multi-scalebiologicalnetworkdynamics.
WethenperformformalstochasticreachabilityanalysiswiththisS-HDSmodelandconcludethattheoutcomesofsocialdiffusionprocessesmaydependcruciallyuponthewaytheearlydynamicsoftheprocessinteractswiththeunderlyingnetwork'scommunitystructureandcore-peripherystructure.
Thistheoreticalfindingprovidesthefoundationsfordevelopingamachinelearningalgorithmthatenablesaccurateearlywarninganalysisforsocialdiffusionevents.
Theutilityofthewarningalgorithm,andthepowerofnetwork-basedpredictivemetrics,aredemonstratedthroughanempiricalinvestigationofthepropagationofpolitical"memes"oversocialmedianetworks.
Additionally,weillustratethepotentialoftheapproachforsecurityinformaticsapplicationsthroughcasestudiesinvolvingearlywarninganalysisoflarge-scaleprotestseventsandpolitically-motivatedcyberattacks.
Keywords:Socialdynamics,Predictiveanalysis,Earlywarning,Protestandmobilization,Cybersecurity,SecurityinformaticsIntroductionUnderstandingthewayinformation,behaviors,innova-tions,anddiseasespropagateoversocialnetworksisofgreatimportanceinawidevarietyofdomainse.
g.
,[1-4],includingnationalsecuritye.
g.
,[5-13].
Ofparticularinterestarepredictivecapabilitiesforsocialdiffusion,forinstancetoenableearlywarningconcerningtheemer-genceofaviolentconflictoroutbreakofanepidemic.
Asaconsequence,vastresourcesaredevotedtothetaskofpredictingtheoutcomesofdiffusionprocesses,butthequalityofsuchpredictionsisoftenpoor.
Itistempt-ingtoconcludethattheproblemisoneofinsufficientinformation.
Clearlydiffusionphenomenawhich"goviral"arequalitativelydifferentfromthosethatdon'tortheywouldn'tbesodominant,theconventionalwisdomgoes,soinordertomakegoodpredictionswemustcollectenoughdatatoallowthesecrucialdifferencestobeidentified.
Recentresearchcallsintoquestionthisintuitivelyplausiblepremiseand,indeed,indicatesthatintuitioncanbeanunreliableguidetoconstructingsuccessfulpredictionmethods.
Forexample,studiesofthepredict-abilityofpopularcultureindicatethattheintrinsicattri-butescommonlybelievedtobeimportantwhenassessingthelikelihoodofadoptionofculturalproducts,suchasthequalityoftheproductitself,donotpossessmuchpre-dictivepower[14-16].
Thisresearchoffersevidencethat,whenindividualsareinfluencedbytheactionsofothers,itmaynotbepossibletoobtainreliablepredictionsusingmethodswhichfocusonintrinsicsalone;instead,itmaybenecessarytoincorporateaspectsofsocialinfluenceintothepredictionprocess.
Veryrecentlyahandfulofinvesti-gationshaveshownthevalueofconsideringevensimpleandindirectmeasuresofsocialinfluence,suchasearlysocialmedia"buzz",whenformingpredictions.
Thisworkhasproducedusefulpredictionalgorithmsforanarrayof*Correspondence:klglass@sandia.
gov2CyberResearchandEducationDepartment,SandiaNationalLaboratories,Albuquerque,USAFulllistofauthorinformationisavailableattheendofthearticle2012GlassandColbaugh;licenseeSpringer.
ThisisanOpenAccessarticledistributedunderthetermsoftheCreativeCommonsAttributionLicense(http://creativecommons.
org/licenses/by/2.
0),whichpermitsunrestricteduse,distribution,andreproductioninanymedium,providedtheoriginalworkisproperlycited.
ColbaughandGlassSecurityInformatics2012,1:18http://www.
security-informatics.
com/content/1/1/18socialphenomena,includingmarkets[16-21],politicalandsocialmovements[17,22],mobilizationandprotestbehavior[23,24],epidemics[17,25],socialmediadynamics[26,27],andtheevolutionofcyberthreats[28].
Recognizingtheimportanceofaccountingforsocialinfluence,thispaperproposesapredictivemethodologywhichexplicitlyconsidersthewayindividualsinfluenceoneanotherthroughtheirsocialnetworks.
Itisexpectedthatpredictionalgorithmswhicharebased,inpart,onnetworkdynamicsmetricswilloutperformexistingmethodsandbeapplicabletoawiderrangeofdiffusionsystems.
Webeginbydevelopingastochastichybriddy-namicalsystems(S-HDS)modelfordiffusionprocessestakingplaceoversocialnetworkswithrealistictopolo-gies.
ThismodelingapproachisinspiredbyrecentworkinbiologydemonstratingthatS-HDSofferausefulmathematicalformalismwithwhichtorepresentmulti-scalebiologicalnetworkdynamics[29-33].
AnS-HDSisafeedbackinterconnectionofadiscrete-statesto-chasticprocess,suchasaMarkovchain,withafamilyofcontinuous-statestochasticdynamicalsystems[34].
Combiningdiscreteandcontinuousdynamicsinthiswayprovidesarigorous,expressive,andcomputationally-tractableframeworkformodelingthedynamicsofthecomplex,highly-evolvednetworksthatareubiquitousinbiologicalsystems[35],andweshowinthispaperthattheS-HDSframeworkisalsowell-suitedtothetaskofmodel-ingthenetworkdynamicswhichunderliesocialdiffusion.
WiththeS-HDSmodelinhand,wethenperformfor-malstochasticreachabilityanalysisandconcludethattheoutcomesofsocialdiffusionprocessesmaydependcruciallyuponthewaytheearlydynamicsoftheprocesspropagateswithrespecttotheunderlyingnetwork's1.
)communitystructure,thatis,denselyconnectedgroupingsofindividualswhichhaveonlyrelativelyfewlinkstoothergroups[36],and2.
)core-peripherystructure,reflectingthepresenceofasmallgroupof"core"individualsthataredenselyconnectedtoeachotherandarealsoclosetotheremainderofthenetwork[36].
Thistheoreticalfindingleadstotheidentificationofnovelmetricsforthecommunityandcore-peripherydynamicswhichshouldbeusefulearlyindicatorsofwhichdiffusioneventswillpropagatewidely,ultimatelyaffectingasubstantialportionofthepopulationofinterest,andwhichwillnot.
Predictionisaccomplishedwithamachinelearningalgorithm[37]whichisbased,inpart,onthesenetworkdynam-icsmetrics.
Thepapermakesthreemaincontributions.
First,wepresentanewS-HDS-basedframeworkformodelingsocialdiffusiononnetworksofreal-worldscaleandcomplexity,enablingthesedynamicstobeappropriatelyrepresentedasmulti-scalephenomena.
Second,weformulatepredictiveanalysisproblemsasquestionsconcerningthereachabilityofdiffusionevents,andpresentanovel"altitudefunction"methodforassessingreachabilitywithoutsimulatingsystemtrajectories.
Thealtitudefunctiontechniqueisbothmath-ematicallyrigorousandcomputationallytractable,therebypermittingthederivationofprovably-correctassessmentsforcomplex,large-scalesystems.
Third,theS-HDSmodelandaltitudefunctionanalyticsareusedtocharacterizetheimportanceofmeso-scalenetworkfeatures,specific-allynetworkcommunityandcore-peripherystructures,forunderstandingdiffusionprocessesandpredictingtheirfates.
Thischaracterization,inturn,formsthefoun-dationfordevelopinganewmachinelearning-basedclassificationalgorithmwhichemploysthesenetworkdynamicsfeaturesforaccurateearlywarninganalysis.
Additionally,weevaluatetheefficacyofthisearlywarn-ingalgorithmthroughthreeempiricalcasestudiesinvestigating:1.
)thepropagationofpolitical"memes"[38]oversocialmedianetworks,2.
)warninganalysisforlarge-scalemobilizationandprotestevents,and3.
)earlywarningforpolitically-motivatedcyberattacks.
Theseempiricalstudiesillustratetheeffectivenessoftheproposedearlywarningmethodologyanddemon-stratethesignificantpredictivepowerofmeso-scalenetworkmetricsforsocialdiffusionprocesses.
More-over,theresultsindicatethattheproposedalgorithmprovidesareadily-implementableWeb-basedtoolforearlywarninganalysisforimportantclassesofsecurity-relevantdiffusionevents.
EarlyWarningMethodologyThissectionbeginsbydefiningtheclassofearlywarningproblemsofinterest,thenpresentsabrief,intuitivesum-maryoftheproposedsocialdiffusionmodelingandpre-dictiveanalysisprocedure,andfinallydescribestheearlywarningindicatorsidentifiedthroughthisanalyticpro-cedureandthewarningalgorithmthatisderivedbasedontheseresults.
AdetailedmathematicalpresentationofthemodelingandanalysismethodsisprovidedinAppendicesOneandTwo.
2.
1ProblemFormulationTheobjectiveofthispaperistodevelopascientifically-rigorous,practically-implementablemethodologyforperformingearlywarninganalysisforsocialdiffusionevents.
Roughlyspeaking,wesupposethatsome"trig-geringevent"hastakenplaceorcontentiousissueisemerging,andwewishtodetermine,asearlyaspossible,whetherthiseventorissuewillultimatelygeneratealarge,self-sustainingreaction,involvingthediffusionofdiscussionsandactionsthroughasubstantialsegmentofapopulation,orwillinsteadquicklydissipate.
Anillus-trativeexampleofthebasicideaisprovidedbythecon-trastingreactionsto1.
)thepublicationinSeptember2005ofcartoonsdepictingMohammadintheDanishColbaughandGlassSecurityInformatics2012,1:18Page2of26http://www.
security-informatics.
com/content/1/1/18newspaperJyllands-Posten,and2.
)thelecturegivenbyPopeBenedictXVIinSeptember2006quotingcontro-versialmaterialconcerningIslam.
Whileeacheventappearedattheoutsettohavethepotentialtotriggersignificantprotests,the"Danishcartoons"incidentul-timatelyledtosubstantialMuslimmobilization,includ-ingmassiveprotestsandconsiderableviolence,whileoutragetriggeredbythepopelecturequicklysubsidedwithessentiallynoviolence.
Itwouldobviouslybeveryusefultohavethecapabilitytodistinguishthesetwotypesofreactionasearlyintheeventlifecycleaspossible.
Inordertostatetheearlywarningproblemmorepre-cisely,wemakeafewassumptions:Wesupposethatthetriggeringeventoremergingsituationisgiven.
Notethatthisisoftenthecaseinnationalsecuritysettings,andthatadditionallythereexisttechniquesfordiscoveringsucheventsorissuesinanautomatedorsemi-automatedmannere.
g.
,[24,27].
Itisassumedthatdataareavailablewhichprovideaviewoftheearlyreactionofarelevantpopulationtothetriggerorissueofinterest.
Thesedatacanbeonlyindirectlyrelatedtotheevent;forexample,inthispapertheprimarydatasourceissocialmediadiscussions(e.
g.
,blogposts)whiletheeventsofinterestare"real-world"activitiessuchasprotests.
Itisexpectedthatthe"customer"fortheanalysisprovidesatleastqualitativedefinitionsofthepopulationofinterestandthescaleofreactionforwhichawarningisdesired.
Thus,forinstance,intheexampleabove,itmightbeofinteresttoanticipateMuslimreactiontothetriggeringincident,andtoobtainawarningalertifthereactionislikelytoeventuallyincludeself-sustaining,violentprotests.
Weformulatetheearlywarningproblemasaclassifi-cationtask.
Morespecifically,givenatriggeringincident,oneormoreinformationsourceswhichreflect(perhapsindirectly)thereactiontothistriggerbyapopulationofinterest(e.
g.
,socialmediadiscussions,intelligencereporting),andadefinitionforwhatconstitutesan"alarming"reaction,thegoalistodesignaclassifierwhichaccuratelypredicts,asearlyaspossible,whetherornotreactiontotheeventwillultimatelybecomealarming.
NotethatamoremathematicallyprecisestatementofthiswarningproblemisgiveninAppendixTwo.
Observethatthistypeofwarninganalysisisbothimportantinapplicationsand"easier"toaccomplishthanmorestandardpredictionorforecastinggoals.
Consider,asafamiliarnon-securityexample,thecaseofmoviesuccess.
Itisshownin[14-16]thatitislikelytobeimpossibletopredictmovierevenues,evenveryroughly,basedontheintrinsicinformationavailableconcerningthemovieexante(e.
g.
,personnel,genre,criticreviews).
However,wehavedemonstratedthatitispossibletoidentifyearlyindicatorsofmoviesuccess,suchastemporalpatternsinpre-release"buzz",andtousetheseindicatorstoaccuratelypredictultimateboxofficerevenues[39].
Recentresearchindicatesthatthisresultholdsmoregenerally,sothatitmaybemorescientifically-sensibleinmanydomainstopursueearlywarningratherthanexantepredictiongoals[14-28].
2.
2S-HDSSocialDiffusionModelInsocialdiffusion,individualsareaffectedbywhatothersdo.
Thisiseasytovisualizeinthecaseofdiseasetransmission,withinfectionsbeingpassedfrompersontoperson.
Information,innovations,behaviors,andsooncanalsopropagatethroughapopulation,asindivi-dualsbecomeawareofanewpieceofinformationoranactivityandarepersuadedofitsrelevanceandutilitythroughtheirsocialandinformationnetworks.
Thedynamicsofsocialdiffusioncanthereforedependuponthetopologicalfeaturesofthepertinentnetworks,suchasthepresenceofhighlyconnectedblogsinasocialmedianetwork(see,e.
g.
,[4]).
Indeed,socialscientistshavedevelopedextensivetheoriesexplainingtheroleofsocialnetworksinthedynamicsofsocialdiffusionandmobilization(seethebooks[2-4]andthereferencestherein,andalsoAppendixOne,fordiscussionsofthiswork).
Thisdependencesuggeststhat,inordertounder-standthepredictabilityofsocialdiffusionphenomenaandinparticulartoidentifyfeatureswhichpossesspre-dictivepower,itisnecessarytoconducttheanalysisusingsocialandinformationnetworkmodelswithrealis-tictopologies.
Thesocialdiffusionmodelsexaminedinthisstudypossessnetworkswiththreetopologicalpropertiesthatareubiquitousinreal-worldsocialandinformationnet-worksandwhichhavethepotentialtoimpactdiffusiondynamics[36]:transitivity–thepropertythatthenetworkneighborsofagivenindividualhaveaheightenedprobabilityofbeingconnectedtooneanother;communitystructure–thepresenceofdenselyconnectedgroupingsofindividualswhichhaveonlyrelativelyfewlinkstoothergroups;core-peripherystructure–thepresenceofasmallgroupof"core"individualswhicharedenselyconnectedtoeachotherandarealsoclosetotheotherindividualsinthenetwork.
Additionally,wepermitournetworkmodelstopossessright-skeweddegreedistributions,inwhichmostindivi-dualshaveonlyafewnetworkneighborswhileafewColbaughandGlassSecurityInformatics2012,1:18Page3of26http://www.
security-informatics.
com/content/1/1/18individualshaveagreatmanyneighbors,assuchnetworksarecommoninonlinesettings.
Themannerinwhichthecommunitiesandthecore-peripheryarearrangedwillbesaidtodefinethenetwork'smeso-scalestructure.
Forcon-venienceofexposition,thesubsetsofindividualsspecifiedbyapartitioningofthenetworkintocommunitiesandintoacoreandperipherywillsometimesbereferredtoasthepartitionelements,andthecollectionofthese(com-munityandcore-periphery)subsetswillbecalledthenet-workpartition.
Inordertodealeffectivelywithnetworkspossessingrealistictopologies,andinparticulartorepresentandanalyzethewaysocialdynamicsisaffectedbythemeso-scalestructure,wemodelsocialdiffusioninamannerwhichexplicitlyseparatestheindividual,or"micro",dynamicsfromthecollectivedynamics.
Morespecific-ally,weadoptamulti-scalemodelingframeworkconsist-ingofthreenetworkscales:amicro-scale,formodelingthebehaviorofindividuals;ameso-scale,whichrepresentstheinteractiondynamicsofindividualswithinthesamenetworkpartitionelement(communityorcore/periphery);amacro-scale,whichcharacterizestheinteractionbetweenpartitionelements.
Themicro-scalequantifiesthewayindividualscom-binetheirowninherentpreferencesorattributeswiththeinfluencesofotherstoarriveattheirchosencoursesofaction.
ItisshowninAppendixOnethatseparatingthemicro-scaledynamicsfromthemeso-andmacro-scaleactivitypermitsthedependenceofthisdecision-makingprocessonthesocialnetworktobecharacterizedinasur-prisinglystraightforwardway.
Themeso-andmacro-scalecomponentsoftheproposedmodelingframeworkto-getherquantifythewaythedecision-makingprocessesofindividualsinteracttoproducecollectivebehavioratthepopulationlevel.
Theroleofthemeso-scalemodelistoquantifyandilluminatethemannerinwhichbehaviorswithineachnetworkpartitionelement(communities,coreorperiphery),whilethemacro-scalemodelcapturestheinteractionsbetweentheseelements.
Theprimaryassump-tionsarethatinteractionsbetweenindividualsbelongingtothesamenetworkpartitionelementcanbemodeledmoresimplythanthosebetweenindividualsfromdistinctpartitionelements,andthatthelatterinteractionsareconstrainedbythe"meta-network"whichdefinesthede-pendenciesbetweenthepartitionelements.
Thisperspectiveoffersanumberofadvantages.
Forex-ample,atthemicro-scaleitispossibletounifybehaviorswhichappeardifferentphenomenologicallybutactuallypossessequivalentdynamics.
WeshowinAppendixOnethatthesocialdynamicsassociatedwithclassical"utility-maximizing"behaviorandthosearisingfromindividualsattemptingtoinferinformationbyobservingtheactionsofotherscanberepresentedwiththesamemicro-scalemodel.
Additionally,separatingtheindividualandcol-lectivedynamicssupportsefficientandflexiblemodelbuildingandsimplifiestheprocessofestimatingmodelcomponentsfromempiricaldata[39].
Dividingthecol-lectivedynamicsintomeso-andmacro-scalesalsopro-videsamathematically-tractable,sociologically-sensiblemeansofrepresentingcomplexsocialnetworkdynam-ics.
Forinstance,becausenetworkcommunitiesaretopologicalstructurescorrespondingtolocalizedsocialsettingsintherealworld,determinedbyworkplace,family,physicalneighborhood,andsoon,itisnaturalbothmathematicallyandsociologicallytomodeltheinteractionsofindividualswithincommunitiesasqualita-tivelydifferent(e.
g.
,morefrequentandhomogeneous)thanthosebetweencommunities.
Developingamathematically-rigorous,expressive,scal-able,andcomputationally-tractableframeworkwithinwhichmulti-scalesocialnetworkdiffusionmodelscanbeconstructedis,ofcourse,achallengingundertaking.
Recentworkinsystemsbiologyhasdemonstratedthatstochastichybriddynamicalsystems(S-HDS)provideausefulmathematicalformalismwithwhichtorepresentbiologicalnetworkdynamicsthatpossessmultipletem-poralandspatialscales[29-33].
AnS-HDSisafeedbackinterconnectionofadiscrete-statestochasticprocess,suchasaMarkovchain,withafamilyofcontinuous-statesto-chasticdynamicalsystems[34].
Thusthediscretesystemdynamicsdependsonthecontinuoussystemstate,perhapsbecausedifferentregionsofthecontinuousstatespaceareassociatedwithdifferentmatricesofMarkovstatetransitionprobabilities,andtheparticularcontinu-oussystemwhichis"active"atagiventimedependsonthediscretesystemstate.
Combiningdiscreteandcontinu-ousdynamicsinthiswayprovidesaneffectiveframeworkformodelingthedynamicsofthecomplex,highly-evolvednetworksthatareubiquitousinbiologicalsystems[35].
Forexample,therigorousyettractableintegrationofswitchingbehaviorwithcontinuousdynamicsenabledbytheS-HDSmodelallowsaccurateandefficientrepresenta-tionofbiologicalphenomenaevolvingoverdisparatetem-poralscales[29-31]andspatialscales[32,33].
Inspiredbythiswork,inthispaperweapplytheS-HDSframeworktosocialdiffusiondynamicsevolvingovermultiplenetworkscales.
AppendixOneprovidesadetaileddiscussionoftheproposedS-HDSsocialdiffusionmodelanddemonstratestheeffectivenesswithwhichthisformalismcapturesmulti-scalenetworkdynamics.
AsanintuitiveillustrationofthewayS-HDSenablecomplexnetworkphenomenatobeefficientlyrepresented,con-siderthetaskofmodelingdiffusiononanetworkthatpossessescommunitystructure.
AsshowninFigure1,thisColbaughandGlassSecurityInformatics2012,1:18Page4of26http://www.
security-informatics.
com/content/1/1/18diffusionconsistsoftwocomponents:1.
)intra-communitydynamics,involvingfrequentinteractionsbetweenindivi-dualswithinthesamecommunityandtheresultinggrad-ualchangeintheconcentrationsof"infected"(red)individuals,and2.
)inter-communitydynamics,inwhichthe"infection"jumpsfromonecommunitytoanother,forinstancebecauseaninfectedindividual"visits"anewcom-munity.
S-HDSmodelsofferanaturalframeworkforrepresentingthesedynamics,withtheS-HDScontinuoussystemmodelingtheintra-communitydynamics(e.
g.
,viastochasticdifferentialequations),thediscretesystemcapturingtheinter-communitydynamics(e.
g.
,usingaMarkovchain),andtheinterplaybetweenthesedynamicsbeingrepresentedbytheS-HDSfeedbackstructure.
AdetaileddescriptionofthemannerinwhichS-HDSmodelscanbeusedtocapturesocialdiffusiononnetworkswithrealistictopologiesisgiveninAppendixOne.
2.
3PredictabilityAssessmentOnehallmarkofsocialdiffusionprocessesistheirosten-sibleunpredictability:phenomenafromhitsandflopsinculturalmarketstofinancialsystembubblesandcrashestopoliticalupheavalsappearresistanttopredictiveana-lysis(althoughthereisnoshortageofexpostexplanationsfortheiroccurrence!
).
Itisnotdifficulttogainanintuitiveunderstandingofthebasisforthisunpredictability.
Indi-vidualpreferencesandsusceptibilitiesaremappedtocol-lectiveoutcomesthroughanintricate,dynamicalprocessinwhichpeoplereactindividuallytoanenvironmentcon-sistinglargelyofotherswhoarereactinglikewise.
Becauseofthisfeedbackdynamics,thecollectiveoutcomecanbequitedifferentfromoneimpliedbyasimpleaggregationofindividualpreferences;standardpredictionmethods,whichtypicallyarebasedonsuchaggregationideas,donotcapturethesedynamicsandthereforeareoftenunsuccessful.
Thissectionprovidesabrief,intuitiveintroductiontoasystematicapproachtoassessingthepredictabilityofsocialdiffusionprocessesandidentifyingprocessobser-vableswhichhaveexploitablepredictivepower(seeAppendixTwo,andalso[17,39],forthemathematicaldetails).
Considerasimplemodelforproductadoption,inwhichindividualscombinetheirownpreferencesandopinionsregardingtheavailableoptionswiththeirobservationsoftheactionsofotherstoarriveattheirdecisionsaboutwhichproducttoadopt.
Asdiscussedabove,itcanbequitedifficulttodeterminewhichcharac-teristicsoftheprocessbywhichadoptiondecisionsinputsinputsmodeoutputsdiscretesystemcontinuoussysteminter-communitydynamicsijkinter-communitydynamicsintra-communitydynamicsFigure1ModelingdiffusiononnetworkswithcommunitystructureviaS-HDS.
Thecartoonattopleftdepictsanetworkwiththreecommunities.
Thecartoonatrightillustratesdiffusionwithinacommunitykandbetweencommunitiesiandj.
TheschematicatbottomleftshowsthebasicS-HDSfeedbackstructure;thediscreteandcontinuoussystemsinthisframeworkmodeltheinter-communityandintra-communitydiffusiondynamics,respectively.
ColbaughandGlassSecurityInformatics2012,1:18Page5of26http://www.
security-informatics.
com/content/1/1/18propagate,ifany,arepredictiveofthingslikethespeedorultimatereachofthepropagation[15-17].
InAppendixTwoweproposeamathematicallyrigorousapproachtopredictabilityassessmentwhich,amongotherthings,per-mitsidentificationoffeaturesofsocialdynamicswhichshouldhavepredictivepower.
Wenowsummarizethisassessmentmethodology.
Thebasicideabehindtheproposedapproachtopre-dictabilityanalysisissimpleandnatural:weassesspre-dictabilitybyansweringquestionsaboutthereachabilityofdiffusionevents.
Toobtainamathematicalformula-tionofthisstrategy,thebehavioraboutwhichpredic-tionsaretobemadeisusedtodefinethesystemstatespacesubsetsofinterest(SSI),whiletheparticularsetofcandidatemeasurablesunderconsiderationallowsiden-tificationofthecandidatestartingset(CSS),thatis,thesetofstatesandsystemparametervalueswhichrepre-sentinitializationsthatareconsistentwith,andequiva-lentunder,thepresumedobservationalcapability.
Asasimpleexample,consideranonlinemarketwithtwoproducts,AandB,andsupposethesystemstatevari-ablesconsistofthecurrentmarketshareforA,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,theproposedapproachtopredict-abilityassessmentinvolvesdetermininghowprobableitistoreachtheSSIfromaCSSanddecidingifthesereachabilitypropertiesarecompatiblewiththepredic-tiongoals.
Ifasystem'sreachabilitycharacteristicsareincompatiblewiththegivenpredictionquestion–if,say,"hit"and"flop"statesintheonlinemarketexamplearebothfairlylikelytobereachedfromtheCSS–thenthesituationisdeemedunpredictable.
Thissetuppermitstheidentificationofcandidatepredictivemeasurables:thesearethemeasurablestatesand/orparametersforwhichpredictabilityismostsensitive(seeAppendixTwo).
Con-tinuingwiththeonlinemarketexample,iftrajectorieswithpositiveearlymarketshareratesr(A)aremuchmorelikelytoyieldmarketsharedominanceforAthanaretrajectorieswithnegativeearlyr(A),thenthesituationisunpredictable(becausetheoutcomedependssensi-tivelyonr(A)andthisquantityisnotmeasured).
Moreover,thisanalysissuggeststhatmarketsharerateislikelytopossesspredictivepower,soitmaybepos-sibletoincreasepredictabilitybyaddingthecapacitytomeasurethisquantity.
Akeyelementofthisapproachtopredictabilityassess-mentistheproposedmethodofestimatingtheprobabil-ityofreachingtheSSIfromaCSS.
NotethatinatypicalassessmentsuchestimatesmustbecomputedforseveralCSSinordertoadequatelyexplorethespaceofcandi-datepredictivefeatures,sothatitiscrucialtoperformtheseestimatesefficiently.
InAppendixTwowedevelopan"altitudefunction"approachtothisreachabilityprob-lem,inwhichweseekascalarfunctionofthesystemstatethatpermitsconclusionstobemaderegardingreachabilitywithoutcomputingsystemtrajectories.
Werefertotheseasaltitudefunctionstoprovideanintuitivesenseoftheiranalyticrole:ifsomemeasureof"altitude"islowontheCSSandhighonanSSI,andiftheexpectedrateofchangeofaltitudealongsystemtrajec-toriesisnonincreasing,thenitisunlikelyfortrajectoriestoreachthisSSIfromtheCSS.
Moreover,thedifferenceinaltitudesbetweentheCSSandSSIgivesameasureoftheprobabilityofreachingthelatterfromtheformer.
Becausethereachprobabilityiscomputedforsetsofstateswithoutsimulatingsystemtrajectories,thealtitudefunctionmethodoffersanextremelyefficientwaytoexplorethespaceofcandidatepredictivefeatures.
Wehaveappliedthepredictabilityassessmentmeth-odologysummarizedabovetothesocialdiffusionpre-dictionproblem,andwenowsummarizethemainconclusionsofthisstudy;amorecompletediscussionofthisinvestigationisgiveninAppendixTwo.
Theanalysisusesthemathematicallyrigorouspredictabilityassess-mentproceduresummarizedabove,incombinationwithempirically-groundedS-HDSmodelsforsocialdynam-ics,tocharacterizethepredictabilityofsocialdiffusiononnetworkswithrealisticdegreedistributions,transitiv-ity,communitystructure,andcore-peripherystructure.
Themainfindingofthestudy,fromtheperspectiveofthepresentpaper,isthatthepredictabilityofthesediffu-sionmodelsdependscruciallyuponsocialandinformationnetworktopology,andinparticularonthecommunityandcore-peripherystructuresofthesenetworks.
Inordertodescribethesetheoreticalresultsmorequantitativelyandleveragethemforprediction,itisne-cessarytospecifymathematicaldefinitionsfornetworkcommunitiesandcore-peripherystructure.
Thereexistseveralqualitativeandquantitativedefinitionsfortheconceptofcommunitystructureinnetworks.
Hereweadoptthemodularity-baseddefinitionproposedin[40],wherebyagoodpartitioningofanetwork'sverticesintocommunitiesisoneforwhichthenumberofedgesbe-tweenputativecommunitiesissmallerthanwouldbeexpectedinarandompartitioning.
Tobeconcrete,aColbaughandGlassSecurityInformatics2012,1:18Page6of26http://www.
security-informatics.
com/content/1/1/18modularity-basedpartitioningofanetworkintotwocommunitiesmaximizesthemodularityQ,definedasQsTBs=4m;wheremisthetotalnumberofedgesinthenetwork,thepartitionisspecifiedwiththeelementsofvectorsbysettingsi=1ifvertexibelongstocommunity1andsi=1ifitbelongstocommunity2,andthematrixBhaselementsBij=Aijkikj/2m,withAijandkidenotingthenetworkadjacencymatrixanddegreeofvertexi,respectively.
Partitionsofthenetworkintomorethantwocommunitiescanbeconstructedrecursively[40].
Notethatmodularity-basedcommunitypartitionscanbeefficientlycomputedforlargesocialnetworks,andcanbecon-structedevenwithincompletenetworktopologydata[39].
Withthisdefinitioninhand,weareinapositiontopresentthefirstcandidatepredictivefeaturenominatedbythetheoreticalpredictabilityassessment:thepresenceofearlydiffusionactivityinnumerousdistinctnetworkcommunitiesshouldbeareliablepredictorthattheul-timatereachofthediffusionwillbelarge(seeAppendixTwo).
Inwhatfollows,propagationdynamicswhichpos-sessthischaracteristicwillbesaidtoexhibitsignificantearlydispersionacrossnetworkcommunities.
Notethatthismeasureshouldbemorepredictivethantheearlyvolumeofdiffusionactivity(thelatterhasrecentlybe-comeafairlystandardmeasuree.
g.
,[19,20]).
AcartoonillustratingthebasicideabehindthisresultisgiveninFigure2.
Analogouslytothesituationwithnetworkcommunities,thereexistsawiderangeofqualitativeandquantitativedescriptionsofthecore-peripherystructurefoundinreal-worldnetworks.
Hereweadoptthecharacterizationofnetworkcore-peripherywhichresultsfromk-shellde-composition,awell-establishedtechniqueingraphtheorythatissummarizedin,forinstance,[41].
Topartitionanetworkintoitsk-shells,onefirstremovesallverticeswithdegreeone,repeatingthisstepifnecessaryuntilallremainingverticeshavedegreetwoorhigher;theremovedverticesconstitutethe1-shell.
Continuinginthesameway,allverticeswithdegreetwo(orless)arerecur-sivelyremoved,creatingthe2-shell.
Thisprocessisrepeateduntilallverticeshavebeenassignedtoak-shell.
Theshellwiththehighestindex,thekmax-shell,isdeemedtobethecoreofthenetwork.
Giventhisdefinition,weareinapositiontoreportthesecondcandidatepredictivefeaturenominatedbyourtheoreticalpredictabilityassessment:earlydiffusionactivitywithinthenetworkkmax-shellshouldbeareli-ablepredictorthattheultimatereachofthediffusionwillbesignificant(seeAppendixTwo).
Inparticular,thismeasureshouldbemorepredictivethantheearlyvol-umeofdiffusionactivity.
AnintuitiveillustrationofthisresultisdepictedinFigure3.
2.
4EarlyWarningMethodWearenowinapositiontopresentanearlywarningmethodwhichiscapableofaccuratelypredicting,veryearlyinthelifecycleofadiffusionprocessofinterest,whetherornottheprocesswillpropagatewidely.
Weadoptamachinelearning-basedclassificationapproachtothisproblem:givenatriggeringincident,oneormoreinformationsourceswhichreflectthereactiontothistriggerbyapopulationofinterest,andadefinitionforwhatconstitutesan"alarming"reaction,thegoalistolearnclassifierthataccuratelypredicts,asearlyaspos-sible,whetherornotreactiontotheeventwillultimatelybecomealarming.
TheclassifierusedintheempiricalstudiesdescribedinthispaperistheAvatarensemblesofdecisiontrees(A-EDT)algorithm[42].
Otherclassifi-cationalgorithmwerealsoexploredtoallowtherobust-nessoftheproposedearlywarningapproachtobeevaluated,andthesealternativemethodsproducedFigure2Earlydispersionacrosscommunitiesispredictive.
Thecartoonillustratesthepredictivefeatureassociatedwithcommunitystructure:socialdiffusioninitiatedwithfive"seed"individualsismuchmorelikelytopropagatewidelyiftheseseedsaredispersedacrossthreecommunities(left)ratherthanconcentratedwithinasinglecommunity(right).
NotethatinAppendixTwothisresultisestablishedfornetworksofrealisticscaleandnotsimplyfor"toy"networksliketheoneshownhere.
ColbaughandGlassSecurityInformatics2012,1:18Page7of26http://www.
security-informatics.
com/content/1/1/18qualitativelysimilarresults[39].
PredictionaccuracyinalltestsisestimatedusingstandardN-foldcross-validation,inwhichthesetofdiffusioneventsofinterestisrandomlypartitionedintoNsubsetsofequalsize,andtheA-EDTalgorithmissuccessively"trained"onN1ofthesubsetsand"tested"ontheheld-outsubsetinsuchawaythateachoftheNsubsetsisusedasthetestsetexactlyonce.
Akeyaspectoftheproposedapproachtoearlywarn-inganalysisisdeterminingwhichcharacteristicsofthesocialdiffusioneventofinterest,ifany,possessexploit-ablepredictivepower.
Weconsiderthreeclassesoffeatures:intrinsics-basedfeatures–measuresoftheinherentpropertiesandattributesofthe"object"beingdiffused;simpledynamics-basedfeatures–metricswhichcapturingsimplepropertiesofthediffusiondynamics,suchastheearlyextentofthediffusionandtherateatwhichthediffusionispropagating;networkdynamics-basedfeatures–measuresthatcharacterizethewaytheearlydiffusionisprogressingrelativetotopologicalpropertiesoftheunderlyingsocialandinformationnetworks(e.
g.
,communitystructure).
Consider,asanillustrativeexample,thediffusionof"memes",thatis,shorttextualphraseswhichpropagaterelativelyunchangedonline(e.
g.
,'lipstickonapig').
Sup-poseitisofinteresttopredictwhichmemeswill"goviral",appearinginthousandsofblogposts,andwhichwillnot.
Inthiscase,intrinsic-basedfeaturescouldincludelan-guagemeasures,suchasthesentimentoremotionexpressedinthetextsurroundingthememesinblogpostsornewsarticles.
Simpledynamics-basedfeaturesformemesmightmeasurethecumulativenumberofpostsorarticlesmentioningthememeofinterestatsomeearlytimeτandtherateatwhichthisvolumeisincreasing.
Networkdynamics-basedfeaturesmightcountthecu-mulativenumberofnetworkcommunitiesinabloggraphGBthatcontainatleastonepostwhichmen-tionsthememebytimeτandthenumberofblogsinthekmax-shellofGBthat,bytimeτ,containatleastonepostmentioningthememe.
Alternatively,inthecaseofanepidemic,theintrinsic-basedfeaturescouldin-cludetheinfectivityofthepathogen,simpledynamics-basedfeaturesmightcapturethenumberofindividualsinfectedbythediseaseintheearlystagesoftheoutbreak,andnetworkdynamics-basedfeaturescouldincludemetricsthatcharacterizethewaytheepidemicisprogres-singoverthecommunitiesofrelevantsocialandtranspor-tationnetworks.
Theproposedapproachtoearlywarninganalysisistocollectfeaturesfromtheseclassesfortheeventofinter-est,inputthefeaturevaluestothe(trained)A-EDTclas-sifier,andthenruntheclassifiertogeneratethewarningprediction(i.
e.
,aforecastthattheeventisexpectedtobecome'alarming'orremain'notalarming').
Inthealgo-rithmpresentedbelowthisprocedureinspecifiedingeneralterms;morespecificinstantiationsoftheproced-urearepresentedinthediscussionsofthethreecasestudiesinSection3.
Inwhatfollowsitisassumedthattheprimarysourceofinformationconcerningtheeventofinterestissocialmedia,asthatisemergingasaveryuse-fuldatasourceforpredictiveanalysise.
g.
,[17-24,26,27].
However,theanalyticprocessisquitesimilarwhenotherdatasources(e.
g.
,intelligencereporting)areemployed[24].
Thuswehavethefollowingearlywarningalgorithm:AlgorithmEWGiven:atriggeringincident,adefinitionforwhatconsti-tutesan'alarming'reaction,andasetofsocialmediaFigure3Earlydiffusionwithinthecoreispredictive.
Thecartoonillustratesthepredictivefeatureassociatedwithk-shellstructure:socialdiffusioninitiatedwiththree"seed"individualsismuchmorelikelytopropagatewidelyiftheseseedsresidewithinthenetwork'score(left)ratherthanatitsperiphery(right).
NotethatinAppendixTwothisresultisestablishedfornetworksofrealisticscaleandnotsimplyfor"toy"networksliketheoneshownhere.
ColbaughandGlassSecurityInformatics2012,1:18Page8of26http://www.
security-informatics.
com/content/1/1/18sites(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,andnetworkdynamicsfeaturesforeachofthegraphsGB(t).
5.
ApplytheA-EDTclassifiertotheavailabletimeseriesoffeatures,thatis,thefeaturesobtainedfromthesequenceofbloggraphs{GB(t0)GB(tp)},wheret0andtparethetriggeringeventtimeandpresenttime,respectively.
Issueanearlywarningalertiftheclassifieroutputis'alarming'.
Wenowofferadditionaldetailsconcerningthispro-cedure;moreapplication-specificdiscussionsofthemethodologyareprovidedinthecasestudiesinSection3.
IdentifyingappropriatekeywordsinStep1canbeaccomplishedwiththehelpofsubjectmatterexpertsandalsothroughvariousautomatedmeans(e.
g.
,viamemeanalysis[27,38]).
Step2isbynowstandard,andvarioustoolsexistwhichcanperformthesetaskse.
g.
,[43].
InStep3,blognetworkcommunitiesareidentifiedwithamodularity-basedcommunityextractionalgo-rithmappliedtothebloggraph[40],whilethedecom-positionofthegraphintoitsk-shellsisachievedthroughstandardmethods[41].
Theparticularchoicesofmetricsfortheintrinsics,simpledynamics,andnet-workdynamicsfeaturescomputedinStep4tendtobeproblemspecific,andtypicalexamplesaregiveninthecasestudiesbelow.
Itisworthnoting,however,thatwehavefounditusefulinarangeofapplicationstoquan-tifythedispersionofactivityoverthecommunitiesofGB(t)usingablogentropymeasureBE:BEtXifitlogfit;wherefi(t)isthefractionoftotalpostscontainingoneormorekeywordsandmadeduringintervaltwhichoccurincommunityi.
Finally,inStep5thefeaturevaluesobtainedinStep4serveasinputstotheA-EDTclassi-fierandtheoutputisusedtodecidewhetheranalertshouldbeissued.
CaseStudiesThissectionappliesAlgorithmEWtothreeearlywarn-ingcasestudiesinvolvingsocialphenomenathathaveprovedtobebothpracticallyimportantandchallengingtoanalyze:1.
)diffusionofinformationthroughsocialmedia,2.
)mobilization/protesteventsresponseto"trig-gering"incidents,and3.
)planning/coordination/execu-tionofpolitically-motivatedcyberattacks.
3.
1CaseStudyOne:MemeDiffusionThegoalofthiscasestudyistoapplyAlgorithmEWtothetaskofpredictingwhetherornotagiven"meme",thatis,ashorttextualphrasewhichpropagatesrelativelyunchangedonline,will"goviral".
Ourmainsourceofdataonmemedynamicsisthepubliclyavailabledatasetsarchivedathttp://memetracker.
org[44]bytheauthorsof[38].
Briefly,thearchive[44]containstimeseriesdatacharacterizingthediffusionof~70000memesthroughsocialmediaandotheronlinesitesduringthefivemonthperiodbetween1Augustand31December2008.
WeareinterestedinusingAlgorithmEWtodistinguishsuccessfulandunsuccessfulmemesearlyintheirlife-cycle.
Moreprecisely,thetaskofinterestistoclassifymemesintotwogroups–thosewhichwillultimatelybesuccessful(acquiremorethanSposts)andthosethatwillbeunsuccessful(attractfewerthanUposts)–veryearlyinthememelifecycle.
TosupportanempiricalevaluationoftheutilityofAlgorithmEWforthisproblems,wedownloadedfrom[44]thetimeseriesdataforslightlymorethan70000memes.
Thesedatacontain,foreachmemeM,ase-quenceofpairs(t1,URL1)M,(t2,URL2)M,.
.
.
,(tT,URLT)M,wheretkisthetimeofappearanceofthekthblogpostornewsarticlethatcontainsatleastonemen-tionofmemeM,URLkistheURLoftheblogornewssiteonwhichthatpost/articlewaspublished,andTisthetotalnumberofpoststhatmentionmemeM.
Fromthissetoftimeserieswerandomlyselected100"successful"memetrajectories,definedasthosecorrespondingtomemeswhichattractedatleast1000postsduringtheirlifetimes,and100"un-successful"memetrajectories,definedasthosewhosememesacquirednomorethan100totalposts.
Itisworthnotingthat,inassemblingthedatain[44],allmemeswhichreceivedfewerthan15totalpostsweredeleted,andthat~50%oftheremainingmemeshavebi,suchthatautilitymaximizingagentwillchooseoption0ifsi0begivenfortheminimumacceptablelevelofvariationinsys-tembehaviorrelativeto{Xs1,Xs2}.
ConsiderthefollowingDefinitionA2.
1:Asituationiseventualstate(ES)pre-dictableif|γ1γ2|>δ,whereγ1andγ2aretheprob-abilitiesofΣS-HDS,diffreachingXs1andXs2,respectively,andisESunpredictableotherwise.
NotethatinESpredictabilityproblemsitisexpectedthatthetwosets{Xs1,Xs2}representqualitativelydiffer-entsystembehaviors(e.
g.
,hitandflopinaculturalmarket),sothatiftheprobabilitiesofreachingeachfromX0*P0aresimilarthensystembehaviorisunpre-dictableinasensethatismeaningfulformanyapplica-tions.
Otherusefulformsofpredictabilityaredefinedandinvestigatedin[39].
Thenotionofpredictabilityformsthebasisforourdefinitionofusefulmeasurables:DefinitionA2.
2:Letthecomponentsofthevectors(x0,p0)∈X0*P0whichcomprisetheCSSbedenotedx0=[x01.
.
.
x0n]Tandp0=[p01.
.
.
p0p]T.
Themeasur-ableswithmostpredictivepowerarethosestatevariablesx0jand/orparametersp0kforwhichpredictabilityismostsensitive.
Intuitively,thosemeasurablesforwhichpredictabilityismostsensitivearelikelytobetheonesthatcanmostdra-maticallyaffectthepredictabilityofagivenproblem.
Notethatwedonotspecifyaparticularmeasureofsensitivitytobeusedwhenidentifyingmeasurableswithmaximumpredictivepower,assuchconsiderationsareordinarilyapplication-dependent(see[39]forsomeusefulspecifica-tions).
DefinitionsA2.
1andA2.
2focusontheroleplayedbyinitialstatesinthepredictabilityofsocialprocesses.
Insomecasesitisusefultoexpandthisformulationtoallowconsiderationofstatesotherthaninitialstates.
Forin-stance,weshowin[18]thatveryearlytimeseriesareoftenpredictiveforPEP,suggestingthatitcanbevaluabletoconsiderinitialstatetrajectorysegments,ratherthanjustinitialstates,whenassessingpredictability.
Thisex-tensioncanbenaturallyaccomplishedbyredefiningtheCSS,forinstancebyaugmentingthestatespaceXwithanexplicittimecoordinate[18].
Wenowturnourattentiontothe"earlywarning"problem.
DefinitionA2.
3:LettheeventofinterestbespecifiedintermsofΣS-HDS,diffreachingorescapingsomeSSIXs,andsupposeawarningsignalistobeissuedonlyiftheprobabilityofeventoccurrenceexceedssomespecifiedthresholdα.
ReachwarninganalysisinvolvesidentifyingastatesetXw,whereXsXwnecessarily,withtheprop-ertythatifthesystemtrajectoryentersXwthentheprobabilitythatΣS-HDS,diffwilleventuallyreachXsisatleastα.
Analogously,escapewarninganalysisinvolvesidentifyingastatesetXw,whereX\XwXsnecessarily,withthepropertythatifthesystemtrajectoryentersXwthentheprobabilitythatΣS-HDS,diffwilleventuallyescapefromXsisatleastα.
A2.
2StochasticReachabilityAssessmentTheprevioussectionformulatespredictiveanalysispro-blemsasreachabilityquestions.
Hereweshowthatthesereachabilityquestionscanbeaddressedthroughan"alti-tudefunction"analysis,inwhichweseekascalarfunc-tionofthesystemstatethatpermitsconclusionstobemaderegardingreachabilitywithoutcomputingsystemtrajectories.
Werefertotheseasaltitudefunctionstoprovideanintuitivesenseoftheiranalyticrole:ifsomemeasureof"altitude"islowontheCSSandhighonanSSI,andiftheexpectedrateofchangeofaltitudealongsystemtrajectoriesisnonincreasing,thenitisunlikelyfortrajectoriestoreachthisSSIfromtheCSS.
ConsidertheS-HDSsocialdiffusionmodelΣS-HDS,diffevolvingonaboundedstatespaceQ*X.
WequantifytheuncertaintyassociatedwithΣS-HDS,diffbyspecifyingboundsonthepossiblevaluesforsomesystemparametersandperturbationsandgivingprobabilisticdescriptionsforotheruncertainsystemelementsanddisturbances.
Giventhisrepresentation,itisnaturaltoseekaprobabilisticas-sessmentofsystemreachability.
Webeginwithaninvestigationofprobabilisticreach-abilityoninfinitetimehorizons.
Thefollowing"super-martingalelemma"isprovedin[53]andisinstrumentalinourdevelopment:LemmaSM:ConsiderastochasticprocessΣswithboundedstatespaceX,andletx(t)denotethe"stopped"processassociatedwithΣs(i.
e.
,x(t)isthetrajectoryofΣswhichstartsatx0andisstoppedifitencounterstheboundaryofX).
IfA(x(t))isanonnegativesupermartin-galethenforanyx0andλ>0PsupAx―t≥λx―0x0o≤Ax0=λ:nDenotebyX0XandXsXtheinitialstatesetandSSI,respectively,forthecontinuoussystemcomponentofΣS-HDS,diff,andassumethatXandtheparametersetParparebothbounded.
Thus,forinstance,theSSIisasubsetofthecontinuoussystemstatespaceXalone;thisistypicallythecaseinapplicationsandiseasilyextendedifnecessary.
Wearenowinapositiontostateourfirststochasticreachabilityresult:ColbaughandGlassSecurityInformatics2012,1:18Page21of26http://www.
security-informatics.
com/content/1/1/18Theorem2:γisanupperboundontheprobabilityoftrajectoriesofΣS-HDS,diffreachingXsfromX0,whileremaininginQ*X,ifthereisafamilyofdifferentiablefunctions{Aq(x)}q∈QsuchthatAqx≤γx∈X0;q∈Q;Aqx≥1x∈Xs;q∈Q;Aqx≥0x∈X;q∈Q;Aq=xfqHqu1=2trGqT2Aq=x2GqΣq0∈Qλqq0Aq0≤0x∈X;q∈Q;u∈U;p∈Par:Proof:NotefirstthatBAqxAq=xfqHqu1=2trGqT2Aq=x2GqPq0∈Qλqq0Aq0istheinfini-tesimalgeneratorforΣS-HDS,diff,andthereforequantifiestheevolutionoftheexpectationofAq(x)[34,53].
Asaconsequence,thethirdandfourthconditionsofthethe-oremimplythatA(q(t),x(t))isanonnegativesupermar-tingale[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.
Insomesituations,in-cludingimportantapplicationsinvolvingsocialsys-tems,itisofinteresttostudysystembehavioronfinitetimehorizons.
Thefollowingresultisusefulforsuchanalysis:Theorem3:γisanupperboundontheprobabilityoftrajectoriesofΣS-HDS,diffreachingXsfromX0duringtimeinterval[0,T],whileremaininginQ*X,ifthereexistsafamilyofdifferentiablefunctions{Aq(x,t)}q∈QsuchthatAqx;t≤γx;t∈X00;q∈Q;Aqx;t≥1x;t∈Xs0;T;q∈Q;Aqx;t≥0x;t∈XR;q∈Q;BAqx;t≤0x;t∈XR;q∈Q;u∈U;p∈Par:Proof:TheprooffollowsimmediatelyfromthatofTheorem2onceitisobservedthatPx―t∈Xsforfsomet∈0;tgPx―t;t∈Xs0;Tfg.
TheideafortheproofofTheorem3wassuggestedin[54].
Havingformulatedpredictabilityassessmentforsocialprocessesintermsofsystemreachabilityandpresentedanewtheoreticalmethodologyforassessingreachability,wearenowinapositiontogiveourapproachtodecid-ingpredictability.
ObservefirstthatTheorems2and3areofdirectpracticalinterestonlyifitispossibletoeffi-cientlycomputeatightprobabilityboundγandasso-ciatedaltitudefunctionA(x)whichsatisfythetheoremconditions.
Towardthatend,observethatthetheoremsspecifyconvexconditionstobesatisfiedbyaltitudefunc-tions:ifA1andA2satisfythetheoremconditionsthenanyconvexcombinationofA1andA2willalsosatisfytheconditions.
Thusthesearchforaltitudefunctionscanbeformulatedasaconvexprogrammingproblem[55].
Moreover,ifthesystemofinterestadmitsapolyno-mialdescription(e.
g.
,thesystemvectorandmatrixfieldsarepolynomials)andwesearchtopolynomialaltitudefunctions,thenthesearchcanbecarriedoutusingsum-of-squares(SOS)optimization[56].
SOSoptimizationisaconvexrelaxationframeworkbasedonSOSdecompositionoftherelevantpolynomialsandsemidefiniteprogramming.
SOSrelaxationinvolvesreplacingthenonnegativeandnonpositiveconditionstobesatisfiedbythealtitudefunctionswithSOSconditions.
Forexample,theconditionsforAq(x)giveninTheorem2canberelaxedasfollows:Ax≤γx∈X0→γAxλ0Txg0xisSOSAx≥1x∈Xs→Ax1λsTxgsxisSOSAx≥0x∈X→Axλx1Txgx1xisSOSBAx≤0x∈X;p∈Par→BAxλx2Txgx2xλPTpgppisSOSwheretheentriesofthevectorfunctionsλ0,λs,λx1,λx2,λpareSOS,thevectorfunctionsg0,gs,gx1,gx2,gpsatisfyg*(·)≥0(entry-wise)wheneverx∈X*orp∈Par,respectively,andweassume|Q|=1fornotationalconvenience.
TheconditionsonAq(x,t)specifiedinTheorem3canberelaxedinexactlythesamemanner.
TherelaxedSOScon-ditionsareclearlysufficientandinpracticearetypicallynotoverly-conservative[39,56].
OncethesetofconditionstobesatisfiedbyA(x)arerelaxedinthisway,SOSprogrammingcanbeusedtocomputeγmin,theminimumvaluefortheprobabilityboundγ,andA(x),theassociatedaltitudefunctionwhichcertifiesthecorrectnessofthisbound.
SoftwareforsolvingColbaughandGlassSecurityInformatics2012,1:18Page22of26http://www.
security-informatics.
com/content/1/1/18SOSprogramsisavailableasthethird-partyMatlabtoolboxSOSTOOLS[56],andexampleSOSprogramsaregivenin[39].
Importantly,theapproachistractable:forfixedpoly-nomialdegrees,thecomputationalcomplexityoftheassociatedSOSprogramgrowspolynomiallyinthedi-mensionofthecontinuousstatespace,thecardinalityofthediscretestateset,andthedimensionoftheparameterspace.
Forcompleteness,weoutlineanalgorithmforcom-putingthepair(γmin,A(x)):AlgorithmA2.
1:altitudefunctionsviaSOSpro-gramming(outline)1.
ParameterizeAasA(x)=Σkckak(x),where{a1,aB}aremonomialsuptoadesireddegreeboundand{c1,cB}areto-be-determinedcoefficients.
2.
RelaxallA(x)criteriaintherelevanttheoremtoSOSconditions.
3.
FormulateanSOSprogramwithdecisionvariablesγ,{c1,cB},wherethedesiredboundonaltitudefunctionpolynomialdegreeisreflectedinthespecificationoftheset{c1,cB}.
Computetheminimumprobabilityboundγminandvaluesforthecoefficients{c1,cB}thatdefineA(x)usingSOSTOOLS.
Itisemphasizedthat,althoughthecomputationof(γmin,A(x))isperformednumerically,theresultingfunctionA(x)isguaranteedtosatisfytheconditionsoftherelevantthe-oremandthereforerepresentsaproofofthecorrectnessoftheprobabilityupperboundγmin.
Notealsothattheprob-abilityestimateisobtainedwithoutcomputingsystemtra-jectories,andisvalidforentiresetsofinitialstatesX0,parametervaluesPar,andexogenousinputsU.
Havinggivenamethodforefficientlycomputingpairs(γmin,A(x)),andtherebycharacterizingreachability,wearenowinapositiontosketchanalgorithmforasses-singESpredictability:AlgorithmA2.
2:ESpredictability(outline)Given:socialdiffusionprocessofinterestisPSHDS,diff,CSS=X0*P0,SSI={Xs1,Xs2}andminimumacceptablelevelofvariation=δ.
Procedure:1.
compute(upperboundfor)probabilityγ1ofΣS-HDS,diff,reachingXs1fromX0*P0;2.
compute(upperboundfor)probabilityγ2ofΣS-HDS,diff,reachingXs2fromX0*P0;3.
if|γ1γ2|>δthenproblemisESpredictable,elseproblemisESunpredictable.
Note:γ1,γ2canbecomputedusingTheorem2(infinitetimehorizon)orTheorem3(finitetimehorizon)togetherwithAlgorithm3.
1andSOSTOOLS[56].
A2.
3ApplicationtoSocialDiffusionThetheoreticalframeworkdevelopedintheprecedingsectionsisnowused,incombinationwithempirically-groundedmodelsforsocialdiffusione.
g.
,[17,49-51],todemonstratethatpredictabilityofthisclassofdiffusionmodelsdependscruciallyuponnetworkcommunitystructure.
Weinvestigatethefollowingpredictabilityquestion:Isthediffusionofsocialmovementsandmobi-lizationsESpredictableand,ifso,whichmeasurablequantitieshavepredictivepowerWeadoptaspecificversionoftheS-HDSsocialdiffu-sionmodelproposedinDefinition2.
2:ΣSHDS;diffGsc;QX;fqx;Gqxq∈Q;nPar;W;Q;ΛxfgowherethesocialnetworkcommunitygraphGscconsistsofKcommunities(so|Vsc|=K),connectedtogetherwithanErdos-Renyirandomgraphtopology,withcommunitysizedrawnfromapowerlawdistribution[36];eachcontinuoussystemPcs,q:dx=fq(x,p)dt+Gq(x,p)dw,q∈Qisgivenbythemeso-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,Xs2arestatesetscorrespondingtoglobal(affectingasignificantfractionofthepopulation)andlocal(remainingconfinedtoasmallfractionofthepopulation)movementevents,respectively.
WethenemployAlgorithmA2.
2iterativelytosearchforadefin-itionforCSS=X0*P0whichensuresthattheprobabil-itiesofreachingXs1andXs2fromX0*P0aresufficientlydifferenttoyieldanESpredictablesituation.
WeusetwomodelsoftheformΣS-HDS,diffforthisana-lysis,correspondingtothetwodefinitionsforthecon-tinuoussystemΣHandΣB.
EachmodeliscomposedofK=10communitiesconnectedtogetherwithanErdos-Renyirandomgraphtopology.
(UsingdifferentrealizationsoftheErdos-Renyirandomgraphdoesnotaffecttheconclusionsreportedbelow.
)ColbaughandGlassSecurityInformatics2012,1:18Page23of26http://www.
security-informatics.
com/content/1/1/18ESpredictabilityanalysisyieldstwomainresults.
First,boththeintra-communityandinter-communitydynam-icsexhibitthresholdbehavior:smallchangesineithertheintra-community"infectivity"orinter-communityinteractionratearoundtheirthresholdvaluesleadtolargevariationsintheprobabilitythatthemovementwillpropagate"globally".
Morequantitatively,forthediffu-sionmodelΣS-HDS,diffwithcontinuoussystemdynamicsΣH,thresholdbehaviorisobtainedwhenvarying1.
)thegeneralizedreproductionnumberR=β/δ2and2.
)therateλatwhichinter-communityinteractionsbetweenindividualstakeplace.
Thusinorderforasocialmove-menttopropagatetoasignificantfractionofthepopula-tion,thethresholdconditionsR≥1andλ≥λ0mustbesatisfiedsimultaneously.
AnanalogousconclusionholdswhenΣHisreplacedwiththediffusionmodelΣBintheS-HDSrepresentation.
Thisfindingisreminiscentofandextendswell-knownresultsforepidemicthresholdsindiseasepropagationmodels[1].
ThisthresholdbehaviorisillustratedintheplotatthetoprightofFigure7,whichshowsthewayprob-abilityofglobalpropagationincreaseswithinter-communityinteractionratewhentheintra-communitydiffusionissufficientlyinfective(i.
e.
,R≥1).
Theprobabilitieswhichmakeupthisplotrepre-sentsprovably-correct(upperbound)estimatescom-putedusingTheorem2andAlgorithmA2.
1.
Asimilarthresholdresponseisobservedwhenvaryingintra-communityinfectivityR,providedtheinter-communityinteractionratesatisfiesλ≥λ0.
Import-antly,theinter-communityinteractionthresholdλ0isseentobequitesmall,indicatingthatevenafewlinksbetweennetworkcommunitiesenablesrapiddif-fusionofthemovementtootherwisedisparateregionsofthesocialnetwork.
Thisresultsuggeststhatausefulpredictorofmovementactivityinagivencommunityisthelevelofmovementactivityamongthatcommunity'sneighborsinGsc.
λλ0R0λ0R0λ0R0Figure7Sampleresultsfromsocialdiffusionpredictabilitystudy.
Cartoonattopleftillustratesthesetupfortheinter-communityinteractionstudy,highlightingtheparametervaluesR0=1andλ0whichquantifyintra-andinter-communitypropagationthresholds;plotattoprightshowsclassicthresholddependenceofglobalpropagationprobabilityoninter-communityinteractionintensityλ.
Plotsinbottomrowdepictthewayglobalpropagationprobabilityincreaseswiththenumberofcommunitiesacrosswhichafixedsetofinnovatingseedsaredistributed(plotsatleftandrightshowcascadeprobabilitiesformulti-scalemodelspossessingΣHandΣBmeso-scaledynamics,respectively).
ColbaughandGlassSecurityInformatics2012,1:18Page24of26http://www.
security-informatics.
com/content/1/1/18ThesecondmainESpredictabilityresultcharacterizesthewayprobabilityofglobalpropagationvarieswiththenumberofnetworkcommunitiesacrosswhichafixedsetof"seed"movementmembersisdistributed.
Toquantifythisdependence,thesocialmovementmodelΣS-HDS,diffisinitializedsothatasmallfractionofindivi-dualsinthepopulationaremovementmembersandtheremainderofthepopulationconsistssolelyofpotentialmembers.
WethenvarythewaythisinitialseedsetofmovementmembersisdistributedacrosstheKnetworkcommunities,atoneextremeassigningallseedstothesamecommunityandattheotherspreadingtheseedsuniformlyoverallKcommunities.
Foreachdistributionofseedmovementmembers,theprobabilityofglobalmovementpropagationiscomputedusingTheorem2andAlgorithmA2.
1.
Otherthaninitializationstrategy,themodelisspecifiedexactlyasintheprecedinganalysis.
TheresultsofthisportionoftheESpredictabilityassessmentaresummarizedinthetwoplotsatthebottomofFigure7.
Itisseenthatforbothchoicesofmeso-scalesocialmovementdynamics,ΣHandΣB,theprobabilityofglobalmovementpropagationincreasesapproximatelylinearlywiththenumberofnetworkcom-munitiesacrosswhichthefixedsetofseedmembersisdistributed(herethenumberofinitialmembersissettoonepercentofthetotalpopulation).
CompetinginterestsTheauthorsdeclarethattheyhavenocompetinginterests.
Authors'contributionsRCandKGdesignedtheresearch,RCdevelopedthetheoreticalresults,RCandKGdevelopedthecomputationalalgorithmsandperformedtheanalysis,andRCwrotethepaper.
Allauthorsreadandapprovedthefinalmanuscript.
AcknowledgementsThisresearchwassupportedbytheU.
S.
DepartmentofDefense,theU.
S.
DepartmentofHomelandSecurity,TheBoeingCompany,andtheLaboratoryDirectedResearchandDevelopmentprogramatSandiaNationalLaboratories.
FruitfuldiscussionsregardingaspectsofthisworkwithCurtisJohnsonofSandiaNationalLaboratories,PaulOrmerodofVolterraPartners,andAnneKaoofBoeingaregratefullyacknowledged.
Authordetails1AnalyticsandCryptographyDepartment,SandiaNationalLaboratories,Albuquerque,USA.
2CyberResearchandEducationDepartment,SandiaNationalLaboratories,Albuquerque,USA.
Received:14December2011Accepted:7September2012Published:15November2012References1.
RAnderson,RMay,InfectiousDiseasesofHumans(OxfordUniversityPress,England,1992)2.
ERogers,DiffusionofInnovations,5thedn.
(FreePress,NewYork,2003)3.
D.
DellaPorta,M.
Diani,SocialMovement,Secondthedn.
(Blackwell,Oxford,England,2006)4.
DEasley,JKleinberg,Networks,Crowds,andMarkets:ReasoningAboutaHighlyConnectedWorld(CambridgeUniversityPress,England,2010)5.
AMoghadam,TheGlobalizationofMartyrdom:AlQaeda,SalafiJihad,andtheDiffusionofSuicideAttacks(JohnsHopkinsUniversityPress,Baltimore,2008)6.
DMyers,POliver,Theopposingforcesdiffusionmodel:theinitiationandrepressionofcollectiveviolence.
DynamicsofAsymmetricConflict1,164–188(2008)7.
GAckermanetal.
,Anticipatingrareevents:Canactsofterror,useofweaponsofmassdestruction,orotherhighprofileactsbeanticipated(USDoDWhitePaper,WasshingtonDC,2008).
November8.
AKrueger,JMaleckova,Attitudesandaction:publicopinionandtheoccurrenceofinternationalterrorism.
Science325,1535–1536(2009)9.
ABergin,SOsman,CUngerer,NYasin,CounteringinternetradicalizationinSoutheastAsia(AustralianStrategicPolicyInstitute,Sydney,2009).
March10.
HChen,CYang,MChau,SLi(eds.
),IntelligenceandSecurityInformatics,LectureNotesinComputerScience(Springer,Berlin,2009)11.
Proc.
2010IEEEInternationalConferenceonIntelligenceandSecurityInformatics(Vancouver,BC,Canada,2010).
May12.
S.
O'Brien,Crisisearlywarninganddecisionsupport:contemporaryapproachesandthoughtsonfutureresearch.
InternationalStudiesReview12,87–104(2010)13.
MWard,BGreenhill,KBakke,Theperilsofpolicybyp-value:predictingcivilconflict.
J.
PeaceResearch47,363–375(2010)14.
WWalls,Modelingmoviesuccesswhen'nobodyknowsanything':conditionalstable-distributionanalysisoffilmreturns.
J.
CulturalEconomics29,177–190(2005)15.
MSalganik,PDodds,DWatts,Experimentalstudyofinequalityandunpredictabilityinanartificialculturalmarket.
Science311,854–856(2006)16.
RColbaugh,KGlass,Predictabilityandpredictionofsocialprocesses,inProc.
4thLakeArrowheadConferenceonHumanComplexSystems,ed.
by(Arrowhead,CA,2007).
April17.
RColbaugh,KGlass,"PredictiveanalysisforsocialprocessesI:Multi-scalehybridsystemmodeling,andII:Predictabilityandwarninganalysis"(Proc.
2009IEEEMulti-ConferenceonSystemsandControl,SaintPetersburg,Russia,2009)18.
RColbaugh,KGlass,POrmerod,"Predictabilityof'unpredictable'culturalmarkets"(Proc.
105thAnnualMeetingoftheAmericanSociologicalAssociation,Atlanta,GA,2010).
August19.
SAsur,BHuberman,Predictingthefuturewithsocialmedia(Proc.
IEEE/WIC/ACMInternationalConferenceonWebIntelligenceandIntelligentAgentTechnology,Toronto,Ontario,Canada,2010).
September20.
SGoel,JHofman,SLahaie,DPennock,DWatts,PredictingconsumerbehaviorwithWebsearch.
Proc.
NationalAcademyofSciencesUSA107,17486–17490(2010)21.
JBollen,HMao,XZeng,"Twittermoodpredictsthestockmarket"(arXivpreprint,2010).
October22.
ATumasjan,TSprenger,PSandner,IWelpe,"PredictingelectionswithTwitter:What140charactersrevealaboutpoliticalsentiment"(Proc.
4thInternationalAAAIConferenceonWeblogsandSocialMedia,Washington,DC,2010).
May23.
RColbaugh,KGlass,"Earlywarninganalysisforsocialdiffusionevents"(Proc.
2010IEEEInternationalConferenceonIntelligenceandSecurityInformatics,Vancouver,BCCanada,2010)24.
RColbaugh,KGlass,JGosler,"Someintelligenceanalysisproblemsandtheirgraphformulations".
J.
IntelligenceCommunityResearchandDevelopment.
PermanentlyavailableonIntelink,Paper315(2010)25.
NChristakis,JFowler,Socialnetworksensorsforearlydetectionofcontagiousoutbreaks.
PLoSONE5,e12948(2010)26.
KLerman,THogg,"UsingstochasticmodelstodescribeandpredictsocialdynamicsofWebusers"(arXivpreprint,2010)27.
RColbaugh,KGlass,"Detectingemergingtopicsandtrendsviapredictiveanalysisof'meme'dynamics"(Proc.
2011AAAISpringSymposiumSeries,PaloAlto,CA,2011)28.
R.
Colbaugh,K.
Glass,"Proactivedefenseforevolvingcyberthreats"(Proc.
2011IEEEInternationalConferenceonIntelligenceandSecurityInformatics,Beijing,China,2011)29.
AUhrmacher,DDegering,BZeigler,"Discreteeventmulti-levelmodelsforsystemsbiology",inTrans.
ComputationalSystemsBiology,(Springer,NewYork,2005).
LNBI338030.
HEl-Samad,SPrajna,APapachristodoulou,JDoyle,MKhammash,Advancedmethodsandalgorithmsforbiologicalnetworksanalysis.
Proc.
IEEE94,832–853(2006)ColbaughandGlassSecurityInformatics2012,1:18Page25of26http://www.
security-informatics.
com/content/1/1/1831.
AJulius,AHalasz,MSakar,HRubin,VKumar,GPappas,Stochasticmodelingandcontrolofbiologicalsystems:thelactoseregulationsystemofEscherichiacoli.
IEEETrans.
AutomaticControl53,51–65(2008)32.
JLygerosetal.
,StochastichybridmodelingofDNAreplicationacrossacompletegenome.
Proc.
NationalAcademyofSciencesUSA105,12295–12300(2008)33.
CYuan,XMao,JLygeros,Stochastichybriddelaypopulationdynamics:well-posedmodelsandextinction.
J.
BiologicalDynamics3,1–21(2009)34.
MBujorianu,JLygeros,MBujorianu,"Towardageneraltheoryofstochastichybridsystems",e-print(UniversityofTwente,TheNetherlands,2008).
March35.
JDoyle,MCsete,"Architecture,constraints,andbehavior".
Proc.
NationalAcademyofSciencesUSA(inpress)36.
MNewman,Thestructureandfunctionofcomplexnetworks.
SIAMReview45,167–256(2003)37.
THastie,RTibshirani,JFriedman,TheElementsofStatisticalLearning,2ndedn.
(Springer,NewYork,2009)38.
JLeskovec,LBackstrom,JKleinberg,"Meme-trackingandthedynamicsofthenewscycle"(Proc.
15thACMInternationalConferenceonKnowledgeDiscoveryandDataMining,Paris,France,2009)39.
RColbaugh,KGlass,SANDReport:Predictionofsocialdynamicsviasocialmediaanalytics(SandiaNationalLaboratories,Albuquerque,2011)40.
MNewman,Modularityandcommunitystructureinnetworks.
Proc.
NationalAcademyofSciencesUSA103,8577–8582(2006)41.
SCarmi,SHavlin,SKirkpatrick,YShavitt,EShir,AmodelofInternettopologyusingthek-shelldecomposition.
Proc.
NationalAcademyofSciencesUSA104,11150–11154(2007)42.
AVATARhttp://www.
sandia.
gov/avatar/,accessedJuly201043.
KGlass,RColbaugh,Webanalyticsforsecurityinformatics(Proc.
EuropeanIntelligenceandSecurityInformaticsConference,Athens,Greece,September,2011)44.
MemeTrackerhttp://memetracker.
org,accessedJanuary201045.
MBradley,PLang,"AffectivenormsforEnglishwords(ANEW):Stimuli,instructionmanual,andaffectiveratings"(TechnicalReportC1,UniversityofFlorida,UnitedStates,1999)46.
GRamakrishnan,AJadhav,AJoshi,SChakrabarti,PBhattacharyya,QuestionansweringviaBayesianinferenceonlexicalrelations(Proc.
AnnualMeetingoftheAssociationforComputationalLinguistics,Sapporo,Japan,July,2003)47.
RIS/RIPEhttp://data.
ris.
ripe.
net/,lastaccessedJuly201148.
KGlass,RColbaugh,MPlanck,AutomaticallyidentifyingthesourcesoflargeInternetevents(Proc.
IEEEInternationalConferenceonIntelligenceandSecurityInformatics,Vancouver,Canada,May,2010)49.
PHedstrom,Explainingthegrowthpatternsofsocialmovements,UnderstandingChoice,ExplainingBehavior(OsloUniversityPress,Norway,2006)50.
PHedstrom,RSandell,CStern,Mesolevelnetworksandthediffusionofsocialmovements:thecaseoftheSwedishSocialDemocraticParty.
AmericanJ.
Sociology106,145–172(2000)51.
LBettencourt,ACintron-Arias,DKaiser,CCastillo-Chavez,Thepowerofagoodidea:quantitativemodelingofthespreadofideasfromepidemiologicalmodels.
PhysicaA364,513–536(2006)52.
JCandia,KMazzitello,Massmediainfluencespreadinginsocialnetworkswithcommunitystructure.
J.
StatisticalMechanics7,P07007(2008)53.
HKushner,StochasticStabilityandControl(AcademicPress,NY,1967)54.
APapachristodoulou,Personalcommunication(May,2008)55.
PParrilo,StructuredSemidefiniteProgramsandSemialgebraicGeometryMethodsinRobustnessandOptimization,PhDdissertation(CaliforniaInstituteofTechnology,UnitedStates,2000)56.
SOS/TOOLShttp://www.
cds.
caltech.
edu/sostools/,accessedJuly2007doi:10.
1186/2190-8532-1-18Citethisarticleas:ColbaughandGlass:Earlywarninganalysisforsocialdiffusionevents.
SecurityInformatics20121:18.
Submityourmanuscripttoajournalandbenetfrom:7Convenientonlinesubmission7Rigorouspeerreview7Immediatepublicationonacceptance7Openaccess:articlesfreelyavailableonline7Highvisibilitywithintheeld7RetainingthecopyrighttoyourarticleSubmityournextmanuscriptat7springeropen.
comColbaughandGlassSecurityInformatics2012,1:18Page26of26http://www.
security-informatics.
com/content/1/1/18