论文标题
全球思考，在本地行动：在最佳播种的非管道影响最大化的最佳播种
Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
论文作者
论文摘要
我们研究$ r $ - 复杂的传播会影响最大化问题。在影响最大化问题中，人们选择了社交网络中固定数量的初始种子，以最大程度地扩散其影响力。在$ r $ - 复杂的传染模型中，如果它至少具有$ r $感染的邻居，则网络中的每个未感染顶点将被感染。在本文中，我们专注于一个随机图模型，称为随机分层块模型，该模型是研究良好的随机块模型的特殊情况。当图并非非常稀疏时，特别是，当每个边缘以概率$ω（n^{ - （1+1/r）}）$出现时，在某些温和的假设下，我们证明，最佳播种策略是将所有种子都放在一个社区中。这匹配这样的直觉，即在非模型级联模型中彼此接近种子会产生协同作用。但是，它与子模型级联模型的直觉（例如独立的级联模型和线性阈值模型）形成鲜明对比，后者附近种子倾向于侵蚀彼此的效果。我们的关键技术是四个级联过程的新型时间同步耦合。最后，我们表明该观察结果产生了多项式时间动态编程算法，如果每个边缘以$ω（n^{ - （1+1/r）}）的概率出现，则输出最佳种子，或以$ o（n^{ - 2}）为$。
We study the $r$-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the $r$-complex contagion model, each uninfected vertex in the network becomes infected if it has at least $r$ infected neighbors. In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability $ω(n^{-(1+1/r)})$, under certain mild assumptions, we prove that the optimal seeding strategy is to put 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 and the linear threshold model) in which nearby seeds tend to erode each others' effects. Our key technique is a novel time-asynchronized coupling of four cascade processes. Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in $ω(n^{-(1+1/r)})$ or in $o(n^{-2})$.
