Identifying critical nodes in complex networks by graph representation learning
This work addresses influence maximization, a key problem in network science, with incremental improvements in efficiency and performance for applications like viral marketing or information diffusion.
The paper tackles the problem of identifying critical nodes for influence maximization in complex networks by proposing a deep graph learning framework called IMGNN, which reduces the size of initial spreaders needed to achieve a fixed infection scale more efficiently than traditional heuristics and outperforms latest algorithms.
Because of its wide application, critical nodes identification has become an important research topic at the micro level of network science. Influence maximization is one of the main problems in critical nodes mining and is usually handled with heuristics. In this paper, a deep graph learning framework IMGNN is proposed and the corresponding training sample generation scheme is designed. The framework takes centralities of nodes in a network as input and the probability that nodes in the optimal initial spreaders as output. By training on a large number of small synthetic networks, IMGNN is more efficient than human-based heuristics in minimizing the size of initial spreaders under the fixed infection scale. The experimental results on one synthetic and five real networks show that, compared with traditional non-iterative node ranking algorithms, IMGNN has the smallest proportion of initial spreaders under different infection probabilities when the final infection scale is fixed. And the reordered version of IMGNN outperforms all the latest critical nodes mining algorithms.