Vital Node Identification in Complex Networks Using a Machine
  Learning-Based Approach
  Vital node identification is the problem of finding nodes of highest
importance in complex networks. This problem has crucial applications in
various contexts such as viral marketing or controlling the propagation of
virus or rumours in real-world networks. Existing approaches for vital node
identification mainly focus on capturing the importance of a node through a
mathematical expression which directly relates structural properties of the
node to its vitality. Although these heuristic approaches have achieved good
performance in practice, they have weak adaptability, and their performance is
limited to specific settings and certain dynamics. Inspired by the power of
machine learning models for efficiently capturing different types of patterns
and relations, we propose a machine learning-based, data driven approach for
vital node identification. The main idea is to train the model with a small
portion of the graph, say 0.5% of the nodes, and do the prediction on the rest
of the nodes. The ground-truth vitality for the train data is computed by
simulating the SIR diffusion method starting from the train nodes. We use
collective feature engineering where each node in the network is represented by
incorporating elements of its connectivity, degree and extended coreness.
Several machine learning models are trained on the node representations, but
the best results are achieved by a Support Vector Regression machine with RBF
kernel. The empirical results confirms that the proposed model outperforms
state-of-the-art models on a selection of datasets, while it also shows more
adaptability to changes in the dynamics parameters.
