Nakao Akihiro, Wang Yufeng
Nanjing University of Posts and Telecommunications, Nanjing 210003, China.
IEEE Trans Syst Man Cybern B Cybern. 2010 Apr;40(2):493-504. doi: 10.1109/TSMCB.2009.2027221. Epub 2009 Sep 1.
In overlay networks, the interplay between network structure and dynamics remains largely unexplored. In this paper, we study dynamic coevolution between individual rational strategies (cooperative or defect) and the overlay network structure, that is, the interaction between peer's local rational behaviors and the emergence of the whole network structure. We propose an evolutionary game theory (EGT)-based overlay topology evolution scheme to drive a given overlay into the small-world structure (high global network efficiency and average clustering coefficient). Our contributions are the following threefold: From the viewpoint of peers' local interactions, we explicitly consider the peer's rational behavior and introduce a link-formation game to characterize the social dilemma of forming links in an overlay network. Furthermore, in the evolutionary link-formation phase, we adopt a simple economic process: Each peer keeps one link to a cooperative neighbor in its neighborhood, which can slightly speed up the convergence of cooperation and increase network efficiency; from the viewpoint of the whole network structure, our simulation results show that the EGT-based scheme can drive an arbitrary overlay network into a fully cooperative and efficient small-world structure. Moreover, we compare our scheme with a search-based economic model of network formation and illustrate that our scheme can achieve the experimental and analytical results in the latter model. In addition, we also graphically illustrate the final overlay network structure; finally, based on the group selection model and evolutionary set theory, we theoretically obtain the approximate threshold of cost and draw the conclusion that the small value of the average degree and the large number of the total peers in an overlay network facilitate the evolution of cooperation.
在覆盖网络中，网络结构与动态特性之间的相互作用在很大程度上仍未得到充分探索。在本文中，我们研究个体理性策略（合作或背叛）与覆盖网络结构之间的动态协同进化，即节点的局部理性行为与整个网络结构的出现之间的相互作用。我们提出一种基于进化博弈论（EGT）的覆盖拓扑进化方案，以将给定的覆盖网络驱动到小世界结构（高全局网络效率和平均聚类系数）。我们的贡献主要体现在以下三个方面：从节点局部交互的角度出发，我们明确考虑节点的理性行为，并引入一个链路形成博弈来刻画在覆盖网络中形成链路的社会困境。此外，在进化链路形成阶段，我们采用一个简单的经济过程：每个节点在其邻域中保留一条与合作邻居的链路，这可以略微加快合作的收敛速度并提高网络效率；从整个网络结构的角度来看，我们的仿真结果表明，基于EGT的方案可以将任意覆盖网络驱动到一个完全合作且高效的小世界结构。而且，我们将我们的方案与一种基于搜索的网络形成经济模型进行比较，并表明我们的方案可以实现后一种模型中的实验和分析结果。此外，我们还以图形方式说明了最终的覆盖网络结构；最后，基于群体选择模型和进化集理论，我们从理论上得出成本的近似阈值，并得出结论：覆盖网络中平均度较小且总节点数较多有利于合作的进化。
