Complex Networks: Structure and Inference

Abstract

From the spread of disease across a population to the dispersion of vehicular traffic in cities, many real-world processes are driven by lots of small components that interact in simple ways at small scales to produce nontrivial large-scale effects. Probing the fundamental mechanisms that govern such systems——broadly called ``complex systems''——is crucial for control, design, and intervention relevant to these processes. Networks, mathematical objects composed of nodes attached in pairs by edges, provide a very useful representation of such systems, and thus modeling networks is of critical importance for understanding real-world complex systems. In this thesis, I examine two different aspects of network modeling: (1) characterizing structure in networks with metadata, and (2) developing scalable, accurate, and interpretable inference techniques for real-world network data.

I approach the problem of characterizing structure in networks with metadata from two different perspectives. First, I discuss new measures for characterizing the structure of signed networks with positive and negative edge signs representing amity and enmity respectively. Signed networks are hypothesized to display structural regularity (balance) as a result of certain configurations of edge signs being more common than others——for instance, the friend of my enemy should be my enemy. I show that we can develop intuitive measures of balance in signed networks that capture long-range correlations, demonstrating that real networks are indeed significantly balanced using these measures, and that these measures can be used to impute missing data. Second, I move on to explore how we can measure diversity at multiple scales in networks with node metadata that take the form of distributions. I detail a general information theoretic framework for this task, illustrating new insights it can give us through example applications involving demographic data across spatially contiguous regions.

With regards to inference, I first describe a new message passing algorithm for fast approximate inference in probabilistic graphical models on networks with short loops. I derive a self-consistent set of message passing equations using a decomposition of the network into generalized neighborhoods surrounding each node, and extend these equations to compute thermodynamic quantities of interest in spin systems including the specific heat and entropy. I then outline an information theoretic clustering algorithm to summarize posterior distributions over community labelings by identifying representative partitions. I cluster sampled community partitions around representative ``modal" partitions using an efficient algorithm based on the minimum description length principle, finding that a variety of distinct modal partitions with different interpretations exist for example networks.

Altogether, these contributions allow for new insights about real-world network data that are obscured by existing measures and methods, and provide a toolkit for researchers to explore the properties of a wide variety of complex systems in an efficient and principled manner. The work in this thesis is intentionally motivated by very fundamental principles, and so provides a starting point for a variety of future domain- and application-specific optimizations.