论文标题
贪婪的局限性：重新访问的无向网络中的影响最大化
Limitations of Greed: Influence Maximization in Undirected Networks Re-visited
论文作者
论文摘要
我们考虑对线性阈值模型下的无向图的影响最大化问题（在网络中选择$ k $种子，从而最大程度地提高预期的总影响）。一方面，我们证明，贪婪的算法总是实现$（1-（1-1/k）^k +ω（1/k^3））$ - 近似值，表明贪婪的算法在无方向的图表上的表现要比通用$（1-（1-（1-1/k）^k）$ bounds bounds farges bydections bydections for Dired dired dired dired dired dired dired dired dired dired dired direction。另一方面，我们通过示出一个示例，在该示例中，贪婪算法最多可以获得$（1-（1-1/k）^k + o（1/k^{0.2}））$近似值，这是不可能的。该结果与以前在独立级联模型上的工作形成鲜明对比。像线性阈值模型一样，贪婪算法在独立级联模型中的有向图上获得了$（1-（1-（1-1/k）^k）$ - 近似值。但是，卡纳（Khanna）和卢西尔（Lucier）表明，在无向图中，贪婪算法的性能要好得多：常数$ c> 0 $的$（1-（1-（1-（1-1/k）^k + c）$）近似值。我们的结果表明，令人惊讶的是，线性阈值模型中没有这种改进。最后，我们表明，在线性阈值模型下，近似值$ $（1-（1-1/k）^k）$如果1）指向图或2）对顶点加权。换句话说，在这两种设置中，贪婪算法无法实现$（1 - （1-1/k）^k + f（k））$ - 对于任何正函数$ f（k）$的近似值。设置2）的结果再次与Khanna和Lucier的$（1-（1-1/K）^K + C）$ - 近似结果的近似结果，其中$（1-（1-（1-1/k）^k + c）$近似值可以将其扩展到位于角度的设置的位置。我们还讨论了更广泛的设置的扩展，包括具有边缘加权图的设置。
We consider the influence maximization problem (selecting $k$ seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a $(1 - (1 - 1/k)^k + Ω(1/k^3))$-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic $(1- (1 - 1/k)^k)$ bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a $(1- (1 - 1/k)^k + O(1/k^{0.2}))$ approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a $(1-(1-1/k)^k)$-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a $(1-(1-1/k)^k + c)$ approximation for constant $c > 0$. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio $(1 - (1 - 1/k)^k)$ is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a $(1 - (1 - 1/k)^k + f(k))$-approximation for any positive function $f(k)$. The result in setting 2) is again in a sharp contrast to Khanna and Lucier's $(1 - (1 - 1/k)^k + c)$-approximation result for the independent cascade model, where the $(1 - (1 - 1/k)^k + c)$ approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.
