TY - JOUR
T1 - On the Robustness of Diffusion in a Network under Node Attacks
AU - Logins, Alvis
AU - Li, Yuchen
AU - Karras, Panagiotis
N1 - Publisher Copyright:
© 1989-2012 IEEE.
PY - 2022/12
Y1 - 2022/12
N2 - 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 or Linear Threshold model, susceptible to attacks by an adversarial attacker who disables nodes. 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 attacker's 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 an attack. 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, and devise ways to enhance the robustness of probabilistic networks.
AB - 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 or Linear Threshold model, susceptible to attacks by an adversarial attacker who disables nodes. 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 attacker's 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 an attack. 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, and devise ways to enhance the robustness of probabilistic networks.
KW - Graphs and networks
KW - reliability and robustness
KW - stochastic processes
UR - http://www.scopus.com/inward/record.url?scp=85103918951&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2021.3071081
DO - 10.1109/TKDE.2021.3071081
M3 - Journal article
AN - SCOPUS:85103918951
SN - 1041-4347
VL - 34
SP - 5884
EP - 5895
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 12
ER -