Topics in Networks: Community Detection, Random Graphs, and Network Epidemiology.

In this dissertation, we present research on several topics in networks including community detection, random graphs, and network epidemiology. Traditional stochastic blockmodels may produce inaccurate fits to complex networks with heterogeneous degree distributions and we devise a degree-corrected blockmodel that alleviates this problematic behavior. The resulting objective function for community detection using the degree-corrected version outperforms the traditional model at finding communities on a variety of real-world and synthetic tests. Then we study a different generative model that associates communities to the edges of the network and naturally includes overlapping vertex communities. We create a fast and accurate algorithm to fit this model to empirical networks and show that it can be used to quickly find non-overlapping communities as well. We also develop random graph models for directed acyclic graphs, a class of networks including family trees and citation networks. We argue that the lack of cycles comes from an ordering constraint and then generalize the configuration model to incorporate this constraint. We calculate many properties of these models and demonstrate that some of the model predictions agree quite well with real-world networks, emphasizing the importance of vertex ordering to generating directed acyclic networks with realistic properties. Finally, we examine the spread of disease over networks, starting with a simple model of two diseases spreading with cross-immunity, where infection by one disease makes an individual immune to the other disease and vice versa. Utilizing a timescale separation argument, we map the system to consecutive bond percolation, one disease spreading after the other. The resulting phase diagram includes discontinuous and continuous phase transitions and a coexistence region where both diseases can spread to a substantial fraction of the population. Then we analyze a flexible susceptible-infected-recovered model that allows arbitrary timing for recovery and infection instead of the traditional exponential distributions. Using a message passing approach, we derive the exact expected behavior for trees and random graphs in the large graph size limit, and show that these results are bounds on other networks.Ph.D.PhysicsUniversity of Michigan, Horace H. Rackham School of Graduate Studie