Identifying multiple influential spreaders based on maximum connected component decomposition method

Identifying influential spreaders is of great significance to the information diffusion, the identifying of hub protein, the control of infectious diseases. For multiple spreaders, an ideal situation is that not only the spreaders themselves are influential but also relatively dispersed to effectively reduce overlaps. However, it is difficult to make a good tradeoff between them. In this paper, the maximum connected component decomposition method (MCCD) is proposed to identify influential spreaders in complex networks. In this method, different topological attributes of nodes are comprehensively considered and combined with the decomposition method of maximum connected components (MCC) with the topological features. Firstly, the nodes are reranked according to the comprehensive consideration of network topology information. Then, the nodes with higher rankings in the network are checked. If the size and number of the largest connected components in the network are the smallest after deleting a node, the node is selected as the new spreader. When multiple nodes have the same size and number of the maximum connected components, values of which are minimal in all cases, topology information for other connected components of these nodes is considered. Moreover, the method can identify initial spreaders that are not the highest ranking but have great impacts on the network, including the spreading speed, propagation range, and distribution range of initial spreaders. Experimental studies in the Susceptible–Infected–Recovered (SIR) model are shown in four networks to verify the performance of our proposed method along with seven centrality-based and heuristic methods.