The relation between network assortativity and fragility

Size: px

Start display at page:

Download "The relation between network assortativity and fragility"

胃赫舍里
7 years ago
Views:

1 从囚徒困境谈起 : 网络演化博弈导论 Prisoner s Dilemma and Beyond: An Introduction to Networked Game Theory 荣智海 rongzhh@gmail.com 互联网科学中心, 电子科技大学, 成都 Web Sciences Center, UESTC, Chengdu

2 最后通牒游戏 (Ultimatum Game) 假设有人出 100 块钱, 给你 ( 甲 ) 和另外一个 ( 乙 ) 不认识的人去分, 只要你们两人都同意怎么分这笔钱, 就可以把钱拿走但是, 两个人必须不能交谈或沟通必须遵守如下规定 : 假定你取得了建议权, 你只会有一次提议的机会, 而另外一个人也只有一次机会回答? 同意或? 不同意对方和你一样, 很清楚游戏规则和现金总额, 如果他同意你的提议, 你们就可以分掉这笔钱 ; 如果他不同意, 你们两个人就一文钱都拿不到无论结果如何, 游戏都到此结束, 不会再重来一遍在这种情况下, 你会怎么办呢? 2 2

3 Ultimatum Game( 最后通牒游戏 ) Imagine that somebody offers you HK$100. All you have to do is agree with some other anonymous person on how to share the sum. The rules are strict. The two of you are in separate rooms and cannot exchange information. A coin toss decides which of you will propose how to share the money. Suppose that you are the proposer. You can make a single offer of how to split the sum. The other person (the responder) can say yes or no. The responder also knows the rules and the total amount of money at stake. If her answer is yes, the deal goes ahead. If her answer is no, neither of you gets anything. In both cases, the game is over and will not be repeated. What will you do? 3

4 Altruistic punishment: Ultimatum Game (Güth, Schmittberger & Schwarze, 1982) 100 M-u u experimenter NO OK proposer responder 4 4

5 Experimental results Responder s optimal strategy: accept anything Proposer s optimal strategy: offer the minimum Results: Responders reject offers below 25% with high probability Large degree of variability of offers among societies (26-58%) 5 Paciotti, Brian, Craig Hadley, Christopher Holmes and Monique Borgerhoff Mulder, Grass-roots Justice in Tanzania, American Scientist(2005) Sigmund K, Fehr E, Nowak M A, The economics of fair play, Scientific American(2002) 5

6 阿豺折箭戮力一心阿豺有子二十人阿豺谓曰 : 汝等各奉吾一支箭折之地下俄而命母弟慕利延曰 : 汝取一支箭折之慕利延折之又曰 : 汝取十九支箭折之延不能折阿豺曰 : 汝曹知否? 单者易折, 众则难摧, 戮力一心, 然后社稷可固! 魏书吐谷浑传 6 6

7 合作 : 人类社会的基石 7 Robert Boyd and Sarah Mathew, A Narrow Road to Cooperation, SCIENCE,2007 7

8 Cooperation is ubiquitous in nature! Vampire bats share blood 8 Nowak MA (2012). Why we help. Sci Am 307 (1):

9 白腹鹞原想抓八哥美餐, 被鸟群团团包围逼退 a 一只单打独斗的白腹鹞原想抓只在湖旁休息的八哥鸟饱餐一顿, 不料, 八哥鸟群迅速以庞大的队形包围落单的白腹鹞, 使得它不得不落荒而逃八哥鸟群在面对像猎鹰白腹鹞这样的猛禽捕捉时都有自成一套的 : 它们不仅会利团结防御策略用数量优势将敌人包围起来, 还会不断变换队形 9 9

10 RNA 世界中的合作如果 RNA 分子能够相互作用而不是独立发挥功能, 生命和演化将会更容易实现由组装成核酶的 RNA 片段形成的合作性网络能够竞争过自催化的 RNA 片段合适的策略可以促使不同的 RNA 自组装成核酶, 搭建成合作的超循环回路, 竞争过自催化的 RNA 片段 RNA 分子具有形成更复杂分子的内在能力, 该行为在地球上的生命形成过程的早期已经确立 Vaidya, N. et al. Spontaneous network formation among cooperative RNA replicators, Nature

