第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201612018 网络出版t地址:http:/kns.cnki.net/cms/detail/23.1538.TP.20170703.1601.002.html 基于囚徒困境策略的改进K网络上的合作博弈 邓云生,杨洪勇 (鲁东大学信息与电气工程学院,山东烟台264025) 摘要:为模拟现实世界的合作行为,本文在HK网络模型基础上提出了一种具有高聚类幂律可调性质的新的网络 模型,并分析了囚徒困境博弈在此网络上的演化。通过仿真实验,研究了该网络的高聚类特性对合作行为的影响。 大量实验表明,网络的高聚类特性可以极大促进合作现象的涌现。同时研究也发现,随着诱惑参数的变大,合作水平 也会随之下降,但幅度不大。总之,该演化博弈模型可以促进合作现象的涌现并抵御背叛策略的传播。 关键词:HK网络:高聚类系数:幂律可调:囚徒博弈:合作行为;网络博弈;背叛的诱惑:收益矩阵 中图分类号:TP273文献标志码:A文章编号:1673-4785(2018)03-0479-07 中文引用格式:邓云生,杨洪勇.基于囚徒困境策略的改进HK网络上的合作博弈.智能系统学报,2018,133:479-485. 英文引用格式:DENG Yunsheng,YANG Hongyong.Improved cooperative behavior in HK networks based on the prisoner di-- lemma game[Jl.CAAI transactions on intelligent systems,2018,13(3):479-485. Improved cooperative behavior in HK networks based on the prisoner di- lemma game DENG Yunsheng,YANG Hongyong (School of Information and Electrical Engineering.Ludong University,Yantai 264025,China) Abstract:To simulate the cooperative behavior using the HK network model,we proposed a new adjustable power-law high-clustering network model to analyze the prisoner dilemma game.Through simulations,we investigated the effect of high clustering on the cooperative behavior.The experimental findings suggested that high clustering coefficient values may considerably contribute toward the emergence of cooperative behavior.We also found that with increasing tempta- tion,the level of cooperation decreased and the variation was small.Altogether,the evolutionary game model promotes cooperation and hinders betrayal. Keywords:HK network;high clustering coefficient:adjustable power law;prisoner dilemma game;cooperative behavi- or,network game;temptation to betrayal;payoff matrix 随着复杂网络研究的兴起,许多现实世界中的 1网络博奔研究现状 系统都可以使用复杂网铬进行描述。系统中的元素 被视为网络中的节点,节点的边用来表示元素之间 最为成功的复杂网络模型当属W$小世界网络 的相互作用和关系。例如,现实社会中的演员合作 模型四和BA无标度网络模型。许多复杂网络方 网、交通运输网、Internet网等都可以用复杂网络进 面的研究都是基于这两个模型而展开的。然而这两 行描述。现实网络规模巨大,节点间联系多而复杂 个模型都有不足之处,不能真实再现现实中的网络 的拓扑结构引起许多学者的极大兴趣,对其进行了 结构。WS模型具有与现实网络相符合的高聚类系 大量的研究。 数特征,但其度分布为泊松分布,这与现实网络不 符。BA模型的度分布具有与现实相符的幂律特 收稿日期:2016-12-14.网络出版日期:2017-07-03 基金项目:国家自然科学基金项日(61673200), 点,但其聚类系数却很低,这一特征与现实网络尤 通信作者:杨洪勇.E-mail:hyyang@yeah.net. 其是社会网络的特征相去甚远
DOI: 10.11992/tis.201612018 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170703.1601.002.html 基于囚徒困境策略的改进 HK 网络上的合作博弈 邓云生,杨洪勇 (鲁东大学 信息与电气工程学院,山东 烟台 264025) 摘 要:为模拟现实世界的合作行为,本文在 HK 网络模型基础上提出了一种具有高聚类幂律可调性质的新的网络 模型,并分析了囚徒困境博弈在此网络上的演化。通过仿真实验,研究了该网络的高聚类特性对合作行为的影响。 大量实验表明,网络的高聚类特性可以极大促进合作现象的涌现。同时研究也发现,随着诱惑参数的变大,合作水平 也会随之下降,但幅度不大。总之,该演化博弈模型可以促进合作现象的涌现并抵御背叛策略的传播。 关键词:HK 网络;高聚类系数;幂律可调;囚徒博弈;合作行为;网络博弈;背叛的诱惑;收益矩阵 中图分类号:TP273 文献标志码:A 文章编号:1673−4785(2018)03−0479−07 中文引用格式:邓云生, 杨洪勇. 基于囚徒困境策略的改进 HK 网络上的合作博弈[J]. 智能系统学报, 2018, 13(3): 479–485. 英文引用格式:DENG Yunsheng, YANG Hongyong. Improved cooperative behavior in HK networks based on the prisoner dilemma game[J]. CAAI transactions on intelligent systems, 2018, 13(3): 479–485. Improved cooperative behavior in HK networks based on the prisoner dilemma game DENG Yunsheng,YANG Hongyong (School of Information and Electrical Engineering, Ludong University, Yantai 264025, China) Abstract: To simulate the cooperative behavior using the HK network model, we proposed a new adjustable power-law high-clustering network model to analyze the prisoner dilemma game. Through simulations, we investigated the effect of high clustering on the cooperative behavior. The experimental findings suggested that high clustering coefficient values may considerably contribute toward the emergence of cooperative behavior. We also found that with increasing temptation, the level of cooperation decreased and the variation was small. Altogether, the evolutionary game model promotes cooperation and hinders betrayal. Keywords: HK network; high clustering coefficient; adjustable power law; prisoner dilemma game; cooperative behavior; network game; temptation to betrayal; payoff matrix 随着复杂网络研究的兴起,许多现实世界中的 系统都可以使用复杂网络进行描述。系统中的元素 被视为网络中的节点,节点的边用来表示元素之间 的相互作用和关系。例如,现实社会中的演员合作 网、交通运输网、Internet 网等都可以用复杂网络进 行描述。现实网络规模巨大,节点间联系多而复杂 的拓扑结构引起许多学者的极大兴趣,对其进行了 大量的研究。 1 网络博弈研究现状 最为成功的复杂网络模型当属 WS 小世界网络 模型[1]和 BA 无标度网络模型[2]。许多复杂网络方 面的研究都是基于这两个模型而展开的。然而这两 个模型都有不足之处,不能真实再现现实中的网络 结构。WS 模型具有与现实网络相符合的高聚类系 数特征,但其度分布为泊松分布,这与现实网络不 符。BA 模型的度分布具有与现实相符的幂律特 点,但其聚类系数却很低,这一特征与现实网络尤 其是社会网络的特征相去甚远。 收稿日期:2016−12−14. 网络出版日期:2017−07−03. 基金项目:国家自然科学基金项目 (61673200). 通信作者:杨洪勇. E-mail:hyyang@yeah.net. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
·480· 智能系统学报 第13卷 有鉴于此,Holmes和Kim构造了一种可调聚 次网络上的囚徒困境博弈,研究结果表明改变收益 类系数的网络模型(HK模型),该模型利用一个可 矩阵中的参数确实会影响系统的演化过程;Lⅵ等1刀 调参数,通过不断构造网络的局部三角形结构,最 在3种规则网络上研究了雪堆博弈,研究发现在复 终形成一个同时具有高聚类特性和幂律分布特性的 制动力学策略调整规则下可以抑制合作行为的参数 网络。其基本思想是,考虑到聚类系数实际上描述 区间;Zhang等u1研究了随机规则网络上的雪崩博 的是第3个节点与前两个节点一起形成三角形的概 弈,研究发现当雪崩博弈成本收益率较小时,系统 率,因此在网络的形成过程中故意增大形成三角形 演化为全面合作状态,反之合作与背叛在系统中共 的可能,则可实现改变聚类系数的目的。HK网络 生;文献[19]研究了基于记忆效应的囚徒博弈在相 模型提出后,许多学者在此基础上对其进行了改进 互依存网络中的合作现象,发现了与记忆长度和依 和研究。文献[4]在HK网铬的基础上,通过引进新 赖程度相关的最优参数区间,可以极大地促进网络 增节点所应具备的连接动态性,改进了HK模型的 中合作现象的涌现;文献[20]研究了加权网络空间 局部特性;文献[5]提出了度分布和聚类系数均可调 上的囚徒博弈,通过仿真实验发现网络中合作者密 的扩展HK模型,将HK网络模型中的三角形结构 度会随网络耦合程度的升高而变大;文献[21]研究 扩展到旧的节点之间:文献6]在HK模型基础上引 双复杂网络上的囚徒博弈,可以提高合作的水平, 入加速增长机制,再现了真实网络中低阶幂律集团 同时也揭示双网络模型下背叛领袖对合作水平的影 度分布特性;文献[7]提出的改进HK网络模型综合 响及其与合作领袖的互动机理。 考虑了“优先连接”、“三角结构”、“内部演化”等机 受以上研究启发,本文提出了一种改进的HK 制;文献[8]研究了基于HK模型的交通网络,在此 网络模型,改进后的模型在服从幂律分布且幂律可 基础上提出了一种新的路由算法,有效缓解了交通 调的情况下与HK网络模型相比具有更高的聚集系 拥堵,大大提高了交通运输的负载能力;文献[9]进 数。由于网络结构的改变是影响演化博弈的一个重 -步推广了HK网络,改进了HK网络构造过程中 要因素,本文在改进的HK网络模型上采用囚徒博 两步的连接方式,对同一时间内采用度优先连接的 弈模型,进一步研究了网络结构对博弈中合作行为 节点数量及其被连接的邻居数量进行限制,构造出 的影响。 一种新的具有幂律分布且平均聚类系数可调的网络 模型;文献[10]研究了HK网络上聚类系数对级联 2改进的HK网络模型 故障的影响,研究结果表明,具有过高或过低聚类 系数的网络在面对蓄意攻击时表现出脆弱性的一 2.1网络模型内部演化机制 现实的社会网络中,相识的两个人可能同时认 面,而具有适度聚类系数的网络能更好地抵御级联 故障的传播:文献[11]研究了聚类系数在相互关联 识一个新的朋友,进而有一定的机率同时认识这个 的两个HK网络面临蓄意攻击时的作用,研究发现 新朋友的朋友,本文提出的改进后的HK模型正是 高聚类系数会增大网络的脆弱性:文献[12]提出了 反映了这种情况。 HK网络构造过程如下。 一个改进的在线社交网络谣言传播模型,并在HK 网络环境上进行仿真实验,实验结果发现,谣言的 1)初始状态:网络初始状态有m个全连通节点。 传播能力会随着网络聚类系数的增加而得到抑制; 2)增长机制:每一个时间步,向网络中加入一 文献[13]在HK网络模型上,采用Susceptible-Infect: 个带有m条边的节点i。连接过程中,节点的第一条 ive-Removal(SIR)模型进行传播影响力的仿真实 边按照度优先规则连接到网络中已存在的节点,即 验,得出了网络聚类系数的改变会对节点中心性指 选择节点j的概率为,=k;/∑k。 标的准确性产生重要影响的结论。 3)其余m-1条边以概率p随机连接到节点j的 复杂网络上的博弈研究始于Nowak和MayI 邻居上,否则以概率1-使用度优先规则在网络中 研究的囚徒困境博弈在规则方格网络上的动态演化, 择优连接。 研究发现合作者在方格网络上可以通过聚集来抵抗 在此基础上,本文提出了如下改进HK网络模 背叛策略入侵。受此影响,许多学者采用不同的博 型(EHK)的演化机制。 弈模型在不同的网络结构上进行研究,得到了丰富 1)初始状态:网络初始状态有个全连通节点。 的理论成果。例如,文献[15]研究了可调聚类系数 2)增长机制:每一个时间步,加入两个连接在 的无标度网络上的合作现象,研究发现高聚类系数 一起的节点,每个节点有m条边。这两个节点的每 有利于网络中合作行为的演化;文献[16]研究了齐 条边进行两两配对,共有m对边与网络中已经存
pt 有鉴于此,Holmes 和 Kim[3]构造了一种可调聚 类系数的网络模型 (HK 模型),该模型利用一个可 调参数 通过不断构造网络的局部三角形结构,最 终形成一个同时具有高聚类特性和幂律分布特性的 网络。其基本思想是,考虑到聚类系数实际上描述 的是第 3 个节点与前两个节点一起形成三角形的概 率,因此在网络的形成过程中故意增大形成三角形 的可能,则可实现改变聚类系数的目的。HK 网络 模型提出后,许多学者在此基础上对其进行了改进 和研究。文献[4]在 HK 网络的基础上,通过引进新 增节点所应具备的连接动态性,改进了 HK 模型的 局部特性;文献[5]提出了度分布和聚类系数均可调 的扩展 HK 模型,将 HK 网络模型中的三角形结构 扩展到旧的节点之间;文献[6]在 HK 模型基础上引 入加速增长机制,再现了真实网络中低阶幂律集团 度分布特性;文献[7]提出的改进 HK 网络模型综合 考虑了“优先连接”、“三角结构”、“内部演化”等机 制;文献[8]研究了基于 HK 模型的交通网络,在此 基础上提出了一种新的路由算法,有效缓解了交通 拥堵,大大提高了交通运输的负载能力;文献[9]进 一步推广了 HK 网络,改进了 HK 网络构造过程中 两步的连接方式,对同一时间内采用度优先连接的 节点数量及其被连接的邻居数量进行限制,构造出 一种新的具有幂律分布且平均聚类系数可调的网络 模型;文献[10]研究了 HK 网络上聚类系数对级联 故障的影响,研究结果表明,具有过高或过低聚类 系数的网络在面对蓄意攻击时表现出脆弱性的一 面,而具有适度聚类系数的网络能更好地抵御级联 故障的传播;文献[11]研究了聚类系数在相互关联 的两个 HK 网络面临蓄意攻击时的作用,研究发现 高聚类系数会增大网络的脆弱性;文献[12]提出了 一个改进的在线社交网络谣言传播模型,并在 HK 网络环境上进行仿真实验,实验结果发现,谣言的 传播能力会随着网络聚类系数的增加而得到抑制; 文献[13]在 HK 网络模型上,采用 Susceptible-Infective-Removal(SIR) 模型进行传播影响力的仿真实 验,得出了网络聚类系数的改变会对节点中心性指 标的准确性产生重要影响的结论。 复杂网络上的博弈研究始于 Nowak 和 May[14] 研究的囚徒困境博弈在规则方格网络上的动态演化, 研究发现合作者在方格网络上可以通过聚集来抵抗 背叛策略入侵。受此影响,许多学者采用不同的博 弈模型在不同的网络结构上进行研究,得到了丰富 的理论成果。例如,文献[15]研究了可调聚类系数 的无标度网络上的合作现象,研究发现高聚类系数 有利于网络中合作行为的演化;文献[16]研究了齐 次网络上的囚徒困境博弈,研究结果表明改变收益 矩阵中的参数确实会影响系统的演化过程;Li 等 [17] 在 3 种规则网络上研究了雪堆博弈,研究发现在复 制动力学策略调整规则下可以抑制合作行为的参数 区间;Zhang 等 [18]研究了随机规则网络上的雪崩博 弈,研究发现当雪崩博弈成本收益率较小时,系统 演化为全面合作状态,反之合作与背叛在系统中共 生;文献[19]研究了基于记忆效应的囚徒博弈在相 互依存网络中的合作现象,发现了与记忆长度和依 赖程度相关的最优参数区间,可以极大地促进网络 中合作现象的涌现;文献[20]研究了加权网络空间 上的囚徒博弈,通过仿真实验发现网络中合作者密 度会随网络耦合程度的升高而变大;文献[21]研究 双复杂网络上的囚徒博弈,可以提高合作的水平, 同时也揭示双网络模型下背叛领袖对合作水平的影 响及其与合作领袖的互动机理。 受以上研究启发,本文提出了一种改进的 HK 网络模型,改进后的模型在服从幂律分布且幂律可 调的情况下与 HK 网络模型相比具有更高的聚集系 数。由于网络结构的改变是影响演化博弈的一个重 要因素,本文在改进的 HK 网络模型上采用囚徒博 弈模型,进一步研究了网络结构对博弈中合作行为 的影响。 2 改进的 HK 网络模型 2.1 网络模型内部演化机制 现实的社会网络中,相识的两个人可能同时认 识一个新的朋友,进而有一定的机率同时认识这个 新朋友的朋友,本文提出的改进后的 HK 模型正是 反映了这种情况。 HK 网络构造过程如下。 1) 初始状态:网络初始状态有m0个全连通节点。 m i i j j Πj = kj/ ∑ l kl 2) 增长机制:每一个时间步,向网络中加入一 个带有 条边的节点 。连接过程中,节点 的第一条 边按照度优先规则连接到网络中已存在的节点 ,即 选择节点 的概率为 。 m−1 p j 1− p 3) 其余 条边以概率 随机连接到节点 的 邻居上,否则以概率 使用度优先规则在网络中 择优连接。 在此基础上,本文提出了如下改进 HK 网络模 型 (EHK) 的演化机制。 1) 初始状态 m0 : 网络初始状态有 个全连通节点。 m m 2) 增长机制: 每一个时间步,加入两个连接在 一起的节点,每个节点有 条边。这两个节点的每 一条边进行两两配对,共有 对边与网络中已经存 ·480· 智 能 系 统 学 报 第 13 卷
第3期 邓云生,等:基于囚徒困境策略的改进HK网络上的合作博弈 ·481· 在的节点进行相连。这两个节点之中的第一对边按 度优先规则与网络中已存在节点(例如选中节点 P(k 图1EHK网络节点度分布图 k Fig.1 Degree distribution of EHK networks m+1 此外,网络中节点的聚类系数C的几何定义为 假设等时间间隔向网络中增加节点,则的概率 包含节点的三角形的数目 1 密度p()= ,则有 Ci= 以节点为中心的连通三元组的数目 (8) mo +f
j 在的节点进行相连。这两个节点之中的第一对边按 度优先规则与网络中已存在节点 (例如选中节点 ) 进行连接。 m−1 p j len ⩾ m−1 len j m−1 i j m−1−len 3) 其余 对边,首先考虑以概率 连接到节 点 的邻节点上。在此过程中,若有 ( 为 节点 的邻居节点数目),可将 对边随机无重复 连接到 的邻节点上,否则 的邻节点全部与新加入 的节点相连,多出的 对边在全局按照度优 先规则进行连接。 m−1 p j m−1 4) 若 对边未能以概率 与节点 的邻节点 相连,则这 对边在全局按照度优先规则进行 连接。 N 5) 终止条件: 重复 2)、3)、4) 步,直至网络规模 达到设定值。 2.2 EHK 网络模型演化动力学分析 t i t+1 ki 根据 EHK 网络模型演化机制,经过 步,点 在 时刻的度 的动力学方程满足: dki dt = 2ki ∑ l kl +(2m−2) p kj1 1 kj1 ∑ l kl + kj2 1 kj2 ∑ l kl +···+ kjv 1 kjv ∑ l kl + (2m−2) (1− p) ki ∑ l kl = 2m ki ∑ l kl (1) kj1 , kj2 ,··· , kjv 式中 为节点 i 的邻居。 2m+1 4m+2 网络中的节点每增加一条连边,网络中的度增 加 2。每一时刻网络中增加 2 个节点,网络中增加 条连边,网络的度增加 。 dki dt = 2m ki ∑ l kl = 2m ki (4m+2)t = mki (2m+1)t (2) 解该方程: lnki = m 2m+1 lnt+c (3) i ti ki = m+1 ki 将节点 看作 时刻进入网络的节点,则 ; 将 代入式 (3) 得 c = lnm+1 t m 2m+1 i , ki = (m+1) ( t ti ) m 2m+1 (4) 节点 i 的度为 P(ki t ( k m+1 )2m+1 (5) ti pi(ti) = 1 m0 +t 假设等时间间隔向网络中增加节点,则 的概率 密度 ,则有 P(ki t ( k m+1 )2m+1 = 1− 1 m0 +t t ( k m+1 ) 2m+1 m (6) 进而有 p(k) = dP(ki < K) dk = t(2m+1) (m+1) 2m+1 m m(m0 +t) k −3− 1 m (7) (7) t → ∞ p(k) ≈ 2m 2 k −3− 1 由式 可知,当 时, m。 γ = 3+m −1 γ ∈ (3,4] γ 这表明,本文提出的 EHK 模型的度分布近似 服从幂指数 的幂律分布。幂指数 , 这意味着 EHK 模型是一个非均匀的异质网络。随 着 增大,EHK 的度分布的均匀性也不断增加。故 EHK 模型同时也是一个幂指数可调的幂律度分布 网络模型。 由网络模型的构造算法可看出每一个时间步引 入的节点与网络中已存在的节点每进行一次成功连 接,必然构造出一个局部三角形结构,通过聚类系 数的定义直观上可以看出由该演化机制构造的网络 模型必然具有更高的聚类系数。 2.3 仿真分析 m0 = 100 m = 80 p = 0.8 N = 11 000 为验证 2.2 节中的结论,检验提出的 EHK 网络 模型是否会继承 HK 网络模型度分布服从幂律分布 这一特性,本文通过仿真实验做出 EHK 网络的度 分布图 (见图 1)。图 1 中网络初始状态为 , , 最终生成的网络规模大小 。 由生成的结果度分布图可看出 EHK 网络的度分布 具有幂律分布的特点,即绝大部分的节点度相对较 低,但存在少量度值相对很高的节点,这类度值高 的节点通常也被称为 hub 节点。这类度分布服从幂 律分布的网络也被称为幂律网络。 㞮◥⮰ᏒK 10−1 10−2 10−3 10−4 10−5 101 102 103 104 㞮◥Ꮢͦ K⮰Ắ⢳P(K) 图 1 EHK 网络节点度分布图 Fig. 1 Degree distribution of EHK networks 此外,网络中节点 i 的聚类系数 Ci的几何定义为 Ci = 包含节点i的三角形的数目 以节点i为中心的连通三元组的数目 (8) 第 3 期 邓云生,等:基于囚徒困境策略的改进 HK 网络上的合作博弈 ·481·
·482· 智能系统学报 第13卷 对网络所有节点的聚类系数C,取平均值,就得 平均聚类系数较大。这也说明,EHK网络中度数较 到整个网络的平均聚类系数CC,即 小的节点及其邻接点之间的联系更加紧密。 ce N (9) 10 网络的平均聚类系数CC可以用来描述网络中 节点之间形成三角形结构的趋势。其值反映了网络 中三角结构连接的密度。由网络模型的构造算法可 10 看出,每一个时间步引入的节点与网络中已存在的 节点每进行一次成功连接,必然构造出一个局部三 角形结构。通过聚类系数的定义直观上可以看出, 10 10 102 10 10 由该演化机制构造的网络模型必然具有更高的聚类 K 系数。 图3平均聚类系数C(K)与度的关系 图2中的仿真结果显示了本文提出的网络模型 Fig.3 Relation between the average clustering coefficient 的聚类系数与HK模型平均聚类系数的比较,初始 and degree k 条件为=10,m=4,最终生成网络规模N=5000, 真实世界的网络往往为幂律网络,且具有高聚 图中每一个数据是10组运算取平均值后所得到的 类的特性。由图1和图2的分析可知,本文构建的 结果。 网络模型成功再现了这两个特征,并且图3的仿真 1.0 结果也说明本文构建的网络符合现实网络的特征, 0.9 由此可见本文所构建的网络模型能够很好地描述真 0.8 0.7 实网络结构特性。 0.6 80.5 3EHK网络上囚徒博弈 0.4 03 0.2 合改进后的HK网络 3.1囚徒博弈模型 0.1 ◆HK网络 在囚徒困境博弈模型(prisoner's dilemma 00.10.2030.40.50.60.70.80.91.0 game,PDG)中,每个人都有两种选择合作(coopera- 0 tion,C)与背叛(defection,D)。其收益矩阵为 图2EHK网络与HK网络平均聚类系数对比 D Fig.2 Comparison of the average clustering coefficient C 「RS (12) between EHK and HK D T P 由仿真结果可见,相同条件下,聚类系数的值 式中:最左侧一列代表自己的选择;最上面一行代 随可调节概率p的值增加而增加;概率相同时,采 表对方的选择:R为相互合作的奖励,即(C,C)策略 用新算法生成网络的聚类系数要高于HK算法生成 组合中,选择C策略所获得的个体收益;S为给傻 网络的聚类系数。此外,在求得各个节点的聚类系 瓜的报酬,即(C,D)策略组合中选择D策略所获得 数基础上,还可以进一步定义度为k的节点的聚类 的个体收益;T为背叛的诱惑(temptation to defect), 系数平均值并将其表示为节点度的函数,即 即(D,C)策略组合中,选择D策略的个体收益; ∑Cok C)= P为相互背叛的惩罚,即(D,D)策略组合中,采用 (10) ∑wkk D策略的个体收益,且满足T>R>P>S,2R>T+S。 其中w定义为 在上述情形下,理性的参与者总是会选择背叛策略 1,k:=k 作为自己的最佳策略,但从总体而言只有都选择合 0.k+k (11) 作策略才能使收益达到最大。然而当理性的参与者 研究表明,许多真实网络的C)分布服从幂律 相互背叛时,没有参与者愿意单方面改变自己的策 分布,即C()~k(y>0)。对图1中的网络,做出其 略,因为这样做会降低自身的收益,因此相互背叛 聚类系数与节点度相关性曲线(见图3)。由图3仿 状态(D,D)就构成了囚徒博弈的纳什均衡状态。 真结果可知,EHK网络中节点的平均聚类系数随着 本文提出的EHK网络中每一个节点代表一个 节点度数k的增大而减小,即EHK网络中度数大的 博弈个体。采用由Nowak和May提出的简化的单 节点具有较小的平均聚类系数,而度数小的节点的 参数囚徒博弈模型,其收益矩阵为
对网络所有节点的聚类系数 Ci取平均值,就得 到整个网络的平均聚类系数 CC,即 CC = 1 N ∑N i=1 Ci (9) 网络的平均聚类系数 CC 可以用来描述网络中 节点之间形成三角形结构的趋势。其值反映了网络 中三角结构连接的密度。由网络模型的构造算法可 看出,每一个时间步引入的节点与网络中已存在的 节点每进行一次成功连接,必然构造出一个局部三 角形结构。通过聚类系数的定义直观上可以看出, 由该演化机制构造的网络模型必然具有更高的聚类 系数。 m0 = 10 m = 4 N = 5 000 图 2 中的仿真结果显示了本文提出的网络模型 的聚类系数与 HK 模型平均聚类系数的比较,初始 条件为 , ,最终生成网络规模 , 图中每一个数据是 10 组运算取平均值后所得到的 结果。 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 CC P HK㑽㐈 ᩥ䔇ऺ⮰HK㑽㐈 图 2 EHK 网络与 HK 网络平均聚类系数对比 Fig. 2 Comparison of the average clustering coefficient between EHK and HK p p 由仿真结果可见,相同条件下,聚类系数的值 随可调节概率 的值增加而增加;概率 相同时,采 用新算法生成网络的聚类系数要高于 HK 算法生成 网络的聚类系数。此外,在求得各个节点的聚类系 数基础上,还可以进一步定义度为 k 的节点的聚类 系数平均值并将其表示为节点度的函数,即 C(k) = ∑ i Ciωkik ∑ i ωkik (10) 其中ωkik定义为 ωkik = { 1, ki = k 0, ki , k (11) C(k) C(k) ∼ k −γ (γ > 0) k 研究表明,许多真实网络的 分布服从幂律 分布,即 。对图 1 中的网络,做出其 聚类系数与节点度相关性曲线 (见图 3)。由图 3 仿 真结果可知,EHK 网络中节点的平均聚类系数随着 节点度数 的增大而减小,即 EHK 网络中度数大的 节点具有较小的平均聚类系数,而度数小的节点的 平均聚类系数较大。这也说明,EHK 网络中度数较 小的节点及其邻接点之间的联系更加紧密。 K 100 C(K) 10−1 101 10−2 102 103 104 图 3 平均聚类系数 C(K) 与度的关系 Fig. 3 Relation between the average clustering coefficient and degree k 真实世界的网络往往为幂律网络,且具有高聚 类的特性。由图 1 和图 2 的分析可知,本文构建的 网络模型成功再现了这两个特征,并且图 3 的仿真 结果也说明本文构建的网络符合现实网络的特征, 由此可见本文所构建的网络模型能够很好地描述真 实网络结构特性。 3 EHK 网络上囚徒博弈 3.1 囚徒博弈模型 在囚徒困境博弈模型 (prisoner’s dilemma game,PDG) 中,每个人都有两种选择合作 (cooperation,C) 与背叛 (defection,D)。其收益矩阵为 C D C D [ R S T P ] (12) 式中:最左侧一列代表自己的选择;最上面一行代 表对方的选择;R 为相互合作的奖励,即 (C, C) 策略 组合中,选择 C 策略所获得的个体收益;S 为给傻 瓜的报酬,即 (C, D) 策略组合中选择 D 策略所获得 的个体收益;T 为背叛的诱惑 (temptation to defect), 即 (D, C) 策略组合中,选择 D 策略的个体收益; P 为相互背叛的惩罚,即 (D, D) 策略组合中,采用 D 策略的个体收益,且满足 T >R>P>S,2R>T+S。 在上述情形下,理性的参与者总是会选择背叛策略 作为自己的最佳策略,但从总体而言只有都选择合 作策略才能使收益达到最大。然而当理性的参与者 相互背叛时,没有参与者愿意单方面改变自己的策 略,因为这样做会降低自身的收益,因此相互背叛 状态 (D, D) 就构成了囚徒博弈的纳什均衡状态。 本文提出的 EHK 网络中每一个节点代表一个 博弈个体。采用由 Nowak 和 May 提出的简化的单 参数囚徒博弈模型,其收益矩阵为 ·482· 智 能 系 统 学 报 第 13 卷
第3期 邓云生,等:基于囚徒困境策略的改进HK网络上的合作博弈 ·483· (13) 以50%的比例随机存在于网络中,博弈演化规则如 图4所示,博弈次数1000次,取最后50次博弈中 式中b>1。令S代表博弈个体的策略类型,其取值为 合作者密度的平均值为达到动态平衡时的合作者密 [10]'(代表合作)或[01'(代表背叛);个体i与其邻 度,记为f仿真结果如图5所示。 居进行一次博弈所得收益u,可以表示为叫,=SPS, 初始策略以一定 在每一轮博弈过程中,每个博弈个体都与自己直接 比例随机分布在 相连的邻居进行博弈,将博弈个体得到的收益总和 网络中 记为 U,=∑SPS, 节点从邻接 (14) 点处获得累 计收益U 式中2:为i的所有邻居节点集合。然后所有个体更 新它们的策略,即个体随机选择自己的邻居j,比较 根据动力学 它们的收益,若有4≥,则个体在下一轮中采取的 规则及概率 博弈策略不变;否则个体将以概率,采取其邻居 P更新策略 j的策略进行下一轮博弈。其中 15-4 P=(T-S)max (ki,k) (15) 系统是否达到预先设定 式中max(k,k,)表示节点i与j中度数较大者,若在博 的时间步 弈过程中使用收益矩阵公式(13),那么则有T-S=b。 r 式(15)说明节点接纳其邻居j的策略的概率正比于 、输出合作比例P。 两者收益之差,同时也说明高收益节点所采用的策 略容易被其低收益的邻居节点所采纳,反之低收益 图4博弈演化流程 节点所采用的策略不可能侵犯高收益的节点。 Fig.4 Process of game evolution 此外合作者密度P()是用来刻画网络博弈行为 1.00 的重要物理量,其定义为采取合作策略的博弈个体 0.95 0.90 占所有博弈个体的比例,即p()=nmW-,nw表示 0.85 博弈时采用合作策略的博弈个体数量。在网络科 0.80 学研究的过程中通常会关注某一类节点的整体行 0.75 eEHK网络 0.70 为。当网络博弈进行的某一时刻,网络中采取合作 0 0.10.20.30.40.50.60.70.80.91.0 策略的节点比例趋于稳定不再发生变化,则称这些 图5合作者比例随聚类系数变化 采取合作策略的节点达到合作稳定状态。这种多数 Fig.5 Variation in the partner proportion and clustering 节点的合作稳定状态也正是本文需要研究的内容。 coefficient 博弈初始时刻,采用合作策略和背叛策略的博弈个 图5中每个数据是相同初始条件下10次重复 体均以50%的比例随机存在于生成的EHK网络 实验所得到的平均值。由图5仿真结果可知合作者 中,每个博弈个体根据其初始策略和收益矩阵按照 比例维持在0.75以上,这充分表明EHK网络对合 式()计算其收益总和,然后根据策略更新规则式(15) 作行为具有较大的促进作用。其原因是,EHK网络 更新其策略,更新完后的策略作为博弈个体下一轮 是高聚类异质网络,其中必然会存在许多具有多三 博弈中使用的策略。每一次博弈策略的更新会使合 角形结构的高连接度的hub节点,若hub节点选择 作者密度ρ(①)在下一次博弈之前发生变化,随着博 合作策略,由于其采用累计收益的计算方式,会使 弈的不断进行,合作者密度()会逐渐达到动态平 hub节点获得较高的收益,由式(15)可知其所采用 衡状态。博弈演化流程如图4所示。 的合作策略容易被其低收益的邻居节点采纳。由 3.2仿真分析 式(13)可知采用(C,C)策略的双方收益都为1,而 3.2.1高聚类特性对合作行为的影响 hub节点采用累计收益的计算方式,会使其始终成 由第2节的研究可知,相同条件下可调节概率 为被模仿的对象,这有利于合作行为在网络中进行 p的值越大,其生成网络的聚类系数越高,故可直接 传播。 用p值对网络动力学特征进行讨论。在由m=m=2、 若hub节点初始采用背叛策略,则由累计收益 T=1.5生成N=1000的EHK网络上进行博弈,初始 的计算方式和式(I3)可知,hub节点会从其大量采 时采用合作策略的个体和采用背叛策略的个体均 用合作策略的邻居中获得较高的收益,由博弈演化
P = [ 1 0 b 0 ] (13) b > 1 S [1 0] T [0 1] T i j ui ui = S T i PSj i 式中 。令 代表博弈个体的策略类型,其取值为 (代表合作) 或 (代表背叛);个体 与其邻 居 进行一次博弈所得收益 可以表示为 , 在每一轮博弈过程中,每个博弈个体都与自己直接 相连的邻居进行博弈,将博弈个体 得到的收益总和 记为 Ui = ∑ j∈Ωi S T i PSj (14) Ωi i i j ui ⩾ uj i i pi←j j 式中 为 的所有邻居节点集合。然后所有个体更 新它们的策略,即个体 随机选择自己的邻居 ,比较 它们的收益,若有 ,则个体 在下一轮中采取的 博弈策略不变;否则个体 将以概率 采取其邻居 的策略进行下一轮博弈。其中 pi←j = uj −ui (T −S)max( ki , kj ) (15) max( ki , kj ) i j T −S = b i j 式中 表示节点 与 中度数较大者,若在博 弈过程中使用收益矩阵公式 (13),那么则有 。 式 (15) 说明节点 接纳其邻居 的策略的概率正比于 两者收益之差,同时也说明高收益节点所采用的策 略容易被其低收益的邻居节点所采纳,反之低收益 节点所采用的策略不可能侵犯高收益的节点。 ρc (t) ρc (t) = nc(t)N −1 nc(t) t ρc (t) ρc (t) 此外合作者密度 是用来刻画网络博弈行为 的重要物理量,其定义为采取合作策略的博弈个体 占所有博弈个体的比例,即 , 表示 博弈时采用合作策略的博弈个体数量。在网络科 学研究的过程中通常会关注某一类节点的整体行 为。当网络博弈进行的某一时刻,网络中采取合作 策略的节点比例趋于稳定不再发生变化,则称这些 采取合作策略的节点达到合作稳定状态。这种多数 节点的合作稳定状态也正是本文需要研究的内容。 博弈初始时刻,采用合作策略和背叛策略的博弈个 体均以 50% 的比例随机存在于生成的 EHK 网络 中,每个博弈个体根据其初始策略和收益矩阵按照 式 (1) 计算其收益总和,然后根据策略更新规则式 (15) 更新其策略,更新完后的策略作为博弈个体下一轮 博弈中使用的策略。每一次博弈策略的更新会使合 作者密度 在下一次博弈之前发生变化,随着博 弈的不断进行,合作者密度 会逐渐达到动态平 衡状态。博弈演化流程如图 4 所示。 3.2 仿真分析 3.2.1 高聚类特性对合作行为的影响 p p m0 = m = 2 T = 1.5 N = 1 000 由第 2 节的研究可知,相同条件下可调节概率 的值越大,其生成网络的聚类系数越高,故可直接 用 值对网络动力学特征进行讨论。在由 、 生成 的 EHK 网络上进行博弈,初始 时采用合作策略的个体和采用背叛策略的个体均 fc 以 50% 的比例随机存在于网络中,博弈演化规则如 图 4 所示,博弈次数 1 000 次,取最后 50 次博弈中 合作者密度的平均值为达到动态平衡时的合作者密 度,记为 仿真结果如图 5 所示。 N Y ݉も⪑Б̬ ℀ҷ䮻ᱦܲጯ 㑽㐈͙ 㞮◥iϺ䗧ᣑ ◥ะ㣣ᓃ㉛ 䃍ᩢ⯶Ui ᵥᢚ߇ߔ႒ 㻰ࣶ݅Ắ⢳ Pi←jᰠも⪑ ㈧㐋᭛॒䓪ݜ䶰ٴ䃪 ⮰ᬢ䬠ₑ 䒿ܦऴ҈℀ҷPc 图 4 博弈演化流程 Fig. 4 Process of game evolution 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.75 0.70 0.80 0.85 0.90 0.95 1.00 fc P EHK网络 图 5 合作者比例随聚类系数变化 Fig. 5 Variation in the partner proportion and clustering coefficient 图 5 中每个数据是相同初始条件下 10 次重复 实验所得到的平均值。由图 5 仿真结果可知合作者 比例维持在 0.75 以上,这充分表明 EHK 网络对合 作行为具有较大的促进作用。其原因是,EHK 网络 是高聚类异质网络,其中必然会存在许多具有多三 角形结构的高连接度的 hub 节点,若 hub 节点选择 合作策略,由于其采用累计收益的计算方式,会使 hub 节点获得较高的收益,由式 (15) 可知其所采用 的合作策略容易被其低收益的邻居节点采纳。由 式 (13) 可知采用 (C, C) 策略的双方收益都为 1,而 hub 节点采用累计收益的计算方式,会使其始终成 为被模仿的对象,这有利于合作行为在网络中进行 传播。 若 hub 节点初始采用背叛策略,则由累计收益 的计算方式和式 (13) 可知,hub 节点会从其大量采 用合作策略的邻居中获得较高的收益,由博弈演化 第 3 期 邓云生,等:基于囚徒困境策略的改进 HK 网络上的合作博弈 ·483·
·484· 智能系统学报 第13卷 策略可知,这些采用背叛策略的邻居在进行策略调 此外,图6也从另一方面说明网络中这种拥有 整时会模仿hub节点的背叛策略,而由式(13)可知 大量邻居节点的hub节点往往受到合作策略的眷 采用(D,D)策略的双方收益为零,故在下一次的网 顾,并且会在欺骗诱惑增大的情况下,起到阻碍背 络博弈中hub节点的收益会随着采用背叛策略邻居 叛策略传播的作用。 增多而大幅下降。 随着网络博弈的进行,hub节点的收益会下降 4结束语 到使其本身所采用的背叛策略不再是其邻居节点模 本文在HK网络基础上提出了一种高聚类幂律 仿的对象,进而在某一时刻hub节点会模仿其邻居 可调的网络结构模型,该模型与原HK网络模型相 的合作策略,此时利用其hub节点本身具有的多连 接的资源优势随着网络博弈的进一步演化会逐渐使 比具有更高的聚类系数。进一步在此模型基础上进 其采用的合作策略成为被邻居节点模仿的对象。 行博弈演化策略的研究,研究结果表明高聚类幂律 由上述分析可知合作策略容易占据网络中的高 可调网络结构有利于促进博弈中合作现象的涌现, 度连接的hub节点,进而影响其周围邻居也采用合 并且随着博弈模型中诱惑参数的增大合作者所占比 作策略,促进在EHK网络上合作现象的涌现。 例会随之降低。 3.2.2背叛的诱惑对合作行为的影响 参考文献: 本节考虑收益矩阵式(13)中参数b(背叛的诱惑) 增大时,对网络上博弈个体的合作行为的影响。在 [1]WATTS D J,STROGATZ S H.Collective dynamics of 初始状态为o=m=2,规模W=1000的EHK网络 small-world'networks[J].Nature,1998,393(6684): 440-442. 上进行80次博弈后的仿真结果(见图6)。由图6 [2]BARABASI A L,ALBERT R,JEONG H.Mean-field the- 可见,无论可调概率P值取多大,当诱惑参数b值增 ory for scale-free random networks[J.Physica A:statistical 大时,群体中合作者的均衡密度都呈现出减小的 mechanics and its applications,1999,272(1/2):173-187. 趋势。这是因为,当诱惑参数b增大时节点采取背叛 [3]HOLME P,KIM B J.Growing scale-free networks with 策略将得到更大的收益,而采取合作策略的节点的 tunable clustering[J].Physical review E,2001,65(2 Pt 2): 收益并没有增加。由策略调整式(14)可知,这将会 026107 增大两者收益之差,进而会加大合作者模仿背叛者 [4李稳国,王力虎,陈明芳.HK网络演化模型的研究和改进 的概率,从而在宏观上表现为合作者的密度的值 [J.计算机工程,2009,35(3):121-122,125 下降。然而,合作者均衡密度虽然整体呈现下降趋 LI Wenguo,WANG Lihu,CHEN Mingfang.Study and im- 势,但下降幅度并不大,这种较小的降幅主要是因 provement on growing HK network model[J].Computer en 为EHK网络的空间结构对合作行为在囚徒博弈上 gineering,2009,35(3)121-122,125. 的影响。过高的聚类系数使得网络中节点的联系更 [⑤]王丹,井元伟,郝彬彬.扩展HK网络结构与同步能力的 加密切,必然会使得低连接度的节点在高连接度的 研究.物理学报,2012.61(22):220511 节点周围形成三角结构,这种三角结构会使得当高 WANG Dan.JING Yuanwei.HAO Binbin.Extended 度节点偶尔采用背叛策略时,低度节点仍然保持合 Holme-Kim network model and synchronizability[J].Acta 作策略不变。大量的这种三角形结构会在空间集 physica sinica,2012,61(22):220511. 结成簇,共同抵御背叛策略的人侵。 [6]崔爱香,傅彦.加速增长的HK网络演化模型[.计算机 科学,2015,42(4):37-39 1.00 CUI Aixiang,FU Yan.Accelerated-growth HK network 0.95 evolution model[J].Computer science,2015,42(4):37-39. 0.90 [)徐玉珠,张达敏,曾成,等.改进HK网络演化模型的研究 0.85 0.80 ).电子科技,2016,29(3:106-109 0.75 XU Yuzhu,ZHANG Damin,ZENG Cheng,et al.Research 0.70 on and modeling of the improved HK network model[J]. 0.65 Electronic science and technology,2016,29(3):106-109. 0.60 [8]CHEN Liuging,GAO Jinchun,XIE Gang,et al.Routing to 1.01.1121.31.41.51.61.71.81.92.0 enhance traffic capacity for scale-free networks with tun- 图6合作者密度与欺骗诱惑关系 able clustering[C]//Proceedings of IEEE Advanced Informa- Fig.6 Relationship between the partner density and de- tion Technology,Electronic and Automation Control Con- ception temptation ference.Chongqing,China,2015:110-113
策略可知,这些采用背叛策略的邻居在进行策略调 整时会模仿 hub 节点的背叛策略,而由式 (13) 可知 采用 (D, D) 策略的双方收益为零,故在下一次的网 络博弈中 hub 节点的收益会随着采用背叛策略邻居 增多而大幅下降。 随着网络博弈的进行,hub 节点的收益会下降 到使其本身所采用的背叛策略不再是其邻居节点模 仿的对象,进而在某一时刻 hub 节点会模仿其邻居 的合作策略,此时利用其 hub 节点本身具有的多连 接的资源优势随着网络博弈的进一步演化会逐渐使 其采用的合作策略成为被邻居节点模仿的对象。 由上述分析可知合作策略容易占据网络中的高 度连接的 hub 节点,进而影响其周围邻居也采用合 作策略,促进在 EHK 网络上合作现象的涌现。 3.2.2 背叛的诱惑对合作行为的影响 b m0 = m = 2 N = 1 000 P b fc b fc 本节考虑收益矩阵式 (13) 中参数 (背叛的诱惑) 增大时,对网络上博弈个体的合作行为的影响。在 初始状态为 ,规模 的 EHK 网络 上进行 80 次博弈后的仿真结果 (见图 6)。由图 6 可见,无论可调概率 值取多大,当诱惑参数 值增 大时,群体中合作者的均衡密度 都呈现出减小的 趋势。这是因为,当诱惑参数 增大时节点采取背叛 策略将得到更大的收益,而采取合作策略的节点的 收益并没有增加。由策略调整式 (14) 可知,这将会 增大两者收益之差,进而会加大合作者模仿背叛者 的概率,从而在宏观上表现为合作者的密度 的值 下降。然而,合作者均衡密度虽然整体呈现下降趋 势,但下降幅度并不大,这种较小的降幅主要是因 为 EHK 网络的空间结构对合作行为在囚徒博弈上 的影响。过高的聚类系数使得网络中节点的联系更 加密切,必然会使得低连接度的节点在高连接度的 节点周围形成三角结构,这种三角结构会使得当高 度节点偶尔采用背叛策略时,低度节点仍然保持合 作策略不变[14]。大量的这种三角形结构会在空间集 结成簇,共同抵御背叛策略的入侵。 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 fc t P=0.0 P=0.3 P=0.5 P=0.7 P=1.0 图 6 合作者密度与欺骗诱惑关系 Fig. 6 Relationship between the partner density and deception temptation 此外,图 6 也从另一方面说明网络中这种拥有 大量邻居节点的 hub 节点往往受到合作策略的眷 顾,并且会在欺骗诱惑增大的情况下,起到阻碍背 叛策略传播的作用。 4 结束语 本文在 HK 网络基础上提出了一种高聚类幂律 可调的网络结构模型,该模型与原 HK 网络模型相 比具有更高的聚类系数。进一步在此模型基础上进 行博弈演化策略的研究,研究结果表明高聚类幂律 可调网络结构有利于促进博弈中合作现象的涌现, 并且随着博弈模型中诱惑参数的增大合作者所占比 例会随之降低。 参考文献: WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. [1] BARABÁSI A L, ALBERT R, JEONG H. Mean-field theory for scale-free random networks[J]. Physica A: statistical mechanics and its applications, 1999, 272(1/2): 173–187. [2] HOLME P, KIM B J. Growing scale-free networks with tunable clustering[J]. Physical review E, 2001, 65(2 Pt 2): 026107. [3] 李稳国, 王力虎, 陈明芳. HK 网络演化模型的研究和改进 [J]. 计算机工程, 2009, 35(3): 121–122, 125. LI Wenguo, WANG Lihu, CHEN Mingfang. Study and improvement on growing HK network model[J]. Computer engineering, 2009, 35(3): 121–122, 125. [4] 王丹, 井元伟, 郝彬彬. 扩展 HK 网络结构与同步能力的 研究[J]. 物理学报, 2012, 61(22): 220511. WANG Dan, JING Yuanwei, HAO Binbin. Extended Holme-Kim network model and synchronizability[J]. Acta physica sinica, 2012, 61(22): 220511. [5] 崔爱香, 傅彦. 加速增长的 HK 网络演化模型[J]. 计算机 科学, 2015, 42(4): 37–39. CUI Aixiang, FU Yan. Accelerated-growth HK network evolution model[J]. Computer science, 2015, 42(4): 37–39. [6] 徐玉珠, 张达敏, 曾成, 等. 改进 HK 网络演化模型的研究 [J]. 电子科技, 2016, 29(3): 106–109. XU Yuzhu, ZHANG Damin, ZENG Cheng, et al. Research on and modeling of the improved HK network model[J]. Electronic science and technology, 2016, 29(3): 106–109. [7] CHEN Liuqing, GAO Jinchun, XIE Gang, et al. Routing to enhance traffic capacity for scale-free networks with tunable clustering[C]//Proceedings of IEEE Advanced Information Technology, Electronic and Automation Control Conference. Chongqing, China, 2015: 110–113. [8] ·484· 智 能 系 统 学 报 第 13 卷
第3期 邓云生,等:基于囚徒困境策略的改进HK网络上的合作博弈 ·485· [9]VARGA I,KOCSIS G.Novel model of social networks ive behavior in evolutionary snowdrift games with the un- with tunable clustering coefficient[C]//Proceedings of the conditional imitation rule on regular lattices[J].Physical re- 9th International Conference on Applied Informatics.Eger, view E.2012.85(2Pt1:02111L. Hungary,2014:171-176. [18]ZHANG Wen,XU Chen,HUI P M.Spatial structure en- [10]ZHANG Xuejun,GU Bo,GUAN Xiangmin,et al.Cascad- hanced cooperation in dissatisfied adaptive snowdrift ing failure in scale-free networks with tunable clustering game[J].European physical journal B,2013,86(5):196. [J].International journal of modern physics C,2016,27(8): [19]LUO Chao,ZHANG Xiaolin,LIU Hong,et al.Coopera- 1650093. tion in memory-based prisoner's dilemma game on interde- [11]LI Ruigi,SUN Shiwen,MA Yilin,et al.Effect of cluster- pendent networks[J].Physica A:statistical mechanics and ing on attack vulnerability of interdependent scale-free net- its applications,2016,450:560-569. works[J].Chaos,solitons&fractals,2015,80:109-116. [20]MENG Xiaokun,SUN Shiwen,LI Xiaoxuan,et al.Interde- [12]朱张祥,刘咏梅.在线社交网络谣言传播的仿真研究 pendency enriches the spatial reciprocity in prisoner's di- 一—基于聚类系数可变的无标度网络环境[.复杂系统 lemma game on weighted networks[J].Physica A:statistic. 与复杂性科学,2016,13(2):74-82 al mechanics and its applications,2016,442:388-396. ZHU Zhangxiang,LIU Yongmei.Study of propagation of [21]向海涛,梁世东.双复杂网络间的演化博弈).物理学报, rumor in online social network based on scale-free net- 2015,641):018902 work with tunable clustering[J].Complex systems and XIANG Haitao,LIANG Shidong.Evolutionary gambling complexity science,2016,13(2):74-82. dynamics for two growing complex networks[J].Acta [13]宋玉萍,倪静.网络集聚性对节点中心性指标准确性的 physica sinica,2015,64(1):018902 影响).物理学报,2016,65(2):028901 SONG Yuping,NI Jing.Effect of variable network cluster- 作者简介: ing on the accuracy of node centrality[J].Acta physica sin- 邓云生,男,1982年生,硕土研究 ica,2016,65(2):028901. 生,主要研究方向为复杂网络、博弈论。 [14]NOWAK M A,MAY R M.Evolutionary games and spa- tial chaos[J].Nature,1992,359(6398):826-829. [15]ASSENZA S,GOMEZ-GARDENES J,LATORA V.En- hancement of cooperation in highly clustered scale-free networks[J].Physical review E,2008,78(1 Pt 2):017101. [16]张文明.网络演化博弈模型和仿真研究D1.哈尔滨:哈 杨洪勇,男,1967年生,教授,主 要研究方向为多智能体编队控制、复 尔滨工业大学,2014. 杂网络、非线性系统控制。 ZHANG Wenming.Model and simulation research on net- wokded evolutionary games[D].Harbin:Harbin Institute of Technology,2014. [17]LI Pingping,KE Jianhong,LIN Zhenquan,et al.Cooperat-
VARGA I, KOCSIS G. Novel model of social networks with tunable clustering coefficient[C]//Proceedings of the 9th International Conference on Applied Informatics. Eger, Hungary, 2014: 171–176. [9] ZHANG Xuejun, GU Bo, GUAN Xiangmin, et al. Cascading failure in scale-free networks with tunable clustering [J]. International journal of modern physics C, 2016, 27(8): 1650093. [10] LI Ruiqi, SUN Shiwen, MA Yilin, et al. Effect of clustering on attack vulnerability of interdependent scale-free networks[J]. Chaos, solitons & fractals, 2015, 80: 109–116. [11] 朱张祥, 刘咏梅. 在线社交网络谣言传播的仿真研究 ——基于聚类系数可变的无标度网络环境[J]. 复杂系统 与复杂性科学, 2016, 13(2): 74–82. ZHU Zhangxiang, LIU Yongmei. Study of propagation of rumor in online social network based on scale-free network with tunable clustering[J]. Complex systems and complexity science, 2016, 13(2): 74–82. [12] 宋玉萍, 倪静. 网络集聚性对节点中心性指标准确性的 影响[J]. 物理学报, 2016, 65(2): 028901. SONG Yuping, NI Jing. Effect of variable network clustering on the accuracy of node centrality[J]. Acta physica sinica, 2016, 65(2): 028901. [13] NOWAK M A, MAY R M. Evolutionary games and spatial chaos[J]. Nature, 1992, 359(6398): 826–829. [14] ASSENZA S, GÓMEZ-GARDEÑES J, LATORA V. Enhancement of cooperation in highly clustered scale-free networks[J]. Physical review E, 2008, 78(1 Pt 2): 017101. [15] 张文明. 网络演化博弈模型和仿真研究[D]. 哈尔滨: 哈 尔滨工业大学, 2014. ZHANG Wenming. Model and simulation research on netwokded evolutionary games[D]. Harbin: Harbin Institute of Technology, 2014. [16] [17] LI Pingping, KE Jianhong, LIN Zhenquan, et al. Cooperative behavior in evolutionary snowdrift games with the unconditional imitation rule on regular lattices[J]. Physical review E, 2012, 85(2 Pt 1): 021111. ZHANG Wen, XU Chen, HUI P M. Spatial structure enhanced cooperation in dissatisfied adaptive snowdrift game[J]. European physical journal B, 2013, 86(5): 196. [18] LUO Chao, ZHANG Xiaolin, LIU Hong, et al. Cooperation in memory-based prisoner’s dilemma game on interdependent networks[J]. Physica A: statistical mechanics and its applications, 2016, 450: 560–569. [19] MENG Xiaokun, SUN Shiwen, LI Xiaoxuan, et al. Interdependency enriches the spatial reciprocity in prisoner’s dilemma game on weighted networks[J]. Physica A: statistical mechanics and its applications, 2016, 442: 388–396. [20] 向海涛, 梁世东. 双复杂网络间的演化博弈[J]. 物理学报, 2015, 64(1): 018902. XIANG Haitao, LIANG Shidong. Evolutionary gambling dynamics for two growing complex networks[J]. Acta physica sinica, 2015, 64(1): 018902. [21] 作者简介: 邓云生,男,1982 年生,硕士研究 生,主要研究方向为复杂网络、博弈论。 杨洪勇,男,1967 年生,教授,主 要研究方向为多智能体编队控制、复 杂网络、非线性系统控制。 第 3 期 邓云生,等:基于囚徒困境策略的改进 HK 网络上的合作博弈 ·485·