Influence maximization: Divide and conquer

作     者：Siddharth Patwardhan Filippo Radicchi Santo Fortunato 

作者机构：Center for Complex Networks and Systems Research Luddy School of Informatics Computing and Engineering Indiana University Bloomington Indiana 47408 USA Indiana University Network Science Institute (IUNI) Indiana Univeristy Bloomington Indiana 47408 USA 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2023年第107卷第5期

页      面：054306-054306页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

基　　金：National Science Foundation, NSF, (1927418) Air Force Office of Scientific Research, AFOSR, (FA9550-19-1-0391, FA9550-21-1-0446) Army Research Office, ARO, (W911NF-21-1-0194) 

主　　题：Community structure Guided network search Network optimization Network structure Spreading 

摘      要：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 such metrics. 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.