  Influence maximization serves as the main goal of a variety of social network
activities such as viral marketing and campaign advertising. The independent
cascade model for the influence spread assumes a one-time chance for each
activated node to influence its neighbors. This reasonable assumption cannot be
bypassed, since otherwise the influence probabilities of the nodes, modeled by
the edge weights, would be altered. On the other hand, the manually activated
seed set nodes can be reselected without violating the model parameters or
assumptions. The reselection of a seed set node, simply means paying extra
budget to a previously paid node in order for it to retry its influential
skills on its uninfluenced neighbors. 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 the behavior of real world networks on the difference between these two
influence maximization cases. First we will show that the difference between
the simple and the reselection cases constitutes a wide spectrum of networks
ranging from the reselection-independent ones, where the reselection case has
no noticeable advantage to the simple case, to the reselection-friendly ones,
where the influence spread in the reselection case is twice the one in the
simple case. Then we will correlate this dynamic to other influence
maximization dynamics of the network. Finally, a significant entanglement
between this dynamic and the network structure is shown and verified by the
experiments. In other words, a series of conditions on the network structure is
specified whose fulfilment is a sign for a reselection-friendly network. As a
result of this entanglement, reselection-friendly networks can be spotted
without performing the time consuming influence maximization algorithms.

Social and Information Networks;Physics and Society