2010-on-the-vulnerability-of-large-graphs.md

authors	link	tags	title	venue	year
Hanghang Tong B. Aditya Prakash Charalampos E. Tsourakakis Tina Eliassi-Rad Christos Faloutsos Duen Horng (Polo) Chau		Eigenvalues And Eigenfunctions Correlation Robustness Scalability Computer Networks Immune System Approximation Methods	On the Vulnerability of Large Graphs.	ICDM	2010

Given a large graph, like a computer network, which k nodes should we immunize (or monitor, or remove), to make it as robust as possible against a computer virus attack? We need (a) a measure of the 'Vulnerability' of a given network, (b) a measure of the 'Shield-value' of a specific set of k nodes and (c) a fast algorithm to choose the best such k nodes. We answer all these three questions: we give the justification behind our choices, we show that they agree with intuition as well as recent results in immunology. Moreover, we propose NetShield a fast and scalable algorithm. Finally, we give experiments on large real graphs, where NetShield achieves tremendous speed savings exceeding 7 orders of magnitude, against straightforward competitors.