相依型双层Holme-Kim网络合作行为研究

邓云生，杨洪勇

(鲁东大学信息与电气工程学院 山东 烟台 264025)

复杂系统中群体合作行为的涌现一直备受关注，是复杂性科学领域中研究热点之一。通过将复杂网络理论和演化博弈理论相结合的方法，对各种复杂系统中的关系进行模拟，为人们研究现实世界中群体合作行为提供了有力的理论支持。复杂网络上的演化博弈研究始于对规则网络上的博弈行为的探讨[1]，随着“小世界”网络模型[2]和“无标度”网络模型[3]的提出，研究逐渐从关注规则网络上的博弈行为发展到关注“小世界”与“无标度”网络模型上的博弈行为，并产生了丰富的理论成果[4-14]。随着研究的深入，人们认识到现实世界中的网络并非独立存在，它们之间往往存在各种各样的联系，相依型多层网络(interdependent networks)的概念由此提出[15]。网络结构是影响网络演化博弈行为的重要因素，相依型多层网络模型提出之后，其上的演化博弈研究成为当前网络科学研究的前沿问题。

文献[16]在由规模相同的网络构成的相依型网络模型上引入公共品博弈，研究了概率连接对整个系统中合作行为的影响以及相依型网络不同网络层间的耦合关系，实验结果发现，存在一个中等大小的连接概率使得系统中的合作者水平达到最优。文献[17]研究了由效用函数构造的相依型网络上的公共合作问题，研究结果发现，效用函数的偏置性越强，公共合作水平越高。文献[18]借助相依型多层网络描述个体所具有的不同社会关系，通过在每一层网络上进行囚徒博弈的动力学演化研究，发现在较大的背叛诱惑参数下，相依型多层网络结构会增大合作行为的韧性，而这种韧性实质上是由一些重要的跨网络层的合作行为构成。文献[19]在相依型多层网络的不同网络之间引入囚徒博弈和雪堆博弈，网络中的节点以概率p学习同一层邻居的策略，以概率1-p学习相邻层邻居的策略。研究发现，当学习概率p的值从p=1处开始下降时，有利于促进采用囚徒博弈策略的群体内的合作，而采用雪堆博弈群体内的合作水平会随之降低。文献[20]研究相依型网络上的囚徒博弈，发现囚徒博弈可以提高系统整体的合作水平，同时也发现了该网络模型下背叛领袖与合作领袖的互动机理。文献[21]研究了相依型网络上小团体的合作行为演化在人群疏散过程中的应用，通过令不同网络层上的小团体内部成员之间以及不同小团体的成员之间采用不同的博弈策略，研究了链路的比例和强度对合作演化行为的影响。文献[22]对相依型多层网络上的演化博弈研究进行了回顾和梳理，概述了单层和多层网络之间最显著的概念差异，提供了基本的定义和分类的最常用术语。最后强调指出，模式的形成和集体行为对于促进在不利条件下的合作行为的重要性。文献[23]研究了由两个耦合的方格网组成的相依型网络上基于记忆的囚徒博弈，研究结果发现，存在一个最优记忆长度和依存强度区间可以极大提高合作者的比例，同时研究也指出网络模型上的节点是否具有记忆能力，是否具有外部连接，都将对节点的演化行为产生重要影响。

受到以上研究启发，本文提出了由Holme-Kim[24]网络构建相依型网络的算法，并依此算法构建了由两个同等规模Holme-Kim网络组成的相依型网络。由于网络结构是影响其上合作行为的重要因素，故本文在该网络模型基础上引入囚徒困境博弈模型，研究了算法模型中的连接度参数n与连接概率p对网络上合作行为的影响，同时还研究了囚徒困境收益矩阵中参数b(背叛的诱惑)的改变对合作行为产生的影响。

1 相依型双层HK网络模型

现实世界中的复杂网络系统往往具有无标度、高聚类的特点。为模拟这些特点，Holme和Kim构造了一种可调聚类系数的Holme-Kim网络模型(HK)。HK网络构造过程算法如下。

