Simulation III: Adaptive Networks

Simulation III:Adaptive NetworksHiroki Sayamasayama@binghamton.edu

A map of network scienceDynamics on networksTheorydrivenER sDynamics of aptivenetworksOther networkgrowth riatetime seriesanalysisTemporalnetworksDynamical approaches2

Adaptive networks Complex networks whose states andtopologies co-evolve, often oversimilar time scales– Link (node) states adaptively changeaccording to node (link) states3

Adaptive networks in action Many real-world complex systemsshow coupling between “dynamics ofnetworks” and “dynamics on networks”SystemNodesEdgesStates n and death ofcells ecificrelationshipsPopulationSpeciation, invasion,extinction of speciesHuman societyIndividualConversations,social relationshipsSocial, professional,economical,political, culturalstatusesChanges in socialrelationships, entry andwithdrawal ofindividualsCommunication ormation storedand transactedAddition and removalof terminal or hub4nodes

Simulation of Adaptive Networks5

Simulating state-topologycoevolution Technically, very easy; not so muchdifferent from other networksimulation models One minor problem:How to handle topological changeswhile state changes are also ongoing? Asynchronous updating6

Example: Epidemics on adaptivenetworks Original epidemic network model adaptive changes of links A susceptible node that has a link toan infected node will cut the link andreconnect it to another susceptiblenode with probability pc Does the disease stay in the network?7

Exercise Study the effects of rewiringprobability on the disease fixation onand the global network structure ofan initially random social network– In what condition will the disease remainwithin society?– How will the topology of the network bereformed through the diseasepropagation process?8

Example: Adaptive voter model Original voter model adaptive disconnection of links A link that connects two nodes withdifferent opinion states may be cutwith probability pc How will the social network andopinions evolve?9

Exercise Study the effects of the linkdisconnection probability on theconsensus formation in the adaptivevoter model– Plot thefunction– How willchangedfinal number of opinions as aof pcthe topology of the network beby the diversity of opinions?10

Example: Adaptive diffusion model Original diffusion model adaptive disconnection of links Link weights will increase or decreasebased on the similarity/dissimilarityof node states across the links– Conceptually similar to the adaptive votermodel11

Application 1: Corporate merger Modeling and simulation of culturalintegration in two merging firmsacceptanceprobabilityrejection acceptanceYamanoi & Sayama,Comput. Math. Org.Theory 19, 516-537,2013.12

“Within-firm” concentration (w)w 0w 1flatw 5w 10w 30centralized Prob. for node i to become an info source:Pw(i) (i/n)w(i 1, 2, , n; n firm size)13

“Between-firm” concentration (b)b 0.1nearly randomb 1b 3b 5executive-level Prob. for node i to have an inter-firm tie:Pb(i) ci b(ci within-firm closeness centrality of i)14

15

Application 2: Social diffusion andglobal drift Sayama & Sinatra, PRE 91, 032809, 2015Adaptive link weightadjustment:16

17

Exercise Change the rule of link weightadjustment in the adaptive diffusionmodel– E.g., Sayama & Sinatra (2015) Simulate the revised model and seehow the network topology and stateco-evolve18

Theoretical Framework:Generative Network Automata19

Generative network automata Unified representation of dynamics onand of networks using graph rewriting Defined by E, R, I :– E : Extraction mechanism ― When,Where– R : Replacement mechanism ― What– I : Initial configurationSayama, Proc. 1st IEEE Symp. Artif. Life, 2007, pp.214-221.20

GNA rewriting example(a)E(c)(b)R(d)21

Actually, it’s a generative networkautomata-onE :ExtractionmechanismR:Replacementmechanism22

Generality of GNA GNA can uniformly represent in E, R,I :– Conventional dynamical systems models If R always conserves local network topologiesand modifies states of nodes only E.g. cellular automata, Boolean networks– Complex network generation models If R causes no change in local states of nodesand modifies topologies of networks only E.g. small-world, scale-free networks23

twork24

