Zhou Chuan, Lu Wei-Xue, Zhang Jingzun, Li Lei, Hu Yue, Guo Li
Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China.
J Comput Sci. 2018 Sep;28:304-317. doi: 10.1016/j.jocs.2017.10.014. Epub 2017 Oct 24.
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 ( 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 (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 (UBG) algorithm with the theoretical performance guarantee reserved. To further meet different types of large-scale networks, we propose two accelerations of UBG: for sparse networks and for dense networks to improve the time complexity. The experimental results on synthetic and real-world social networks demonstrate the practicality of our approaches.
快速检测网络中的有害级联可以让我们分析其成因并防止破坏性影响的进一步扩散。由于通常不可能观察网络中所有节点的状态，一种常见的方法是从稀疏分布的传感器检测有害级联。然而，有害级联通常是动态的（级联发起者和扩散轨迹会随时间变化），这可能严重破坏所选传感器的鲁棒性。同时，当前网络的大规模极大地增加了传感器选择的时间复杂度。受此观察启发，在本文中，我们研究了用于网络中动态有害级联早期检测的可扩展传感器选择问题。具体而言，我们首先提出一个动态易感 - 感染模型来描述有害级联，并正式定义一个动态传感器选择（DTM）问题，该问题专注于为动态级联的早期检测进行有效传感器布置。我们证明精确计算目标函数是#P难的，并提出两种蒙特卡罗方法来高效估计它。我们证明了DTM问题的NP难性并设计了相应的贪心算法。基于此，我们提出一种具有保留理论性能保证的高效统一贪心（UBG）算法。为了进一步适应不同类型的大规模网络，我们提出了UBG的两种加速方法：一种适用于稀疏网络，另一种适用于密集网络，以提高时间复杂度。在合成和真实世界社交网络上的实验结果证明了我们方法的实用性。
