Influence Maximization: Divide and Conquer

Abstract

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.

References in corpus (10)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Community detection in networks: A user guide
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Predicting percolation thresholds in networks
• Three faces of node importance in network epidemiology: Exact results for small graphs
• Systematic comparison of graph embedding methods in practical tasks