论文标题
通过网络缩减的大规模多目标影响最大化
Large-scale multi-objective influence maximisation with network downscaling
论文作者
论文摘要
在网络中找到最有影响力的节点是一个在各种基于网络的问题中的可能应用的计算困难问题。尽管已经提出了几种解决影响最大化问题（IM）问题的方法，但当网络大小增加时，它们的运行时通常会缩放较差。在这里，我们提出了一种基于网络缩减的原始方法，该方法允许多目标进化算法（MOEA）在减少的比例网络上解决IM问题，同时保留原始网络的相关属性。然后使用基于中心度指标（例如Pagerank）的机制将缩小的解决方案升级到原始网络。我们在八个大型网络（包括$ \ sim $ 50K节点）上的结果证明了该方法的有效性，与原始网络所需的时间相比，运行时增益超过10倍，与CELF相比，最高$ 82 \％$ $。
Finding the most influential nodes in a network is a computationally hard problem with several possible applications in various kinds of network-based problems. While several methods have been proposed for tackling the influence maximisation (IM) problem, their runtime typically scales poorly when the network size increases. Here, we propose an original method, based on network downscaling, that allows a multi-objective evolutionary algorithm (MOEA) to solve the IM problem on a reduced scale network, while preserving the relevant properties of the original network. The downscaled solution is then upscaled to the original network, using a mechanism based on centrality metrics such as PageRank. Our results on eight large networks (including two with $\sim$50k nodes) demonstrate the effectiveness of the proposed method with a more than 10-fold runtime gain compared to the time needed on the original network, and an up to $82\%$ time reduction compared to CELF.
