Influence Maximization in Independent Cascade Model with Limited Propagation Distance

摘要

Influence Maximization (IM) is the problem of finding k most influential users in a social network. In this paper, a novel propagation model named Independent Cascade Model with Limited Propagation Distance (ICLPD) is established. In the ICLPD, the influence of seed nodes can only propagate limited hops and the transmission capacities of the seed nodes are different. It is proved that IM problem in the ICLPD is NP-hard and the influence spread function has submodularity. Thus a greedy algorithm can be used to get a result which guarantees a ratio of (1 - 1/e) approximation. In addition, an efficient heuristic algorithm named Local Influence Discount Heuristic (LIDH) is proposed to speed up the greedy algorithm. Extensive experiments on two real-world datasets show LIDH works well in the ICLPD. LIDH is several orders of magnitude faster than the greedy algorithm while its influence spread is close to that of the greedy algorithm.