文章快速检索  
  高级检索
共演博弈下的网络合作
仇建平
太原科技大学 计算机科学与技术学院,山西 太原 030024
基金项目: 山西省回国留学人员科研基金资助项目(2013-097)    
摘要: 针对社会网络上个体之间的竞争与合作,设计了社会网络模型。通过引入博弈理论,仿真社会网络个体间复杂的交互关系,即合作者或背叛者依据收益矩阵和邻居节点进行博弈。仿真结果显示当影响度过低或过高时,合作不易形成,影响度适中时合作水平最高;当收益固定时,合作变为扩散,形成更高的威望。最后,通过MovieLens数据集验证了群聚效应的存在,分析了舆论领袖对于网络群体的巨大影响力。
关键词: 社会网络     共演博弈     合作     群聚效应     舆论领袖    
Network cooperation of co-evolutionary games
QIU Jianping
Institute of Computer Science and technology, Taiyuan University of Science and Technology, Taiyuan 030024, China
Abstract: In accordance with competition and cooperation among individuals in social networks, a social network model has been designed. Game theory is introduced to simulate the complicated interaction relations among individuals in social networks. Cooperators or defectors interact with their neighbors following the payoff matrix. It can be seen that the cooperative behavior is easy to extinct for too low or too high values of degrees of influence, and the maximum cooperation level is achieved for medium values of degrees of influence. When the reward is fixed, the cooperative behavior can gradually diffuse and build higher reputations. Finally, we verified the existence of the cluster effect based on the MovieLens dataset and analyzed important influences of opinion leaders in netizen groups.
Key words: social network     co-evolutionary game     cooperation     cluster effect     opinion leader    

随着基于社会网络的媒体及其应用的迅速发展,人们越来越多地参与到社会网络上丰富的活动中,社会网络应用在人们的日常生活中发挥了越来越重要的作用[1]。社会网络是指社会个体成员之间因为互动而形成的相对稳定的复杂网络,其关注的是个体之间的互动和联系, 这种复杂的社会结构对个体行为的价值偏向以及大众舆论的形成起着至关重要的作用。社会网络分析有着重要的现实意义,在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用[2-3]。社会网络分析作为一种应用性很强的研究方法, 引起了国内外学者的关注,主要集中于以下三方面:1)网络拓扑对于合作的影响;2)合作与演化的共演;3)网络拓扑与群聚效应。其中,P. S. Dodds和D. J. Watts[4]研究了社会网络传播中的累积效应,E. Agliari等[5]探讨了社会网络传播中的演化问题。本文则把社会网络中的合作共演博弈作为研究的重点,主要集中于网络个体间的动态交互对于合作的影响以及社会网络中的群聚效应。

1 社会网络模型

一般将社会网络抽象为一张有向加权网络G(t)={N(t), L(t), f},其中N(t)为社会网络中的节点(称为个体),其状态集合用S来表示;L(t)为社会网络中的链路,链路有一个权重(影响度)h,定义了链路对节点态度和立场的影响; f是一个N×N的映射,即G的拓扑图。网络的状态方程如式(1)所示。

(1)

式中:Δsi(t)=[ηT(i, j)(sj-si)]代表个体i在社会网络中每次互动后其态度改变的量。如果L(t)的谱隙小于0,则Δsi(t)=Lsi(t)(LL(t)转置矩阵的拉普拉斯算子),网络便会同步,即相邻个体之间的态度没有区别,达成认同[6],如式(2)所示,否则陷入僵局。

(2)

在社会网络中,个体状态的变化由个体本身的状态及与相邻个体之间的状态差异来决定,即个体能量和势阱的能量(个体受到的平均压力)。

社会网络是网络中的个体基于局部信息行动的智能性、自适应性的主体网络,网络内的个体的行为遵循一定的规则,根据“环境”和接收信息来调整自身的状态和行为。通过网络内个体之间的相互竞争、协作等局部相互作用,在整体上显现出更高层次、更加复杂、更加协调的有序性。

2 仿真博弈

在仿真系统中建立一个网络人群,其人口规模为M,由2种个体行为状态组成[7],即M=C+D,其中C为合作者(用(0, 1]的正数表示),D为背叛者(用[-1, 0)的负数表示),每个个体都只与其邻居进行交互。

在时间维上,将仿真的全部过程分成若干个仿真时间单位。在每一个时间单位内,每个网络个体最多只能与一个邻居个体交互一次,并且最多只能变换一次个体行为状态,状态的变化取决于收益的博弈,其收益矩阵如表 1所示。合作者C遇到背叛者D,合作者收益为S,背叛者收益为T;2个合作者相遇,收益均为R;2个背叛者相遇,收益均为P,收益值的大小为T>R>S>P。当2个个体陷入僵局时所需付出的代价为c,带来的收益为b。如果2人都为合作者,则他们的收益为R=b-c/2;如果只有一人付出代价,虽然2个个体都可以获得好处,但背叛者未付出代价,背叛者收益为T=b,而合作者的收益为S=b-c;如果2人都选择不合作,即2人都为背叛者,2人都被无法改变对方状态,则他们的收益都为P=0。不失一般性,假定b-c/2为1,则损益比为T=1+rR=1,S=1-rP=0。

