第3卷第2期 智能系统学报 Vol.3№2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 复杂网络上的群体决策 王龙，伏锋，陈小杰，王靖，武斌，楚天广，谢广明 (北京大学工学院，北京100871) 摘要：主要论述了复杂网络上群体决策的研究现状和最新进展.首先介绍了观点动力学研究中的几种基本模型， 即Isig模型、投票者模型、多数决定模型和有界自信模型等.其次以这些模型为基础，讨论了小世界、无标度等复杂 网络上观点动力学的研究结果，然后指出了观点动力学与语言游戏、一致性和耦合振子同步问题的联系，接着给出 了笔者在观点动力学方面所做的一些相关工作，最后指出了复杂网络上群体决策的未来发展方向和一些可能的应 用前景. 关键词：复杂网络：群体决策：观点动力学：自组织行为：复杂性科学：多智能体系统：群体行为：语言游戏 中图分类号：TP18文献标识码：A文章编号：16734785(2008)02009514 Collective decision-making over complex net works WANG Long,FU Feng,CHEN Xiaojie,WANG Jing,WU Bin,CHU Tiarr guang,XIE Guang ming (College of Engineering,Peking University,Beijing 100871,China) Abstract:In this paper,current theories and recent developments in collective decisionmaking over com- plex networks are discussed.First,several basic models in opinion dynamics are introduced,including the Ising model,the voter model,the majority rule model,the bounded confidence model,etc.Then,based upon these models,some recent findings about opinion dynamics over complex networks such as small- world and scale-free networks are discussed.Connections between opinion dynamics,language games, consensus,and synchronization of coupled oscillators are analyzed.Some original work on opinion dynam- ics is also presented.Finally possible future research directions and applications for collective decision making in complex networks are given. Key words :complex networks;collective decisionmaking;opinion dynamics;self-organization;complexity science;multi-Agent systems;collective behaviors;consensus;language games 观点动力学(opinion dynamics)主要研究社会 注.近年来，由于复杂性科学研究的兴起，在不同学 经济系统中由于个体之间决策的影响与外界公共信 科的交叉和融合之下，出现了经济物理学(econo 息的影响，人群中对某些特定事件或事物所持的不 physics))2l、社会物理学(soci1 ophysics)1,1、人工社 同观点的形成(formation)和演化(evolution)等现 会221等新兴研究领域，其研究范畴都包括了观点 象，并包括观点的一致性(consensus)与多样性(di- 动力学纵观观点动力学的发展，可以看出它在政治 versity)保持等问题).数十年来，观点动力学在社 事务2]、电子商务2]、市场营销、专家决策系 会学1、心理学61、政治科学川、经济学8)、物理 统03，]等方面都得到了成功的应用和发展，从而 学1、系统科学0201等不同学科中得到了广泛的关 加深了人们对观点的形成和演化的认识，同时也引 起了不同学科背景的研究人员的兴趣 收稿日期：2007-0712. 观点是个体对某事物或问题所持的看法或选 基金项目：国家自然科学基金资助项目(60674050,60528007)；国家 “973”资助项目(2002CB312200);国家“863”资助项目 择.为研究方便，观点可以简化为一个二值选择(bi (2006AA04Z258);“十一五”计划资助项目 (A2120061303). nary choice),分别用+1和-1表示，如支持(+1) 通讯作者：王龙.E-mail:longwang@pku.edu.cn. 或反对(-1)某个候选人或某种行为.更一般地，可 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 复杂网络上的群体决策 王 龙 ,伏 锋 ,陈小杰 ,王 靖 ,武 斌 ,楚天广 ,谢广明 (北京大学 工学院 ,北京 100871) 摘 要 :主要论述了复杂网络上群体决策的研究现状和最新进展. 首先介绍了观点动力学研究中的几种基本模型 , 即 Ising 模型、投票者模型、多数决定模型和有界自信模型等. 其次以这些模型为基础 ,讨论了小世界、无标度等复杂 网络上观点动力学的研究结果 ,然后指出了观点动力学与语言游戏、一致性和耦合振子同步问题的联系 ,接着给出 了笔者在观点动力学方面所做的一些相关工作 ,最后指出了复杂网络上群体决策的未来发展方向和一些可能的应 用前景. 关键词 :复杂网络 ;群体决策 ;观点动力学 ;自组织行为 ;复杂性科学 ;多智能体系统 ;群体行为 ;语言游戏 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2008) 0220095214 Collective decision2making over complex networks WANG Long , FU Feng , CHEN Xiao2jie , WANG Jing , WU Bin , CHU Tian2guang , XIE Guang2ming (College of Engineering , Peking University , Beijing 100871 , China) Abstract :In t his paper , current t heories and recent developments in collective decision2making over com2 plex networks are discussed. First , several basic models in opinion dynamics are introduced , including t he Ising model , t he voter model , t he majority rule model , t he bounded confidence model , etc. Then , based upon t hese models , some recent findings about opinion dynamics over complex networks such as small2 world and scale2free networks are discussed. Connections between opinion dynamics , language games , consensus , and synchronization of coupled oscillators are analyzed. Some original work on opinion dynam2 ics is also presented. Finally possible f ut ure research directions and applications for collective decision2 making in complex networks are given. Keywords :complex networks; collective decision2making ; opinion dynamics; self2organization ; complexity science ; multi2Agent systems; collective behaviors; consensus ; language games 收稿日期 :2007207212. 基金项目 :国家自然科学基金资助项目 (60674050 ,60528007) ;国家 “973”资助项目 ( 2002CB312200) ; 国家“863”资助项目 ( 2006AA04Z258 ) ; “ 十 一 五 ” 计 划 资 助 项 目 (A2120061303) . 通讯作者 :王 龙. E2mail :longwang @pku. edu. cn. 观点动力学 (opinion dynamics) 主要研究社会 经济系统中由于个体之间决策的影响与外界公共信 息的影响 ,人群中对某些特定事件或事物所持的不 同观点的形成 (formation) 和演化 (evolution) 等现 象 ,并包括观点的一致性 (consensus) 与多样性 (di2 versity) 保持等问题[124 ] . 数十年来 ,观点动力学在社 会学[5 ] 、心理学[6 ] 、政治科学[7 ] 、经济学[8 ] 、物理 学[9 ] 、系统科学[10220 ] 等不同学科中得到了广泛的关 注. 近年来 ,由于复杂性科学研究的兴起 ,在不同学 科的交叉和融合之下 ,出现了经济物理学 ( econo2 p hysics) [ 21 ] 、社会物理学 (sociop hysics) [1 ,3 ] 、人工社 会[22223 ]等新兴研究领域 ,其研究范畴都包括了观点 动力学. 纵观观点动力学的发展 ,可以看出它在政治 事务[24 ] 、电 子 商 务[25 ] 、市 场 营 销、专 家 决 策 系 统[10213 ,19 ]等方面都得到了成功的应用和发展 ,从而 加深了人们对观点的形成和演化的认识 ,同时也引 起了不同学科背景的研究人员的兴趣. 观点是个体对某事物或问题所持的看法或选 择. 为研究方便 ,观点可以简化为一个二值选择 (bi2 nary choice) ,分别用 + 1 和 - 1 表示 ,如支持 ( + 1) 或反对( - 1) 某个候选人或某种行为. 更一般地 , 可
·96 智能系统学报 第3卷 以映射为介于一段区间内的任一实数，如对某一使 熟的模型和研究方法，从而可以促进这些领域的相 用商品的满意度评价，从“很坏”到“很好”，就可以用 互融合和发展 闭区间[0,1]来描述.实际上，由于人们所产生的观 1 基本模型 点值并不是严格精确的，因此可以将个体的观点值 模糊化，用之间[0，Q]的实数表示个体的观点值.给 l.1 Ising模型与Gauber动力学(Gauber dynam 定初始时刻观点在人群中的分布，就可以根据某种 ics) 个体观点更新规则来考察群体中的观点演化.目前， 在观点动力学研究中，Ising模型是最基本的也 关于观点演化的模型有很多，如Ising模型、投票者 是应用最广泛的模型9,4s).Ising模型最初用于 模型(voter model)、多数决定模型(majority model) 相变研究中，后来随着复杂性科学的发展，由于其机 和有界自信模型(bounded confidence model)等，且 理简单且具有丰富的动力学行为，能有效地模拟二 大多数工作都可归到以上几类模型.这些模型一般 值观点的演化，因此被广泛地应用于观点动力学的 假设个体观点的更新受到周围环境中其他个体决策 研究中，假设一个群体由N个个体（类似统计物理 (或社会群体选择趋势)的影响.为了描述个体之间 学中的自旋(spin)组成，个体具有二值的观点： 的复杂社会（影响）关系近年来蓬勃发展的复杂网 a()=1,i=1,…,N(类似于自旋的方向).如在 络理论为其提供了方便而系统的框架：网络中的顶 金融市场中的决策：“+1”对应于“买”，“.1”对应于 点表示个体，边表示个体之间的相互作用关系260) “卖”.个体1的观点更新受周围邻居和整个社会趋 可以知道，社会关系网络具有小世界和无标度等特 势的影响类似于自旋的方向选择受局部自旋相互 性，有的还具有社团结构(community structure).著 作用和外在场的影响)：g(1+1)以概率p:()取 名的Watts-Strogatz(WS)小世界网络模型s)和 +1,1-p:()取-1： Barabasi-Albert(BA)无标度网络模型就是对真 p(t)= 实社会网络可行有效的刻画，在一定程度上能反映 1+e始 真实社会网络的特征.因此，与在全连通图或多维规 N 则格子上研究观点动力学相比，以及达到一致的时 五W=w太，0+hrW 间跟系统大小的标度关系等：也关注不同观点之间 Ka表示Boltzmann常数，T表示个体决策中的随 的竞争关系，考察是否存在不同观点的共存态，不同 机因素，包括噪声、决策错误等（对应于绝对温度） 网络拓扑对群体观点演化的影响等.另一方面，观点 1,()的右端第1项表示个体周围邻居的影响（局部 和网络拓扑的共同演化是当前研究中的一个热点问 场)，a表示其作用强度，第2项表示整个社会趋势 题.事实上，社会网络是持续动态演化的，个体将根 的影响（外场），即系统平均观点r()(系统反馈)对 据与邻居观点相互作用的结果进行连接的调整，同 个体决策的影响，：表示系统反馈对个体决策作用 时调整后的网络连接也影响群体的观点演化 g().另外 个体之间观点的表达是建立在共同语言基础上 的大小程度.r1定义为r)=上之 Ni-1 的.与观点动力学的研究类似，语言的演化(evolu~ ()、几()分别表示个体与周围邻居和系统反馈的 tion of language)是研究语音、语义、语法等表达方 确信程度，一般取为介于(-1,1)之间的非相关 式一致性的涌现行为(emergent behavior)B).近 (noncorrelated)随机噪声.以上介绍的Ising模型所 几年来出现的命名游戏(naming game)是一类简化 演化的过程也称为Glauber动力学.为了模型简单 的语言演化模型0)，这些研究方向和内容属于广 和方便处理，一般假设kaT=1,特殊地，若考虑T= 义的观点动力学，与观点动力学有着紧密的联系.同 0,则个体观点更新的过程由一个随机的过程变成了 时应该指出：近年来系统控制界的热点问题，如多智 确定性的更新过程，称为零温度Glauber动力学 能体系统的一致性问题(consensus problem),其模 (zero-temperature Glauber dynamics).(t+ 型和方法与观点动力学有相似之处4*4，.而且物理 1)=sign1,若1，=0，则个体随机选择+1或-1.上 界、非线性科学界、动力系统界等长期研究的同步问 sing模型一般用于观点是二值的情形，如果观点是 题，也与观点动力学有着千丝万缕的联系05].因 连续的或离散多值的，就需要用其他模型来刻画观 此，观点动力学的研究可以借鉴这些领域内比较成 点的演化了 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
以映射为介于一段区间内的任一实数 ,如对某一使 用商品的满意度评价 ,从“很坏”到“很好”,就可以用 闭区间[ 0 ,1 ]来描述. 实际上 ,由于人们所产生的观 点值并不是严格精确的 ,因此可以将个体的观点值 模糊化 ,用之间[0 ,Q ]的实数表示个体的观点值. 给 定初始时刻观点在人群中的分布 ,就可以根据某种 个体观点更新规则来考察群体中的观点演化. 目前 , 关于观点演化的模型有很多 ,如 Ising 模型、投票者 模型(voter model) 、多数决定模型(majority model) 和有界自信模型 ( bounded confidence model) 等 ,且 大多数工作都可归到以上几类模型. 这些模型一般 假设个体观点的更新受到周围环境中其他个体决策 (或社会群体选择趋势) 的影响. 为了描述个体之间 的复杂社会(影响) 关系 ,近年来蓬勃发展的复杂网 络理论为其提供了方便而系统的框架 :网络中的顶 点表示个体 ,边表示个体之间的相互作用关系[ 26230 ] . 可以知道 ,社会关系网络具有小世界和无标度等特 性 ,有的还具有社团结构(community structure) . 著 名的 Watts2Strogatz ( WS) 小世界网络模型[31 ] 和 Barabasi2Albert (BA) 无标度网络模型[ 32 ]就是对真 实社会网络可行有效的刻画 ,在一定程度上能反映 真实社会网络的特征. 因此 ,与在全连通图或多维规 则格子上研究观点动力学相比 ,以及达到一致的时 间跟系统大小的标度关系等 ;也关注不同观点之间 的竞争关系 ,考察是否存在不同观点的共存态 ,不同 网络拓扑对群体观点演化的影响等. 另一方面 ,观点 和网络拓扑的共同演化是当前研究中的一个热点问 题. 事实上 ,社会网络是持续动态演化的 ,个体将根 据与邻居观点相互作用的结果进行连接的调整 ,同 时调整后的网络连接也影响群体的观点演化. 个体之间观点的表达是建立在共同语言基础上 的. 与观点动力学的研究类似 ,语言的演化 (evolu2 tion of language) 是研究语音、语义、语法等表达方 式一致性的涌现行为 (emergent behavior) [33239 ] . 近 几年来出现的命名游戏( naming game) 是一类简化 的语言演化模型[ 40247 ] . 这些研究方向和内容属于广 义的观点动力学 ,与观点动力学有着紧密的联系. 同 时应该指出 :近年来系统控制界的热点问题 ,如多智 能体系统的一致性问题 (consensus problem) ,其模 型和方法与观点动力学有相似之处[48249 ] . 而且物理 界、非线性科学界、动力系统界等长期研究的同步问 题 ,也与观点动力学有着千丝万缕的联系[50253 ] . 因 此 ,观点动力学的研究可以借鉴这些领域内比较成 熟的模型和研究方法 ,从而可以促进这些领域的相 互融合和发展. 1 基本模型 1. 1 Ising 模型与 Glauber 动力学 ( Glauber dynam2 ics) 在观点动力学研究中 ,Ising 模型是最基本的也 是应用最广泛的模型[1 ,9 ,54258 ] . Ising 模型最初用于 相变研究中 ,后来随着复杂性科学的发展 ,由于其机 理简单且具有丰富的动力学行为 ,能有效地模拟二 值观点的演化 ,因此被广泛地应用于观点动力学的 研究中. 假设一个群体由 N 个个体 (类似统计物理 学中的自旋 (spin) ) 组成 ,个体具有二值的观点 : σi ( t) = ±1 , i = 1 , …, N (类似于自旋的方向) . 如在 金融市场中的决策“: + 1”对应于“买”“, - 1”对应于 “卖”. 个体 i 的观点更新受周围邻居和整个社会趋 势的影响(类似于自旋的方向选择受局部自旋相互 作用和外在场的影响) :σi ( t + 1) 以概率 pi ( t) 取 + 1 ,1 - pi ( t) 取 - 1 : pi ( t) = 1 1 + e - 2 I i (t) KB T , Ii ( t) = aξ( t) 1 Ni ∑ N j = 1 σj ( t) + hηi i ( t) r( t) . KB 表示 Boltzmann 常数 , T 表示个体决策中的随 机因素 ,包括噪声、决策错误等 (对应于绝对温度) , Ii ( t) 的右端第 1 项表示个体周围邻居的影响 (局部 场) , a 表示其作用强度 ,第 2 项表示整个社会趋势 的影响(外场) ,即系统平均观点 r( t) (系统反馈) 对 个体决策的影响 , hi 表示系统反馈对个体决策作用 的大小程度. r( t) 定义为 r( t) = 1 N Σ N j = 1 σj ( t) . 另外 , ξ( t) 、ηi ( t) 分别表示个体与周围邻居和系统反馈的 确信程度 , 一般取为介于 ( - 1 , 1) 之间的非相关 (noncorrelated) 随机噪声. 以上介绍的 Ising 模型所 演化的过程也称为 Glauber 动力学. 为了模型简单 和方便处理 ,一般假设 kB T = 1. 特殊地 ,若考虑 T = 0 ,则个体观点更新的过程由一个随机的过程变成了 确定性的更新过程 , 称为零温度 Glauber 动力学 (zero2temperat ure Glauber dynamics) . 此时σi ( t + 1) = sign Ii ,若 Ii = 0 ,则个体随机选择 + 1 或 - 1. I2 sing 模型一般用于观点是二值的情形 ,如果观点是 连续的或离散多值的 ,就需要用其他模型来刻画观 点的演化了. ·96 · 智 能 系 统 学 报 第 3 卷
第2期 王龙，等：复杂网络上的群体决策 ·97· 1.2投票者模型(voter model) 投票者模型是观点动力学研究中比较简单的一 种模型s96].假设个体观点受到周围邻居的影响，并 14 且更新时从周围邻居中随机选择一个邻居的观点， 取代自己的观点（见图1）.由于在投票者模型中很 容易写出系统不同状态之间的转移概率，因此许多 问题可以进行解析分析，这是此模型的一个优点 图3多数决定投票模型示意图 Fig.3 Schematic graph of majority voter model 点的相互作用与演化2221.设x()为个体i的观点 图1投票者模型示意图 值，i=1,,N.在1时刻，向量x(t)=(x1() Fig.I Schematic graph of voter model x2(),,xx())的元素由各个个体的观点值组成， 在图1中，个体1从周围邻居中随机选取一个 称之为背景(profile).模型假设2个个体之间的观 邻居j,用j的观点+1取代自己原先的观点-1. 点差异在某一个界之内时，他们之间的观点才有相 1.3多数决定模型(majority rule model,MR) 互影响，即影响i的观点的个体集合为 多数决定模型刻画个体决策时充分利用周围邻 1i,x(0)=1≤j≤N(0-y1≤， 居的信息，观点更新时选取数目占优的那个观 式中：G表示个体i的自信强度(confidence level) 点2-641.一般地，从系统中选取奇数个个体（如G 由此，个体1下一时刻的观点取为 个)，被选中个体的观点全部更新为G个个体中较 多个体持有的观点（见图2）.一般网络上多数决定 x+V=.xI,e0: 式中|表示集合元素个数.式(1)可以写成如下 模型的更新过程为：随机选取一个节点，节点下一时 形式： 刻选取某观点的概率正比于周围邻居所持此观点的 x(t+1)=A(t,x(t))x() 总数目.这种更新规则又叫做多数决定投票模型 式中：A(1,x(W)={a画}，是一个行和为1的随机矩 (majority voter model),见图3.实际上，MR模型在 阵.对于j1(i,x(),a则=0；对于j∈1(i,x() 理论上一般很难解析，但是由于模型更符合实际，也 a叫=|1(i,x()川1.这是关于有界自信的线性模 得到了很好的研究」 型.还有其他有界自信的非线性模型，参见文献 651,这里不再赘述 2复杂网络上的观点动力学 一般地，在复杂网络上的各种动力学研究中，网 图2多数决定模型示意图 络的节点表示个体，节点之间的边表示个体之间的 Fig.2 Schematic graph of majority rule model 相互作用和影响.个体就是通过这样的相互作用并 在图2中，在个体i和其邻居（共5人）中，选择 且按照一定的演化规则来更新自身的状态、属性.复 -1的有3人，占多数，因此i及其邻居下一时刻观 杂网络上的观点动力学即是在这种框架下来研究系 点依据多数原则取为-1.在图3中，个体i的邻居 统观点的形成、传播和一致性等问题的.复杂网络上 中1/4选择+1,3/4选择-1，因此下一时刻i以1/ 的观点动力学主要分为两方面：一方面是研究静态 4概率选择+1，以314概率选择.1。 网络上的观点动力学问题：另一方面是关注网络拓 l.4有界自信模型(bounded confidence model) 扑和观点动力学的共同演化问题 更为现实一些，在某些情况下，观点并不是二值 首先讨论静态网络上基于投票者模型的一些相 的，如前文所叙，观点可以映射为一段区间内的任一 关结论.在异质网络网络中大部分节点的邻居数目 实数，此时有界自信模型就可以用来描述群体中观 存在差异，甚至成幂律分布)上，Sood等人16o研究 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1. 2 投票者模型(voter model) 投票者模型是观点动力学研究中比较简单的一 种模型[59261 ] . 假设个体观点受到周围邻居的影响 ,并 且更新时从周围邻居中随机选择一个邻居的观点 , 取代自己的观点 (见图 1) . 由于在投票者模型中很 容易写出系统不同状态之间的转移概率 ,因此许多 问题可以进行解析分析 ,这是此模型的一个优点. 图 1 投票者模型示意图 Fig. 1 Schematic graph of voter model 在图 1 中 ,个体 i 从周围邻居中随机选取一个 邻居 j ,用 j 的观点 + 1 取代自己原先的观点 - 1. 1. 3 多数决定模型( maj orit y rule model , M R) 多数决定模型刻画个体决策时充分利用周围邻 居的信息 , 观点更新时选取数目占优的那个观 点[62264 ] . 一般地 , 从系统中选取奇数个个体 (如 G 个) ,被选中个体的观点全部更新为 G 个个体中较 多个体持有的观点 (见图 2) . 一般网络上多数决定 模型的更新过程为 :随机选取一个节点 ,节点下一时 刻选取某观点的概率正比于周围邻居所持此观点的 总数目. 这种更新规则又叫做多数决定投票模型 (majority voter model) ,见图 3. 实际上 ,MR 模型在 理论上一般很难解析 ,但是由于模型更符合实际 ,也 得到了很好的研究. 图 2 多数决定模型示意图 Fig. 2 Schematic graph of majority rule model 在图 2 中 ,在个体 i 和其邻居(共 5 人) 中 ,选择 - 1 的有 3 人 ,占多数 ,因此 i 及其邻居下一时刻观 点依据多数原则取为 - 1. 在图 3 中 ,个体 i 的邻居 中 1/ 4 选择 + 1 ,3/ 4 选择 - 1 ,因此下一时刻 i 以 1/ 4 概率选择 + 1 ,以 3/ 4 概率选择 - 1. 1. 4 有界自信模型(bounded confidence model) 更为现实一些 ,在某些情况下 ,观点并不是二值 的 ,如前文所叙 ,观点可以映射为一段区间内的任一 实数 ,此时有界自信模型就可以用来描述群体中观 图 3 多数决定投票模型示意图 Fig. 3 Schematic graph of majority voter model 点的相互作用与演化[22223 ] . 设 xi ( t) 为个体 i 的观点 值 , i = 1 , …, N . 在 t 时刻 , 向量 x ( t) = ( x1 ( t) , x2 ( t) , …, x N ( t) ) 的元素由各个个体的观点值组成 , 称之为背景 (profile) . 模型假设 2 个个体之间的观 点差异在某一个界之内时 ,他们之间的观点才有相 互影响 ,即影响 i 的观点的个体集合为 I(i , x (t)) = 1 ≤j ≤N ≤| xi (t) - xj ( y) | ≤εi , 式中 :εi 表示个体 i 的自信强度 (confidence level) . 由此 ,个体 i 下一时刻的观点取为 xi ( t + 1) =| I( i , x ( t) ) | - 1 j ∈I(∑i , x ( t) ) x j ( t) . (1) 式中 :| ·| 表示集合元素个数. 式 (1) 可以写成如下 形式 : x ( t + 1) = A( t , x ( t) ) x( t) . 式中 :A( t , x( t) ) = { aij} ,是一个行和为 1 的随机矩 阵. 对于 j I ( i , x( t) ) , aij = 0 ;对于 j ∈I ( i , x ( t) ) , aij = | I ( i , x ( t) ) | - 1 . 这是关于有界自信的线性模 型. 还有其他有界自信的非线性模型 , 参见文献 [65 ] ,这里不再赘述. 2 复杂网络上的观点动力学 一般地 ,在复杂网络上的各种动力学研究中 ,网 络的节点表示个体 ,节点之间的边表示个体之间的 相互作用和影响. 个体就是通过这样的相互作用并 且按照一定的演化规则来更新自身的状态、属性. 复 杂网络上的观点动力学即是在这种框架下来研究系 统观点的形成、传播和一致性等问题的. 复杂网络上 的观点动力学主要分为两方面 :一方面是研究静态 网络上的观点动力学问题;另一方面是关注网络拓 扑和观点动力学的共同演化问题. 首先讨论静态网络上基于投票者模型的一些相 关结论. 在异质网络(网络中大部分节点的邻居数目 存在差异 ,甚至成幂律分布) 上 , Sood 等人[ 60 ] 研究 第 2 期 王 龙 ,等 :复杂网络上的群体决策 ·97 ·
·98 智能系统学报 第3卷 了基于二值观点的投票者模型.通过运用平均场方 相同观点的节点聚在一起成条形的现象.Li等) 法对模型进行理论分析，发现系统能够达到一致状 通过数值仿真研究了在空间方格上随机加边对收敛 态（即所有个体持有相同的观点），并且收敛的平均 时间的影响，发现随机加边可以缩短网络的平均最 时间Tx的量级为N/b,其中N为个体的数目， 短路径，从而使得收敛时间变短.Lambiotte!7用平 表示网络度分布的k阶矩(k th moment).当网 均场方法分析了二分网络(dichotomous networks, 络的度分布为幂律分布时，指数v>3时Tw量级为 即网络只由2种度不同的节点组成)上的观点动力 N,指数v=3时Tx量级为N/InN;指数2<v<3 学行为，发现度的差异性对系统中不同观点共存状 时，Tw的量级为N2w.”,指数v=2时Tw量级 态到观点一致状态的转变是有影响的，并且系统呈 为AnN)2:指数v<2时Tw量级为O(1);指数v< 现出非均分现象，说明系统观点的一致性与其网络 2时Tx量级为0(1).另外，对于节点度相关或不 连通性有很大关系.进一步地，他们研究了带有社团 相关的网络，这些理论分析和仿真结果都吻合得比 结构的网络上的多数决定模型，讨论了网络上观点 较好.而在方格网络上，Krapivsky等66-6)发现系统 呈现的不同状态与社团网络结构的关系63，！ 收敛时间与其维度有关.当维度是1时，其收敛到一 基于Ising模型，Bartolozzi等s研究了无标度 致状态的时间量级为N2;维度是2时，其收敛到一 网络上的观点动力学.初始时刻+1和·1两种观点 致状态的时间量级为NInN;当维度大于2时，收敛 随机均匀地分布在网络的节点上，并且令kaT=1. 可以发现随着强度α的不断增大，系统平均观点r 时间减少到N.这些结果表明，在异质网络上的投 对应于时间序列在零值附近的波动强度会越来越 票者模型中，系统能较快到达一致状态.进一步地， 大，从而使系统到达不了一致状态，并且r对应于时 文献[68]研究了分形方格网络上的投票者模型，发 间序列的所有值概率分布函数近似为高斯分布，而 现网络上观点状态的无序性（观点不同的节点对占 所有节点对的比值)是时间的幂律函数.Castellano 且对应于其他不同的参数这种分布依然存在.进一 等6发现在个体数目相同的情况下，小世界网络上 步地，Jung等s简化了上述模型，定义l,()为 M 的系统收敛时间比规则网络上的要短，其收敛时间 1:()=∑9().与文献[541相反的是，他们发现 量级为N.并且，当个体数目趋向无穷大时，小世界 系统平均观点r可以收敛到+1或者-1，并且BA 网络上不能表现出观点的完全有序性，因为小世界 网络上的系统收敛时间比其他网络的要短 网络上的长程连接能够抑制观点的有序化.另外，文 基于有界自信模型251，文献[74]研究了增长 献[61]发现引入少量的“狂热者”（即永远不改变自 的无标度网络上的观点动力学.初始时刻，每个个体 己观点的个体)将会阻碍系统到达一致状态，并且能 都赋给一个(0,1)之间的观点值.在观点演化过程 使这种不同观点共存的状态保持稳定.文献[70]在 中，随机选取个体1及它的一个邻居j,计算他们的 平均磁场守恒的条件下研究BA网络上的投票者模 观点值差异6，=g-g,当差异值满足|8，|<e时， 型，发现点对演化(link-update,以网络上的边为研 个体观点值做相应调整：a=q-δ，且g,=g- 究对象)时，磁场守恒，系统的收敛时间量级为N: δ，，其中￡为差异极限，u(0<u<0.5)为收敛参 单点演化(node-update,以网络上的节点为研究对 数，表示改变观点值的强度.仿真结果表明系统观点 象)时，平均磁场在网络上不守恒.如果偏好性地进 动力学依赖于参数￡，它决定了观点最终分布的峰 行单点演化，则可以使其平均磁场守恒 值：而个体数目N和收敛参数u只影响系统的收敛 基于多数决定模型，Krapivsky等61研究了方 时间和最终观点的分布范围：另外，无论在固定的无 格上二值观点的传播动力学，发现系统中群体观点 标度网络上还是在增长的无标度网络上，这些结果 达到一致状态的收敛时间量级为lnN,其中N为 均成立.Krause Deffuant等人提出了几类改进的有 个体的数目，并且收敛时间随着方格网络维度的增 界自信模型，即Krause-Hegselmann(KH)模型和 大而减少，当维度大于4的时候，有可能出现一个临 Weisbuch-Deffuant模型(WD)2223】.文献[76]在 界维度使得收敛时间与个体数目N无关.进一步 KH模型的基础上，研究发现，在BA网络上存在一 地，Chen等I研究了有限维空间方格上的观点动 个比较小的自信值使得扰动传播行为发生变化 力学，发现系统能最终达到一致状态.有趣的是，在 并且存在一个临界值￡，当自信值大于临界值时，初 系统达到一致状态的过程中，在方格网络上出现了 始的扰动可以传播到其他所有节点.并且网络的平 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
了基于二值观点的投票者模型. 通过运用平均场方 法对模型进行理论分析 ,发现系统能够达到一致状 态(即所有个体持有相同的观点) ,并且收敛的平均 时间 TN 的量级为 N u 2 1 / u2 ,其中 N 为个体的数目 , uk 表示网络度分布的 k 阶矩 ( k th moment) . 当网 络的度分布为幂律分布时 ,指数 v > 3 时 TN 量级为 N ,指数 v = 3 时 TN 量级为 N / ln N ;指数 2 < v < 3 时 , TN 的量级为 N (2 v - 4) / ( v - 1) ,指数 v = 2 时 TN 量级 为(ln N) 2 ;指数 v < 2 时 TN 量级为 O (1) ;指数 v < 2 时 TN 量级为 O (1) . 另外 ,对于节点度相关或不 相关的网络 ,这些理论分析和仿真结果都吻合得比 较好. 而在方格网络上 , Krapivsky 等[66267 ]发现系统 收敛时间与其维度有关. 当维度是 1 时 ,其收敛到一 致状态的时间量级为 N 2 ;维度是 2 时 ,其收敛到一 致状态的时间量级为 Nln N ;当维度大于 2 时 ,收敛 时间减少到 N . 这些结果表明 ,在异质网络上的投 票者模型中 ,系统能较快到达一致状态. 进一步地 , 文献[ 68 ]研究了分形方格网络上的投票者模型 ,发 现网络上观点状态的无序性 (观点不同的节点对占 所有节点对的比值) 是时间的幂律函数. Castellano 等[69 ]发现在个体数目相同的情况下 ,小世界网络上 的系统收敛时间比规则网络上的要短 ,其收敛时间 量级为 N . 并且 ,当个体数目趋向无穷大时 ,小世界 网络上不能表现出观点的完全有序性 ,因为小世界 网络上的长程连接能够抑制观点的有序化. 另外 ,文 献[ 61 ]发现引入少量的“狂热者”(即永远不改变自 己观点的个体) 将会阻碍系统到达一致状态 ,并且能 使这种不同观点共存的状态保持稳定. 文献[ 70 ]在 平均磁场守恒的条件下研究 BA 网络上的投票者模 型 ,发现点对演化 (link2update ,以网络上的边为研 究对象) 时 ,磁场守恒 ,系统的收敛时间量级为 N ; 单点演化 ( node2update ,以网络上的节点为研究对 象) 时 ,平均磁场在网络上不守恒. 如果偏好性地进 行单点演化 ,则可以使其平均磁场守恒. 基于多数决定模型 , Krapivsky 等[64 ] 研究了方 格上二值观点的传播动力学 ,发现系统中群体观点 达到一致状态的收敛时间量级为 ln N ,其中 N 为 个体的数目 ,并且收敛时间随着方格网络维度的增 大而减少 ,当维度大于 4 的时候 ,有可能出现一个临 界维度使得收敛时间与个体数目 N 无关. 进一步 地 ,Chen 等[62 ] 研究了有限维空间方格上的观点动 力学 ,发现系统能最终达到一致状态. 有趣的是 ,在 系统达到一致状态的过程中 ,在方格网络上出现了 相同观点的节点聚在一起成条形的现象. Li 等[71 ] 通过数值仿真研究了在空间方格上随机加边对收敛 时间的影响 ,发现随机加边可以缩短网络的平均最 短路径 ,从而使得收敛时间变短. Lambiotte [72 ]用平 均场方法分析了二分网络 (dichotomous networks , 即网络只由 2 种度不同的节点组成) 上的观点动力 学行为 ,发现度的差异性对系统中不同观点共存状 态到观点一致状态的转变是有影响的 ,并且系统呈 现出非均分现象 ,说明系统观点的一致性与其网络 连通性有很大关系. 进一步地 ,他们研究了带有社团 结构的网络上的多数决定模型 , 讨论了网络上观点 呈现的不同状态与社团网络结构的关系[63 ,73 ] . 基于 Ising 模型 ,Bartolozzi 等[ 54 ]研究了无标度 网络上的观点动力学. 初始时刻 + 1 和 - 1 两种观点 随机均匀地分布在网络的节点上 ,并且令 kB T = 1. 可以发现随着强度 a 的不断增大 ,系统平均观点 r 对应于时间序列在零值附近的波动强度会越来越 大 ,从而使系统到达不了一致状态 ,并且 r 对应于时 间序列的所有值概率分布函数近似为高斯分布 ,而 且对应于其他不同的参数这种分布依然存在. 进一 步地 ,J ung 等[ 55 ] 简化了上述模型 , 定义 Ii ( t) 为 Ii ( t) = ∑ M j =1 σj ( t) . 与文献[54 ]相反的是 ,他们发现 系统平均观点 r 可以收敛到 + 1 或者 - 1 ,并且 BA 网络上的系统收敛时间比其他网络的要短. 基于有界自信模型 [22 ,75 ] ,文献[ 74 ]研究了增长 的无标度网络上的观点动力学. 初始时刻 ,每个个体 都赋给一个 (0 ,1) 之间的观点值. 在观点演化过程 中 ,随机选取个体 i 及它的一个邻居 j ,计算他们的 观点值差异δij =σi - σj ,当差异值满足|δij | <ε时 , 个体观点值做相应调整 :σi =σi - uδij 且σj =σj - uδij ,其中ε为差异极限 , u (0 < u < 0. 5) 为收敛参 数 ,表示改变观点值的强度. 仿真结果表明系统观点 动力学依赖于参数ε,它决定了观点最终分布的峰 值;而个体数目 N 和收敛参数 u 只影响系统的收敛 时间和最终观点的分布范围;另外 ,无论在固定的无 标度网络上还是在增长的无标度网络上 ,这些结果 均成立. Krause、Deff uant 等人提出了几类改进的有 界自信模型 ,即 Krause2Hegselmann ( KH) 模型和 Weisbuch2Deff uant 模型 ( WD) [22223 ] . 文献 [ 76 ] 在 KH 模型的基础上 ,研究发现 ,在 BA 网络上存在一 个比较小的自信值εd 使得扰动传播行为发生变化 , 并且存在一个临界值εs ,当自信值大于临界值时 ,初 始的扰动可以传播到其他所有节点. 并且网络的平 ·98 · 智 能 系 统 学 报 第 3 卷
第2期 王龙，等：复杂网络上的群体决策 ·99· 均度和初始扰动的个体数目的改变对以上结果的影 到了更多地分析9则，目前，关于这方面的研究比较为 响比较小.文献[77]发现在KH和WD模型上，向 大家所关注，相信它将是今后研究的一个重点方向 量维度的增加对一致状态的收敛有促进作用 3相关的群体决策问题 除了采用以上常用模型来研究网络上的观点动 力学问题，还可以采用其他模型，如Galam和Szna 3.1语言游戏(language games) jd等人为研究观点动力学提出的相关模型58,7s). 语言演化过程的研究，如词汇、语法的发展等， 其实这些模型和上述几类模型有着非常密切的关 吸引了国际上众多学者的研究兴趣).个体观点 系其中有些模型就是在这些模型的基础上加以改 的表达是基于语言的，因此语言的演化研究也可以 进得到的.除了用这些模型来研究复杂网络上的观 看作是一类广义的观点演化过程.这里，将简单介绍 点动力学，噪声、非线性作用、记忆效应等机制也可 语言游戏中关于语法演化(evolution of grammar) 以加以考虑65,28).借助这些机制，再结合以上模 的一个基本模型31，并指出它与上文所介绍的观点 型，复杂网络上的观点动力学将成为复杂网络动力 动力学模型的联系 学中一个新的热点 考虑一个异质人群中的语言演化动力学问题， 另一方面，观点动力学与网络拓扑的共同演化 假设语法G,其中含有n个候选语法，G,G, 问题也得到了关注和研究.网络拓扑不同对观点传 G.每一个语法都有各自的构成规则.定义参数 播是有影响的，而不同个体之间的观点相互影响也 表示一个句子同时符合语法G,和G的概率，即语 可以反作用于网络拓扑.在社会系统中，研究系统观 法G,和G相通的程度，其中0≤，且aa=1 点收敛的模型大致分为2种：一种是个体对事物观 由a构成的矩阵A表示这n个语法之间两两相通 点的形成是受邻居观点影响的：另外一种是对事物 的程度.假设一个使用语法G,的个体和一个使用语 持相同（近）观点的个体比较容易成为邻居.Nw~ 法G,的个体交流的收益是F(G,G)=(a+ man等ss结合以上实际情形，通过一个概率参数 a)/2,显然F(G,G)=1.设x,为使用语法G,的 中来控制这2种演化过程的相互影响程度，进而提 个体占群体的比例，那么每个使用语法G,的个体的 出了一种考察网络拓扑和个体观点相互作用的模 型.他们发现，改变这个参数，系统平衡时的状态可 平均收益可以表示为f:=∑xF(G,G).假设一 以由不同观点共存的状态转化到绝大多数个体持相 个后代在使用语法G,的语言环境里学习，但最终说 同观点的状态.另外，G1等81也提出了一种观点 的却是使用语法G的语言的概率是Q,.根据复制 传播和网络拓扑共同演化的模型，其规则如下：初始 突变方程(replicator-mutator equation),可以得到 网络拓扑为N个节点组成的全连通图：观点+1， 该模型的人口动力学方程为 -1随机等比例地分布在网络上.在演化过程中，每 =,1=1，…m 2) 次从网络中随机选取一节点对（节点之间相互连 接)，如果选取的节点对的状态相同，进行下一步演 式中：=∑f,∑：=1.可以看出，式2有很 化，否则，即当选取的节点对之间的观点不同时，节 多稳定的和不稳定的平衡点.而当Qg=0时，这个 点对中的一个节点以概率p1改变自己的状态，即采 系统存在i个非对称的稳定平衡点x:=1,x=0() 用另一个节点的状态来保证节点对之间的观点相 ≠).当Q,比较大时，惟一的稳定平衡点是在所有 同，或者节点对以概率1-p保持观点不变，在这种 语法的使用者比例x,几乎相等的点处取得.因此当 情况下，两节点之间的边再以概率2断开.按照这 Qg=0,j≠i时，系统会收敛到全局一致的语法 样的演化规则，网络会演化成为由互不连通的社团 (universal grammar)).式(2)可以看成一个非线性 组成，社团内部的个体保持相同的观点，而社团之间 耦合的观点动力学模型，并且最终能达到一致.此 个体的观点不同，从而形成了不同观点有效分离的 外，引起物理界研究人员兴趣的命名游戏(naming 有趣现象.相应地，Rosvall等人采用个体之间交流 game)1o1,也可以看成一类广义的观点动力学.由 反馈的规则研究了系统中拓扑结构和信息之间的自 此，观点演化的研究可以借鉴语言演化中的一些模 组织现象s8)进一步地，通过运用统计物理的方法， 型，并且可以运用演化博弈论的相关理论，从而可以 观点动力学与网络拓扑的共同演化问题在理论上得 进一步地促进观点动力学的发展 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
均度和初始扰动的个体数目的改变对以上结果的影 响比较小. 文献[77 ]发现在 KH 和 WD 模型上 ,向 量维度的增加对一致状态的收敛有促进作用. 除了采用以上常用模型来研究网络上的观点动 力学问题 ,还可以采用其他模型 ,如 Galam 和 Szna2 jd 等人为研究观点动力学提出的相关模型[58 ,78281 ] . 其实这些模型和上述几类模型有着非常密切的关 系 ,其中有些模型就是在这些模型的基础上加以改 进得到的. 除了用这些模型来研究复杂网络上的观 点动力学 ,噪声、非线性作用、记忆效应等机制也可 以加以考虑[ 65 ,82284 ] . 借助这些机制 ,再结合以上模 型 ,复杂网络上的观点动力学将成为复杂网络动力 学中一个新的热点. 另一方面 ,观点动力学与网络拓扑的共同演化 问题也得到了关注和研究. 网络拓扑不同对观点传 播是有影响的 ,而不同个体之间的观点相互影响也 可以反作用于网络拓扑. 在社会系统中 ,研究系统观 点收敛的模型大致分为 2 种 :一种是个体对事物观 点的形成是受邻居观点影响的 ;另外一种是对事物 持相同 (近) 观点的个体比较容易成为邻居. New2 man 等[85 ]结合以上实际情形 ,通过一个概率参数 <来控制这 2 种演化过程的相互影响程度 ,进而提 出了一种考察网络拓扑和个体观点相互作用的模 型. 他们发现 ,改变这个参数 ,系统平衡时的状态可 以由不同观点共存的状态转化到绝大多数个体持相 同观点的状态. 另外 , Gil 等[ 86287 ] 也提出了一种观点 传播和网络拓扑共同演化的模型 ,其规则如下 :初始 网络拓扑为 N 个节点组成的全连通图;观点 + 1 , - 1随机等比例地分布在网络上. 在演化过程中 ,每 次从网络中随机选取一节点对 (节点之间相互连 接) ,如果选取的节点对的状态相同 ,进行下一步演 化;否则 ,即当选取的节点对之间的观点不同时 ,节 点对中的一个节点以概率 p1 改变自己的状态 ,即采 用另一个节点的状态来保证节点对之间的观点相 同;或者节点对以概率 1 - p1 保持观点不变 ,在这种 情况下 ,两节点之间的边再以概率 p2 断开. 按照这 样的演化规则 ,网络会演化成为由互不连通的社团 组成 ,社团内部的个体保持相同的观点 ,而社团之间 个体的观点不同 ,从而形成了不同观点有效分离的 有趣现象. 相应地 , Rosvall 等人采用个体之间交流 反馈的规则研究了系统中拓扑结构和信息之间的自 组织现象[88 ] . 进一步地 ,通过运用统计物理的方法 , 观点动力学与网络拓扑的共同演化问题在理论上得 到了更多地分析[89294] .目前 ,关于这方面的研究比较为 大家所关注 ,相信它将是今后研究的一个重点方向. 3 相关的群体决策问题 3. 1 语言游戏(language games) 语言演化过程的研究 ,如词汇、语法的发展等 , 吸引了国际上众多学者的研究兴趣[33239 ] . 个体观点 的表达是基于语言的 ,因此语言的演化研究也可以 看作是一类广义的观点演化过程. 这里 ,将简单介绍 语言游戏中关于语法演化 (evolution of grammar) 的一个基本模型[35 ] ,并指出它与上文所介绍的观点 动力学模型的联系. 考虑一个异质人群中的语言演化动力学问题. 假设语法 G, 其中含有 n 个候选语法 , G1 , G2 , …, Gn . 每一个语法都有各自的构成规则. 定义参数 aij 表示一个句子同时符合语法 Gi 和 Gj 的概率 ,即语 法 Gi 和 Gj 相通的程度 ,其中 0 ≤aij ≤1 ,且 aii = 1. 由 aij构成的矩阵 A 表示这 n 个语法之间两两相通 的程度. 假设一个使用语法 Gi 的个体和一个使用语 法 Gj 的个体交流的收益是 F ( Gi , Gj ) = ( aij + aji) / 2 ,显然 F( Gi , Gi) = 1. 设 xi 为使用语法 Gi 的 个体占群体的比例 ,那么每个使用语法 Gi 的个体的 平均收益可以表示为 f i = ∑ j x j F ( Gi , Gj) . 假设一 个后代在使用语法 Gi 的语言环境里学习 ,但最终说 的却是使用语法 Gj 的语言的概率是 Qij . 根据复制 突变方程 (replicator2mutator equation) ,可以得到 该模型的人口动力学方程为 x . i = ∑ n j =1 x j f jQji - <x i , i = 1 , …, n. (2) 式中 :< = ∑i x i f i , ∑i x i = 1. 可以看出 ,式(2) 有很 多稳定的和不稳定的平衡点. 而当 Qij = 0 时 ,这个 系统存在 i 个非对称的稳定平衡点 x i = 1 , x j = 0 ( j ≠i) . 当 Qij 比较大时 ,惟一的稳定平衡点是在所有 语法的使用者比例 xi 几乎相等的点处取得. 因此当 Qij = 0 , j ≠i 时 , 系统会收敛到全局一致的语法 (universal grammar) . 式 (2) 可以看成一个非线性 耦合的观点动力学模型 ,并且最终能达到一致. 此 外 ,引起物理界研究人员兴趣的命名游戏 (naming game) [40247 ] ,也可以看成一类广义的观点动力学. 由 此 ,观点演化的研究可以借鉴语言演化中的一些模 型 ,并且可以运用演化博弈论的相关理论 ,从而可以 进一步地促进观点动力学的发展. 第 2 期 王 龙 ,等 :复杂网络上的群体决策 ·99 ·