  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 {\em 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 {\em 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(2^{\log^{1-\epsilon} n})$, for any fixed $\epsilon>0$,
unless $NP\subseteq DTIME(n^{polylog(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.
