Viral marketing with positive influence

摘要

One model for viral marketing is the positive influence. In this model, an inactive node is changed into active if and only if at least half of its neighbors are already in active state. The positive influence model can be viewed as a special case of a general threshold model, in which the threshold function at each node has value one if at least a certain fraction of neighbors are in active state, and value 0 otherwise. This function can be proved to be monotonically increasing and nonsubmodular for any predefined fraction. Therefore, given a seed set, the number of influenced nodes is not submodular with respect to the size of the seed set. This fact makes those optimization problems related with positive influence very hard, including the minimum partial positive influence seeding problem: Given a social network G = (V, E) and a number 02H ([pn]))-approximation algorithm for the minimum partial positive influence seeding problem, where n is the number of nodes, and H(·) is the Harmonic number.