[Python]利用python实现复杂网络的博弈（0）——Introduction

什么是演化博弈？

Evolutionary Gaming Theory（EGT）， 演化博弈，或曰，进化博弈。顾名思义，演化博弈同传统博弈的不同之处就在于，其模仿了类似于生物进化的形式。在一个达尔文式的框架之下，参与博弈的节点通过给定的规则竞争，然后根据结果改变自身的策略。与传统的博弈论不同的是，这里，参加博弈的双方不再是被认为具有超级理性的个体，而是在不断的试错、评估中，动态的调整自己的策略
本次博弈，我们将会尝试构建（指直接调用别人写的库）一个复杂的随机网络，该网络具有两种不同的节点，他们会按照一定的概率选择“分享”与“不分享”两种策略。每个节点会与图中所有的其他节点博弈，计算其收益，并依照一定的概率改变其策略，改变其初值，并查看最终的演变情况与稳定状态。

Reference ：EGT的wiki或者百度百科

关于Networkx

networkx是一个python包，用于创建、操作和研究复杂网络的结构、动态和功能.NetworkX出生于2002年5月。最初的版本是由AricHagberg、DanSchult和PieterSwart在2002年和2003年设计和编写的。第一次公开发布是在2005年4月。

NetworkX提供：

研究社会、生物和基础设施网络结构和动态的工具； 一种适用于多种应用的标准编程接口和图形实现； 为协作性、多学科项目提供快速发展环境； 与现有的数值算法和C、C++和FORTRAN代码的接口； 能够轻松处理大型非标准数据集。

Networkx的相关知识将在下一篇文章里面讲解。

Reference:官方文档

什么是无标度网络？

Scale-free network, 无标度网络。在很多实际模型抽象出的网络当中，节点之间节点度的分布是不均匀的，是依照幂率分布的。少数节点连接着大多数的点，而大多数节点只与很少的点连接。如果用公式描述的话，则是：P(k)∼k−γP(k) \sim k^{-\gamma}P(k)∼k−γ 。意即：在网络中，节点度为kkk 的点所占的比例大致服从k−γk^{-\gamma}k−γ，其中γ\gammaγ的取值大致为2~3之间。不过，关于无标度网络的具体数学特性，学界仍有争论（参考）。

Reference:无标度网络的wiki或者百度百科

无标度网络最为经典的生成算法是Barabási-Albert算法，其大致的内容为：

1.增长：从一个具有 m0m_0m0​ 个节点的联通网络开始，每次引入一个新的节点, 并且连到 mmm 个已经存在的节点上，这里 m<=m0m <= m_0m<=m0​。

2.优先连接：一个新的节点与一个已经存在的节点 iii 相连的概率 www 与节点 iii 的度 kik_iki​ 之间的关系为 w=ki/(k1+k2+k3+...+kn)w = k_i / ( k_1 + k_2 + k_3 + ... + k_n )w=ki​/(k1​+k2​+k3​+...+kn​)，其中nnn为网络中的节点的总个数。
Reference ：BA无标度网络模型构造算法

其在networkx中的源码为：

def barabasi_albert_graph(n, m, seed=None): """Returns a random graph according to the Barabási–Albert preferential attachment model. A graph of ``n`` nodes is grown by attaching new nodes each with ``m`` edges that are preferentially attached to existing nodes with high degree. Parameters ---------- n : int Number of nodes m : int Number of edges to attach from a new node to existing nodes seed : int, optional Seed for random number generator (default=None). Returns ------- G : Graph Raises ------ NetworkXError If ``m`` does not satisfy ``1 <= m < n``. References ---------- .. [1] A. L. Barabási and R. Albert "Emergence of scaling in random networks", Science 286, pp 509-512, 1999. """ if m =n: raise nx.NetworkXError("Barabási–Albert network must have m >= 1" " and m < n, m = %d, n = %d" % (m, n)) if seed is not None: random.seed(seed) # Add m initial nodes (m0 in barabasi-speak) G=empty_graph(m) G.name="barabasi_albert_graph(%s,%s)"%(n,m) # Target nodes for new edges targets=list(range(m)) # List of existing nodes, with nodes repeated once for each adjacent edge repeated_nodes=[] # Start adding the other n-m nodes. The first node is m. source=m while source<n: # Add edges to m nodes from the source. G.add_edges_from(zip([source]*m,targets)) # Add one node to the list for each new edge just created. repeated_nodes.extend(targets) # And the new node "source" has m edges to add to the list. repeated_nodes.extend([source]*m) # Now choose m unique nodes from the existing nodes # Pick uniformly from repeated_nodes (preferential attachement) targets = _random_subset(repeated_nodes,m) source += 1 return G

