A community-based algorithm for influence maximization on dynamic social networks

Abstract

The purpose of the influence maximization is to find the top $k$ influential seeds which can maximize the influence spread. Recently, some researchers address this problem through community structure. However, most of these community-based studies only consider the static social network, which ignores that social networks change frequently. In order to deal with the above problem, we present a community-based algorithm on the dynamic social network, which is divided into three phases: (i) community detection, (ii) candidate seed set on the dynamic network, and (iii) final seed set. In the first phase, we use the Louvain algorithm to obtain the community structure. In each community, we analyze the node location to judge the importance of the node. In the second phase, considering the dynamic social network, when a node is added to the network or removed from the network, we update the structure of the social network. Then, the candidate nodes are those nodes with a large influence in each community. And in the third phase, we select $k$ influential seeds from the candidate seeds by CELF algorithm. Extensive experimental results show that our algorithm obtains a better influence spread than many baseline algorithms as well as an acceptable running time while considering the dynamic social networks.