Research Of Influence Maximization In Online Social Networks

With the development of online social network, influence maximization becomes a hotspot in social network analysis field once again. Domingos and Richardson gave the definition of influence maximization:In order to promote some products or concepts, how to choose k influential nodes as the initial spreading set to maximize the final scope of propagation.The key aim of influence maximization in social networks is to maximize the final spread of influence and reduce the running time. Kempe and Kleinberg proposed a natural climbing-hill greedy algorithm that chooses the nodes which could provide a good marginal influence. This greedy algorithm has large spread of influence, but is very costly and cannot be applied to large social networks. Also, greedy algorithm could not guarantee the best final influence spread. In this paper, we propose a framework on the linear threshold model and a hybrid potential-influence greedy algorithm (HPG) which can make good use of the influence accumulation property of the linear threshold model. Considering the network structure and propagation characteristics, HPG algorithm first heuristically choose half of the initial seeds with the biggest potential influence (PI) in constant time and then greedily choose the other half initial seeds with the most influence. For signed social network, we give some rules, and then extend the HPG algorithm to signed social network. Experiments are conducted comprehensively on different real datasets (including weighted social networks, directed social networks and signed social networks). Experimental results demonstrate that HPG algorithm significantly outperforms the local-optimal greedy algorithm and could achieve reduced running time.In addition, we design experiments to verify and analyze the reasonableness of the PI formula.