Exhaustive search of rules E samples a node randomly and thenextracts an induced subgraph around it R takes 2-bit inputs (states of the nodeand neighbors) and makes 1-out-of-10decisions22– Total number of possible R’s: 10 10,000 “Rule Number” rn(R) is defined byrn(R) a11 103 a10 102 a01 101 a00 100– aij {0, 1, 9} : Choices of R when state of u is iand local majority state is j25

Exhaustive search of rulesSayama & Laramee, Adaptive Networks, Springer, 2009, pp.311-332.26

Developing Adaptive NetworkModels from Empirical Data27

A challenge How to derive a set ofdynamical rules directlyfrom empirical data ofnetwork evolution? Separation ofextraction andrewriting in GNA helpsthe rule discoveryPestov, Sayama, & Wong, Proc. 9th Intl. Conf.Model. Simul. Visual. Methods, 2012.Schmidt & Sayama, Proc. 4th IEEE Symp. Artif.Life, 2013, pp.27-34.?28

Application to operational networkmodeling Canadian Arctic SAR (Search AndRescue) operational network– Rewriting rules manuallybuilt directly fromactual communicationlog of a December 2008SAR incident– Developed a simulator for hypotheticalSAR operational network development29

30

Automation of model discoveryfrom data: PyGNA Adaptive network rule discovery andsimulation implemented in Python– https://github.com/schmidtj/PyGNA Input: Time series of networksnapshots Output: A GNA model that bestdescribes given data31

32

Extracted subgraphsInput NetworkCompressed NetworkExtracted Subgraphs33

Extraction mechanismidentification: “Where, when” Candidate models provided by user Degree-based preferential selectionState-based preferential selectionDegree & State-based etc Maximum likelihood method Computes likelihood using eachhypothetical model & accumulates loglikelihood over timeChooses the model with maximumlikelihood34

Algorithm35

Replacement mechanismidentification: “What”36

Algorithm37

Results Example: “Degree-state” networks38

InputSimulated39State-basedBarabási-Albert

InputSimulated40Forest FireDegree-State

Barabási-AlbertDegree-stateState-basedForest Fire41

Comparison with other methods PyGNA produces generative modelsusing detailed state-topologyinformation– Capable of generative simulation that isnot available in statistical approaches(e.g., Rossi et al. 2013) PyGNA models extraction andreplacement as explicit functions– More efficient and flexible than graphgrammars (e.g., Kurth et al. 2005)42

What can we do? Prediction? Classification Anomaly detection?43

Summary State-topology coevolution of adaptivenetworks is a promising, unexplored area– Theory-driven approaches Dynamical modeling, exhaustive rule search Applications to social sciences etc.– Data-driven approaches Application to operational network modeling Automatic rule discovery from datahttp://coco.binghamton.edu/NSF-CDI.html44

Additional Topic:Analysis of Adaptive Networks45

How to analyze adaptive networkdynamics? Non-trivial coupling between networkstates and topologies are not easilyhandled in a simple analytical formula But such couplings could be partiallyincorporated in analysis by consideringdensities of node “pairs”46

Pair approximation Considers densities of every pair ofnodes with states & connectivity (inaddition to individual state densities)r00c density of 0 0r01c density of 0 1Describeshow theser11c density of 1 1densitiesr00n density of 0 0change overtimer01n density of 0 1r11n density of 1 147

Example: Adaptive voter model Disconnect of a link:01011010-1 1 Change of an opinion:010001-1 ?00 1 ?(Any other densities affected too?)48

Exercise Complete the number of changes ineach pair density for the adaptivevoter model on a random network Calculate how often each transitionoccurs Make a prediction using the pairapproximation-based model49

Exercise Conduct pair approximation of theadaptive SIS model and study itsdynamics50

FYI: Moment closure Similar approximations are possiblefor densities of higher-order motifs Approximation techniques (includingMFA, PA and higher-order ones) iscalled the “moment closure method”– Predicting the change of a “moment” (r00)would require higher-order “moments”(r000), but you “close” this open chain byassuming r000 r00 r00 / r0 , etc.51

Original epidemic network model adaptive changes of links . al\sampleruns.bmp. Developing Adaptive Network Models from Empirical Data. 27. A challenge How to derive a set of dynamical rules