This dissertation contains a variety of projects on random networks with entropy and dynamics as unifying themes. Entropy-maximizing models are unbiased given a choice of constraints and sample space; the latter choice can be very consequential, as illustrated by the first two projects herein, which pertain to (a) the impact of the allowance of multi-edges on percolation properties of scale-free networks, and (b) models of unlabeled networks in comparison to their labeled counterparts. The space of network models can also be explored by scanning through parameterized families; in the third project, we do so for a variety of models, examining the mean graph distance between independently and identically sampled pairs of graphs, according to a wide range of different graph distance metrics. In projects four, five, and six, we study dynamic networks exhibiting structural persistence, often quantifiable by such graph distances. In particular, in the fourth project, we introduce models of dynamic networks with a tunable level of structural persistence, and with dynamic nodewise variables that guide the evolution of network structure. The fifth and sixth projects continue to explore this class of models: they pertain to (a) modified activity-driven temporal networks in which activities vary with time and in which links persist, and (b) dynamic-coordinate random geometric graphs and their long-timescale correlations.
Finally, in the seventh project, we return to the setting of maximum-entropy null modeling but this time apply it to temporal networks, combining the two main themes of this dissertation. We construct maximum-entropy temporal network models with expectation-based constraints on local and global static and dynamical properties. The resulting graph-trajectory distribution is a Markov chain composed of independent pairwise binary-state dynamics. We derive the transition probabilities and the constraint consistency conditions, and apply those considerations to develop temporal versions of the Erdős-Rényi model and soft configuration model, as well as novel models with no static analogs. Altogether, the work in this dissertation advances the ongoing endeavor of exploration and elucidation of the space of network models of various kinds, with both entropy and dynamics serving as unifying themes.
- Dmitri Krioukov, Northeastern University
- Fragkiskos Papadopoulos, Cyprus University of Technology
- Samuel V. Scarpino, Rockefeller Foundation
- Alessandro Vespignani, Northeastern University