Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation: a tutorial overview. (English) Zbl 1360.93001
Summary: In this tutorial paper, we study three specific applications: opinion formation in social networks, centrality measures in complex networks and estimation problems in large-scale power systems. These applications fall under a general framework which aims at the construction of algorithms for distributed computation over a network. The two key ingredients of randomization and time-averaging are used, together with a local gossip communication protocol, to obtain convergence of these distributed algorithms to the global synchronous dynamics.
MSC:
| 93-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to systems and control theory |
| 93A15 | Large-scale systems |
| 91D30 | Social networks; opinion dynamics |
| 93E25 | Computational methods in stochastic control (MSC2010) |
Keywords:
networked control systems; distributed randomized algorithms; opinion formation; centrality computation; PageRank; power systems estimationReferences:
| [1] | Abelson, R., Mathematical models of the distribution of attitudes under controversy, (Fredericksen, N.; Gullicksen, H., Contributions to Mathematical Psychology (1964), Holt, Rinehart & Winston: Holt, Rinehart & Winston NewYork, NY) |
| [2] | Abur, A.; Gómez-Expósito, A., Power System State EstimationTheory and Implementation (2004), Marcel Dekker: Marcel Dekker New York |
| [3] | Acemoglu, D.; Como, G.; Fagnani, F.; Ozdaglar, A., Opinion fluctuations and disagreement in social networks, Math. Oper. Res., 38, 1, 1-27 (2013) · Zbl 1297.91130 |
| [4] | Altafini, C.; Lini, G., Predictable dynamics of opinion forming for networks with antagonistic interactions, IEEE Trans. Autom. Control, 60, 2, 342-357 (2015) · Zbl 1360.91114 |
| [5] | Baillieul, J.; Antsaklis, P. J., Control and communication challenges in networked real-time systems, Proc. IEEE, 95, 1, 9-28 (2007) |
| [6] | Barooah, P.; Hespanha, J. P., Estimation from relative measurementsalgorithms and scaling laws, IEEE Control Syst. Mag., 27, 4, 57-74 (2007) |
| [7] | Bertsekas, D. P.; Tsitsiklis, J. N., Parallel and Distributed ComputationNumerical Methods (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0743.65107 |
| [8] | Blondel, V. D.; Hendrickx, J. M.; Tsitsiklis, J. N., On Krause׳s multi-agent consensus model with state-dependent connectivity, IEEE Trans. Autom. Control, 54, 11, 2586-2597 (2009) · Zbl 1367.93426 |
| [9] | Blondel, V. D.; Hendrickx, J. M.; Tsitsiklis, J. N., Continuous-time average-preserving opinion dynamics with opinion-dependent communications, SIAM J. Control Optim., 48, 8, 5214-5240 (2010) · Zbl 1213.93008 |
| [10] | Bonacich, P., Power and centralitya family of measures, Am. J. Sociol., 92, 5, 1170-1182 (1987) |
| [11] | Borgatti, S. P., Centrality and network flow, Social Netw., 96, 27, 55-71 (2005) |
| [12] | Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE Trans. Inf. Theory, 52, 6, 2508-2530 (2006) · Zbl 1283.94005 |
| [13] | Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Comput. Netw. ISDN Syst., 30, 1, 107-117 (1998) |
| [14] | Bryan, K.; Leise, T., The \(25,000,000,000 eigenvectorthe linear algebra behind Google, SIAM Rev., 48, 3, 569-581 (2006\) · Zbl 1115.15007 |
| [15] | Bullo, F.; Carli, R.; Frasca, P., Gossip coverage control for robotic networksdynamical systems on the space of partitions, SIAM J. Control Optim., 50, 1, 419-447 (2012) · Zbl 1253.37089 |
| [16] | Bullo, F.; Cortès, J.; Martìnez, S., Distributed Control of Robotic Networks, Applied Mathematics Series (2009), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1193.93137 |
| [17] | Canuto, C.; Fagnani, F.; Tilli, P., An Eulerian approach to the analysis of Krause׳s consensus models, SIAM J. Control Optim., 50, 1, 243-265 (2012) · Zbl 1242.93005 |
| [18] | Carron, A.; Todescato, M.; Carli, R.; Schenato, L., An asynchronous consensus-based algorithm for estimation from noisy relative measurements, IEEE Trans. Control Netw. Syst., 1, 3, 283-295 (2014) · Zbl 1370.90064 |
| [19] | Ceragioli, F.; Frasca, P., Continuous and discontinuous opinion dynamics with bounded confidence, Nonlinear Anal.: Real World Appl., 13, 3, 1239-1251 (2012) · Zbl 1239.91129 |
| [22] | Chatterjee, S.; Seneta, E., Towards consensussome convergence theorems on repeated averaging, J. Appl. Probab., 14, 1, 89-97 (1977) · Zbl 0381.60056 |
| [23] | Chiuso, A.; Fagnani, F.; Schenato, L.; Zampieri, S., Gossip algorithms for simultaneous distributed estimation and classification in sensor networks, IEEE J. Select. Top. Signal Process., 5, 4, 691-706 (2011) |
| [25] | Como, G.; Fagnani, F., Scaling limits for continuous opinion dynamics systems, Ann. Appl. Probab., 21, 4, 1537-1567 (2011) · Zbl 1235.60136 |
| [26] | Conejo, A. J.; de la Torre, S.; Canas, M., An optimization approach to multiarea state estimation, IEEE Trans. Power Syst., 22, 1, 213-221 (2007) |
| [27] | DeGroot, M. H., Reaching a Consensus, J. Am. Stat. Assoc., 69, 345, 118-121 (1974) · Zbl 0282.92011 |
| [28] | Deffuant, G.; Neau, D.; Amblard, F.; Weisbuch, G., Mixing beliefs among interacting agents, Adv. Complex Syst., 3, 1-4, 87-98 (2000) |
| [29] | Easley, D.; Kleinberg, J., Networks, Crowds, and MarketsReasoning About a Highly Connected World (2010), Cambridge University Press: Cambridge University Press New York, NY · Zbl 1205.91007 |
| [32] | Freeman, L. C., A set of measures of centrality based upon betweenness, Sociometry, 40, 35-41 (1977) |
| [33] | Freeman, L. C., Centrality in social networksconceptual clarification, Social Netw., 1, 3, 215-239 (1979) |
| [35] | Freris, N. M.; Graham, S. R.; Kumar, P. R., Fundamental limits on synchronizing clocks over networks, IEEE Trans. Autom. Control, 56, 2, 1352-1364 (2011) · Zbl 1368.90021 |
| [36] | Friedkin, N., Theoretical foundations for centrality measures, Am. J. Sociol., 96, 6, 1478-1504 (1991) |
| [37] | Friedkin, N. E., A formal theory of reflected appraisals in the evolution of power, Adm. Sci. Q., 56, 4, 501-529 (2011) |
| [40] | Gómez-Expósito, A.; Abur, A.; de la Villa Jaen, A.; Gómez-Quiles, C., A multilevel state estimation paradigm for smart grids, Proc. IEEE, 99, 6, 952-976 (2011) |
| [41] | Hegselmann, R.; Krause, U., Opinion dynamics and bounded confidence models, analysis, and simulation, J. Artif. Soc. Soc. Simul., 5, 3, 1-33 (2002) |
| [42] | Ishii, H.; Tempo, R., Distributed randomized algorithms for the PageRank computation, IEEE Trans. Autom. Control, 55, 9, 1987-2002 (2010) · Zbl 1368.68045 |
| [43] | Ishii, H.; Tempo, R., The Page Rank problem, multiagent consensus, and web aggregationa systems and control viewpoint, IEEE Control Syst. Mag., 34, 3, 34-53 (2014) |
| [45] | Jiang, W.; Vittal, V.; Heydt, G. T., A distributed state estimator utilizing synchronized phasor measurements, IEEE Trans. Power Syst., 22, 2, 563-571 (2007) |
| [46] | Kekatos, V.; Giannakis, G., Distributed robust power system state estimation, IEEE Trans. Power Syst., 28, 2, 1617-1626 (2012) |
| [47] | Korres, G. N., A distributed multiarea state estimation, IEEE Trans. Power Syst., 26, 1, 73-84 (2011) |
| [48] | Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov Chains and Mixing Times (2009), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1160.60001 |
| [49] | Lin, F.; Fardad, M.; Jovanovic, M., Algorithms for leader selection in stochastically forced consensus networks, IEEE Trans. Autom. Control, 59, 7, 1789-1802 (2014) · Zbl 1360.90052 |
| [51] | Lopes, C. G.; Sayed, A. H., Diffusion least-mean squares over adaptive networksformulation and performance analysis, IEEE Trans. Signal Process., 56, 7, 3122-3136 (2008) · Zbl 1390.94283 |
| [52] | Marelli, D.; Fu, M., Distributed weighted least-squares estimation with fast convergence for large-scale systems, Automatica, 51, 1, 27-39 (2015) · Zbl 1309.93159 |
| [53] | Mesbahi, M.; Egerstedt, M., Graph Theoretic Methods for Multiagent Networks, Applied Mathematics Series (2010), Princeton University Press: Princeton University Press Providence, RI · Zbl 1203.93001 |
| [54] | Mirtabatabaei, A.; Bullo, F., Opinion dynamics in heterogeneous networksconvergence conjectures and theorems, SIAM J. Control Optim., 50, 5, 2763-2785 (2012) · Zbl 1258.91191 |
| [55] | Mo, Y.; Kim, T.; Brancik, K.; Dickinson, D.; Lee, H.; Perrig, A.; Sinopoli, B., Cyber-physical security of a smart grid infrastructure, Proc. IEEE, 100, 2, 262-282 (2012) |
| [56] | Mobilia, M.; Petersen, A.; Redner, S., On the role of zealotry in the voter model, J. Stat. Mech.: Theory Exp., 2007, 8, 8-29 (2007) · Zbl 1456.91047 |
| [57] | Monticelli, A., Electric power system state estimation, Proc. IEEE, 88, 2, 262-282 (2000) |
| [58] | Nedic, A.; Ozdaglar, A., Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control, 54, 1, 48-61 (2009) · Zbl 1367.90086 |
| [59] | Newman, M. J., A measure of betweenness centrality based on random walks, Social Netw., 27, 1, 39-54 (2005) |
| [60] | Pasqualetti, F.; Carli, R.; Bullo, F., Distributed estimation via iterative projections with application to power network monitoring, Automatica, 48, 5, 747-758 (2012) · Zbl 1246.93108 |
| [62] | Petersen, I. R.; Tempo, R., Robust control of uncertain systemsclassical results and recent developments, Automatica, 50, 5, 1315-1335 (2014) · Zbl 1296.93048 |
| [63] | Polyak, B.; Juditsky, A., Acceleration of stochastic approximation by averaging, SIAM J. Control Optim., 30, 4, 838-855 (1992) · Zbl 0762.62022 |
| [64] | Ravazzi, C.; Frasca, P.; Tempo, R.; Ishii, H., Ergodic randomized algorithms and dynamics over networks, IEEE Trans. Control Netw. Syst., 2, 1, 78-87 (2015) · Zbl 1370.93308 |
| [68] | Stephenson, K.; Zelen, M., Rethinking centralitymethods and examples, Social Netw., 11, 1, 1-37 (1989) |
| [69] | Tempo, R.; Calafiore, G.; Dabbene, F., Randomized Algorithms for Analysis and Control of Uncertain Systems, with Applications (2013), Springer: Springer London · Zbl 1280.93002 |
| [72] | Vassio, L.; Fagnani, F.; Frasca, P.; Ozdaglar, A., Message passing optimization of harmonic influence centrality, IEEE Trans. Control Netw. Syst., 1, 1, 109-120 (2014) · Zbl 1371.91143 |
| [73] | Wagner, C., Consensus through respecta model of rational group decision-making, Philos. Stud., 34, 4, 335-349 (1978) |
| [75] | White, D. R.; Borgatti, S. P., Betweenness centrality measures for directed graphs, Social Netw., 16, 4, 335-346 (1994) |
| [76] | Yildiz, E.; Ozdaglar, A.; Acemoglu, D.; Saberi, A.; Scaglione, A., Binary opinion dynamics with stubborn agents, ACM Trans. Econ. Comput., 1, 4, 1-30 (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
