Toward understanding spatial dependence on epidemic thresholds in networks

Document Type


Presentation Date


Conference Name

2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Conference Location

San Francisco, California

Source of Publication

Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on




Social influence in online social networks bears resemblance to epidemic spread in networks and has been studied through epidemiological models. The epidemic threshold is a fundamental metric used to evaluate epidemic spread in networks. Previous work has shown that the epidemic threshold of a network is exactly the inverse of the largest eigenvalue of its adjacency matrix. In this work, however, we indicate that such a threshold ignores spatial dependence among nodes and hence underestimates the actual epidemic threshold. Focusing on regular graphs, we analytically derive a more accurate epidemic threshold based on spatial Markov dependence. Our model shows that the epidemic threshold indeed depends on the spatial correlation coefficient between neighboring nodes and decreases with the death rate. Through both analysis and simulations, we show that our proposed epidemic threshold incorporates a certain spatial dependence and thus achieves a greater accuracy in characterizing the actual epidemic threshold in regular graphs. Moreover, we extend our study to irregular graphs by conjecturing a new epidemic threshold and show that such a threshold performs significantly better than previous work.


irregular graphs, spatial dependence, epidemic thresholds, online social networks, social influence, epidemic spread evaluation, epidemiological models, regular graphs, spatial Markov dependence, spatial correlation coefficient, neighboring nodes, death rate, Markov processes, epidemics, graph theory, Mathematical model, Markov processes, Nickel, Computational modeling, Silicon, Eigenvalues and eigenfunctions, Social network services


Computer Sciences

This document is currently not available here.



Link to Original Published Item