1. Targeting influence in a harmonic opinion model
- Author
-
Boyd, Zachary M., Fraiman, Nicolas, Marzuola, Jeremy L., Mucha, Peter J., and Osting, Braxton
- Subjects
Computer Science - Social and Information Networks ,Mathematics - Numerical Analysis ,Mathematics - Probability ,35J05, 05C50, 49M41, 65K10 - Abstract
Influence propagation in social networks is a central problem in modern social network analysis, with important societal applications in politics and advertising. A large body of work has focused on cascading models, viral marketing, and finite-horizon diffusion. There is, however, a need for more developed, mathematically principled \emph{adversarial models}, in which multiple, opposed actors strategically select nodes whose influence will maximally sway the crowd to their point of view. In the present work, we develop and analyze such a model based on harmonic functions and linear diffusion. We prove that our general problem is NP-hard and that the objective function is monotone and submodular; consequently, we can greedily approximate the solution within a constant factor. Introducing and analyzing a convex relaxation, we show that the problem can be approximately solved using smooth optimization methods. We illustrate the effectiveness of our approach on a variety of example networks., Comment: 23 pages, 5 figures, comments welcome!!
- Published
- 2024