论文摘要
复杂网络理论是近年来复杂系统科学研究中最活跃的分支之一。大量实证性研究表明,许多真实网络（比如因特网,万维网、电力网、生物网、社会合作网等等）具有许多相似的结构特性,如小世界和（或）无标度特性。此外,不同类型的无标度网络常常表现明显的度相关性:社会合作网络中的中心节点倾向于相互连接,表现同配度混合模式;而技术网络和生物网络中的中心节点倾向于选择小度节点作为邻居,呈现异配度混合模式。这些网络结构特性对于运行其上的动力学行为有着重要影响。研究竞争个体之间的合作涌现机制一直是经济、生物乃至信息领域学者关心的问题,博弈理论为此提供了一个理论框架。网络演化博弈把个体看作节点,个体之间的联系通过网络的边描述,研究网络结构与策略演化之间的相互作用关系。而机制设计（又称为逆博弈理论）关注于设计合理的协议,引导个体的自私行为使系统的全局目标达得最优。机制设计近期被应用于网络路由协议设计中,可以把超付作为一种结构特性研究。本文重点探讨复杂网络上的演化博弈和超付特性,包括小世界、无标度和度相关特性对网络演化博弈行为的作用,以及小世界网络和无标度网络中的超付特性,主要内容和研究成果如下:从个体动态组织角度,本文首先研究了小世界网络中的合作行为。研究表明在节点具有相同度的随机正则网络中,对于囚徒困境博弈,交换边概率的增加促进了网络中合作行为的涌现,这是由于个体通过结成大的合作簇有效抵御背叛者的入侵所致;然而对于雪堆博弈,由于合作者很难形成大的合作簇,所以当损益比超过一定阈值后随机正则网络中的合作频率低于均匀混合状态的均衡频率。而对于Watts-Strogatz（WS）小世界网络模型,通过随机重连机制使WS网络的度分布变得异质,网络中的合作水平得到了有效提升。基于一个扩展的雪堆博弈,本文进一步研究了可调度异质性的无标度网络上的合作行为。研究表明越异质的无标度网络具有越高的合作水平。这是由于具有大度的中心节点在稳定状态坚持合作策略,随着异质性的提高,中心节点可以带动更多的邻居成为合作者,促使了无标度网络中稳定策略个体的涌现。本文还研究了度相关性对网络博弈行为的影响。研究发现不论对于囚徒困境博弈还是雪堆博弈,由于同配网络的中心节点倾向于相互相连,减弱了合作中心节点之间的相持能力,使背叛者容易入侵中心节点;然而在异配网络中,中心节点之间沟通的减弱使它们更容易坚持初始策略不变,所以合作行为不容易在异配网络中湮灭。通过研究小世界网络中的超付特性,本文发现WS小世界网络中的平均超付高于最近邻网络和完全随机网络,这是由于WS小世界网络中的长程边拥有过高的超付。因此,通过在原始长程边附近移入新的长程边,可以有效减小长程边的超付。最后,本文研究了可调度异质性的无标度网络中的节点超付分布。研究表明节点超付与度之间呈现幂律关系,随着异质性的增加,超付-度指数是减小的。在度指数小于3的无标度网络中节点超付的分布也是幂律的。通过把节点收取的超付除以它传递数据包的数目,可以得到传递每个数据包的平均收益。仿真表明异质网络的中心节点的每包平均收益高于小度节点的收益,而随着网络变得均质,大度与小度节点之间的每包平均收益的差异是减小的。