11 Dave 11 囚徒困境博弈 Prisoner s dilemma game,pdg) Cooperator ( 合作者,C): help others at a cost to himself. Defector ( 背叛者 D): receive the benefits without providing help. Henry C (Reject) D (Confess) C (-2,-2) (-5,-1) D (-1,-5) (-3,-3) (Dave gets, Henry gets) If you opponent plays C: you better play D. If you opponent plays D: you better play D. But, CC is better than DD Dilemma: Despite mutual cooperation being the best, individual tends to DD 11

12 Tit for tat ( 针锋相对, 一还一报,TFT) R. Axelrod and W. D. Hamilton, Science 211, 1390 (1981) TFT: Strategy tournament: TFT winner In general, the best strategies are nice( 善良 ), punishing( 惩罚 ) and forgiving( 宽容 ) 12 12

13 棘鱼 (stickleback) 间的 TFT Milinski M.(1987),TIT FOR TAT in sticklebacks and the evolution of cooperation,nature 13

14 现实生活中的 TFT 衡阳血战怪异现象 : 中日停战相约洗澡双方有一个约定, 就是在下午两三点钟大家都不约而同地停止战斗, 然后在两军阵地中间的池塘洗澡, 各不相干, 也互相不作攻击花是蜜蜂的食物, 而蜜蜂反过来又帮助果树传授花粉, 将树种撒向四处 Peer to peer (BT) 14 14

15 Tit for tat ( 针锋相对, 一还一报,TFT) R. Axelrod and W. D. Hamilton, Science 211, 1390 (1981) TFT: Strategy tournament: TFT winner In general, the best strategies are nice, punishing and forgiving But there exists noise? 15 15

16 宽容的 TFT (Generous tit-for-tat,gtft) Nowak, Sigmund (1992). Tit for tat in heterogeneous population. Nature p: the conditional probability to cooperate after a C q: the conditional probability to cooperate after a D TFT(p,q)=(1,0), GTFT=(1,0.33) 16 16

17 Win stay, lost shift (WSLS, 赢存输去 ) Nowak, Sigmund (1993). A strategy of win-stay, lose-shift that outperforms tit for tat in Prisoner's Dilemma. Nature 364 (p1,p2,p3,p4) is the conditional probabilities to cooperate, after (CC, CD, DC, DD). TFT= (1,0,1,0), GTFT=(1,0.33,1,0.33),WSLS=(1,0,0,1) 17 17

18 Win stay, lost shift (WSLS, 赢存输去 ) Nowak, Sigmund (1993). A strategy of win-stay, lose-shift that outperforms tit for tat in Prisoner's Dilemma. Nature 364 Win stay, lost shift (Pavlov): p l a y e r 2 C D p l a y e r 1 C R S D T P P D : T R x P S R is REWARD for mutual cooperation S SUCKER s payoff T TEMPTATION to defect P PUNISHMENT for mutual defection 18 18

19 Snowdrift game (SG, 雪堆博弈 ) p l a y e r 2 p l a y e r 1 C D c C b, b c 2 D b, 0 C : c o o p e r a t o r ; D : d e f e c t o r c 1, 1 2 b c 1, 1 c 1 r, 0 1, 0 2 b c r=c/(2b-c): cost to benefit of mutual cooperation r p l a y e r 1 p l a y e r 2 C D C 1 S D T 0 C and D coexist: C1-rD The equilibrium frequency of cooperators in SG is 1-r 19 19

20 Chicken game( 胆小鬼博弈 )& Hawk-Dove game( 鹰鸽博弈 ) 一些例子 : 鸟类和动物 ( 蒙哥 ) 的报警冷战中的美苏关系 20 20

21 Game theory models( 几类博弈模型 ) Cooperator( C, 合作者 ): help others at a cost to themselves. Defector( D, 背叛者 ): receive the benefits without providing help. Prisoner s Dilemma (PD) :T>R>P>S, T+S 2R D dominates C : CD p l a y e r 2 21 p l a y e r 1 C D C R S D T P R is REWARD for mutual cooperation S SUCKER s payoff T TEMPTATION to defect P PUNISHMENT for mutual defection 21

