论文标题
蒙斯托：一种估计和最大化对未见网络影响的归纳方法
MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Networks
论文作者
论文摘要
影响最大化（IM）是社交网络分析中最重要的问题之一。它的目标是找到给定数量的种子节点，以最大程度地通过社交网络传播信息。由于这是一个NP硬性问题，因此已经开发了许多近似/启发式方法，并且其中许多重复蒙特卡洛（MC）模拟一遍又一遍，以可靠地估计种子集的影响（即受感染节点的数量）。在这项工作中，我们提出了一种称为Monte Carlo Simulator（Monstor）的归纳机器学习方法，用于估计培训期间看不见的社交网络中给定的种子节点的影响。据我们所知，蒙斯托是为此目的的第一种归纳方法。 Monstor可以通过替换重复的MC模拟来大大加速现有的IM算法。在我们的实验中，蒙斯托提供了高度准确的估计，在看不见的现实世界社交网络中实现了0.998或更高的Pearson和Spearman相关系数。此外，在63％的IM用例中，配备有Monstor的IM算法比最先进的竞争对手更准确。
Influence maximization (IM) is one of the most important problems in social network analysis. Its objective is to find a given number of seed nodes that maximize the spread of information through a social network. Since it is an NP-hard problem, many approximate/heuristic methods have been developed, and a number of them repeat Monte Carlo (MC) simulations over and over to reliably estimate the influence (i.e., the number of infected nodes) of a seed set. In this work, we present an inductive machine learning method, called Monte Carlo Simulator (MONSTOR), for estimating the influence of given seed nodes in social networks unseen during training. To the best of our knowledge, MONSTOR is the first inductive method for this purpose. MONSTOR can greatly accelerate existing IM algorithms by replacing repeated MC simulations. In our experiments, MONSTOR provided highly accurate estimates, achieving 0.998 or higher Pearson and Spearman correlation coefficients in unseen real-world social networks. Moreover, IM algorithms equipped with MONSTOR are more accurate than state-of-the-art competitors in 63% of IM use cases.