1) 初始状态：网络中有m0个全连通的节点；

2) 增长机制：每一时间步，一个具有m条边的节点i加入网络。节点i的第一条边按照度优先规则连接到网络中已存在的节点 j，即选择节点 j进行连接的概率为：

3) 其余m-1条边以概率pt随机连接到节点 j的邻居上，否则以概率1-pt在全网络中使用度优先规则进行连接。

根据以上网络模型构造算法的仿真图如图1所示。

图1 HK网络统计特性图

图1 a中网络初始状态m0=10，m=4，pt= 0 .6，最终生成的网络规模 N = 1 2 000。图1b中网络初始状态m0=10，m=4，最终生成网络规模 N = 5 000，图中每一个数据是10组独立运算取平均值后所得到的结果。由仿真结果可见，HK网络模型同时具有无标度、高聚类等现实网络所具有的特点，且其聚类系数的值会随着概率pt的值增大而增大。当 pt=0时，HK网络即退化为BA网络[3]。HK网络模型提出后，许多学者研究了该网络的高聚类特性对其上的演化博弈的影响。例如，文献[25]研究了HK网络上的公共品博弈，揭示了网络聚类结构的反馈互惠机制。文献[26]对单层HK网络上的演化博弈行为进行了总结性阐释。

鉴于HK模型可以再现真实网络的这些特点，本文提出一种基于HK网络的相依型HK网络模型，其网络模型由两个HK网络层构成。这两个网络层上的节点之间通过随机性概率p进行连接。通过这种不同层节点之间的连接，两个HK网络之间具有了交互性，进而可以在该模型基础上研究合作行为是如何进行演化的。为了方便研究，具体化网络构成的条件如下：HK_A和HK_B是两个规模为N的HK网络层，HK_A上的每个节点与HK_B上的随机n (1 ≤ n≤N )个节点以概率p进行连接，其中n与p分别称为连接度与连接概率。其结构如图2所示。

图2 相依型双层HK网络结构示意图

考虑到在实际网络中，一个网络层上的节点在另一层网络中相“熟识”的节点往往不会太多，所以n的值通常不会太大，且应n≪N。由上述的建模过程可以看出，参数n与p的值决定了不同网络层之间存在多少连接，故可用这两个参数值对两个HK网络层之间耦合程度进行衡量。用参数k表示两个网络之间存在的连接数量。当参数n的值固定时，可以通过讨论参数p的值决定网络层间的耦合强度。当p=0时，k=0，两个HK网络是相互独立的网络层，它们之间不存在连接。当0＜p＜1时，k服从二项分布，k～ B (n N,p)，0 ≤ k ≤ n N。当p=1时，k=nN，HK_A中的每一个节点都与HK_B中的n个节点存在连接。通过构建这样结构的网络模型，在此基础上引入囚徒博弈模型，对该网络模型上的合作演化行为进行分析与研究。

2 相依型HK网络上的囚徒困境博弈

2.1 模型描述

在囚徒困境博弈模型(prisoner’s dilemma game,PDG)中，每个参与者都有合作(cooperation, C)与背叛(defection，D)两种策略可供选择。参与者的收益矩阵如下：

式中，最左侧一列代表自己的选择，最上面一行代表对方的选择；R为(C,C)策略组合中，选择C策略的参与者所获得的收益；S为(C,D)策略组合中，选择C策略的参与者所获得的收益；T为(D,C)策略组合中，选择D策略的参与者所获得的收益；P为(D,D)策略组合中，采用D策略的参与者所获得的收益。且满足T ＞ R ＞ P ＞ S ，2R＞T+S。其中R、S、T、P分别被称为“合作的奖励”、“傻瓜的报酬”、“背叛的诱惑”、“背叛的惩罚”。基于该收益矩阵，理性的参与者一定会选择背叛策略作为自己的最佳策略，然而就总体而言只有博弈双方都选择合作策略才能使整体的收益最大化。这种个人利益与整体利益的选择冲突，在博弈论中也被成为社会两难选择(social dilemma)。

