Spreading Processes on Networks: Theory and Applications

The interactions between people, technology and modern communication paradigms form large and complex human--machine networks. Complex network theory attempts to address the global and local behavior of such network structures. Of particular interest within the area of network theory is understanding the dynamic behavior of spreading processes on complex networks. In this work, we examine a variety of models covering the intersection of spreading processes and complex network theory, and although we study a large range of problem formulations, we find that--surprisingly--a single parameter effectively summarizes the topology. We begin by examining the effect that topology has on spreading processes in dynamic networks. Dynamic networks are becoming more common due to our increased reliance on and the functionality of mobile devices, smartphones, etc. Specifically, we ask, given discrete information spread through a proximity-based communication channel across dynamic network of mobile end-users, what criteria is required such that the information will ultimately die-out; that is, can we determine the tipping point between information survival and die-out? We show analytically that yes, such a threshold exists, yet it is computationally infeasible to calculate. To avoid such computationally intensive methods, we go on to provide two approximation methods for determining the tipping point. Next, we analyze the effect of topology on the propagation of competing information. Using a novel graph structure we refer to as a composite network, we model the intertwined propagation of competing information across a variety of underlying network layers. Through a combination of analytical and empirical methods, we show how the topology affects the competing information, and ultimately, using topology, we predict the winner of competition.Building on the success of the previous analyses, we formulate a model describing the spread of non-categorical information. Unlike our previous models, the information in this system is represented by a continuous value.We determine the phase transitions of the overall system, relate them to the tipping points in our previous models, and show both analytically and empirically how the structure of the network affects those phase transitions.Ultimately, for each of these models, a single topological parameter, the largest eigenvalue of the adjacency matrix, is all that is necessary to characterize the effect of topology on the spreading process