A New Structure-Hole-Based Algorithm For Influence Maximization in Large Online Social Networks

IEEE Access

Jinghua Zhu¹  Yong Liu¹  Xuming Yin¹ 

[1] School of Computer Science and Technology, Heilongjiang University, Harbin, China;

关键词: Social network;    influence maximization;    structural hole;    greedy algorithms;   

DOI  :  10.1109/ACCESS.2017.2758353

来源: DOAJ

【 摘 要 】

The problem of influence maximization (IM) in a social network is to determine a set of nodes that could maximize the spread of influence. The IM problem has been vitally applied to marketing, advertising, and public opinion monitoring. Although recent studies have studied the IM problem, they are generally greedy or heuristic-based algorithms, which are time consuming for practical use in large-scale social networks. Based on the observation that structural hole nodes usually are much more influential than other nodes, in this paper, we develop a structure-hole-based influence maximization algorithm (SHIM) with an emphasis on time efficiency. The SHIM algorithm utilizes structure hole information to significantly decrease the number of candidates of seed nodes. To measure the structure importance of nodes, we propose an structure hole value calculate algorithm to calculate the structural hole value of nodes. We prove the SHIM is NP-hard and propose a structure-based greedy algorithm to select seeds with wide influence spread and high structural hole value. We conduct experiments on real data sets to verify our algorithm's time efficiency and accuracy, and the experimental results show that comparing with the existing algorithms, our algorithms are much more efficient and scalable.

【 授权许可】

Unknown