Using Proxies for Node Immunization Identification on Large Graphs

Document Type

Article

Publication Date

1-1-2017

Publication Title

IEEE Access

Volume

5

First page number:

13046

Last page number:

13053

Abstract

Given a large graph, like a social network, which nodes should be immunized (or removed) to make the network safe from the spread of a virus? This is the node immunization problem. One of the classical methods, inspired by immunology, in analyzing this problem relies on the calculation of the largest eigenvalue before and after immunization in order to create the largest difference in eigenvalue. We propose a method that does not rely on a costly calculation of eigenvalues; instead, we rely on the notion of proxies and deterministic routing areas in order to find such nodes to immunize. We show that our results are consistent with the notion of vulnerability and produces equivalent results when compared with the existing algorithms. Furthermore, experimental results show that when a virus is not allowed to die out (controlled by the strength of the virus), our algorithm ensures that more nodes are safe from infection. © 2013 IEEE.

Keywords

Immunization; Linear time; Proxies; Tree-graph

Language

english

Find It

UNLV article access

Find in your library

Share

COinS