Search

Influence maximization is the problem of finding a subset of the most influential individuals in a network. The impact of social networks on the dissemination of information and the development of viral marketing has made this problem as the subject of many studies. Influence maximization is $\NP$-hard and many greedy algorithms have been proposed to solve the problem. In this paper we propose a greedy algorithm that approximates the influence by using a novel analytic activation probability computation method. We propose a nonlinear system of equations to compute the activation probabilities which is more accurate than state-of-the-arts. Moreover, we propose a method to compute the activation probabilities efficiently, in order to reduce the running time of the algorithm. We examine our proposed methods on some real-world data sets. Our experiments demonstrate that the proposed algorithms outperform the previous works by computing more accurate activation probabilities. In addition, Our efficient method has much improvements on the running-time, so it can be easily scaled on large networks.

The problem of influence maximization is to select the most influential individuals in a social network. With the popularity of social network sites, and the development of viral marketing, the importance of the problem has been increased. The influence maximization problem is NP-hard, and therefore, there will not exist a polynomial-time algorithm to solve the problem unless P=NP. Many heuristics are proposed to find a nearly good solution in a shorter time. In this paper, we propose two heuristic algorithms to find good solutions. The heuristics are based on two ideas: (1) vertices of high degree have more influence in the network, and (2) nearby vertices influence on almost analogous sets of vertices. We evaluate our algorithms on several well-known data sets and show that our heuristics achieve better results (up to $15\%$ in influence spread) for this problem in a shorter time (up to $85\%$ improvement in the running time).