表 1 收益矩阵 Table 1 Payoff matrix
收益CD
C R S
D T P

在每一个时间单位内,社会网络中的个体会以一定的概率改变其状态。比如,当网络个体x随机选择邻居个体y,并受其影响改变状态的概率8]如式(3)所示。

(3)

式中:个体的平均收益Px表征了个体具有的能量,而个体所有邻居的平均收益Ux则代表了个体所处的势阱的能量;K表示选择邻居的随机性,K=0代表下一个邻居已确定,K=∞代表下一邻居为随机。在仿真博弈中,采用经济人假设,即网络个体的行为动机根源于经济诱因,网络个体都要争取最大的经济利益,因此将个体之间的影响度h定义为平均收益。

随着仿真博弈的进行,网络个体状态会不断变化。设nx(t)为在仿真时间单位t内网络个体x的邻居中改变状态的邻居个数。nx(t)越大表明x越多的邻居改变状态,这暗示着个体x在邻居中有着更大的威望,处于群体领袖地位,网络个体x的威望可定义为式(4):

(4)

设初始状态R(0)=0,当影响度h为0时,表示个体无法影响他人,从而无法改变邻居状态,当h不为0时,表示个体有能力影响他人,随着h的增加,个人威望也快速增长。同时,nx(t)的增长也促进了威望的增长。

3 仿真系统及结果分析 3.1 仿真系统

在仿真系统中,根据文献[8]生成无标度网络,起始网络为3个节点的完全网络,每次有3条边与新节点相连,每个仿真时间单位以概率P(ki)=ki/ kj添加一个节点来增长网络,生成的无标度网络服从幂律分布,从而构建仿真社会网络。

在仿真系统中将社会网络个体抽象为具有自主学习、自主适应和自主组织的智能代理Agent,利用Agent可以模拟个体之间复杂的相互作用,容易实现个体的差异化及个体的决策行为。网络模型的系统框架如图 1所示。系统初始化模块包括两部分,分别用来配置初始参数和Agent的初始设置。其中,K为0.1,仿真时间单位为0.5 s,Rmax=100, 合作者密度fc=合作者人数/总人数Nt,最初只有一个背叛者作为种子。运行模块用于系统的正常运行控制,在系统运行过程中,代表网络个体的Agent会与邻居实行交互,网络个体每交互一次,将根据式(3)改变当前类型。数据统计模块用于统计仿真过程产生的数据。

图 1 系统框架 Fig. 1 System architecture
3.2 结果分析

图 2所示,合作者密度随着收益的增加呈现下降趋势,当影响度η过大或过小时不容易产生合作,只有影响度η处于中间水平时(η=1.0)合作水平最高。

图 2 合作者密度与收益在不同η值时的关系 Fig. 2 Relationship between frequency of cooperators and payoff whenηis different

当收益固定时,例如b=1.1,如图 3所示,前期由于背叛者能获得较高的收益,随着仿真的进行,合作者的密度呈现快速下降的趋势。当合作者密度降低到0.3附近时,合作者的收益逐渐高于背叛者,网络个体趋向于合作,即认同。合作者密度分别在影响度η处于中间水平(η=1.0或2.0)及过大或过小时(η=0.5或5.0)趋向于同一点,这种状态的出现原因解释为人群的自组织效应。根据普里高津的理论,非线性非平衡体系在一定条件下,可以产生自组织效应,从混沌走向有序。也就是说,无需外力干涉,由于人与人之间的一些特殊相互作用(比如认同),随着时间演化,人群会自发产生在时间、空间和功能上相对稳定的有序结构,从而增强自身的适应性,提高生存能力。大量实证证明,许多以人类活动为基础的社会现象具有动力学的自组织效应,这导致了不依赖于人类规划和系统工程的特定模式的涌现,因特网便是动力学自组织效应最好的例子。

图 3 在不同η值时背叛行为的扩散 Fig. 3 Defective behavior diffuses for different values ofη

图 4所示,当影响度η过小时(η=0.5),合作者和背叛者之间的威望差别很小,因此网络个体威望增长缓慢。相反,当影响度η过大时(η=5.0),合作者和背叛者之间的威望差别非常大,在此情况下,随着合作的扩散,群体领袖往往获得了很高的威望,对群体的影响力非常大。

图 4 在不同η值时合作者与背叛者的威望差 Fig. 4 Reputation difference between cooperators and defectors for different values ofη

随着计算机技术的广泛使用和社会网络的成熟普及,人们在享受着前所未有的便捷的同时,在利益格局固定的情况下,处于某一利益共同体的个体,个性就会自觉地消失而群体的共性便随之显现出来,即形成所谓的“群体效应”,如图 56所示。