在本文的网络博弈演化过程中，使用简化后的单参数囚徒博弈模型[1]，其收益矩阵如下：

在该单参数模型中参数R=1、P=0、S=0，参数T=b为变量。故参数T的不同取值可以影响网络上的合作行为，是本文需要考察的一个重要变量。

2.2 网络博弈过程

网络中每一个节点视为一个博弈个体，C为博弈个体所采用的策略，其取值为[1 0 ]T(代表合作)或[0 1 ]T(代表背叛)。网络模型初始时合作与背叛策略均匀分布在网络中。在每一轮博弈过程中，个体i与其所有邻居进行一次博弈(这里的所有邻居既包括与节点i处于同一网络层且直接相连的节点，还有可能包括与节点i处于不同网络层以概率p进行连接的节点)，所得的累计收益总和为：

式中，Ωi为i的所有邻居节点集合；j为i的邻节点。

完成本轮博弈后，个体i从所有邻居中随机选择一个邻居j，并比较两者收益。若有 Ui＜Uj，则个体i以概率pi←j采用 j的策略作为自己在下一轮博弈中所使用的策略。

式中，max(ki, kj)表示个体i与个体 j的度的最大者；D为收益矩阵中最大参数与最小参数之差，其作用相当于归一化因子，以确保概率pi←j的值不超过1。本文中使用的收益矩阵为式(1)，则有D = T-S = b 。

此外合作者密度是衡量网络博弈行为的重要物理量。随着网络博弈的进行，网络中采取合作策略的节点的比例不再发生变化或者变化值小于一个极小的阈值时，网络的运动状态进入或者逐渐进入合作稳定状态。本文用 fc(t)表示在t时刻相依型HK网络中合作者的密度， fc1(t)与 fc2(t)分别表示HK_A网络与HK_B网络中t时刻合作者密度。C1i(t)表示t时刻HK_A网络中节点i所采用的策略，其值取0或1。同理(t)表示t时刻HK_B网络中节点 j所采用的策略，其值取0或1。则相依型HK网络在t时刻合作者密度可以表示为：

3 仿真分析

3.1 网络层间连接概率对合作行为的影响

为研究网络构成算法中的参数n与p对网络上合作演化行为的影响，本文在不同规模的网络模型上进行了大量合作演化行为的仿真实验。实验步长t= 2 000，仿真图中每一个数据都是10次独立运算取平均值后的结果，网络进入或逐渐进入合作稳定状态。在此基础上，首先讨论连接概率p对网络中合作行为的影响。由于群体合作行为的演化过程受多种因素影响，为保证实验对连接概率p的讨论真实有效，首先固定n与T的值以及其他影响网络演化行为的因素，并画出n=2，T=1.5，网络中合作者比例趋于稳定时，连接概率p对网络中合作演化行为影响的仿真图。

图3a中的网络是由两个规模为1 000的HK网络(初始条件为m0=10，m=4，pt= 0 .5)按照本文算法构成的规模为2 000的相依型HK网络。图3b～3d中的网络与3a中网络初始条件和构造过程相同，其规模分别为4 400、5 200、7 200。其中网络博弈模型本文采用第2节中介绍的囚徒困境博弈模型，初始时采用合作策略的节点与采用背叛策略的节点各占50%均匀分布在每一个网络层中。

图3 动态演化过程(n不变)

由上述仿真图可以看出，不同规模的网络在初始阶段合作者的密度都会存在不同程度的下降。这是由于本文采用的收益矩阵式(1)中的参数b＞1，即背叛者所得收益大于合作者所得收益。故开始阶段会有部分合作者模仿其采用背叛策略的邻居，从而导致网络中合作者密度的减少。然而具有高聚类特性的HK网络中存在大量具有高度连接的hub节点，这些hub节点周围分布着大量低度连接的节点[8]。累积收益的计算方式会使hub节点受合作策略的眷顾，在博弈的过程中收获过高的博弈收益。这种高收益会在其周围低度的邻居节点中起到示范效应，使这些低度节点纷纷模仿hub节点的合作策略，从而致使合作策略在网络上快速传播开来。另一方面，仿真图中在连接度n=2，T=1.5以及相同的网络规模下，连接概率p值越小，网络中合作者密度值fc在初始阶段下降的幅度Δfc也越小，在其后的动态演化过程中其反弹的力度反而越大。这种“低开高走”的特性，最终会使低连接概率构造的网络在博弈达到平衡状态时，获得较高的合作者比例。

