2017/01/30 by Alan Kuhnle, Tianyi Pan, Kuhnle, Alan +6 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.1701.08799
arxiv created 2017/01/30 · openalex publication_date 2017/01/30 · arxiv updated 2017/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 α∈ (0,1): given η> 0, with probability 1 - η our algorithm returns a solution A with expected activation greater than T - 2 αT, and the size of the solution A is within factor 1 + 4 αT + log ( T ) of the optimal size. The algorithm runs in time O ( α-2log ( n / η) (n + m) |A| ), 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.