  We consider the Threshold Activation Problem (TAP): given social network $G$
and positive threshold $T$, find a minimum-size seed set $A$ that can trigger
expected activation of at least $T$. We introduce the first scalable,
parallelizable algorithm with performance guarantee for TAP suitable for
datasets with millions of nodes and edges; we exploit the bicriteria nature of
solutions to TAP to allow the user to control the running time versus accuracy
of our algorithm through a parameter $\alpha \in (0,1)$: given $\eta > 0$, with
probability $1 - \eta$ our algorithm returns a solution $A$ with expected
activation greater than $T - 2 \alpha T$, and the size of the solution $A$ is
within factor $1 + 4 \alpha T + \log ( T )$ of the optimal size. The algorithm
runs in time $O \left( \alpha^{-2}\log \left( n / \eta \right) (n + m) |A|
\right)$, where $n$, $m$, refer to the number of nodes, edges in the network.
The performance guarantee holds for the general triggering model of internal
influence and also incorporates external influence, provided a certain
condition is met on the cost-effectivity of seed selection.