3.2 网络层间连接度对合作层的影响

接下来讨论当连接概率p与诱惑参数T固定时，网络层间连接度n对网络中合作行为的影响。令p=0.5，T=1.5，不同规模网络上的仿真图如图4所示。

图4 动态演化过程(p不变)

图4 a中的网络是由两个规模为1 500的HK网络(初始条件为m0=10，m=4， pt= 0 .5)按照本文算法构成的规模为3 000的相依型HK网络。图4b～4d中的网络与4a中网络初始条件和构造过程相同，其规模分别为3 800、5 000、6 000。初始时合作者与背叛者各以50%的比例均匀混合在每一层网络中。图中每一个数据都是10次独立运算取平均值后的结果。与参数n、T固定时网络中的合作演化行为相对比，本文发现当参数p、T固定时，同样是由于T＞R的存在，网络中的合作行为也呈现出一种“低开高走”的状态。与参数n、T固定时不同的是，当参数p、T固定时，连接度参数n的值越小，最终网络博弈达到平衡时合作者的密度fc的值越高。

两个不同HK网络层之间的耦合程度，本文用两个网络层之间存在的连接数k进行衡量。由网络构造算法可知k～ B (n N,p)，故参数k的数学期望值为E(k)=nNp。当网络的规模N固定时，有E(k)∝np。通过对图3、图4的分析可知，在相同网络规模N，相同背叛诱惑T下，连接度参数n与连接概率p的值越小，最终网络上合作行为达到平衡时合作者占比fc的值越高。故当网络上合作演化行为达到平衡时合作者的密度值其中E(k)∝np，即有由此可见，E(k)是影响相依型HK网络上合作行为的重要参数，即当两个不同的网络层间的耦合程度较低时，反而有利于网络中合作行为的涌现，高耦合度反而会导致最终合作者比例的降低。

为验证结论，进行仿真实验的结果如图5所示。

图5 动态演化过程

图5 a与图5b分别为在规模 N = 3 000和N=5 000网络上，参数n、p分别取不同值后得到的演化结果，其中每一个数据都是10次独立运算取平均值后的结果。图5a中的4条曲线由上到下(fc值由大到小)的 E(k)值分别为2 400、3 600、4 800、7 200，即有 fc∝ 1 E(k)。同样对图5b进行分析也可以得到相同的结论，可见本文的结论具有普遍性。图5c与图5d考察了当网络规模N，初始策略分布都相同时，网络上的合作行为的演化过程。由图5c与图5d两图可看出虽然网络层间的连接概率p与连接度n不相同，但只要参数n与p的乘积值np相同，它们的演化进程近乎是相似的过程。这充分说明，E(k)是影响相依型HK网络上合作行为的重要因素。

3.3 背叛的诱惑对合作行为的影响

囚徒困境收益矩阵中的参数T被称为“背叛的诱惑”(temptation to defect)，它表示当博弈双方分别采用背叛、合作策略时，采用背叛策略的一方所获得的收益。当采用式(1)中的收益矩阵时有T=b。随着参数 b( 1 ≤ b≤ 3 )的增大，单层HK网络上的合作者密度会经历一个由快到慢的下降过程[8]。当网络由单层HK网络扩展为相互之间存在联系的双层相依型网络时，为研究参数T以及网络之间的连接度n、连接概率p对网络中博弈演化进程的影响，首先考虑参数n、p固定时，不同规模网络上合作者密度随参数T动态演化过程，仿真图如图6所示。

