Target users' activation probability maximization with different seed set constraints in social networks (Q2197539)

This paper studies the target user's activation probability maximization with constraint (TUAPM-WC) problem and target user's activation probability maximization without constraint (TUAPM-WOC) problem that find a seed set such that the activation probability of the target users is optimized. The activation probability for a node is defined on a directed social network, which is described as a graph \(G=(V, E, P)\), an influence decay model, and a seed set. Here, \(P\) forms that matrix of probability that one node activates the other. The influence decay model is characterized by a logarithmic decay of propagation probability of each edge. Moreover, the activation probability of a node depends on the activation probability of its active neighbors. It is shown that the TUAPM-WC problem is \(NP\)-hard under the influence decay model. Some algorithms such as basic greedy algorithm and scalable algorithm are presented. Given a seed set and a target set, it is shown that for TUAPM-WOC problem, computing the activation probability from the seed to the target is \(\#P\)-hard under the influence decay model. A double greedy algorithm is described. Numerical results are presented to illustrate the theory.