文献类型：期刊文献

英文题名：Early detection of dynamic harmful cascades in large-scale networks

作者：Zhou, Chuan[1,2];Lu, Wei-Xue[3];Zhang, Jingzun[4];Li, Lei[5];Hu, Yue[1,2];Guo, Li[1,2]

第一作者：Zhou, Chuan

通讯作者：Hu, Y[1];Li, L[2]

机构：[1]Chinese Acad Sci, Inst Informat Engn, Beijing 100093, Peoples R China;[2]Univ Chinese Acad Sci, Sch Cyber Secur, Beijing 100049, Peoples R China;[3]JD Com, Beijing 100176, Peoples R China;[4]Beijing Union Univ, Coll Intellectualized City, Beijing 100101, Peoples R China;[5]Hefei Univ Technol, Sch Comp Sci & Informat Engn, Hefei 230009, Anhui, Peoples R China

第一机构：Chinese Acad Sci, Inst Informat Engn, Beijing 100093, Peoples R China

通讯机构：[1]corresponding author), Chinese Acad Sci, Inst Informat Engn, Beijing 100093, Peoples R China;[2]corresponding author), Hefei Univ Technol, Sch Comp Sci & Informat Engn, Hefei 230009, Anhui, Peoples R China.

年份：2018

卷号：28

起止页码：304-317

外文期刊名：JOURNAL OF COMPUTATIONAL SCIENCE

收录：;EI(收录号：20174404321276);Scopus(收录号：2-s2.0-85032197760);WOS:【SCI-EXPANDED(收录号:WOS:000449242900029)】；

基金：This work was supported by the NSFC (No. 61502479, 61370025 and 61503114), the National Key Research and Development Program of China (No. 2016YFB0801003, 2017YFB0803304 and 2016YFB0801301), and the Youth Innovation Promotion Association CAS (No. 2017210).

语种：英文

外文关键词：Early detection; Sensor placement; Diffusion networks

摘要：Quickly detecting harmful cascades in networks can allow us to analyze the causes and prevent further spreading of destructive influence. Since it is often impossible to observe the state of all nodes in a network, a common method is to detect harmful cascades from sparsely placed sensors. However, the harmful cascades are usually dynamic (e.g., the cascade initiators and diffusion trajectories can change over the time), which can severely destroy the robustness of selected sensors. Meanwhile the large scale of current networks greatly increases the time complexity of sensor selection. Motivated by the observation, in this paper we investigate the scalable sensor selection problem for early detection of dynamic harmful cascades in networks. Specifically, we first put forward a dynamic susceptible-infected model to describe harmful cascades, and formally define a detection time minimization (DTM) problem which focuses on effective sensors placement for early detection of dynamic cascades. We prove that it is #P-hard to calculate the objective function exactly and propose two Monte-Carlo methods to estimate it efficiently. We prove the NP-hardness of DTM problem and design a corresponding greedy algorithm. Based on that, we propose an efficient upper bound based greedy (UBG) algorithm with the theoretical performance guarantee reserved. To further meet different types of large-scale networks, we propose two accelerations of UBG: Quickest-Path-UBG for sparse networks and Local-Reduction-UBG for dense networks to improve the time complexity. The experimental results on synthetic and real-world social networks demonstrate the practicality of our approaches. (C) 2017 Elsevier B.V. All rights reserved.