Scalable Bicriteria Algorithms for the Threshold Activation Problem in Online Social Networks

Abstract

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.