Which Targets to Contact First to Maximize Influence over Social Network

We address a new type of influence maximization problem which we call “target selection problem”. This is different from the traditionally thought influence maximization problem, which can be called “source selection problem”, where the problem is to find a set of K nodes that together maximizes their influence over a social network. The very basic assumption there is that all these K nodes can be the source nodes, i.e. can be activated. In “target selection problem” we maximize the influence of a new user as a source node by selecting K nodes in the network and adding a link to each of them. We show that this is the generalization of “source selection problem” and also satisfies the submodularity. The selected nodes are substantially different from those of “source selection problem” and use of the solution of “source selection problem” results in a very poor performance.