Loading...

A New Immunization Algorithm Based on Spectral Properties for Complex Networks

Zahedi, Ramin | 2014

507 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: English
  3. Document No: 46573 (52)
  4. University: Sharif University of Technology, International Campus, Kish Island
  5. Department: Science and Engineering
  6. Advisor(s): Khansari, Mohammd
  7. Abstract:
  8. Vaccination is one of the ways of disease control and prevention, which not only protect individuals against the disease, but also reduce the disease spread rate. Mass vaccination of individuals is not always possible due to the high cost and limitation of immunization resources. Therefore, researchers are always seeking solutions to find the persons that their immunization may have a greater impact in reduction of disease spread rate. The advent of network epidemic models and the possibility of removal the secured nodes in those models, showed that this problem is equivalent to finding a limited set of individuals that their removal will eliminate or minimize the number of people at risk of infection to a minimum or to zero. The problem of immunization according to available resources can be divided into three categories: immunization based on the limited budget, immunization with an uncertain budget and securing the whole society with minimal possible budget.
    In this thesis, a new algorithm will be proposed for solving the problem of immunization with limited budget. This algorithm by use of some spectral properties of the network’s graph minimizes the worst expected growth of an epidemic. It uses a technique for minimum-cut graph partitioning problem which is called Fiedler vector to perform community detection. The simulation of the proposed algorithm and comparisons with the common immunization algorithms in some real networks and computer generated networks have shown that this algorithm performs about 8% better than the best proposed algorithms yet in real networks and up to 20% better than degree centrality in computer generated modular networks
  9. Keywords:
  10. Immunization ; Epidemic ; Social Networks ; Complex Network ; Spectral Properties

 Digital Object List

 Bookmark

No TOC