[1]WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,3(2):95-108.
Copy

Collective decision-making over complex networks

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 2 Page number: 95-108 Column: 学术论文—智能系统 Public date: 2008-04-25
Title:
Collective decision-making over complex networks
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
CLC:
TP18
DOI:
-
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.
Similar References:

Memo

-

Last Update: 2009-05-11

Copyright © CAAI Transactions on Intelligent Systems