1、Disconnected-connected network transitions and phase separation driven by coevolving dynamics由耦合演化驱动的网络结构与相分离行为 Pak Ming Hui 许伯铭许伯铭 Department of PhysicsThe Chinese University of Hong Kong香港中文大学香港中文大学 物理系物理系In collaborations with:Oliver Grser 顾皓森(CUHK)Chen XU许晨(Soochow University)CCCN 2010(15-17 Oct
2、ober 2010,Suzhou)Dynamic models(SIS,SIR,opinion formation),or games(PD,SG,)NETWORKS(group dynamics)NEW FEATURES?COMPUTERSIMULATIONSTHEORIESREAL SYSTEMSCOEVOLVINGSYSTEMTwo dynamics influencing one anotherTo read more on the topic in general:Perc and Szolnoki,Biosystems 99,109(2009)Szabo and Fath,Phys
3、ics Reports 446,97(2007)Gross and Blasius,J.R.Soc.Interface 5,259(2008)Dynamic models(SIS,SIR,opinion formation),or games(PD,SG,)NETWORKS(group dynamics)NEW FEATURES?COMPUTERSIMULATIONSTHEORIESREAL SYSTEMSCOEVOLVINGSYSTEMTwo dynamics influencing one anotherThe general ideas have been applied to:Adap
4、tive epidemic models:e.g.,Gross et al.,PRL 96,208701(2006);Shaw and Schwartz,PRE 71,066101(2008)Opinion formation models:e.g.,Vazquez et al.,PRL 100,108702(2008);Nardini et al.,PRL 100,158701(2008)Wars and human conflicts:e.g.Bohorquez et al.,Nature 462,911(2009);Zhao et al.,PRL 103,148701(2009)Dyna
5、mic models(SIS,SIR,opinion formation),or games(PD,SG,)NETWORKS(group dynamics)NEW FEATURES?COMPUTERSIMULATIONSTHEORIESREAL SYSTEMSCOEVOLVINGSYSTEMTwo dynamics influencing one anotherAnd more(from PM Huis group):Modeling of guilds in online games(World of Warcraft)and LA street gangs Zhao et al.,PRE
6、79,066117(2009)Effects of social group dynamics on contagion(YouTube downloads,foreign exchange rates,flu)Zhao et al.,PRE 81,056107(2010)Co-evolving Modeling “Job Hunting Model”An agent looks for a group that he thinks he could contribute A group assess the agent to see if he can contribute to the g
7、roup After joining group,agent has a better understanding of the group and assess the group(Can I really contribute?)If agent is unhappy with the group,agent will quit!If agent feels OK with the group,he still wants to find a better group If he finds a better group,he will switch group;if not,he sta
8、ys Team formation model(agents with skills that complement each other)against kinship(buddy-buddy)modelMain Empirical Results from Data Sets:Online guilds and Offline street gangsWow Guild size distribution N(s)for all guilds in 3 servers S1,S2,S3(put together)in Oct 2005 Total players:76686Cumulati
9、ve size distributionInset:Churn vs guild sizeCumulative gang size distribution of LA Street gangs with all ethnicity put togetherTotal members:5214Small data setsSteps even in N(ss)Data from:Ducheneaut and Yee(Palo Alto Research Center)WoW Empirical data(blue)&Team-formation Modeling Results(red)Cum
10、ulative guild size distribution and Churn vs guild sizeN from data is taken as input(data in Oct 2005)N=76686N=24033N=24477N=28176Cumulative gang size distributionData(blue)and team-formation modeling results(red)Dashed line(kinship/”buddy-buddy”model)N=5214See APS News item(June 2009)http:/physics.
11、aps.org/synopsis-for/10.1103/PhysRevE.79.066117for an news item reporting our workHere,we use an adaptive snowdrift game as an example to illustrate-how coupled dynamics influence each other and explicit coupled transitions in the form of disconnected to connected network transition(structural)highl
12、y cooperative to lower cooperative population(functional)segregated phase to mixed-character phase(population characteristics)frozen to continously evolving(dynamical)-how one could approach such problems analytically-what to look at in formulating a theory and its validity-what a proper theory can
13、inform us about the properties of the system Snowdrift Game(SDG)1nTwo drivers heading home in opposite directionsnBlocked by a snowdriftnEach driver:2 actions/characters C(“cooperate”)=to shovel the snowdrift D(“not-to-operate”)OR“defect”(in prisoners dilemma language)=not to shovel vScenario:1 J.M.
14、Smith,Evolution and the Theory of Games(Cambridge Univ.Press 1982).In other contexts,the“game of chicken”.b=reward of getting homec=cost(doing the laborious job of shoveling)bc0Player 1Player 2CC,2 2ccbb|,RRD ,b bc|,TSD ,bbc|,ST ,0 0|,PPSucker payoffPlayer 2CCDDn b c 0 defines the snowdrift game It
15、follows that T R S P(defines SDG),2 2ccbb|,RR ,b bc|,TS ,bbc|,ST ,0 0|,PPPlayer 1n Showing only the payoffs of player 1:CCDDRTSP Snowdrift Game:T R S P Prisoners Dilemma:T R P S Difficult to measure payoffs accurately SDG is an alternative to PD in studying cooperation in competing populationsn Ofte
16、n,use one parameter r to represent the payoffs:T R S P(=0)1+r 1 1-r 0(0 r no incentive to make any changes Thus,dissatisfaction comes in only when opponent plays D=switch character or rewiring S=expected payoff received payoff=P(,C)-P(,D)We define a parameter,called the disappointment S,when opponen
17、t plays D asSwitching Probability P S P=SIf not switched,cut link and rewire to someone else.(Here,we take =1/2)Node-driven dynamicsCD-links AND DD-links are the active links(possible system evolution)PC,switch=r/2PD,switch=(1-r)/2PC,rewire=1-r/2PD,rewire=(1+r)/2Probabilities for the 4 adaptive even
18、ts that lead to system evolution“Dissatisfied Adaptive Snowdrift Game”(DASG)How does the level of cooperation(long time behavior)vary with r?How does dissatisfaction behavior alter network structure?Time evolution?Constructing analytic approaches?New features hinted at by theory?Initially,we have 50
19、%cooperators randomly distributed in the lattice.The results indicate two regimes with different features.What if the initial frequency of cooperators is varied?uThis figure gives us a message of the extent of cooperation.u But how the different characters connected?Definition:fC=number of C-nodes /
20、number of total nodeslCClCDlDD Initially,we have 10%cooperators randomly distributed in the lattice.The symbols show a transition behavior at some value of r.Can we obtain the features of the previous figure based on the link densities?uThis figure gives us a message of link distributions on network
21、.CDCD Definition:lxy=number of XY-links /number of total linksDisconnectedConnectedDisconnected-connected network transition accompanying a C/D phase-separated and mixed phase transitionRef:Graser,Xu,Hui,EPL 87,38003(2009)Low-r PhaseHigh-r PhaseLevel of cooperationNetwork StructureDynamicsPopulation
22、High Disconnected FrozenSegregatedLow ConnectedEvolvingMixed-characterr=0.1r=0.9fci=0.1fci=0.9(a)&(b):Initial frequency of cooperation fci=0.(c)&(d):For cost-to-benefit ratio r=0.3.More simulation results trajectories showing time evolution Definition(x-axis):NC-NDm=NTrajectory of Systems(time evolu
23、tion)Constructing a theoryRecall:The number of Cooperators(i.e.,NC or fC or m)determines the fraction of characters on nodes.The number of links(i.e.,LCCor lCCor ml)indicates,on average,how links are distributed between nodes.lCClCDlDClDDCDWhen an adaptive event occurs,local environment of updating
24、node changes,leading to corresponding changes in variables such as node/link numbers.Write down the change of the variables in general(recall:CD and DD are active links):Probability that the node in action takes on character n=C or DConditional probability of having links around a node of character
25、nProbability that among links there are nd linksFraction of nd-links among links(prob.of picking an active link)Probability that an event E occurs(switch/rewire)under the condition that the node is of character n？()Remark:Could start from node-level equations and construct equations for global quant
26、itiesDefinitions:C DM=NC-ND,Ml=LCC-LDDD CCD-cut&rewireDD-cut&rewire-22 00CC-CDDD-CD-1+ND/NNC/N-CC-CDDD+CD NC/NNC/NMLCDMlCDND/NNC/NTo illustrate the different ways of mean-field treatment,we write down one of the equations based on():Here,we choose fC,lCD,lCC as independent variables.denotes an avera
27、ge over a type of nodes(subscript).Note:These averages distinguish different types of nodes.Need to treat C and D nodes separately.To proceed,we first decouple the quantity of the form We treat the first moments using global mean values,i.e.,Aim:To close the set of equations There are several ways t
28、o treat the second moments.(1)Simple Squared Closure(SSC)simplest approximationSecond moments assumed to be equal to the first moments squared.Physical Picture:Every C node has identical neighborhood,every D node has identical neighborhood;but C and D could have different neighborhoods(thus ignored
29、fluctuations).A closed set of 3 equations does it work?Lines:From closed set of equations using SSC and iterate them in timeCapture all key features qualitatively,including non-monotonic behavior!Ref(DASG):Graser,Xu,Hui,EPL 87,38003(2009)Theory captures the disconnected-connected network transition
30、and phase separation fci=0.1(squares),0.7(circles),0.9(triangles)How about the trajectories?Line shows the locations of endpoints as calculated by iterating closed set of equations to long time.With initial frequency of cooperation fc=0.Time evolution of degreesfci=0.8 and r=0.8fci=0.1Steady state m
31、ean degreesLines are results of equations,symbols are simulation resultsNote the necessity in treating C and D nodes separatelyWhile simple theory captures all the main features,there are discrepancies between simple theory and numerical results!Can we improve the theory?Better moment closure scheme
32、s?Alternative ways to treat the second moments and to close the equations(2)Binomial distribution treatment(BINO)Picture:Assume that C-node(or D-node)of degree has a binomial distribution of links CD.Comparing with SSC treatment,we have extra terms in BINO treatment!(3)Aside:Keeling-Eames treatment(
33、KE)Fluctuations are included in a way that assumes the variance equals to the mean.Comparing with SSC treatment,there is an extra term in KE treatmentA moment closure method used by Gross et al.in PRL 96,208701(2006)for an adaptive SIS model,based on Keeling and Eames PNAS 99,13330(2002)and J.R.Soc.
34、Interface 2,295(2005)for epidemic modelsBut KE approximation turns out to be a bad approximation for the present model.SSC treatment(dashed lines)BINO treatment(solid lines)Worked much better in the disconnected state Comparing simple and modified theories with numerical resultsRef:Oliver Graser,PhD
35、 Dissertation(CUHK 2010)Fixed Point AnalysisFixed Points:Nc=LCC=Lcd=0Obvious candidate:LCC=/2,Lcd=0(no dissatisfied links disconnected state)Occurs for small r,large fciFixed-point analysis is carried out based on MF equations using a binomial approximationFixed point vs iteration of equations start
36、ing from some initial condiitionsTaking advantage of having a set of mean-field equationsFixed Point AnalysisFixed Point:Nc=LCC=Lcd=0Obvious candidate:LCC=/2,Lcd=0(no dissatisfied links)Sticky fixed point(disconnected state)!Occurs for small r,large fciConfirmed in simulations Other type of fixed po
37、ints with Lcd 0(connected and mixed phase state)exists for larger r.What about small r?Fixed Point AnalysisFixed Point:Nc=LCC=Lcd=0Obvious candidate:LCC=/2,Lcd=0(no dissatisfied links)Sticky fixed point!Occurs for small r,large fciCan be confirmed in simulations.Other type of fixed point with Lcd0(c
38、onnected mixed-phase state)exists for larger r.What about small r?Roots of mean-field equations indicate a fixed point of connected mixed-phase state also exists for small r!If exists,this is an UNUSUAL state,as cooperation DROPS as TEMPTATION to be uncooperative DROPS!Why not found in simulations?U
39、nstable or stable fixed point?Stability of fixed pointA fixed point is attractive if trajectories starting in a small environment are drawn towards it.Linearization of the system and looking at eigenvalues of Jacobian Matrix.If the Jacobi-Matrix has only(real)negative eigenvalues,then the fixed poin
40、ts are attractive.The fixed point has negative eigenvalues(two are identical,approaching zero as r drops,and one becomes increasingly negative),thus it is stable!How can we realize the connected mixed-phase in small r?Realizing the unusual stateWhy not found in simulations?Related to choice of initi
41、al condition!Trace system from r=1.Equilibrate Record configuration(use it as next initial condition)Reduce rObserved connected mixed-phase state for lower values of r(but basin shrinks as r decreases)System freezes at r=0.05 Unusual connected state can indeed be realized by tracing r gradually,usin
42、g as initial condition the steady state at slightly larger r This is the origin of the non-monotonic behavior observed near transitionDynamic models(SIS,SIR,opinion formation),or games(PD,SG,)NETWORKS(group dynamics)NEW FEATURES?COMPUTERSIMULATIONSTHEORIESREAL SYSTEMSCOEVOLVINGSYSTEMTwo dynamics inf
43、luencing one anotherFinal Remarks Used an adaptive snowdrift game to illustrate the richness in co-evolving dynamical systems and the approaches to analytic formalism Approach that works in one problem(e.g.,SIS)may not work in another(SG)Interesting results follow from having a closed set of equatio
44、ns.Fixed-point analysis shows a disconnected state competing with a connected state with a shrinking attractive basin.An unusual state of irrational character is revealed first by theory and then confirmed by numerical simulations by properly choosing the initial conditions.-The End-The End-Suppleme
45、ntary pages on:Decoupling schemes Q:Which approximation(Bino vs KE)is better for our model?Lets look at the quantityand the probability of picking a neighbor of the opposite type(for C or D nodes)is directly related to the mean field equations:it is the expectation value of LCC for the event of a CD switch.It vanishes in the two limits of P.Appendix A:KE vs Binowhich ranges from 0 to 1KE(doesnt give proper behavior)BINOSSC at least behaves properlysimulationr=0.1r=0.5
