论文标题
影响最大化：分裂和征服
Influence Maximization: Divide and Conquer
论文作者
论文摘要
影响最大化的问题，即找到对网络具有最大影响的节点的集合，对于多种应用来说至关重要。在过去的二十年中，已经提出了许多针对影响者的启发式指标。在这里，我们介绍了一个框架，以提高任何此类指标的性能。该框架包括将网络分为影响的扇区，然后选择这些扇区内最具影响力的节点。我们探索三种不同的方法来在网络中找到扇区：图形分区，图形双曲线嵌入和社区结构。通过对真实和合成网络的系统分析来验证该框架。我们表明，随着网络的模块化和异质性的增加，在选择影响的散布器之前，通过将网络分为扇区而产生的性能增长。另外，我们表明，可以在与网络大小线性扩展的时间内有效地执行网络分为扇区，从而使该框架适用于大规模影响最大化问题。
The problem of influence maximization, i.e., finding the set of nodes having maximal influence on a network, is of great importance for several applications. In the past two decades, many heuristic metrics to spot influencers have been proposed. Here, we introduce a framework to boost the performance of any such metric. The framework consists in dividing the network into sectors of influence, and then selecting the most influential nodes within these sectors. We explore three different methodologies to find sectors in a network: graph partitioning, graph hyperbolic embedding, and community structure. The framework is validated with a systematic analysis of real and synthetic networks. We show that the gain in performance generated by dividing a network into sectors before selecting the influential spreaders increases as the modularity and heterogeneity of the network increase. Also, we show that the division of the network into sectors can be efficiently performed in a time that scales linearly with the network size, thus making the framework applicable to large-scale influence maximization problems.