22 Game theory models( 几类博弈模型 ) Prisoner s Dilemma (PD) :T>R>P>S, T+S 2R D dominates C : CD Snowdrift game (SG): T>R>S>P, T+S 2R C and D coexist: CrD Stag hunt game (SH, Battle of the sexes): R>T>P>S, C and D are bistable: CD C dominates, CD, R>T>S>P p l a y e r 2 C D 22 p l a y e r 1 C R S D T P 22

23 FEAR p l a y e r 2 2D parameter space p l a y e r 1 C D C 1 S D T 0 GREED (fear) SH (greed) SG (fear&greed) PD Formally, these dilemmas span the parameter space of T (temptation to defect = greed) S (sucker s payoff = fear). Santos, Pacheco, Lenaerts, PNAS 103 (2006)

24 Defectors can diffuse in well-mixed populations Cooperator (C): help others at a cost to himself. Prisoners of the dilemma:when mathematics and biology met on a mountain. Nature 2004 Defector (D): receive the benefits without providing help. Nowak MA (2006). Five rules for the evolution of cooperation. Science 24

25 Natural cooperation( 自然合作 ) Nowak MA (2006). Five rules for the evolution of cooperation. Science The two fundamental principles of evolution are mutation and natural selection. But evolution is constructive because of cooperation. New levels of organization evolve when the competing units on the lower level begin to cooperate. Thus, we might add natural cooperation as a third fundamental principle of evolution beside mutation and natural selection. 25

26 Some rules for evolutions cooperation ( 一些演化合作的规则 ) Nowak MA (2006). Five rules for the evolution of cooperation. Science 26 Kin selection: relative 我会跳进河里去救我的两个弟弟或者八个堂兄 Direct reciprocity: unrelated individuals 如果你帮我挠挠后背, 我也帮你挠 Indirect reciprocity: reputation 为了得到大家的回报, 我现在得多半住别人, 为自己赢得一个好的名声 Group selection 一群相互协作的人往往比一群相会背叛的人更能获得成功 Network reciprocity 26

27 How to understand the complex world? Complex systems NETWORK Barabasi, The Architecture of Complexity, IEEE CONTROL 27 SYSTEMS MAGAZINE,2007/8(Complex Networked Control) s t r u c t r u a l p r o p e r t y, i. e., d e g r e e d e s i t r i b u t i o n, clu sterin g, a s s o r t a t i v i t y... d y n a m i c s, i. e., r o b u s t & f r a g i l e, s y n c h r o n i z a t i o n, sp read in g, h u m a n d y n a m i c s... 27

28 Networked Game Theory M. Nowak and R. May, Nature 1992 Each player x occupying a site on a network playing game with neighbors and obtaining payoff: P x (t) updating rule (replicator dynamics): x select a neighbor y and learn its behavior with probability ~ f(p y (t)-p x (t)) p l a y e r 2 C D p l a y e r 1 C 1 0 D b 0 P D : 1 b 2 b : t h e t e m p t a t i o n t o d e f e c t T h e p a y o f f o f p l a y e r 1 g e ts 28

29 Chaos pattern M. Nowak and R. May, Evolutionary games and spatial chaos,nature A single defector invades the world of cooperators C->C D->D C->D D->C 29

30 Some key quantities to characterize the cooperative behaviors Frequency of cooperators: f C p l a y e r 2 C D p l a y e r 1 C 1 0 D b 0 P D : b 1 b : t h e t e m p t a t i o n t o d e f e c t The extinction threshold of defectors/cooperators: AllC Coexistence with C&D AllD b c1 and b c2 30

31 Cooperation Diffusion on Lattice György Szabó, Jeromos Vukov and Attila Szolnoki: Phase diagrams for an evolutionary prisoner's dilemma game on two-dimensional lattices,pre05 Micro-point: x randomly select a neighbor y If P x <P y,w x (t+1)=w y (t) Overlap triangle (OL) b D 1 2 2b p l a y e r 1 p l a y e r 2 C D C 1 0 D b 0 P D : 1 b 2 C b<

32 Cooperation Diffusion on Lattice(cont) Gyorgy Szabo and G. Fath, "Evolutionary games on graphs," Phys. Rep. 446, Fermi dynamics(noise): W y x 1 1 e x p [ ( P P ) / K ] x y P x <P y P x >P y P x -P y b c1 b c2 C D 32 C+D 32