这个算法使用了一个tricky的手段来完成了ba算法对于概率的要求。变量repeated_nodes其中实际上存储了所有边的两个端点（重复也会算进去），然后在repeated_nodes里面随机选择，这样每个节点被选中的概率与其度数相关。

在这个算法里面，参数mmm实际上和图的平均节点度存在一定的关系。具体可以参考给定平均链接度的无标度网络演化模型，结论是经历足够长的时间（也就是总结点数趋近于无穷时），平均节点度为2m2m2m ，实际上，平均节点度会小于这个值

无标度网络的生成过程（参数为10， 3。该gif使用python生成，参考了IT派森的使用Python将多个png图片转为gif）：

什么是小世界网络

"Small-world" network，小世界网络。在现实生活中，我们不一定是彼此的邻居，但是往往通过很少的步数，就可以到达彼此。 描述小世界网络有两个重要的参数：

特征路径长度（characteristic path length or typical distance) : 我们将任意两个点到达彼此的最短距离称作两点间的路径长度，所有点的组合便被称作图的特征路径长度，记作LLL，其与图的总结点数NNN服从如下数学关系：L∝logNL \propto logNL∝logN 聚合系数（clustering coefficient)：这个其实是在图论里面的概念。对于一个节点nnn，如果有kkk个节点与他相连，那么这kkk个与其相连的节点组成的子图所具有的边数，与大小为kkk的完全图所含的边数（即为(k−1)k/2(k - 1)k/ 2(k−1)k/2）之比即为该点的聚合系数，所有点的聚合系数之均值便为该图的聚合系数。小世界网络的聚合系数一般不小。

Reference：小世界网络的Wiki和百度百科

小世界网络中最为经典的生成算法是Watts-Strogatz算法，其大致的内容为：

1.初始化，首先创建一个具有nnn个节点的环状图。每个节点均与其最临近的kkk（kkk必须为偶数）个点相连，均匀分布于两侧

2.重新连接，对于每个边，其中一个随机端点依照ppp的概率取消这个链接，并重连至另外一个随机端点

其在networkx中的源码为：

def watts_strogatz_graph(n, k, p, seed=None): """Return a Watts–Strogatz small-world graph. Parameters ---------- n : int The number of nodes k : int Each node is joined with its ``k`` nearest neighbors in a ring topology. p : float The probability of rewiring each edge seed : int, optional Seed for random number generator (default=None) See Also -------- newman_watts_strogatz_graph() connected_watts_strogatz_graph() Notes ----- First create a ring over ``n`` nodes. Then each node in the ring is joined to its ``k`` nearest neighbors (or ``k - 1`` neighbors if ``k`` is odd). Then shortcuts are created by replacing some edges as follows: for each edge ``(u, v)`` in the underlying "``n``-ring with ``k`` nearest neighbors" with probability ``p`` replace it with a new edge ``(u, w)`` with uniformly random choice of existing node ``w``. In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring does not increase the number of edges. The rewired graph is not guaranteed to be connected as in :func:`connected_watts_strogatz_graph`. References ---------- .. [1] Duncan J. Watts and Steven H. Strogatz, Collective dynamics of small-world networks, Nature, 393, pp. 440--442, 1998. """ if k>=n: raise nx.NetworkXError("k>=n, choose smaller k or larger n") if seed is not None: random.seed(seed) G = nx.Graph() G.name="watts_strogatz_graph(%s,%s,%s)"%(n,k,p) nodes = list(range(n)) # nodes are labeled 0 to n-1 # connect each node to k/2 neighbors for j in range(1, k // 2+1): targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list G.add_edges_from(zip(nodes,targets)) # rewire edges from each node # loop over all nodes in order (label) and neighbors in order (distance) # no self loops or multiple edges allowed for j in range(1, k // 2+1): # outer loop is neighbors targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list # inner loop in node order for u,v in zip(nodes,targets): if random.random()

= n-1: break # skip this rewiring else: G.remove_edge(u,v) G.add_edge(u,w) return G

这个算法对于图，使用了添加边的方式来初始化，向里面添加[(1,2), (2, 3), .....][(1,3),(2,4),.....]...来完成初始化。之后以同样的方式开始遍历每个边，进行重连。

他的平均节点度就是kkk，但是一定是一个偶数。

一个小世界网络的生成过程（参数为6, 4, 0.8):

作者：Span_1024

用python 博弈 复杂网络 Python