Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

4-2020

Abstract

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.

Keywords

Attack strategies, Building blockes, Diffusion entropy, Homogeneous network, World wide web

Discipline

Data Science | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

WWW ’20: Proceedings of the 29th Web Conference, Virtual, Taipei, April 20-24

First Page

2711

Last Page

2717

ISBN

9781450370233

Identifier

10.1145/3366423.3380028

Publisher

ACM

City or Country

New York

Embargo Period

5-30-2021

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Additional URL

https://doi.org/10.1145/3366423.3380028

Download

Share

COinS