Identifying influential nodes in complex networks with community structure

摘要

It is a fundamental issue to find a small subset of influential individuals in a complex network such that they can spread information to the largest number of nodes in the network. Though some heuristic methods, including degree centrality, betweenness centrality, closeness centrality, the k-shell decomposition method and a greedy algorithm, can help identify influential nodes, they have limitations for networks with community structure. This paper reveals a new measure for assessing the influence effect based on influence scope maximization, which can complement the traditional measure of the expected number of influenced nodes. A novel method for identifying influential nodes in complex networks with community structure is proposed. This method uses the information transfer probability between any pair of nodes and the k-medoid clustering algorithm. The experimental results show that the influential nodes identified by the k-medoid method can influence a larger scope in networks with obvious community structure than the greedy algorithm without reducing the expected number of influenced nodes.