Influence Maximization by Probing Partial Communities in Dynamic Social Networks

Abstract

With the rapid development of online social networks, exploring influence maximization for product publicity and advertisement marketing has attracted strong interests from both the academia and industry. However, due to the continuous network topology changing, updating the variation of an entire network moment by moment is resource intensive and often insurmountable. On the other hand, the classical influence maximization models IC and LT together with their derived varieties are all computationally intensive. Thus developing a solution for dynamic networks with lower cost and higher accuracy is in an urgent necessity. In this paper, a practical framework is proposed by only probing partial communities to explore the real changes of a network. Our framework minimizes the possible difference between the observed topology and the real network through several representative communities. Based on the framework, an algorithm that takes full advantage of divide-and-conquer strategy which reduces the computational overhead is proposed. The systemically theoretical analysis shows that the proposed effective algorithm could achieve provable approximation guarantees. Empirical studies on synthetic and real large scale social networks demonstrate that our framework has better practicality compared with most existing works and provides a regulatory mechanism for enhancing influence maximization.