Abstract
We explore the competitive influence maximisation problem in the voter model. We extend past work by modelling real-world settings where the strength of influence changes nonlinearly with external allocations to the network. We use this approach to identify two distinct regimes—one where optimal intervention strategies offer significant gain in outcomes, and the other where they yield no gains. The two regimes also vary in their sensitivity to budget availability, and we find that in some cases, even a tenfold increase in the budget only marginally improves the outcome of an intervention in a population.
This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W911NF-16-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon. The authors would like to thank Dr. Markus Brede for the insightful discussions. The authors acknowledge the use of the IRIDIS High Performance Computing Facility at the University of Southampton for the completion of this work.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For a comprehensive review see [2].
- 2.
The total vote-share is a function of the network structure L, competitor allocations \(p_{B}\) and controller allocations \(p_{A}\). The maximum vote-share \(X_{A}^*\) is achieved by the optimal allocation vector \(p_{A}^*\).
- 3.
Given by \(\nabla _{p_{A}} X_{A} = \frac{1}{N} \boldsymbol{1}^{T} [L+diag(p_{A}+p_{B})] ^{-1} (I - diag(x_{A})).\)
- 4.
When \(X_{A}(t+1) < X_{A}(t)\), the solution \(p_{A}(t+1)\) at time step \((t+1)\) is rejected and the allocation vector is optimised again with an updated step-length \(\eta (t+1) = \frac{\eta (t)}{2}\).
- 5.
See https://github.com/Optimizater/Lp-ball-Projection for more details.
- 6.
The majorisation step relaxes and linearises the \(\ell _{p}\) ball to obtain a weighted \(\ell _{1}\) ball, and the minimisation step obtains the projection of the point on the \(\ell _{1}\) ball.
References
Barbero, A., Sra, S.: Modular proximal optimization for multidimensional total-variation regularization. arXiv preprint arXiv:1411.0589 (2014)
Castellano, C., Fortunato, S., Loreto, V.: Statistical physics of social dynamics. Rev. Mod. Phys. 81(2), 591 (2009)
Castellano, C., Muñoz, M.A., Pastor-Satorras, R.: Nonlinear q-voter model. Phys. Rev. E 80(4), 041129 (2009)
Chakraborty, S., Stein, S., Brede, M., Swami, A., de Mel, G., Restocchi, V.: Competitive influence maximisation using voting dynamics. In: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 978–985 (2019)
Clifford, P., Sudbury, A.: A model for spatial conflict. Biometrika 60(3), 581–588 (1973)
Darko, A., Chan, A.P.: Review of barriers to green building adoption. Sustain. Dev. 25(3), 167–179 (2017)
Goldstein, D.G., McAfee, R.P., Suri, S.: The effects of exposure time on memory of display advertisements. In: Proceedings of the 12th ACM Conference on Electronic Commerce, pp. 49–58. ACM (2011)
Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., Arenas, A.: Self-similar community structure in a network of human interactions. Phys. Rev. E 68(6), 065103 (2003)
Holley, R.A., Liggett, T.M.: Ergodic theorems for weakly interacting infinite systems and the voter model. Ann. Probab. 3(4), 643–663 (1975)
Jain, P., Kar, P., et al.: Non-convex optimization for machine learning. Found. Trends Mach. Learn. 10(3–4), 142–363 (2017)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)
Masuda, N.: Opinion control in complex networks. New J. Phys. 17(3), 033031 (2015)
Moon, S.: Analysis of Twitter unfollow: how often do people unfollow in Twitter and why? In: Datta, A., Shulman, S., Zheng, B., Lin, S.-D., Sun, A., Lim, E.-P. (eds.) SocInfo 2011. LNCS, vol. 6984, pp. 7–7. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24704-0_6
Newman, M.: Networks. Oxford University Press, Oxford (2018)
Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86(14), 3200 (2001)
Redner, S.: Reality-inspired voter models: a mini-review. C R Phys. 20(4), 275–292 (2019)
Rogers, E.M.: Diffusion of Innovations. Simon and Schuster, New York (2010)
Romero Moreno, G., Chakraborty, S., Brede, M.: Shadowing and shielding: effective heuristics for continuous influence maximisation in the voting dynamics. PLoS ONE 16(6), e0252515 (2021)
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http://networkrepository.com
Tanabe, S., Masuda, N.: Complex dynamics of a nonlinear voter model with contrarian agents. Chaos Interdisc. J. Nonlinear Sci. 23(4), 043136 (2013)
Tanaka, T., Aoyagi, T.: Optimal weighted networks of phase oscillators for synchronization. Phys. Rev. E 78(4), 046210 (2008)
Yang, X., Wang, J., Wang, H.: Towards an efficient approach for the nonconvex \(\ell _p\) ball projection: algorithm and analysis. arXiv preprint arXiv:2101.01350 (2021)
Yildiz, E., Ozdaglar, A., Acemoglu, D., Saberi, A., Scaglione, A.: Binary opinion dynamics with stubborn agents. ACM Trans. Econ. Comput. (TEAC) 1(4), 1–30 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Chakraborty, S., Stein, S. (2023). Competitive Influence Maximisation with Nonlinear Cost of Allocations. In: Dinh, T.N., Li, M. (eds) Computational Data and Social Networks . CSoNet 2022. Lecture Notes in Computer Science, vol 13831. Springer, Cham. https://doi.org/10.1007/978-3-031-26303-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-26303-3_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-26302-6
Online ISBN: 978-3-031-26303-3
eBook Packages: Computer ScienceComputer Science (R0)