Whom to befriend to influence people

Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network has a certain threshold t(v) for activation, i.e. adoption of the product or idea. If v has at least t(v) activated neighbors, then v will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This Minimum Links Problem has applications in viral marketing and the study of epidemics. Its solution can be quite different from the related and widely studied Target Set Selection problem. We prove that the Minimum Links problem cannot be approximated to within a ratio of O(2log1−ϵ⁡n), for any fixed ϵ>0, unless NP⊆DTIME(npolylog(n)), where n is the number of nodes in the network. On the positive side, we give linear time algorithms to solve the problem for trees, cycles, and cliques, for any given set of external influencers, and give precise bounds on the number of links needed. For general graphs, we design a polynomial time algorithm to compute size-efficient link sets that can activate the entire graph.