[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报,2008,(02):95-108.
 WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,(02):95-108.
点击复制

复杂网络上的群体决策(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
期数:
2008年02期
页码:
95-108
栏目:
出版日期:
2008-04-25

文章信息/Info

Title:
Collective decision-making over complex networks
文章编号:
1673-4785(2008)02-0095-14
作者:
王 龙伏 锋陈小杰王 靖武 斌楚天广谢广明
北京大学 工学院,北京 100871
Author(s):
WANG Long FU Feng CHEN Xiao-jie WANG Jing WU Bin CHU Tianguang XIE Guang-ming
College of Engineering, Peking University, Beijing 100871, China
关键词:
复杂网络群体决策观点动力学自组织行为复杂性科学多智能体系统群体行为语言游戏
Keywords:
complex networks collective decisionmaking opinion dynamics selforganization complexity science multiAgent systems collective behaviors consensus language games
分类号:
TP18
文献标志码:
A
摘要:
现状和最新进展.首先介绍了观点动力学研究中的几种基本模型,即Ising模型、投票者模型、多数决定模型和有界自信模型等.其次以这些模型为基础,讨论了小世界、无标度等复杂网络上观点动力学的研究结果,然后指出了观点动力学与语言游戏、一致性和耦合振子同步问题的联系,接着给出了笔者在观点动力学方面所做的一些相关工作,最后指出了复杂网络上群体决策的未来发展方向和一些可能的应用前景.
Abstract:
In this paper, current theories and recent developments in collective decisionmaking over complex 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 dynamics is also presented. Finally possible future research directions and applications for collective decisionmaking in complex networks are given.

参考文献/References:

[1] STAUFFER D. Opinion dynamics and sociophysics [EB/OL].[20070507]. http://arxiv.org/abs/0705.0891v1.
[2] STAUFFER D. Sociophysics simulations II: opinion dynamics [C]// AIP Conference Proceedings, Granada,Spain,2005, 779: 5668.
[3] STAUFFER D, De OLIVEIRA S, De OLIVEIRA PMC, et al. Biology, sociology, geology by computational physicists [M]. Amsterdam: Elsevier, 2006. 
[4] BILLARI FC, FENT T, PRSKAWETZ A, et al. Agentbased computational modeling [M]. Heidelberg: PhysicaVerlag, 2006.
[5] JAIN S, MUKAND S. Public opinion and the dynamics of reform [C]// Sixth Jacques Polak Annual Research Conference Hosted by the International Monetary Fund Washington. Washington,USA,2005. 
[6] VALLACHER R R, NOWAK A, MILLER M E. Social influence and group dynamics [M].New York: Wiley, 2003.
[7] BALDASSARRI D, BEARMAN P. Dynamics of political polarization [J]. American Sociological Review, 2007, 72(5):784811. 
[8] BLUME L, DURLAUF S. The economy as an evolving complex system III [M]. Oxford: Oxford University Press, 2004.
[9] K RAWIECKI A, HOLYST J A, HELBING D. Volatilityclustering and scaling for financial time series due to attractor bubbling [J]. Phys Rev Lett, 2002, 89(15): 158701
[10]HERRERAVIEDMA E, MARTINEZ L, MATA F, et al. A consensus support system model for group decisionmaking problems with multigranular linguistic preference relations [J]. IEEE Transactions on Fuzzy Systems, 2005, 13(5): 644658.
[11]HUMMEL R, MEMBER, MANEVITZ L. A statistical approach to the representation of uncertainty in beliefs using spread of opinions [J]. IEEE Tranactions on System, Man, Cyberneticspart A: System and Humans, 1996, 26(3): 378384.
[12]LEE H S. Aggregation of fuzzy opinions under group decision making environment [C]// IEEE International Fuzzy Systems Conference, Melbourne, Australia, 2001: 172175.
[13]LEE H S. An optimal aggregation method for fuzzy opinion of group decision [C]// IEEE International Conference on Systems, Man and Cybernetics.Tokyo, 1999: 314319.
[14]KAIZOJI T, SUZUDO T. Evolutionary model of opinion formation [C]// ICCIMA Proceedings of the Fourth International Conference on Computational Intelligence and Multimedia Applications.Yokusika,Japan,2001: 39.
[15]RAMIREZCANO D, PITT J. Follow the leader: Profiling Agents in an opinion formation model of dynamic confidence and individual mindsets [C]// Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology.Hong Kong,China, 2006: 660667.
[16]LEVY W B, DELIC H. Maximum entropy aggregation of individual opinions [J]. IEEE Transactions on Systems,Man and Cybernetics, 1994, 24(4): 606613.
[17]GREENSTEIN S. Contrasting opinions about convergence [J]. IEEE Micro Economics, 1997, 17(5): 78.
[18]ONO K, HARAO M, HIRATA K. MultiAgent based modeling and simulation of consensus formations in arguments [C]// IEEE Proceedings of the Third International Conference on Information Technology and Applications, Sydney,Australia,2005: 264267.
[19]LAN J B, XU Y, LIU J Z. Multiple attributes group decision making under fuzzy environment [C]// IEEE International Conference on Systems Man and Cybernetics.[S.l.].2003: 49864991.
[20]HSIAO W F, LIN H H, CHANG T M. Valuebased consensus measure on verbal opinions [C]// Proceedings of the 38th Hawaii International Conference on System Science,Hawaii,USA, 2005: 16.
[21]MANTEGNA R N, STANLEY H E. An introduction to Econophysics: correlations and complexity in finance [M]. Cambridge, England: Cambridge University Press, 1999.
[22]DEFFUANT G, AMBLARD F, WEISBUCH G, et al. How can extremism prevail? a study based on the relative agreement interaction model [J]. Journal of Artificial Societies and Social Simulation, 2002, 5(4):110.
[23]HEGSELMANN R. Opinion dynamics and bounded confidence models, analysis, and simulation [J]. Journal of Artificial Societies and Social Simulation, 2002, 5(3):5562.
[24]AIKENS G S, CANDIDATE D. The democratization of systems of public opinion formation[EB/OL]. [20070320]http://ieeexplore.ieee.org/iel3/3818/11162/00540433.pdf?arnumber=540433.
[25]KNOTZER N, MADLBERGER M. Consumers’ interest in personalized recommendations: the role of productinvolvement and opinion seeking [C]// Proceedings of the 40th Hawaii International Conference on System Science.Hawaii,USA,2007: 168173.
[26]STROGATZ S H. Exploring complex networks [J]. Nature, 2001, 410: 268276.
[27]ALBERT R, BARABASI A L. Statistical mechanics of complex networks [J]. Rev Mod Phys, 2002, 74(1): 4797.
[28]WANG X F, CHEN G R. Complex networks: smallworld, scalefree and beyond [J]. IEEE Cir Sys Mag, 2003, 3(1): 620.
[29]NEWMAN M E J. The structure and function of complex networks [J]. SIAM Review, 2003, 45(2): 167256.
[30]BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics [J]. Physics Reports, 2006, 424: 175308.[31] WATTS D J, STROGATZ S H. Collective dynamics of ’smallworld’ networks [J]. Nature, 1998, 393: 440442.
[32] BARABASI A L, ALBERT R. Emergence of scaling in random networks [J]. Science, 1999, 286: 509512.
[33] NOWAK M A, PLOTKIN J B, KRAKAUER D C. The evolutionary language game[J]. J Theo Biol, 1999, 200: 147162.
[34] NOWAK M A, KOMAROVA N L, NIYOGI P. Computational and evolutionary aspects of language [J]. Nature, 2002, 417: 611617.[35] NOWAK M A. Evolutionary dynamics [M]. Cambridge, Massachusetts: Harvard University Press, 2006. 
[36] NOWAK M A, KRAKAUER D C. The evolution of language [J]. Procedings of the National Academy of Sciences of the United States of America, 1999, 96: 80288033.
[37] NOWAK M A, KOMAROVA N L. Towards an evolutionary theory of language [J]. Trends in Cognitive Sciences, 2001, 5(7): 288295.[38] LENAERTS T, JANSEN B, TUYLS K, et al. The evolutionary language game: an orthogonal approach [J]. J Theo Biol, 2005, 235: 566582.
[39] VYLDER B D, TUYLS K. How to reach linguistic consensus:a proof of convergence for the naming game [J]. J Theo Biol, 2006, 242: 818831.
[40] DALL’ L, BARONCHELLI A. Microscopic activity patterns in the naming game [J]. J Phys A: Math Gen, 2006, 39: 1485114867.[41] DALL’ASTA L, BARONCHELLI A. Nonequilibrium dynamics of language games on complex networks [J]. Phys Rev E, 2006, 74: 036105.
[42] BARONCHELLI A, DALL’ASTA L, BARRAT A, et al. Topologyinduced coarsening in language games [J]. Phys Rev E, 2006, 73: 015102.
[43] DALL’ASTA L, BARONCHELLI A, BARRAT A,et al. Agreement dynamics on smallworld networks [J]. Europhys Lett, 2006, 73(6): 969975.
[44] BARONCHELLI A, FELICI M, LORETO V, et al. Sharp transition towards shared vocabularies in multiagent systems [J]. J Stat Mech, 2006, 6: 06014.
[45] TANG C L, LIN B Y, WANG W X, et al. Role of connectivityinduced weighted words in language games [J]. Phys Rev E, 2007, 75: 027101.
[46] LIN B Y, REN J, YANG H J, et al. Naming game on smallworld networks: the role of clustering structure [EB/OL]. [20061015]. http://arxiv.org/abs/physics/0607001v2.
[47] LU Q, KORNISS G, SZYMANSKI B K. Dynamics of naming games in random geometric networks [EB/OL]. [20070507]. http://arxiv.org/abs/cs/0604075.
[48] OLFATISABER R, FAX J A, MURRAY R M. Consensus and cooperation in networked multiAgent systems [J]. Proceedings of the IEEE, 2007, 95(1): 215233.
[49] REN W, BEARD R W, ATKINS E M. Information consensus in multivehicle cooperative control [J]. IEEE Control Systems Magazine, 2007, 27(2): 7182.
[50] ACEBRON J, BONILLA L L, PEREZ C J, et al. The Kuramoto model: a simple paradigm for synchronization phenomena [J]. Rev Mod Phys, 2005, 77:137185.
[51] STROGATZ S H. From kuramoto to crawford: exploring the onset of synchronization in populations of coupled oscillators [J]. Physica D, 2000, 143: 120.
[52] STROGATZ S H. Sync: the emerging science of spontaneous order [M].New York:Hyperion Press, 2003.
[53] KURAMOTO Y. Chemical oscillations, waves, and turbulence [M]. Berlin: SpringerVerlag, 1984.
[54] BARTOLOZZI M, LEINWEBER D B, THOMAS A W. Stochastic opinion formation in scalefree networks [J]. Phys Rev E, 2005, 72: 046113.
[55] JUNG W S, MOON H T, STANLEY H E. Dynamics of clustered opinions in complex networks [EB/OL]. [20070803]. http://arxiv.org/abs/physics/0702108.
[56] GLAUBER R. Timedependent statistics of the Ising model [J]. Math Phys, 1963, 4: 294307.
[57] SZNAJDWERON K. Dynamical model of Ising spins [J]. Phys Rev E, 2004, 70: 037104.
[58] GALAM S. Rational group decision making: a random field Ising model at T=0 [J]. Physica A, 1997, 238: 6680.
[59] KWAK W, YANG J S, SOHN J I, et al. Critical behavior of the majority voter model is independent of transition rates [J]. Phys Rev E, 2007, 75: 061110.
[60] SOOD V, REDNER S. Voter model on heterogeneous graphs [J]. Phys Rev Lett, 2005, 94: 178701.
[61] MOBILIA M, PETERSEN A, REDNER S. On the role of zealotry in the voter model [J]. J Stat Mech, 2007, 8: 08029.
[62] CHEN P, REDNER S. Majority rule dynamics in finite dimensions [J]. Phys Rev E, 2005, 71: 036101.
[63] LAMBIOTTE R, AUSLOOS M, HOLYST J A. Majority model on a network with communities [J]. Phys Rev E, 2007, 75: 030101.
[64] KRAPIVSKY P L, REDNER S. Dynamics of majority rule in twostate interacting spin systems [J]. Phys Rev Lett, 2003, 90(23): 238701.[65] GABBAY M. The effects of nonlinear interactions and network structure in small group opinion dynamics [J]. Physica A, 2007, 373: 118126.
[66] LIGGETT T M. Stochastic interaction systems: contact, voter, and exclusion processes [M]. New York: SpringerVerlag, 1999.
[67] KRAPIVSKY P L. Kinetics of monomermonomer surface catalytic reactions [J]. Phys Rev A, 1992, 45: 10671072.
[68] SUCHECKI K, HOLYST J A. Voter model on Sierpinski fractals [J]. Physica A, 2006, 362 : 338344.
[69] CASTELLANO C, VILONE D, VESPIGNANI A. Incomplete ordering of the voter model on smallworld networks [J]. Europhys Lett, 2003, 63: 153158.
[70] SUCHECKI K, EGUILUZ V M, MIGUEL M S. Conservation laws for the voter model in complex networks [J]. Europhys Lett, 2005, 69: 228234.
[71] LI P P, ZHENG D F, HUI P M. Dynamics of opinion formation in a smallworld network [J]. Phys Rev E, 2006, 73: 056128.
[72] LAMBIOTTE R. How does degree heterogeneity affect an orderdisorder transition [J]. Europhys Lett, 2007, 78: 68002.
[73] LAMBIOTTE R, AUSLOOS M. Coexistence of opposite opinions in a network with communities [J]. J Stat Mech, 2007, 8: 08026.
[74] SOUSA A O. Bounded confidence model on a still growing scalefree network [EB/OL]. [20050119]. http://arxiv.org/abs/condmat/0406766v2.
[75] DEFFUANT G, NEAU D, AMBLARD F, et al. Mixing beliefs among interacting agents[J]. Adv Complex Syst, 2000(3): 8798.
[76] FORTUNATO S. Damage spreading and opinion dynamics on scalefree networks [J]. Physica A, 2005, 348: 683690.
[77] LORENZ J. Continuous opinion dynamics of multidimensional allocation problems under bounded confidence: More dimensions lead to better chances for consensus[EB/OL].[20070821]. http://acseg.univmrs.fr/document/Lorenzpapier.pdf.
[78] GALAM S. Social paradoxes of majority rule voting and renormalization group [J]. J Stat Phys, 1990, 61: 943951.
[79] GALAM S. Heterogeneous beliefs, segregation, and extremism in the making of public opinions [J]. Phys Rev E, 2005, 71: 046123.[80] GALAM S. Contrarian deterministic effects on opinion dynamics: the hung elections scenario [J]. Physica A, 2004, 333: 453460.[81] GALAM S, BORGHESI C. Chaotic, staggered, and polarized dynamics in opinion forming: the contrarian effect [J]. Phys Rev E, 2006, 73: 066118.
[82] GUZMANVARGAS L, HERNANDEZPEREZ R. Smallworld topology and memory effects on decision time in opinion dynamics [J]. Physica A, 2006, 372: 326332.
[83] GEKLE S, PELITI L, GALAM S. Opinion dynamics in a threechoice system [J]. Euro Phys J B, 2005, 45: 569575.

[84] STAUFFER D, SAHIMI M. Can a few fanatics influence the opinion of a large segment of a society [J]. Euro Phys J B, 2007, 57: 147152.
[85] PETTER H, NEWMAN M E J. Nonequilibrium phase transition in the coevolution of networks and opinions [J]. Phys Rev E, 2006, 74: 056108.
[86] GIL S, ZANETTE D H. Coevolution of Agent and networks: opinion spreading and community disconnection [J]. Phys Lett A, 2006, 356: 8994.
[87] ZANETTE D H, GIL S. Opinion spreading and Agent segregation on evolving networks [J]. Physica D, 2006, 224: 156165.
[88] ROSVALL M, SNEPPEN K. Modeling selforganization of communication and topology in social networks [J]. Phys Rev E, 2006, 74: 016108.
[89] VAZQUEZ F, GONZALEZAVELLA J C, EGUILUZ V M, et al. Timescale competition leading to fragmentation and recombination transitions in the coevolution of network and states [J]. Phys Rev E, 2007, 76: 046120. 
[90] KOZMA B, BARRAT A. Consensus formation on adaptive networks [J]. Phys Rev E, 2007, 77: 016102.
[91] BENCZIK I J, BENCZIK S Z, SCHMITTMANN B, et al. Lack of consensus in social systems [EB/OL]. [20070925]. http://arxiv.org/abs/0709.4042v1.
[92] VAZQUEZ F, EGUILUZ V M, MIGUEL M S. Generic absorbing transition in coevolution dynamics [EB/OL]. [20071025]. http://arxiv.org/abs/0710.4910v1.
[93] NARDINI C, KOZMA B, BARRAT A. Who’s talking first? Consensus of lack thereof in coevolving opinion formation models [EB/OL].[20071108]. http://arxiv.org/abs/0711.1261v1.
[94] CASTELLANO C, FORTUNATO S, LORETO V. Statistical physics of social dynamics [EB/OL]. [20071017]. http://arxiv.org/abs/0710.3256v1.
[95] VICSEK T, CZIROK A, BENJACOB E, et al. Novel type of phase transition in a system of selfdriven particles [J]. Phys Rev Lett, 1995, 75(6): 12261229.
[96] HOFBAUER J, SIGMUND K. Evolutionary games and population dynamics [M]. Cambridge: Cambridge University Press, 1998.
[97] TAYLOR C, NOWAK M A. Evolutionary game dynamics with nonuniform interaction rates [J]. J Theo Bio, 2006, 69: 243252.
[98] HOLYST J A, KACPERSKY K,SCHWEITZER F. Social impact models of opinion dynamics [J]. Annual Reviews of Computational Physics IX, 2001(1): 253273.
[99] MARE A D, LATORA V. Opinion formation models based on game theory [EB/OL]. [20060914]. http://arxiv.org/abs/physics/0609127v1.
[100] BARABASI A L. Taming complexity [J]. Nature physics, 2005( 1): 6870.

相似文献/References:

[1]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报,2009,(05):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
 XIA Cheng-yi,LIU Zhong-xin,CHEN Zeng-qiang,et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems,2009,(02):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[2]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报,2011,(01):57.
 LI Wei,YANG Xiaofeng,ZHANG Chongyang,et al.A clustering method for community detection on complex networks[J].CAAI Transactions on Intelligent Systems,2011,(02):57.
[3]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报,2011,(03):208.
 SUN Shiwen,XIA Chengyi,WANG Li.Survey of the measurement of software structures based on complex networks[J].CAAI Transactions on Intelligent Systems,2011,(02):208.
[4]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报,2013,(02):128.[doi:10.3969/j.issn.1673-4785.201210027]
 ZHAO Jing,XIA Chengyi,SUN Shiwen,et al.A novel SIR model with infection delay and nonuniform transmission in complex networks[J].CAAI Transactions on Intelligent Systems,2013,(02):128.[doi:10.3969/j.issn.1673-4785.201210027]
[5]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报,2014,(06):734.[doi:10.3969/j.issn.1673-4785.201311014]
 QIU Jianping,CHEN Lichao,PAN Lihu.Synchronization in complex networks via pinning control[J].CAAI Transactions on Intelligent Systems,2014,(02):734.[doi:10.3969/j.issn.1673-4785.201311014]
[6]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报,2015,(04):508.[doi:10.3969/j.issn.1673-4785.201408006]
 LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,(02):508.[doi:10.3969/j.issn.1673-4785.201408006]
[7]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报,2015,(04):577.[doi:10.3969/j.issn.1673-4785.201411031]
 CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,(02):577.[doi:10.3969/j.issn.1673-4785.201411031]
[8]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,(6):949.[doi:10.11992/tis.201507042]
 WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,(02):949.[doi:10.11992/tis.201507042]
[9]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报,2016,(3):426.[doi:10.11992/tis.201603045]
 ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,(02):426.[doi:10.11992/tis.201603045]
[10]闫玲玲,陈增强,张青.基于度和聚类系数的中国航空网络重要性节点分析[J].智能系统学报,2016,(5):586.[doi:10.11992/tis.201601024]
 YAN Lingling,CHEN Zengqiang,ZHANG Qing.Analysis of key nodes in China’s aviation network basedon the degree centrality indicator and clustering coefficient[J].CAAI Transactions on Intelligent Systems,2016,(02):586.[doi:10.11992/tis.201601024]

备注/Memo

备注/Memo:
收稿日期:2007-07-12.
基金项目:
国家自然科学基金资助项目(60674050,60528007);
国家“973”资助项目(2002CB312200);
国家“863”资助项目(2006AA04Z258);
“十一五”计划资助项目(A2120061303).
作者简介:
王  龙,男,1964年生,教授、博士生导师、长江学者,主要研究方向为复杂系统智能控制、多机器人系统的协调与控制、网络化控制系统的分析与综合、集群行为与集群智能、演化博弈与群体决策等,特别是在参数摄动系统、离散事件系统、混合集成系统的分析与控制方面,作出了突出贡献,取得了一系列具有国际水平的重要成就.是国家教委跨世纪人才基金、国家杰出青年科学基金、日本学术振兴基金获得者.其研究成果被国内外广泛引用,并获得国家教委霍英东奖(研究类一等奖)、国家自然科学奖、国家教委科技进步奖(一等奖)、第一届Ho Outstanding Paper Award、第一届关肇直控制理论奖等多项奖励.伏  锋,男,1981年生,博士研究生,主要研究方向为实证网络分析、网络建模、复杂网络上的演化博弈动力学和观点动力学等. 
陈小杰,男,1982年生,博士研究生,主要研究方向为网络建模、复杂网络上的演化博弈动力学和观点动力学等.
通讯作者:王 龙.E-mail:longwang@pku.edu.cn.
更新日期/Last Update: 2009-05-11