33 Cooperation Diffusion on Lattice(cont) Gyorgy Szabo and G. Fath, "Evolutionary games on graphs," Phys. Rep. 446, Macro-point W y x 1 1 e x p [ ( P P ) / K ] x y C b c1 b c2 Vukov J, Szabo G, Szolnoki A, Evolutionary prisoner's D dilemma game on Newman-Watts networks, C+D PRE

34 Chaos Pattern of SG Hauert, C., Doebeli, M. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. NATURE 428, , (a) PD: larger,compact cluster (b) SG: cross-like structure 34 34

35 SG on Regular Lattice Hauert, C., Doebeli, M.NATURE Spatial structure eliminates cooperation if r is high? <k>=3 <k>=4 1-r: the equilibrium frequency of cooperation <k>=6 <k>=

36 The Emergence of The New Science of Networks... Heterogenous networks Albert-Laszlo Barabasi Looking for the Next Big Thing 36 36

37 Real-world structural properties The structure and function of complex networks, M. E. J. Newman, SIAM Review (2003)

Cooperative social networks of hunter-gatherers Apicella, Marlowe, Fowler & Christakis, Nature 2012 The social networks of the Hadza, a population of hunter-gatherers in Tanzania,, have important

38 Cooperative social networks of hunter-gatherers Apicella, Marlowe, Fowler & Christakis, Nature 2012 The social networks of the Hadza, a population of hunter-gatherers in Tanzania,, have important properties, including a skewed degree distribution, assortativity, transitivity, reciprocity and homophily. The individuals play the public goods game within each camp. certain elements of social network structure may have been present at an early point in human history. Social networks may thus have contributed to the emergence of cooperation. 38

39 The small-world (SW) phenomenon WS small-world network model Low average path length High clustering coefficient Watts D J, Strogatz S H. Nature,98 Heterogeneous small-world network! 39

40 PD : C D C 1 0 D b 0 PD on small-world networks F.C.Santos, J.F.Rodrigues, J.M.Pacheco, Epidemic spreading and cooperation dynamics on homogeneous small-world networks, PRE 2005 Strategy Update rule(replicator dynamics) Homogeneous small-world networks Player x randomly selects a neighbor y Wx(t+1)=Wy(t) with (Py(t)-Px(t))/bk max Heterogeneous (WS) small-world networks Szolnoki 40 A, Evolutionary prisoner's dilemma game on Newman-Watts networks, PRE08

41 Regular random graph (RRG) p RRG Santos F C, Rodrigues J F, Pacheco J M, Epidemic spreading and cooperation dynamics on homogeneous small-world networks, PRE05. Hauert C,Szabo G, Game theory and physics, American Journal Of Physics

42 Dynamical organization of individuals frequency of cooperators: fc Cooperator clusters: N CC, <S> CC Defector clusters: N DC, <S> DC 42 C cluster

43 Cooperator clusters in RRG Rong Zhihai, Li Xiang, Wang Xiaofan, IEEE ISCAS 09 p RRG, f C, Ncc1 43

44 Road map vs. airline routing map p ( k ) ~ k (nodes: cities links: highways) (nodes: airports links: flights) Each major city has at least one link to the highway system. No cities served by hundreds of highways, uniform Vast majority of airports are tiny nodes, connected by a few hubs (Chicago, Dallas, 44 Denver, Atlanta, NY)

45 Barabási-Albert (BA) Scale-free networks A.-L.Barabási, R. Albert, Emergence of scaling in random networks,science, 1999 (1) Growth: At each time step a new node is added and connected to the m old nodes in the system. (2)Preferential attachment: The probability Π that a new node will be connected to node i is proportional to the degree k i of that node k i ( k ) i k j j m P(k) ~k -3 45

46 Classes of small-world networks L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, PNAS 2000 Scale-free networks: characterized by a vertex connectivity distribution that decays as a power law; Broad-scale networks: characterized by a connectivity distribution that has a power law regime followed by a sharp cutoff; 46 Single-scale networks, characterized by a connectivity distribution with a fast decaying tail.

