Targeting influence in a harmonic opinion model
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909234389581824 |
|---|---|
| author | Boyd, Zachary M. Fraiman, Nicolas Marzuola, Jeremy L. Mucha, Peter J. Osting, Braxton |
| author_facet | Boyd, Zachary M. Fraiman, Nicolas Marzuola, Jeremy L. Mucha, Peter J. Osting, Braxton |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00213 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Targeting influence in a harmonic opinion model Boyd, Zachary M. Fraiman, Nicolas Marzuola, Jeremy L. Mucha, Peter J. Osting, Braxton Social and Information Networks Numerical Analysis Probability 35J05, 05C50, 49M41, 65K10 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. |
| title | Targeting influence in a harmonic opinion model |
| topic | Social and Information Networks Numerical Analysis Probability 35J05, 05C50, 49M41, 65K10 |
| url | https://arxiv.org/abs/2407.00213 |