On the Reselection of Seed Nodes in Independent Cascade Based Influence Maximization

Influence maximization serves as the main goal of a variety of social network activities such as viral marketing. The independent cascade model for the influence spread assumes a one-time chance for each activated node to influence its neighbors. On the other hand, the manually activated seed set nodes can be reselected without violating the model parameters or assumptions. This view divides the influence maximization process into two cases: the simple case where the reselection of the nodes is not considered and the reselection case. In this study we will analyze real world networks in the reselection case. First we will show that the difference between the simple and the reselection cases constitutes a wide spectrum of networks ranging from the reselection-free to the reselection-friendly ones. Then we will experimentally show a significant entanglement between this and influence spread dynamics as well as other structural parameters of the network. Specifically, we show that under a realistic condition, the reselection gain of a network has a correlation of 0.73 to a newly introduced influence spread dynamic. Furthermore, we propose a measure for detecting star-like networks and experimentally show a significant correlation between our proposed measure and the reselection gain in real world networks with different edge weight models.

Keywords:

Influence Maximization , Network Structure , Independent Cascade , Maximization over Integer Lattice , Core Decomposition