An Influence Maximization Algorithm Based on Community-Topic Features for Dynamic Social Networks
Xi Qin, Cheng Zhong, Qingshan Yang
Abstract
Real social networks are huge and continueto expand rapidly. Most existing dynamic influence maximization (IM) algorithms are based on the node-to-node propagation model; hence, they have high time complexity and large storage space consumption. They usually reduce computational complexity using a sampling method while sacrificing the influence spread. In this paper, we propose a topic-aware community independent cascade (IC) model to reduce the complexity of dynamic IM without losing accuracy. The proposed model reduces the problem domain through community-level propagation, and then enhances the global features by integrating community structural features, community topic features, and time information into an IC model. We construct the data structure of the dynamic community index to avoid recalculation when the network grows. Based on the dynamic community index, we design a dynamic IM algorithm to quickly approximate the solution with the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(1-\frac{1}{e})$</tex-math></inline-formula> -approximation guarantee. The experimental results on real social networks demonstrated that, compared with existing IM algorithms, the proposed algorithm had better stability and dynamic adaptability, higher computational efficiency, and less space consumption without reducing the approximation ratio and influence spread.