Cyber-epidemics, the widespread of fake news or propaganda through socialmedia, can cause devastating economic and political consequences. A commoncountermeasure against cyber-epidemics is to disable a small subset ofsuspected social connections or accounts to effectively contain the epidemics.An example is the recent shutdown of 125,000 ISIS-related Twitter accounts.Despite many proposed methods to identify such subset, none are scalable enoughto provide high-quality solutions in nowadays billion-size networks. To this end, we investigate the Spread Interdiction problems that seek mosteffective links (or nodes) for removal under the well-known Linear Thresholdmodel. We propose novel CPU-GPU methods that scale to networks with billions ofedges, yet, possess rigorous theoretical guarantee on the solution quality. Atthe core of our methods is an $O(1)$-space out-of-core algorithm to generate anew type of random walks, called Hitting Self-avoiding Walks (HSAWs). Such alow memory requirement enables handling of big networks and, more importantly,hiding latency via scheduling of millions of threads on GPUs. Comprehensiveexperiments on real-world networks show that our algorithms provides muchhigher quality solutions and are several order of magnitude faster than thestate-of-the art. Comparing to the (single-core) CPU counterpart, our GPUimplementations achieve significant speedup factors up to 177x on a single GPUand 338x on a GPU pair.
展开▼
