论文标题
影响时间网络最大化的有效次数
Effective submodularity of influence maximization on temporal networks
论文作者
论文摘要
我们研究对时间网络的影响最大化。这是一个特殊的设置，其中影响函数不是suppodular，并且没有通过贪婪优化实现的解决方案的最佳保证。我们对真实和合成网络进行详尽的分析。我们表明，随机采样的种子集的影响函数通常违反了子二次性的必要条件。但是，当根据贪婪优化策略选择一组种子时，影响功能有效地作为下函数。具体而言，在真实网络中永远不会观察到对违规的违规，而在合成的网络中很少观察到。与通过蛮力搜索获得的精确解决方案的直接比较表明，贪婪的策略提供了近似的解决方案，这些解决方案符合严格的次管函数保证的最佳差距。因此，贪婪优化似乎是对时间网络影响最大化的有效策略。
We study influence maximization on temporal networks. This is a special setting where the influence function is not submodular, and there is no optimality guarantee for solutions achieved via greedy optimization. We perform an exhaustive analysis on both real and synthetic networks. We show that the influence function of randomly sampled sets of seeds often violates the necessary conditions for submodularity. However, when sets of seeds are selected according to the greedy optimization strategy, the influence function behaves effectively as a submodular function. Specifically, violations of the necessary conditions for submodularity are never observed in real networks, and only rarely in synthetic ones. The direct comparison with exact solutions obtained via brute-force search indicate that the greedy strategy provides approximate solutions that are well within the optimality gap guaranteed for strictly submodular functions. Greedy optimization appears therefore an effective strategy for the maximization of influence on temporal networks.