图 5 五分制评分序列 Fig. 5 Five grade Grading sequence
图 6 正负分评分序列 Fig. 6 Positive and negative grading sequence

利用MovieLens站点提供的数据集(http://www.grouplens.org)来验证群聚效应的存在。MovieLens数据集由美国明尼苏达大学的GroupLens研究项目组收集,是一个基于网络的推荐系统,包含了简要的用户统计信息。数据集包括71 567个用户对10 681部电影的10 000 054个评分。

通过观察评分[9],发现在高分对象后面的打分普遍高,而在低分对象后面的打分普遍也低。进一步地,采用去除均值偏移的办法将打分分成2类:相比而言偏高的打分和相比而言偏低的打分。图 5为某一用户按五分制对电影的打分,图 6中白色表示为正分,黑色为负分。从图 5中可以看出,这是一个典型的用户打分偏高和偏低出现的序列,这种统计具有显著的群聚效应,即偏高分和偏低分倾向于集中一起出现。

在社会网络中,网民的个人责任感极容易消失,从而变得非常烦躁、多变和冲动[10]。这时网民的理智不容易受控制,所谓的真相变得无足轻重,取而代之的是具有浓重感情色彩的主观价值判断。网民归属群体的舆论领袖往往影响着网民群体的思维方式,左右着大众的观点和看法。原因解释如下。

1)群体的推理判断能力往往低于孤立的个体,而群体态度的选择也很大程度上取决于群体领袖,群体对领袖暗示盲从的心理特征,让领袖暗示的价值取向变得尤为重要。当群体领袖所传播的信息客观公正时,群体的态度选择往往比较理性;反之,则不然。

2)舆论领袖往往充当着群体领袖的角色,且威力巨大,比如微博上的“大V”。

4 结束语

社会网络,比如互联网,都是典型的多体关联系统,网络中的每一个人都不自觉地被所处的环境所影响。本文研究了社会网络上的合作博弈行为。首先通过无标度上个体博弈结果,得到个体影响度对网络合作水平的作用;其次探索了合作收益固定时,影响网络个体威望的因素;最后阐述了群聚效应的存在及社交网络中舆论领袖的影响。研究结果将对探讨社交网络中的某些现象提供帮助。

参考文献
[1] PAN Wei, AHARONY N, PENTLAND A. Composite social network for predicting mobile apps installation[C]//The 25th AAAI Conference on Artificial Intelligence. San Francisco, USA: AAAI Press, 2011: 821-827.
[2] ZHANG Chengjun, ZENG An. Behavior patterns of online users and the effect on information filtering[J]. Physical A: Statistical Mechanics and its Applications , 2011, 391 (12) : 1822-1830
[3] GUO S, WANG Mengqiu, LESKOVEC J. The role of social networks in online shopping: information passing, price of trust, and consumer choice[C]//The 12th ACM Conference on Electronic Commerce. New York, USA: ACM Press, 2011: 157-166.
[4] DODDS P S, WATTS D J. Universal behavior in a generalized model of contagion[J]. Physical Review Letter , 2004, 92 (21) : 1-4
[5] AGLIARI E, BURIONI R, CASSI D, et al. Efficiency of information spreading in a population of diffusing agents[J]. Physical Review E , 2006, 73 (1) : 1-16
[6] GABBAY M. The effects of nonlinear interactions and network structure in small group opinion dynamics[J]. Physical A , 2007, 378 (1) : 118-126 DOI:10.1016/j.physa.2006.11.051
[7] AXELROD R. The evolution of cooperation[M]. New York: American Association for the Advancement of Science, 1981 : 1390 -1396.
[8] SZABO G, TOKE C. Evolutionary prisoner's dilemma game on a square lattice[J]. Physical Review E , 1998, 58 (1) : 69-73 DOI:10.1103/PhysRevE.58.69
[9] 王根生. 网络舆情群体极化动力模型与仿真分析[J]. 情报杂志 , 2012, 31 (3) : 20-24 WANG Gensheng. Dynamic model and simulation analysis of group polarization of online public opinion[J]. Journal of Intelligence , 2012, 31 (3) : 20-24
[10] MOSCOVICI S. The age of the crowd: a historical treatise on mass psychology[M]. Cambridge: Cambridge University Press, 1985 : 439 -450.
DOI: 10.3969/j.issn.1673-4785.201309020
中国人工智能学会和哈尔滨工程大学联合主办。
0

文章信息

仇建平
QIU Jianping
共演博弈下的网络合作
Network cooperation of co-evolutionary games
智能系统学报, 2014, 9(1): 88-91
CAAI Transactions on Intelligent Systems, 2014, 9(1): 88-91
http://dx.doi.org/10.3969/j.issn.1673-4785.201309020

文章历史

收稿日期: 2013-09-07
网络出版日期: 2014-02-20

相关文章

工作空间