On the Robustness of Cascade Diffusion under Node Attacks

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


How can we assess a network's ability to maintain its functionality under attacks? Network robustness has been studied extensively in the case of deterministic networks. However, applications such as online information diffusion and the behavior of networked public raise a question of robustness in probabilistic networks. We propose three novel robustness measures for networks hosting a diffusion under the Independent Cascade (IC) model, susceptible to node attacks. The outcome of such a process depends on the selection of its initiators, or seeds, by the seeder, as well as on two factors outside the seeder's discretion: the attack strategy and the probabilistic diffusion outcome. We consider three levels of seeder awareness regarding these two uncontrolled factors, and evaluate the network's viability aggregated over all possible extents of node attacks. We introduce novel algorithms from building blocks found in previous works to evaluate the proposed measures. A thorough experimental study with synthetic and real, scale-free and homogeneous networks establishes that these algorithms are effective and efficient, while the proposed measures highlight differences among networks in terms of robustness and the surprise they furnish when attacked. Last, we devise a new measure of diffusion entropy that can inform the design of probabilistically robust networks.
Original languageEnglish
Title of host publicationWWW'20 : Proceedings of the Web Conference 2020
PublisherAssociation for Computing Machinery
Publication yearApr 2020
ISBN (Electronic)978-1-4503-7023-3
Publication statusPublished - Apr 2020
EventWWW '20: The Web Conference 2020 - Taipei , Taiwan
Duration: 20 Apr 202024 Apr 2020


ConferenceWWW '20

See relations at Aarhus University Citationformats

ID: 179364129