Identifying influential nodes in complex networks with community structure

• DOI: 10.1016/j.knosys.2013.01.017
• Publication Date: 2013-01-26T16:15:40Z
• Authors: Xiaohang Zhang; Ji Zhu; Qi Wang; Han Zhao
• Keywords: Scope (computer science); Complement; Closeness; Heuristics; Interdependent networks; Maximization

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.