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.

翻译：在网络中找到最有影响力的节点是一个计算上很困难的问题,在各种基于网络的问题中可能会有几种应用。 虽然提出了几种方法来解决影响最大化(IM)问题, 但当网络规模扩大时,其运行时间通常不那么精确。 我们在这里提出了一个基于网络缩小缩放的原始方法, 使多目标进化算法(MOEA)能够在缩小规模的网络中解决IM问题, 同时保留原始网络的相关特性。 缩小规模的解决方案随后升级到原始网络, 使用以PageRank等核心指标为基础的机制。 我们在8个大型网络上的结果( 包括2个以$\sim50k节点计算) 显示, 与原始网络所需的时间相比, 运行时间增加了10倍以上, 与 CELF 相比, 减少了82 $ 。