Community-based k-shell decomposition for identifying influential spreaders

How to identify the most influential nodes in a network for the maximization of influence spread is a great challenge. Known methods like k-shell decomposition determine core nodes who individually might be the most influential spreaders for the spreading originating in a single origin. However, these techniques are not suitable for determining multiple origins that together lead to the most effective spreading. The reason is that core nodes are often found to be located closely to each other, which results in large overlapping regions rather than spreading far across the network. In this paper, we propose a new algorithm, called community-based k-shell decomposition, by which a network can be viewed as multiple hierarchically ordered structures each branching off from the innermost shell to the periphery shell. To alleviate the overlap problem, our algorithm pursues a greedy strategy that preferably selects core nodes from different communities in the network, thus maximizing the joint influence of multiple origins. We systematically evaluate our algorithm against competing algorithms on multiple networks with varying network characteristics, and find that our algorithm outperforms other algorithms on networks that exhibit community structures, and the stronger communities, the better performance.