Scale-free networks enhances the cooperation Santos, F.C., Pacheco, J.M., Scale-Free networks provide a unifying framework for the Emergence of Cooperation.Physical Review Letters 95 (2005) 098104.

47 Scale-free networks enhances the cooperation Santos, F.C., Pacheco, J.M., Scale-Free networks provide a unifying framework for the Emergence of Cooperation.Physical Review Letters 95 (2005) Replicator dynamics: Accumulate payoff: P x (t) Player x randomly selecting a neighbor y If P y (t)>p x (t), x adopts y s strategy with probability (P y (t)-p x (t))/bk max BA PD : C D SG : C D C 1 0 D b 0 C 1 1 r D 1 r 0 47

48 Cooperation diffusion on Scale-free(SF) networks G. Szabó and G. Fath, Evolutionary games on graphs, Phys. Rep. 446, Negative (Positive) feedback mechanism of D-hub(C-hub): Initial one hub(y) is D and others are Cs Hubs have higher payoff than leaves D-hub(y) s behavior: Py fc(y) Px>Py y:dc fc(y) p l a y e r 1 p l a y e r 2 C D C 1 0 D b 0 P D : 1 b 2 C D P y <P x 48

49 Cooperators frequency around D-hubs Sustainability of cooperation Santos,Pacheco, A new route to the evolution of cooperation.journal of Evolutionary Biology 19 (3), (2006). p l a y e r 2 C D p l a y e r 1 C 1 0 D b 0 P D : 1 b 2 In a BA network Starting with a single defector placed in the hub with max degree Replicator dynamics: Player x randomly selecting a neighbor y Adopting probability: (P y (t)-p x (t))/bk max 49

Dynamical organization of cooperation J. Gomez-Gardenes, M. Campillo, L. M. Floria, and Y. Moreno, Dynamical Organization of Cooperation in Complex Topologies, PRL 2007.

50 Dynamical organization of cooperation J. Gomez-Gardenes, M. Campillo, L. M. Floria, and Y. Moreno, Dynamical Organization of Cooperation in Complex Topologies, PRL Pure cooperator/defector (PureC/PureD):the individual who always hold on C/D strategies at the steady state. Fluctuating individuals (Fc):the individual who ever change their strategies 50

51 Degree correlation( 度相关性 ) 51 51

52 Pearson correlation coefficient How to indicate a linear relationship between two variables (a, b)? r ( a, b ) N N i 1 ( a a ) ( b b ) i 1 i 1 i N 2 2 ( a a ) ( b b ) i i i a b a b ( a a ) ( b b ) (, ) b (, ) 1 r ( a, b ) 1 r ( a, b ) 0 r ( a, b ) 0 ( a, b ) a 52 (, ) (, )

53 Degree-Correlation Newman, Assortative mixing in networks. PRL, 2002 Assortative(disassortative) mixing: nodes of high degree mostly have the neighbors of high (Low) degree Degree assortative coefficient: r k j k j k 2 2 k k Assorative (r k >0) Disassortative (r k <0) Uncorrelated (r k 0) 53

54 Xulvi-Sokolov(XS) model Xulvi-Brunet&Sokolov, Reshuffling scale-free networks: From random to assortative. PRE04 At each step, two links connecting four different nodes are randomly chosen. Then, ordering them with respect to their degrees and rewiring as following (assortative): 54

55 Xulvi-Sokolov(XS) model Xulvi-Brunet&Sokolov, Reshuffling scale-free networks: From random to assortative. PRE04 At each step, two links connecting four different nodes are randomly chosen. Then, ordering them with respect to their degrees and rewiring as following (assortative): 55

56 Xulvi-Sokolov(XS) model Xulvi-Brunet&Sokolov, Reshuffling scale-free networks: From random to assortative. PRE04 At each step, two links connecting four different nodes are randomly chosen. Then, ordering them with respect to their degrees and rewiring as following (disassortative): disassortative 56

57 The structure of correlated networks r k 0.3 BA, r k 0 How the degree correlation affects the emergence of cooperation? Zhihai Rong, Xiang Li & Xiaofan Wang (2007) Physical Review E76: r k

