Factor Analysis for Influence Maximization Problem in Social Networks

In recent years, researchers have paid more attention to influence maximization problem. This problem is firstly defined by Domingos and Richardson as follows: finding a small set of individuals in a social network that could maximize the spread of influence under certain influence cascade model. To solve this issue, researchers proposed different algorithms. However, in all of these algorithms, the size of the chosen individuals -k, is assigned in advance. In this paper, we conduct a preliminary exploration on the relationship between the size of the chosen set and the corresponding influence spread. We propose two metrics to analyze the factor k. Then we further consider the performance metric of the chosen set, which can be described by the stability of the chosen set. Experimental results on two real social networks show the efficiency and necessity of our proposed metrics.