A Parallel IRAM Algorithm to Compute PageRank for Modeling Epidemic Spread

• Zifan Liu Maison de la Simulation
• Nahid Emad Maison de la Simulation
• Soufian Ben Amor University of Versailles
• Michel Lamure University of Lyon 1

Resumo

The eigenvalue equation intervenes in models of infectious disease propagation and could be used as an ally of vaccination campaigns in the actions carried out by health care organizations. The stochastic model based on Page Rank allows to simulate the epidemic spread, where a Like-like infection vector is calculated to help establish efficient vaccination strategy. In the context of epidemic spread, generally the damping factor is high. This is because the probability that an infected individual contaminates any other individual through some unusual contact is low. One consequence of this results is that the second largest eigenvalue of Page Rank matrix could be very close to its dominant eigenvalue. Another difficulty arises from the growing size of real networks. Handling very big graph becomes a challenge for computing Page Rank. Furthermore, the high damping factor makes many existing algorithms less efficient. In this paper, we explore the computation methods of Page Rank to address these issues. Specifically, we study the implicitly restarted Arnoldi method (IRAM) and discuss some possible improvements over it. We also present a parallel implementation for IRAM, targeting big data and sparse matrices representing scale-free networks (also known as power law networks). The algorithm is tested on a nation wide cluster of clusters Grid5000. Experiments on very large networks such as twitter, yahoo (over 1 billion nodes) are conducted.

Palavras-chave: Vectors, Eigenvalues and eigenfunctions, Program processors, Damping, Convergence, Computational modeling, Sparse matrices, Epidemic, PageRank, Scale free networks, Power law, IRAM, Big data