由图6可以看出当网络规模N、连接概率p及连接度n都相同的情况下，背叛的诱惑T的不同取值会对网络中的合作行为产生较大的影响。在低诱惑参数(T=1.1)下，fc的值一路上扬，在极短的时间内达到动态平衡。反之在较高的诱惑参数下，fc在博弈初始阶段都呈现出不同程度的下降，其下降的幅度Δfc随T值的增大而增大。当诱惑参数T值过大时(T=1.9)，fc值在初始阶段急剧下跌，并短时间内迅速达到动态平衡状态，不过此时平衡状态下fc的值低于其初始状态值0.5。此外，尽管T值很大时，合作者仍然能以较低的占比存在于网络中，这充分证明了高聚类网络中的hub节点对于背叛策略传播具有阻碍作用的结论[8]。

图6 不同诱惑参数下动态演化过程

为考虑诱惑参数T对相依型HK网络中合作行为的具体影响，仿真图图7所示。

图7 合作者密度与背叛诱惑关系图

图7 是在规模 N = 3 000的网络上，参数n、p分别取不同的值得到的演化结果。图中每一个数据都是独立10次2 000步博弈后fc取平均值的结果。由图可见，无论参数n与p取何值，当背叛诱惑T增大时，最终合作密度fc都呈现出下降的趋势。这是由于T增大时，采取背叛策略的节点将会获得更大的收益，而采取合作策略的节点并不会获得额外的收益，这将会增大两者之间的收益差。由式(3)可知这将增大合作者模仿背叛者的概率，从而在宏观上表现为 fc值的下降。当1.05≤b≤2时，对于图中不同n、p值所对应的曲线，都存在一个不同的阈值λn,p∈ ( 1.55,1.70)， 当 T ＞λn,p时 fc＞ 0 .5， 反 之fc≤ 0 .5。由图中可以看出乘积值np越小则λn,p值越大，这说明np值越小的网络其演化博弈过程不易受诱惑参数T的影响，有利于促进网络中合作行为的涌现。这一结论也可从观察图中相同诱惑参数T下，np值小的曲线其fc值反而大而得到。当b≥2时，不同n、p值的网络的合作频率fc并未出现交叠的情况[8]，合作者占比随着b值的增大不断变小，当b=2.5时，合作者在网络中消失。

由上述分析过程可知，存在适当的诱惑参数T值(1.05 ≤ T ≤ 2 )，使得np值越小的双层网络越不易受到诱惑参数T的影响，即有 fc∝ 1 /np。这与上一小节中讨论的结果相一致。当T值过大时(T≥2.5)，会导致网络中合作者的彻底消失。

4 结 束 语

本文提出了一种相依型双层HK网络的构造算法，并在此算法构造的网络模型上引入囚徒困境博弈模型进行了演化合作行为的研究。研究了网络构造算法中的连接度参数n与连接概率p以及博弈收益矩阵中的参数T对网络中合作行为的影响。研究结果发现当n与p的取值较小时，网络中的节点易采取合作策略。稳定状态下，网络中合作者的密度值fc与不同网络层之间的连接数量k值的数学期望E(k)密切相关，网络的E(k)值越小越容易抵御诱惑参数T的影响，越有利于促进网络中合作行为的涌现。

同时仍有一些问题值得探讨。如，处于不同网络层的大度节点间通过完全随机的方式进行相连，通过多次模拟取平均值的方法消除随机误差，得到合作者占比与网络连接参数n与p值有关的结论。文献[27]与文献[28]分别研究了单层无标度网络的度相关特性对其上的囚徒博弈和公共品博弈的影响。研究表明无标度网络上的同配性会抑制其上的合作行为，而异配性会使其中心节点与周围节点形成维持其初始策略的合作/背叛簇，从而导致合作行为不易在网络中湮灭。与之类似，也可以定义相依型网络的同配性(不同网络层的大度节点之间相连)与异配性(大度节点与另一个网络层上的小度节点相连)。不同网络层间的同配与异配连接模式会对其上合作行为有何影响？同配方式、异配方式、随机方式，哪一种更有利于合作现象的产生？本文在此未做进一步探讨，这也是未来研究工作的着力点。