Name
Title | ||
|---|---|---|
Think globally, act locally: On the optimal seeding for nonsubmodular influence maximization |
Abstract | ||
|---|---|---|
In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. We study this problem with the r-complex contagion model, where each uninfected vertex in the network becomes infected if it has at least r infected neighbors. We focus on a random graph model called the stochastic hierarchical blockmodel. When the graph is not exceptionally sparse, under certain mild assumptions, we prove the optimal seeding strategy puts all the seeds in a single community. This matches the intuition that, in a nonsubmodular cascade model, placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model) in which nearby seeds tend to erode each others' effects. We use this observation to design a polynomial-time dynamic programming algorithm for a slightly more general setting. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.ic.2022.104919 | Information and Computation |
Keywords | DocType | Volume |
Influence maximization,r-Complex contagion,Stochastic hierarchical blockmodel | Journal | 285 |
ISSN | Citations | PageRank |
0890-5401 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Grant Schoenebeck | 1 | 509 | 39.48 |
| Biaoshuai Tao | 2 | 0 | 0.34 |
| Fang-Yi Yu | 3 | 0 | 0.34 |