Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems

Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete graphical dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also address other problems that deal with the time evolution of such stochastic dynamical systems. Further, we point out the implications of our results to problems for other computational models such as Hopfield networks, communicating finite state machines and systolic arrays. In particular, our polynomial time algorithms for the predecessor existence problem for stochastic dynamical systems imply similar results for one-dimensional finite cellular automata.