Optimizing Graph Structure for Targeted Diffusion

Autor:	Yu, Sixie, Torres, Leonardo, Alfeld, Scott, Eliassi-Rad, Tina, Vorobeychik, Yevgeniy
Rok vydání:	2020
Předmět:	Computer Science - Social and Information Networks Physics - Physics and Society
Druh dokumentu:	Working Paper
Popis:	The problem of diffusion control on networks has been extensively studied, with applications ranging from marketing to controlling infectious disease. However, in many applications, such as cybersecurity, an attacker may want to attack a targeted subgraph of a network, while limiting the impact on the rest of the network in order to remain undetected. We present a model POTION in which the principal aim is to optimize graph structure to achieve such targeted attacks. We propose an algorithm POTION-ALG for solving the model at scale, using a gradient-based approach that leverages Rayleigh quotients and pseudospectrum theory. In addition, we present a condition for certifying that a targeted subgraph is immune to such attacks. Finally, we demonstrate the effectiveness of our approach through experiments on real and synthetic networks. Comment: Corrected a few citation errors in the appendix
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2008.05589 Zobrazit plný text záznamu View this record from Arxiv