Linear-time Frameworks For Influence Maximization In Large-scale Networks

Influence maximization is a classic optimization problem in the fields of social networks and viral marketing.It aims to find k nodes in the network as the initial propagation sources,and achieve the maximum number of affected nodes after the end of the propagation.Influence maximization has many practical values,such as effective promotion of products or new ideas,effective control of viruses or disasters,monitoring of public opinion,and comprehensive management of social stability.In order to better handle the influence maximization problem in large-scale networks,the current research on this issue mainly focuses on how to ensure that the selected nodes can improve the time efficiency without reducing the influence spread.Considering that algorithms with linear time complexity are scarce in the research of influence maximization,in this paper,we propose two linear time complexity models:(1)Linear time complexity model based on multi-layer neighbor potential and community structure(2)Linear time complexity model based on node neighborhood and iterative optimization.Based on the observation that nodes within communities are densely connected while between communities they are sparsely connected,the influence of activated nodes is likely to be confined to their own communities.In the first linear time complexity model,by utilizing the connection patterns of community structure,we assume that propagation is divided into two phases: the first stage is the seed propagation between different communities;the second stage is propagation of the active nodes within their own communities.Based on the above assumptions,we derive an submodular objective function about the model and give an algorithm with linear time complexity for influence maximization.The node neighborhood and iterative optimization based linear time complexity model also consists of two steps:(1)influence calculation;(2)seed node selection.The first step approximate the influence of any node using its local influence within its neighbors,which can be efficiently computed with an iterative algorithm.The second step uses the greedy strategy to select the k seed nodes based on the results of the first step.We can design a recursive formulae according to the diffusion model,and then quickly calculate the influence of nodes in the network in an iterative manner.We also theoretically proves that the algorithm has linear time complexity under the IC propagation model.Experiments show that our algorithms not only perform better in time-efficiency than the state-of-the-art algorithms,but also ensure effectiveness by maintaining high influence spread,as evaluated in both large-scale real networks and synthetic networks.