The Role of Graphlets in Viral Processes on Networks
- PDF / 1,319,348 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 185 Views
The Role of Graphlets in Viral Processes on Networks Samira Khorshidi1 · Mohammad Al Hasan1 · George Mohler1 · Martin B. Short2
Received: 7 February 2018 / Accepted: 3 May 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Predicting the evolution of viral processes on networks is an important problem with applications arising in biology, the social sciences, and the study of the Internet. In existing works, mean-field analysis based upon degree distribution is used for the prediction of viral spreading across networks of different types. However, it has been shown that degree distribution alone fails to predict the behavior of viruses on some real-world networks and recent attempts have been made to use assortativity to address this shortcoming. In this paper, we show that adding assortativity does not fully explain the variance in the spread of viruses for a number of real-world networks. We propose using the graphlet frequency distribution in combination with assortativity to explain variations in the evolution of viral processes across networks with identical degree distribution. Using a data-driven approach by coupling predictive modeling with viral process simulation on real-world networks, we show that simple regression models based on graphlet frequency distribution can explain over 95% of the variance in virality on networks with the same degree distribution but different
Communicated by Mason A. Porter and Andrea L. Bertozzi.
B
Martin B. Short [email protected] Samira Khorshidi [email protected] Mohammad Al Hasan [email protected] George Mohler [email protected]
1
Computer and Information Science, Indiana University - Purdue University Indianapolis, Indianapolis, USA
2
School of Mathematics, Georgia Institute of Technology, Atlanta, USA
123
J Nonlinear Sci
network topologies. Our results not only highlight the importance of graphlets but also identify a small collection of graphlets which may have the highest influence over the viral processes on a network. Keywords Graphlets · Viral processes · Hawkes process · SIS model Mathematics Subject Classification 68R10 · 91D30 · 60G99
1 Introduction A variety of dynamic phenomena, including Youtube video views (Crane and Sornette 2008), Tweet resharing (Zhao et al. 2015), viral marketing campaigns (Leskovec et al. 2007), the spread of computer viruses on the Internet (Berger et al. 2005), and gang retaliation (Short et al. 2014) can be explained as evolving viral processes on networks. As such, the study of the evolution of viral processes on networks has attracted considerable attention in recent years. It is now well known that for a connected network, the largest eigenvalue of its adjacency matrix is a good metric for predicting the viral process in that network (Ganesh et al. 2005; Chakrabarti et al. 2008a; Yang et al. 2015). The largest eigenvalue can be roughly estimated by the average degree of the network (Lovasz 2007), but the complete degree distribution of the network is more expressive than the poin
Data Loading...
