Identifying vital nodes for influence maximization in attributed networks

Abstract

Abstract Identifying a set of vital nodes to achieve influence maximization is a topic of general interest in network science. Many algorithms have been proposed to solve the influence maximization problem in complex networks. Most of them just use topology information of networks to measure the node influence. However, the node attribute is also an important factor for measuring node influence in attributed networks. To tackle this problem, we first propose an extension model of linear threshold (LT) propagation model to simulate the information propagation in attributed networks. Then, we propose a novel community-based method to identify a set of vital nodes for influence maximization in attributed networks. The proposed method considers both topology influence and attribute influence of nodes, which is more suitable for identifying vital nodes in attributed networks. A series of experiments are carried out on five real world networks and a large scale synthetic network. Compared with CELF, IMM, CoFIM, HGD, NCVoteRank and K-Shell methods, experimental results based on different propagation models show that the proposed method improves the influence spread by $$-2.28\% \, \textrm{to} \, 4.76\%$$ - 2.28 % to 4.76 % , $$-2.50\% \, \textrm{to} \, 16.97\%$$ - 2.50 % to 16.97 % , $$0.18\% \, \textrm{to} \, 16.07\%$$ 0.18 % to 16.07 % , $$0.22\% \, \textrm{to} \, 41.82\%$$ 0.22 % to 41.82 % , $$0.23\% \, \textrm{to} \, 11.24\%$$ 0.23 % to 11.24 % and $$10.78\% \, \textrm{to} \, 75.22\%$$ 10.78 % to 75.22 % .