METHODS FOR COMPUTATION AND ANALYSIS OF MARKOVIAN DYNAMICS ON COMPLEX NETWORKS

Embargo until
Date
2013-10-11
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
A problem central to many scientific and engineering disciplines is how to deal with noisy dynamic processes that take place on networks. Examples include the ebb and flow of biochemical concentrations within cells, the firing patterns of neurons in the brain, and the spread of disease on social networks. In this thesis, we present a general formalism capable of representing many such problems by means of a master equation. Our study begins by synthesizing the literature to provide a toolkit of known mathematical and computational analysis techniques for dealing with this equation. Subsequently a novel exact numerical solution technique is developed, which can be orders of magnitude faster than the state-of-the-art numerical solver. However, numerical solutions are only applicable to a small subset of processes on networks. Thus, many approximate solution techniques exist in the literature to deal with this problem. Unfortunately, no practical tools exist to quantitatively evaluate the quality of an approximate solution in a given system. Therefore, a statistical tool that is capable of evaluating any analytical or Monte Carlo based approximation to the master equation is developed herein. Finally, we note that larger networks with more complex dynamical phenomena suffer from the same curse of dimensionality as the classical mechanics of a gas. We therefore propose that thermodynamic analysis techniques, adapted from statistical mechanics, may provide a new way forward in analyzing such systems. The investigation focuses on a behavior known as avalanching—complex bursting patterns with fractal properties. By developing thermodynamic analysis techniques along with a potential energy landscape perspective, we are able to demonstrate that increasing intrinsic noise causes a phase transition that results in avalanching. This novel result is utilized to characterize avalanching in an epidemiological model for the first time and to explain avalanching in biological neural networks, in which the cause has been falsely attributed to specific neural architectures. This thesis contributes to the existing literature by providing a novel solution technique, enhances existing and future literature by providing a general method for statistical evaluation of approximative solution techniques, and paves the way towards a promising approach to the thermodynamic analysis of large complex processes on networks.
Description
Keywords
Markov process, complex networks, thermodynamics, master equation, stochasticity, neural networks, chemical reactions, epidemiology
Citation