58 Uncorrelated vs Assortative networks p l a y e r 2 C D P D-hub >P C-hub for b>1 C D The frequency of cooperators: f C Extinction threshold of cooperation: b c2 p l a y e r 1 P D The temptation to defection b C 1 0 D b 0 : b 1 Based on a BA networks with N=5000 and <k>=4 58

59 How defectors diffusing among SF networks with assortative mixing? The D-hub with 149 neighbors and the C-hub with 147 neighbors share 12,25,43,65 neighbors for r k =0.0,0.1,0.2,0.3 respectively. b=1.5. Defectors are easier to invade hubs as a network becomes assortative! 59

60 Defector & Cooperator distribution N=1000, <k>=4, b=1.5 r k =0.0 r k =0.3 60

61 Dissortative networks Based on a BA networks with N=5000 and <k>=4 61

62 Defector & Cooperator distribution The isolation among hubs protects the cooperative behavior from extinction. r k =-0.3, b=1.5 The initial state The end state 62

63 Prof. McDonald s (Jan.,2008) I am mostly an empiricist but have studied social networks in manakins. I am thinking of doing a paper on how the social network I study is age disassortative... I'm not sure how close my system is to yours, but it is certainly interesting. McDonald D B, Predicting fate from early connectivity in a social network, Proc. of the National Academy of Sciences of the United States of America (PNAS), 2007 Cited>140: F. Fu F, X. J. Chen, L.H. Liu, etc., Phys. Let. A, 2007 A. Pusch, S. Weber & M. Porto, Phys. Rev E, 2008 A.Szolnoki and M. Perc, New Jour of Phys,2008 A. Sih, S. F. Hanser & K. A. McHugh, Behav Ecol Sociobiol,2009 JL Payne, MJ Eppstein,IEEE Tran. Evolutionary computation, 2009 A.Szolnoki and M. Perc, BioSystems,2010 T.Chadefaux & D.Helbing,PLOS One, 2010 J. Tanimoto, Physica A,2010 long-tailed manakin 63

64 学术评价美国加州大学 Andrew Sih 教授 ( 美国动物行为学会前主席 ) 发表在 Behav Ecol Sociobiol (IF=3.179) 在社会网络综述中单独一段介绍申请人的度相关演化博弈的研究斯洛文尼亚的 Perc 教授和匈牙利科学院的 Szolnoki 博士在 BioSystems(IF=1.784) 上的演化博弈综述中指出, 度相关博弈研究解释了为什么异配混合的网络中最大度节点能促进合作涌现 64

65 Conclusion The ultimate understanding of the overall behavior of a complex network must, however, account for its architecture as well as the nature of dynamical processes taking place on such a network. Barabasi, The Architecture of Complexity, IEEE CONTROL SYSTEMS MAGAZINE,2007/8 CHAOUKI T. ABDALLAH & HERBERT G. TANNER, Complex Networked Control Systems, IEEE CONTROL SYSTEMS MAGAZINE,2007/8 65

66 Science Paradigms and Big Data Jim Gray on escience: A Transformed Scientific Method 66

67 三次工业革命第一次工业革命 (176x- 184x): 蒸汽时代煤第二次工业革命 (187x- 191x): 电气时代蒸汽机 / 火车电力 / 石油印刷术电动机 / 内燃机 / 汽车 / 飞机手工机器电报 / 电话力学流水线工业化标准生产电磁学第三次工业革命 (195x- 至今 ): 信息时代可再生能源宇航 / 电脑网络分布 + 协作量子力学 +? 67

68 THANKS! Discussing Rong Zhihai ( 荣智海 ):rongzhh@gmail.com Web Sciences Center, UESTC, Chengdu 68

,,,,, :,, (.,, );, (, : ), (.., ;. &., ;.. &.., ;, ;, ),,,,,,, ( ) ( ),,,,.,,,,,, : ;, ;,.,,,,, (., : - ),,,, ( ),,,, (, : ),, :,

: 周晓虹 : - -., - - - -. :( ), -,.( ),,, -. - ( ).( ) ', -,,,,, ( ).( ),,, -., '.,, :,,,, :,,,, ,,,,, :,, (.,, );, (, : ), (.., ;. &., ;.. &.., ;, ;, ),,,,,,, ( ) ( ),,,,.,,,,,, : ;, ;,.,,,,, (., : - ),,,,