Controllability of network opinion in Erdös-Rényi graphs using sparse control inputs. (English) Zbl 1468.91115
Summary: This paper considers a social network modeled as an Erdös-Rényi random graph. Each individual in the network updates her opinion using the weighted average of the opinions of her neighbors. We explore how an external manipulative agent can drive the opinions of these individuals to a desired state with a limited additive influence on their innate opinions. We show that the manipulative agent can steer the network opinion to any arbitrary value in finite time (i.e., the system is controllable) almost surely when there is no restriction on her influence. However, when the control input is sparsity constrained, the network opinion is controllable with some probability. We lower bound this probability using the concentration properties of random vectors based on the Lévy concentration function and small ball probabilities. Our theoretical and numerical results shed light on how controllability of the network opinion depends on the parameters such as the size and the connectivity of the network and sity constraints faced by the manipulative agent.
MSC:
| 91D30 | Social networks; opinion dynamics |
| 93B05 | Controllability |
| 05C80 | Random graphs (graph-theoretic aspects) |
Keywords:
social network opinion; sparse controllability; Erdős-Rényi graph; linear propagation; concentration inequalitiesReferences:
| [1] | A. Aydoğdu, M. Caponigro, S. McQuade, B. Piccoli, N. P. Duteil, F. Rossi, and E. Trélat, Interaction network, state space, and control in social dynamics, in Active Particles, Volume 1, Springer, Cham, 2017, pp. 99-140. |
| [2] | A. Banerjee, E. Breza, A. G. Chandrasekhar, and M. Mobius, Naive Learning with Uninformed Agents, Technical report, National Bureau of Economic Research, 2019. |
| [3] | A. Basak and M. Rudelson, Invertibility of sparse non-hermitian matrices, Adv. Math., 310 (2017), pp. 426-483. · Zbl 1406.60013 |
| [4] | P. S. Bearman, J. Moody, and K. Stovel, Chains of affection: The structure of adolescent romantic and sexual networks, Am. J. Sociol., 110 (2004), pp. 44-91. |
| [5] | B. Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc., 286 (1984), pp. 257-274. · Zbl 0579.05046 |
| [6] | B. Bollobás and B. Béla, Random Graphs, Cambridge University Press, Cambridge, UK, 2001. · Zbl 0979.05003 |
| [7] | M. Cremonini and F. Casamassima, Controllability of social networks and the strategic use of random information, Comput. Soc. Netw., 4 (2017), 10. |
| [8] | M. H. DeGroot, Reaching a consensus, J. Amer. Statist. Assoc., 69 (1974), pp. 118-121. · Zbl 0282.92011 |
| [9] | R. Dhal and S. Roy, Vulnerability of network synchronization processes: A minimum energy perspective, IEEE Trans. Automat. Control, 61 (2015), pp. 2525-2530. · Zbl 1359.93165 |
| [10] | F. Dietrich, S. Martin, and M. Jungers, Opinion dynamics control by leadership with bounded influence, in Proceedings of the IEEE Conference on Decision and Contral, 2016. |
| [11] | P. Erdös and A. Rényi, On random graphs, Publ. Math. Debrecen, 6 (1959), pp. 290-297. · Zbl 0092.15705 |
| [12] | S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhäuser, Basel, 2013. · Zbl 1315.94002 |
| [13] | S. Friedland and M. Aliabadi, Linear Algebra and Matrices, SIAM, Philadelphia, PA, 2018. · Zbl 1451.15001 |
| [14] | J. Ghaderi and R. Srikant, Opinion dynamics in social networks: A local interaction game with stubborn agents, Automatica J. IFAC, 50 (2014), pp. 3209-3215. · Zbl 1309.93010 |
| [15] | B. Golub and M. O. Jackson, How homophily affects the speed of learning and best-response dynamics, Quart. J. Econom., 127 (2012), pp. 1287-1338. · Zbl 1400.91465 |
| [16] | M. Hautus, Stabilization, controllability and observability of linear autonomous systems, Indag. Math., 73 (1970), pp. 448-455. · Zbl 0212.47302 |
| [17] | M. O. Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2010. · Zbl 1203.91001 |
| [18] | G. Joseph and C. Murthy, Controllability of linear dynamical systems under input sparsity constraints, IEEE Trans. Automat. Control, 66 (2021), pp. 924-931. · Zbl 1536.93078 |
| [19] | M. Kafashan, A. Nandi, and S. Ching, Relating observability and compressed sensing of time-varying signals in recurrent linear networks, Neural Netw., 83 (2016), pp. 11-20. |
| [20] | T. Kailath, Linear Systems, Prentice-Hall, Englewood Cliffs, NJ, 1980. · Zbl 0454.93001 |
| [21] | K. Li, C. R. Rojas, T. Yang, H. Hjalmarsson, K. H. Johansson, and S. Cong, Piecewise sparse signal recovery via piecewise orthogonal matching pursuit, in Proceedings of the IEEE International Conference on Acoustics Speech, and Signal Processing, 2016, pp. 4608-4612. |
| [22] | Z. Liu, J. Ma, Y. Zeng, L. Yang, Q. Huang, and H. Wu, On the control of opinion dynamics in social networks, Phys. A, 409 (2014), pp. 183-198. · Zbl 1402.91635 |
| [23] | K. Luh and V. Vu, Sparse random matrices have simple spectrum, Ann. Inst. Henri Poincaré Probab. Stat., 56 (2020), pp. 2307-2328. · Zbl 1465.60011 |
| [24] | M. Nabi-Abdolyousefi, Social control and optimal marketing, in Controllability, Identification, and Randomness in Distributed Systems, Springer, Cham, 2014, pp. 137-146. · Zbl 1352.93007 |
| [25] | F. Pasqualetti, S. Zampieri, and F. Bullo, Controllability metrics, limitations and algorithms for complex networks, IEEE Trans. Control Netw. Syst., 1 (2014), pp. 40-52. · Zbl 1370.93164 |
| [26] | A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt, Controllability of multi-agent systems from a graph-theoretic perspective, SIAM J. Control Optim., 48 (2009), pp. 162-186. · Zbl 1182.93025 |
| [27] | M. Rudelson and R. Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math., 218 (2008), pp. 600-633. · Zbl 1139.15015 |
| [28] | M. Rudelson and R. Vershynin, Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math., 62 (2009), pp. 1707-1739. · Zbl 1183.15031 |
| [29] | S. Sefati, N. J. Cowan, and R. Vidal, Linear systems with sparse inputs: Observability and input recovery, in Proceedings of the America Control Conference, 2015, pp. 5251-5257. |
| [30] | K. Shu, H. R. Bernard, and H. Liu, Studying fake news via network analysis: Detection and mitigation, in Emerging Research Challenges and Opportunities in Computational Social Network Analysis and Mining, Springer, Cham, 2019, pp. 43-65. |
| [31] | C. Sriram, G. Joseph, and C. R. Murthy, Control of linear dynamical systems using sparse inputs, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, 2020, pp. 5765-5769. |
| [32] | R. Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms, 44 (2014), pp. 135-182. · Zbl 1291.15088 |
| [33] | H.-T. Wai, A. Scaglione, and A. Leshem, Active sensing of social networks, IEEE Trans. Signal Inform. Process. Netw., 2 (2016), pp. 406-419. |
| [34] | N. Wendt, C. Dhal, and S. Roy, Control of network opinion dynamics by a selfish agent with limited visibility, IFAC-PapersOnLine, 52 (2019), pp. 37-42. |
| [35] | Y. Zhao, G. Kou, Y. Peng, and Y. Chen, Understanding influence power of opinion leaders in e-commerce networks: An opinion dynamics theory perspective, Inform. Sci., 426 (2018), pp. 131-147. |
| [36] | Y. Zhao, L. Zhang, M. Tang, and G. Kou, Bounded confidence opinion dynamics with opinion leaders and environmental noises, Comput. Oper. Res., 74 (2016), pp. 205-213. · Zbl 1349.91236 |
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.
