摘要
复杂网络理论是近年来复杂系统科学研究中最活跃的分支之一。大量实证性研究表明,许多真实网络(比如因特网,万维网、电力网、生物网、社会合作网等等)具有许多相似的结构特性,如小世界和(或)无标度特性。此外,不同类型的无标度网络常常表现明显的度相关性:社会合作网络中的中心节点倾向于相互连接,表现同配度混合模式;而技术网络和生物网络中的中心节点倾向于选择小度节点作为邻居,呈现异配度混合模式。这些网络结构特性对于运行其上的动力学行为有着重要影响。
研究竞争个体之间的合作涌现机制一直是经济、生物乃至信息领域学者关心的问题,博弈理论为此提供了一个理论框架。网络演化博弈把个体看作节点,个体之间的联系通过网络的边描述,研究网络结构与策略演化之间的相互作用关系。而机制设计(又称为逆博弈理论)关注于设计合理的协议,引导个体的自私行为使系统的全局目标达得最优。机制设计近期被应用于网络路由协议设计中,可以把超付作为一种结构特性研究。
本文重点探讨复杂网络上的演化博弈和超付特性,包括小世界、无标度和度相关特性对网络演化博弈行为的作用,以及小世界网络和无标度网络中的超付特性,主要内容和研究成果如下:
从个体动态组织角度,本文首先研究了小世界网络中的合作行为。研究表明在节点具有相同度的随机正则网络中,对于囚徒困境博弈,交换边概率的增加促进了网络中合作行为的涌现,这是由于个体通过结成大的合作簇有效抵御背叛者的入侵所致;然而对于雪堆博弈,由于合作者很难形成大的合作簇,所以当损益比超过一定阈值后随机正则网络中的合作频率低于均匀混合状态的均衡频率。而对于Watts-Strogatz(WS)小世界网络模型,通过随机重连机制使WS网络的度分布变得异质,网络中的合作水平得到了有效提升。
基于一个扩展的雪堆博弈,本文进一步研究了可调度异质性的无标度网络上的合作行为。研究表明越异质的无标度网络具有越高的合作水平。这是由于具有大度的中心节点在稳定状态坚持合作策略,随着异质性的提高,中心节点可以带动更多的邻居成为合作者,促使了无标度网络中稳定策略个体的涌现。
本文还研究了度相关性对网络博弈行为的影响。研究发现不论对于囚徒困境博弈还是雪堆博弈,由于同配网络的中心节点倾向于相互相连,减弱了合作中心节点之间的相持能力,使背叛者容易入侵中心节点;然而在异配网络中,中心节点之间沟通的减弱使它们更容易坚持初始策略不变,所以合作行为不容易在异配网络中湮灭。
通过研究小世界网络中的超付特性,本文发现WS小世界网络中的平均超付高于最近邻网络和完全随机网络,这是由于WS小世界网络中的长程边拥有过高的超付。因此,通过在原始长程边附近移入新的长程边,可以有效减小长程边的超付。
最后,本文研究了可调度异质性的无标度网络中的节点超付分布。研究表明节点超付与度之间呈现幂律关系,随着异质性的增加,超付-度指数是减小的。在度指数小于3的无标度网络中节点超付的分布也是幂律的。通过把节点收取的超付除以它传递数据包的数目,可以得到传递每个数据包的平均收益。仿真表明异质网络的中心节点的每包平均收益高于小度节点的收益,而随着网络变得均质,大度与小度节点之间的每包平均收益的差异是减小的。
Complex networks theory is one of the most active branches in the field of complex system science. It is widely recognized that many real-world networks, such as Internet, the World Wide Web, power grids, biological networks, social collaboration networks, and etc, share many similar structural features including the small-world and (or) scale-free phenomena. Besides, various scale-free networks exhibit degree correlations: social collaboration networks usually display the assortative degree-mixing pattern, where hubs tend to interconnect with each other. While in the technological and biological networks, hubs are willing to select those neighbors having smaller degrees, by which the networks are disassortatively mixed. These structural features play crucial roles on the dynamical behaviors.
Investigating the emerging mechanisms of cooperation emerging among competitive individuals holds a very long history with strong interest as the hot topic in the fields of economics, biology and information science, and the game theory provides a theoretical framework for it. The networked evolutionary game theory focuses on the interaction between the network structures and the evolution of strategies, where the individuals are located on vertices and the interaction among individuals are described by edges of the network. On the other hand, the mechanism design, the so-called inverse game theory, aims at designing protocols to induce these selfish individuals’behaviors to achieve the optimization of the whole systematic object. Recently, the mechanism design was applied to design the routing protocol and the overpaymen as a structural property was studied.
In this paper, we investigate the roles of the small-world, scale-free and degree correlation features on the networked evolutionary games, and study the structural property of overpayment in networks with small-world and scale-free properties. The main content and contributions of this dissertation are summarized as follows:
From the viewpoint of the individuals' dynamical organization, we first investigate the cooperative behaviors on small-world networks. We observe that, for a random regular graph where all vertices have the same number of neighbors, the increase of the swapping edge probabilities promotes the emergence of cooperative behaviors in the Prisoner’s delimma game, mainly due to the fact that the individuals protect themselves from the invasion of defectors by composing larger clusters at the steady state. While for the snowdrift game, since the cooperators are difficult to form large clusters, the cooperators’frequencies of random regular graphs are less than the equilibrium frequency in well mixed populations when the cost-to-benefit ratio is larger than the threshold value. Moreover, since the mechanism of rewring edges makes the Watts-Strogatz(WS) small-world networks become heterogeneous, the cooperative behaviors are enhanced.
We further study the cooperative behaviors on the networks with different degree heterogeneities on an extended snowdrift game model. Our findings show that the cooperative behaviors are promoted rapidly when the network becomes more heterogeneous, because the hubs which have high degrees are found to hold on their cooperation strategy at the steady state, and influence more neighbors to become cooperators. Therefore, the heterogeneity promotes the emergence of individuals with steady strategies.
Furthermore, we investigate how the degree-mixing pattern affects the emergence of cooperation in the networked game. Our study shows that not only for the Prisoner's dilemma game, but also for the snowdrift game, when a network becomes assortative mixing by degree, the hubs tend to interconnect each other closely, destroying the sustainability among cooperators and promoting the invasion of defectors. However, in disassortative networks, the absence of close connections among hubs protects the cooperative hubs to hold on their initial strategies from extinction.
With extensive investigations of the overpayment on small-world networks, we find that the average overpayment of WS small-world networks is larger than those of nearest neighbor networks and completely random graphs. This is because those shortcuts in WS small-world networks obtain very high overpayments. Therefore, we propose a new method by rewiring some new edges beside those original shortcuts, through which the overpayments of shortcuts are restrained efficiently.
Finally, we study the distribution of vertex overpayments in scale-free networks with different degree exponents. We find the relation between degree and overpayment is a power-law form, and the overpayment-degree exponent decrease as the network becomes more heterogeneous. The overpayment distribution is also in a power-law form for the scale-free networks whose degree exponents are less than 3. The bonus per packet of a vertex is obtained through dividing the overpayment of this vertex by its carried traffic. Our investigation shows that a vertex with larger degree will charge more than that with smaller degree for transmitting per packet in heterogeneous networks, and the difference between those vertices with different degrees becomes minor when the network becomes homogeneous.
引文
[1] Albert R, Barabási A L, Statistical mechanics of complex networks, Reviews of Modern Physics, 2002, 74(1): 47-97.
[2] Dorogovtsev S N, Mendes J F F, Evolution of networks, Advances in Physics, 2002, 51(4):1079-1187.
[3] Newman M E J, The structure and function of complex networks, SIAM Review, 2003, 45(2):167-256.
[4] Wang X F,Chen G R, Complex networks: Small-world, scale-free and beyond, IEEE Circuits Syst. Mag., 2003, 3(1):6-20.
[5] Boccaletti S, Latora V, Moreno Y, etc., Complex networks: Structure and dynamics, Physics Reports, 2006, 424(4-5):175-308.
[6] Watts D J,Strogatz S H, Collective dynamics of 'small-world' networks, Nature, 1998, 393(6684):440-442.
[7] Barabási A L,Albert R, Emergence of scaling in random networks, Science, 1999, 286(5439):509-512.
[8] Von Neumann J,Morgenstern O, Theory of Games and Economic Behavior, Princeton University Press, 1944.
[9] Smith J M, Evolution and the Theory of Games, Cambridge University Press, 1982.
[10] Papadimitriou C H, Algorithms, games, and the internet, in Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 2001, 749-753.
[11] Nisan N,Ronen A, Algorithmic mechanism design, Games and Economic Behavior, 2001(1-2):166-196.
[12] Weibull J W, Evolutionary Game Theory, MIT Press, 1995.
[13] Axelrod R, The Evolution of Cooperation, New York: Basic Books, 1984.
[14] Nisan N, Roughgarden T, Tardos E, etc., Algorithmic Game Theory, Cambridge University Press, 2007.
[15] McCain R A, Game Theory: A Non-Technical Introduction to the Analysis of Strategy, Thomson South-Western, 2004.
[16] Nash J F, Equilibrium points in n-person games, Proceedings of the National Academy of Sciences, 1950, 36(1):48-49.
[17] Schelling T C, The Strategy of Conflict, Cambridge, MA: Harvard University Press., 1960.
[18] Fudenberg D,Levine D K, The Theory of Learning in Games, Cambridge, MA: MIT Press., 1998.
[19] Smith J M,Price G R, The logic of animal conflict, Nature, 1973, 246(5427):15-18.
[20] Nowak M A, Sasaki A, Taylor C, etc., Emergence of cooperation and evolutionary stability in finite populations, Nature, 2004, 428(6983), 646-650.
[21] Taylor P D,Jonker L, Evolutionary stable strategies and game dynamics,Mathematical Biosciences, 1978, 40:145-156.
[22] SzabóG,Fath G, Evolutionary games on graphs, Physics Reports, 2007, 446(4-6):97-216.
[23] Skyrms B, The Stag Hunt and the Evolution of Social Structure, Cambridge Univ. Press, 2003.
[24] Wilkinson G S, Reciprocal food sharing in the vampire bat, Nature, 1984, 308(5955):181–184.
[25] Clutton-Brock T H, O'Riain M J, Brotherton P N M, etc., Selfish sentinels in cooperative mammals, Science, 1999, 284(5420), 1640-1644.
[26] Hauert C, De Monte S, Hofbauer J, etc., Volunteering as Red Queen mechanism for cooperation in public goods games, Science, 2002, 296(5570), 1129-1132.
[27] Sinervo B,Lively C M, The rock-paper-scissors game and the evolution of alternative male strategies, Nature, 1996, 380(6571):240-243.
[28] Sinervo B, Heulin B, Surget-Groba Y, etc., Models of density-dependent genic selection and a new rock-paper-scissors social system, American Naturalist, 2007, 170(5):663–680.
[29] Nowak M A, Evolutionary dynamics, Harvard University Press, 2006.
[30] Nowak M A, Five rules for the evolution of cooperation, Science, 2006, 314(5805):1560-1563.
[31] Hamilton W D, The genetical evolution of social behaviour. I, Journal of Theoretical Biology, 1964, 7(1):1:16.
[32] Hamilton W D, The genetical evolution of social behaviour. II, Journal of Theoretical Biology, 1964, 7(1):17-52.
[33] Nowak M A,Sigmund K, Tit for tat in heterogeneous populations, Nature, 1992, 355(6357):250-253.
[34] Nowak M A,Sigmund K, A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner's Dilemma game, Nature, 1993, 364(6432):56-58.
[35] Nowak M A,Sigmund K, Evolution of indirect reciprocity, Nature, 2005, 437(7063):1291-1298.
[36] Sigmund K, Hauert C, Nowak M A, Reward and punishment, Proceedings of the National Academy of Sciences of the United States of America, 2001, 98(19):10757-10762.
[37] Sober E,Wilson D S, Unto Others: The Evolution and Psychology of Unselfish Behavior, Harvard University Press, 1998.
[38] Traulsen A,Nowak M A, Evolution of cooperation by multilevel selection, Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(29):10952-10955.
[39] Nowak M A,May R, Evolutionary games and spatial chaos, Nature, 1992, 359:826-829.
[40] Diestel R, Graph Theory (Second Edition), Springer-Verlag, Heidelberg, 2000.
[41] SzabóG,Toke C, Evolutionary prisoner's dilemma game on a square lattice, Physical Review E, 1998, 58(1):69-73.
[42] SzabóG, Vukov J, Szolnoki A, Phase diagrams for an evolutionary prisoner'sdilemma game on two-dimensional lattices, Physical Review E, 2005, 72(4):047107.
[43] Vukov J, SzabóG, Szolnoki A, Cooperation in the noisy case: Prisoner’s dilemma game on two types of regular random graphs, Physical Review E, 2006, 73(6):067103.
[44] Vukov J, SzabóG, Szolnoki A, Evolutionary prisoner's dilemma game on Newman-Watts networks, Physical Review E, 2008, 77(2):026109.
[45] Perc M, Coherence resonance in a spatial prisoner's dilemma game, New Journal of Physics, 2006, 8:22.
[46] Perc M, Transition from Gaussian to Levy distributions of stochastic payoff variations in the spatial prisoner's dilemma game, Physical Review E, 2007, 75(2):022101.
[47] Perc M,Szolnoki A, Social diversity and promotion of cooperation in the spatial prisoner's dilemma game, Physical Review E, 2008, 77(1):011904.
[48] Guan J Y, Wu Z X, Huang Z G, etc., Promotion of cooperation induced by nonlinear attractive effect in spatial Prisoner's Dilemma game, Europhysics Letters, 2006, 76(6):1214-1220.
[49] Wu Z-X, Xu X-J, Wang Y-H, Prisoner's Dilemma Game with Heterogeneous Influential Effect on Regular Small-World Networks, Chinese Physics Letters, 2006, 23(3):531-534.
[50] Wu Z-X, Xu X-J, Huang Z-G, etc., Evolutionary prisoner’s dilemma game with dynamic preferential selection, Physical Review E, 2006, 74(2):021107.
[51] Szolnoki A,SzabóG, Cooperation enhanced by inhomogeneous activity of teaching for evolutionary Prisoner's Dilemma games, Epl, 2007, 77(3):30004.
[52] Szolnoki A,Perc M, Coevolution of teaching activity promotes cooperation, New Journal of Physics, 2008, 10:043036.
[53] Ohtsuki H, Hauert C, Lieberman E, etc., A simple rule for the evolution of cooperation on graphs and social networks, Nature, 2006, 441(7092):502-505.
[54] Langer P, Nowak M A, Hauert C, Spatial invasion of cooperation, Journal Of Theoretical Biology, 2008, 250(4):636-643.
[55] Doebeli M,Hauert C, Models of cooperation based on the Prisoner's Dilemma and the Snowdrift game, Ecology Letters, 2005, 8(7):748-766.
[56] Hauert C,Doebeli M, Spatial structure often inhibits the evolution of cooperation in the snowdrift game, Nature, 2004, 428(6983):643-646.
[57] Challet D,Zhang Y C, Emergence of cooperation and organization in an evolutionary game, Physica A, 1997, 246(3-4):407-418.
[58] Wang W X, Ren J, Chen G R, etc., Memory-based snowdrift game on networks, Physical Review E, 2006, 74(5):056113.
[59] Sysi-Aho M, Saramaki J, Kertesz J, etc., Spatial snowdrift game with myopic agents, European Physical Journal B, 2005, 44(1):129-135.
[60] Erdos P,Renyi A, On random graphs, Publicationes Mathematicae, 1959, 6:290-297.
[61] Barrat A,Weigt M, On the properties of small-world network models, European Physical Journal B, 2000, 13(3):547-560.
[62] Newman M E J,Watts D J, Renormalization group analysis of the small-world network model, Physics Letters A, 1999, 263(4-6):341-346.
[63] Hauert C,SzabóG, Game theory and physics, American Journal Of Physics, 2005, 73(5):405-414.
[64] Santos F C, Rodrigues J F, Pacheco J M, Epidemic spreading and cooperation dynamics on homogeneous small-world networks, Physical Review E, 2005, 72(5):056128.
[65] Abramson G,Kuperman M, Social games in a social network, Physical Review E, 2001, 63(3):0309011.
[66] Ren J, Wang W X, Qi F, Randomness enhances cooperation: A resonance-type phenomenon in evolutionary games, Physical Review E, 2007, 75(4):045101.
[67] Szolnoki A, Perc M, SzabóG, Diversity of reproduction rate supports cooperation in the prisoner's dilemma game on complex networks, Eur. Phys. J. B, 2008, 61(4), 505-509.
[68] Kim B J, Trusina A, Holme P, etc., Dynamic instabilities induced by asymmetric influence: Prisoners' dilemma game in small-world networks, Physical Review E, 2002, 66(2):021907.
[69] Fu F, Liu L H, Wang L, Evolutionary prisoner's dilemma on heterogeneous Newman-Watts small-world network, European Physical Journal B, 2007, 56(4):367-372.
[70] Tang C L, Wang W X, Wu X, etc., Effects of average degree on cooperation in networked evolutionary game, European Physical Journal B, 2006, 53(3):411-415.
[71] Chen X J,Wang L, Promotion of cooperation induced by appropriate payoff aspirations in a small-world networked game, Physical Review E, 2008, 77(1):017103.
[72] Tomassini M, Luthi L, Giacobini M, Hawks and Doves on small-world networks, Physical Review E, 2006, 73(1):016132.
[73] Kleinberg J M, Navigation in a small world - It is easier to find short chains between points in some networks than others., Nature, 2000, 406(6798):845-845.
[74] Shang L H, Li X, Wang X F, Cooperative dynamics of snowdrift game on spatial distance-dependent small-world networks, European Physical Journal B, 2006, 54(3):369-373.
[75] Zhong L X, Zheng D F, Zheng B, etc., Networking effects on cooperation in evolutionary snowdrift game, Europhysics Letters, 2006, 76(4):724-730.
[76] Xu C, Hui P M, Zheng D F, Networking effects on evolutionary snowdrift game in networks with fixed degrees, Physica A, 2007, 385(2):773-780.
[77] Faloutsos M, Faloutsos P, Faloutsos C, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, 1999,29(4):251-262.
[78] Jeong H, Mason S P, Barabási A L, etc., Lethality and centrality in protein networks, Nature, 2001, 411(6833):41-42.
[79] Jeong H, Tombor B, Albert R, etc., The large-scale organization of metabolicnetworks, Nature, 2000, 407(6804):651-654.
[80] Dorogovtsev S N,Mendes J F F, The shortest path to complex networks, cond-mat/0404593, 2004:1-25.
[81] Barabási A L, Albert R, Jeong H, Mean-field theory for scale-free random networks, Physica A, 1999, 272(1-2):173-187.
[82] Chung F,Lu L, The average distances in random graphs with given expected degrees, Proceedings of the National Academy of Sciences, 2002, 99(25):15879-15882.
[83] Fronczak A, Fronczak P, Holyst J A, Mean-field theory for clustering coefficients in Barabási-Albert networks, Physical Review E, 2003, 68(4),046126.
[84] Holme P,Kim B J, Growing scale-free networks with tunable clustering, Physical Review. E, 2002, 65(2):026107.
[85] Dorogovtsev S N, Mendes J F F, Samukhin A N, Structure of growing networks with preferential linking, Physical Review Letters, 2000, 85(21):4633.
[86] Goh K I, Kahng B, Kim D, Universal behavior of load distribution in scale-free networks, Physical Review Letters, 2001, 87(27):2787011.
[87] Li X,Chen G R, A local-world evolving network model, Physica A, 2003, 328(1-2):274-286.
[88] Krapivsky P L,Redner S, Organization of growing random networks, Physical Review E, 2001, 6306(6):066123.
[89] Newman M E J, Assortative mixing in networks, Physical Review Letters, 2002, 89(20): 2087011.
[90] Ravasz E, Somera A L, Mongru D A, etc., Hierarchical organization of modularity in metabolic networks, Science, 2002, 297(5586):1551-1555.
[91] Newman M E J, The structure of scientific collaboration networks, Proceedings of the National Academy of Sciences, 2001, 98(2):404-409.
[92] Song C M, Havlin S, Makse H A, Self-similarity of complex networks, Nature, 2005, 433(7024):392-395.
[93]汪小帆.,李翔.,陈关荣.,复杂网络理论及其应用,清华大学出版社, 2006.
[94] Santos F C,Pacheco J M, Scale-free networks provide a unifying framework for the emergence of cooperation, Physical Review Letters, 2005, 95(9):098104.
[95] Santos F C, Pacheco J M, Lenaerts T, Evolutionary dynamics of social dilemmas in structured heterogeneous populations, Proceedings of the National Academy of Sciences, 2006, 103(9):3490-3494.
[96] Santos F C, Rodrigues J F, Pacheco J M, Graph topology plays a determinant role in the evolution of cooperation, Proceedings of the Royal Society B, 2006, 273(1582):51-55.
[97] Santos F C,Pacheco J M, A new route to the evolution of cooperation, Journal Of Evolutionary Biology, 2006, 19(3):726-733.
[98] Gomez-Gardenes J, Campillo M, Floria L M, etc., Dynamical Organization of Cooperation in Complex Topologies, Physical Review Letters, 2007,98(10):108103.
[99] Poncela J, Gomez-Gardenes J, Floria L M, etc., Robustness of cooperation in the evolutionary prisoner's dilemma on complex networks, New Journal of Physics, 2007, 9:184.
[100] Assenza S, Gomez-Gardenes J, Latora V, Enhancement of cooperation in highly clustered scale-free networks, arXiv:0801.2146, 2008.
[101] Pusch A, Weber S, Porto M, Impact of topology on the dynamical organization of cooperation in the prisoner's dilemma game, Physical Review E, 2008, 77(3): 036120.
[102] Wu Z X, Guan J Y, Xu X J, etc., Evolutionary prisoner's dilemma game on Barabási-Albert scale-free networks, Physica A, 2007, 379(2):672-680.
[103] Ren. J, Wang. W-X, Yan. G, etc., Emergence of cooperation induced by preferential learning, axXiv /0603007, 2006.
[104] Szolnoki A, Perc M, Danku Z, Towards effective payoffs in the prisoner's dilemma game on scale-free networks, Physica A, 2008, 387(8-9):2075-2082.
[105] Wang W-X, Lu J, Chen G, etc., Phase transition and hysteresis loop in structured games with global updating, Physical Review E, 2008, 77(4): 046109.
[106] Holme P, Trusina A, Kim B J, etc., Prisoners' dilemma in real-world acquaintance networks: Spikes and quasiequilibria induced by the interplay between structure and dynamics, Physical Review E, 2003, 68(3):030901.
[107] Fu F, Chen X J, Liu L H, etc., Social dilemmas in an online social network: The structure and evolution of cooperation, Physics Letters A, 2007, 371(1-2):58-64.
[108] Rong Z H, Li X, Wang X F, Roles of mixing patterns in cooperation on a scale-free networked game, Physical Review E, 2007, 76(2):027101.
[109] Zimmermann M G, Egui?luz V M, Miguel M S, Coevolution of dynamical states and interactions in dynamic networks, Physical Review E, 2004, 69(6):065102.
[110] Zimmermann M G,Egui?luz V M, Cooperation, social networks, and the emergence of leadership in a prisoner's dilemma with adaptive local interactions, Physical Review E, 2005, 72(5):056118.
[111] Santos F C, Pacheco J M, Lenaerts T, Cooperation prevails when individuals adjust their social ties, Plos Computational Biology, 2006, 2(10):1284-1291.
[112] Pacheco J M, Traulsen A, Nowak M A, Active linking in evolutionary games, Journal of Theoretical Biology, 2006, 243(3):437-443.
[113] Pacheco J M, Traulsen A, Nowak M A, Coevolution of strategy and structure in complex networks with dynamical linking, Physical Review Letters, 2006, 97(25):258103.
[114] Pacheco J M, Traulsen A, Ohtsuki H, etc., Repeated games and direct reciprocity under active linking, Journal of Theoretical Biology, 2008, 250(4):723-731.
[115] Fu F, Chen X J, Liu L G, etc., Promotion of cooperation induced by the interplay between structure and game dynamics, Physica A, 2007,383(2):651-659.
[116] Fu F, Hauert C, Nowak M A, etc., Reputation-based partner choice promotes cooperation in social networks, Physical Review E, 2008, 78(2): 026117.
[117] Li W, Zhang X M, Hu G, How scale-free networks and large-scale collective cooperation emerge in complex homogeneous social systems, Physical Review E, 2007, 76(4):045102.
[118] Biely C, Dragosits K, Thurner S, The prisoner's dilemma on co-evolving networks under perfect rationality, Physica D, 2007, 228(1):40-48.
[119] Vainstein M H,Arenzon J J, Disordered environments in spatial games, Physical Review E, 2001, 6405(5):051905.
[120] Vainstein M H, Silva A T C, Arenzon J J, Does mobility decrease cooperation? Journal of Theoretical Biology, 2007, 244(4):722-728.
[121] Ren. J, Wang. W-X, Wu. X, etc., Interplay between evolutionary game and network structure: the coevolution of social net, cooperation and wealth, arXiv:physics/0605250, 2006.
[122] Poncela J, Gomez-Gardenes J, Floria L M, etc., Complex cooperative networks from evolutionary preferential attachment, arXiv.org:0803.1773, 2008.
[123] Ohtsuki H, Nowak M A, Pacheco J M, Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs, Physical Review Letters, 2007, 98(10):108106.
[124] Ohtsuki H, Pacheco J M, Nowak M A, Evolutionary graph theory: Breaking the symmetry between interaction and replacement, Journal of Theoretical Biology, 2007, 246(4), 681-694.
[125] Wu Z X,Wang Y H, Cooperation enhanced by the difference between interaction and learning neighborhoods for evolutionary spatial prisoner's dilemma games, Physical Review E, 2007, 75(4):041114.
[126] Hauert C, Traulsen A, Brandt H, etc., Via freedom to coercion: The emergence of costly punishment, Science, 2007, 316(5833):1905-1907.
[127] McNamara J M, Barta Z, Fromhage L, etc., The coevolution of choosiness and cooperation, Nature, 2008, 451(7175):189-192.
[128] Santorelli L A, Thompson C R L, Villegas E, etc., Facultative cheater mutants reveal the genetic complexity of cooperation in social amoebae, Nature, 2008, 451(7182):1107-U7.
[129] Herrmann B, Thoni C, Gachter S, Antisocial punishment across societies, Science, 2008, 319(5868):1362-1367.
[130] Dreber A, Rand D G, Fudenberg D, etc., Winners don't punish, Nature, 2008, 452(7185):348-351.
[131] SzabóG,Hauert C, Evolutionary prisoner's dilemma games with voluntary participation, Physical Review E, 2002, 66(6), 062903.
[132] SzabóG, Szolnoki A, Izsak R, Rock-scissors-paper game on regular small-world networks, Journal of Physics A, 2004, 37(7): 2599-2609.
[133] Wu Z X, Xu X J, Chen Y, etc., Spatial prisoner's dilemma game with volunteering in Newman-Watts small-world networks, Physical Review E,2005, 71(3),037103.
[134] Reichenbach T, Mobilia M, Frey E, Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games, Nature, 2007, 448(7157):1046-1049.
[135] SzabóG,Hauert C, Phase transitions and volunteering in spatial public goods games, Physical Review Letters, 2002, 89(11):118101.
[136] Brandt H, Hauert C, Sigmund K, Punishment and reputation in spatial public goods games, Proceedings of the Royal Society B, 2003, 270(1519):1099-1104.
[137] Guan J Y, Wu Z X, Wang Y H, Effects of inhomogeneous activity of players and noise on cooperation in spatial public goods games, Physical Review E, 2007, 76(5):056101.
[138] Vickrey W, Counterspeculation, auctions, and competitive sealed tenders, Journal of Finance, 1961, 16(1):8-37.
[139] Clarke E H, Multipart pricing of public goods, Public Choice, 1971, 11(1):17-33.
[140] Groves T, Incentives in teams, Econometrica, 1973, 44(4):617-631.
[141] Feigenbaum J,Shenker S, Distributed Algorithmic Mechanism Design: Recent Results and Future Directions, Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2002:1-13.
[142] Feigenbaum J, Papadimitriou C, Sami R, etc., A BGP-based mechanism for lowest-cost routing, Distributed Computing, 2005, 18(1):61-72.
[143] Anderegg L,Eidenbenz S, Ad hoc-VCG: A Truthful and Cost-Efficient Routing Protocol for Mobile Ad hoc Networks with Selfish Agents, Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM, 2003:245-259.
[144] Archer A,Tardos E, Frugal path mechanisms, ACM Transactions on Algorithms, 2007, 3(1):1219948.
[145] Mihail M, Papadimitriou C, Saberi A, On certain connectivity properties of the internet topology, Journal of Computer and System Sciences, 2006, 72(2):239-251.
[146] Karger D,Nikolova E, VCG overpayment in random graphs, Proceedings of the 45th IEEE Conference on Decision and Control 2006, 2006:2831-2836.
[147] Elkind E, True costs of cheap labor are hard to measure: Edge deletion and VCG payments in graphs, Proceedings of the ACM Conference on Electronic Commerce, 2005:108-116.
[148] Czumaj A,Roner A, On the expected payment of mechanisms for task allocation, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2004:98-106.
[149] Kumar R,Latapy M, Preface, Theoretical Computer Science, 2006, 355(1):1-5.
[150] Motter A E, Matias M A, Kurths J, etc., Dynamics on complex networks and applications, Physica D, 2006, 224(1-2): Vii-Viii.
[151] Amaral L A N,Uzzi B, Complex systems - A new paradigm for the integrativestudy of management, physical, and technological systems, Management Science, 2007, 53(7):1033-1035.
[152] Abdallah C T,Tanner H G, Complex networked control systems: Introduction to the special section, IEEE Control Systems Magazine, 2007, 27(4):30-32.
[153] Motter A E,Toroczkai Z, Introduction: Optimization in networks, Chaos, 2007, 17(2):026101.
[154] Barabási A L, The architecture of complexity, IEEE Control Systems Magazine, 2007, 27(4):33-42.
[155] Maslov S,Sneppen K, Specificity and stability in topology of protein networks, Science, 2002, 296(5569):910-913.
[156] Motter A E,Lai Y C, Cascade-based attacks on complex networks, Physical Review E, 2002, 66(6):065102.
[157] Pastor-Satorras R,Vespignani A, Epidemic spreading in scale-free networks, Physical Review Letters, 2001, 86(14):3200-3203.
[158] Nishikawa T, Motter A E, Lai Y C, etc., Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize? Physical Review Letters, 2003, 91(1):014101.
[159] Lee S,Kim Y, Coevolutionary dynamics on scale-free networks, Physical Review E, 2005, 71(5):057102.
[160] Taylor P D,Day T, Behavioural evolution - Cooperate with thy neighbour? Nature, 2004, 428(6983):611-612.
[161] Amaral L A N, Barrat A, Barabási A L, etc., Virtual Round Table on ten leading questions for network research, European Physical Journal B, 2004, 38(2):143-145.
[162] Maslov S, Sneppen M, Zaliznyak A, Detection of topological patterns in complex networks: correlation profile of the internet, Physica A, 2004, 333(1-4):529-540.
[163] Pastor-Satorras R, Vazquez A, Vespignani A, Dynamical and correlation properties of the Internet, Physical Review Letters, 2001, 87(25):258701.
[164] Xulvi-Brunet R,Sokolov I M, Reshuffling scale-free networks: From random to assortative, Physical Review E, 2004, 70(6):066102.
[165] Xulvi-Brunet R,Sokolov I M, Changing correlations in networks: Assortativity and dissortativity, in Acta Physica Polonica, Series B, Zakopane, 2005,36(5):1431-1455.
[166] Chavez M, Hwang D U, Martinerie J, etc., Degree mixing and the enhancement of synchronization in complex weighted networks, Physical Review E, 2006, 74(6):066107.
[167] Sorrentino F, di Bernardo M, Cuellar G H, etc., Synchronization in weighted scale-free networks with degree-degree correlation, Physica D, 2006, 224(1-2):123-129.
[168] McDonald D B, Predicting fate from early connectivity in a social network, Proceedings of the National Academy of Sciences, 2007, 104(26):10910-10914.
[169] Hershberger J,Suri S, Vickrey prices and shortest paths: What is an edge worth?in Proceedings in Annual Symposium on Foundations of Computer Science, 2001:252-259.
[170] Hershberger J, Maxel M, Suri S, Finding the k shortest simple paths: A new algorithm and its implementation, ACM Transactions on Algorithms, 2007, 3(4):1290682.
[171] White J G, Southgate E, Thomson J N, etc., The structure of the nervous system of the nematode caenorhabditis elegans, Philos. Trans. R. Soc. London Ser. B, 1986, 314:1-340.
[172] Morita S, Oshio K, Osana Y, etc., Geometrical structure of the neuronal network of Caenorhabditis elegans, Physica A, 2001, 298(3-4):553-561.
[173] Freeman L C, A set of measures of centrality based on betweenness, Sociometry, 1977, 40:35-41.
[174] Brandes U, A faster algorithm for betweenness centrality, Journal of Mathematical Sociology, 2001, 25(2):163-177.
[175] Barthelemy M, Betweenness centrality in large complex networks, European Physical Journal B, 2004, 38(2):163-168.
[176] Goh K I, Oh E, Jeong H, etc., Classification of scale-free networks, Proceedings of the National Academy of Sciences, 2002, 99(20):12583-12588.
[177] SzabóG, Alava M, Kertesz J, Shortest paths and load scaling in scale-free trees, Physical Review E, 2002, 66(2):026101.
[178] Bollobas B,Riordan O, Shortest paths and load scaling in scale-free trees, Physical Review E, 2004, 69(3):036114.
[179] Barthelemy M, Comment on "Universal behavior of load distribution in scale-free networks", Physical Review Letters, 2003, 91(18):189803.
[180] Holme P, Kim B J, Yoon C N, etc., Attack vulnerability of complex networks, Physical Review E, 2002, 65(5):056109.
[181] Motter A E,Lai Y C, Cascade-based attacks on complex networks, Physical Review E, 2002, 66(6):065102.
[182] Motter A E, Cascade control and defense in complex networks, Physical Review Letters, 2004, 93(9):098701.
[183] Girvan M,Newman M E J, Community structure in social and biological networks,Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826.
[184] Newman M E J,Girvan M, Finding and evaluating community structure in networks, Physical Review E, 2004, 69(2):026113.
[185] Newman M E J, Fast algorithm for detecting community structure in networks, Physical Review E, 2004, 69(6),066133.
[186] Clauset A, Newman M E J, Moore C, Finding community structure in very large networks, Physical Review E, 2004, 70(6):066111.
[187] Guimera R,Amaral L A N, Modeling the world-wide airport network, European Physical Journal B, 2004, 38(2): 381-385.
[188] Guimera R, Mossa S, Turtschi A, etc., The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles, Proceedings of the National Academy of Sciences, 2005, 102(22):7794-7799.
[189] Kim D H, Noh J D, Jeong H, Scale-free trees: The skeletons of complex networks, Physical Review E, 2004, 70(4):046126.
[190] Goh K I, Salvi G, Kahng B, etc., Skeleton and fractal scaling in complex networks, Physical Review Letters, 2006, 96(1):018701.
[191] Santos F C, Santos M D, Pacheco J M, Social diversity promotes the emergence of cooperation in public goods games, Nature, 2008, 454(7201):213-216.
[192] Ackermann M, Stecher B, Freed N E, etc., Self-destructive cooperation mediated by phenotypic noise, Nature, 2008, 454(7207):987-990.
[193] Milinski M, Sommerfeld R D, Krambeck H J, etc., The collective-risk social dilemma and the prevention of simulated dangerous climate change, Proceedings Of The National Academy Of Sciences, 2008, 105(7):2291-2294.
[194] Olfati-Saber R, Fax J A, Murray R M, Consensus and cooperation in networked multi-agent systems, Proceedings of the IEEE, 2007, 95(1):215-233.