Structural Heterogeneity and Performance in Stochastic Networks: From Distributed Inference to Epidemics and Beyond

Abstract

Recent breakthroughs in computing and communication paradigms have led to an increasingly interconnected and networked world, redefining patterns of personal, economic, and social interactions. The networks that govern our world are continuously expanding in scale and are increasingly integrating heterogeneous components that interact in complex ways. An underlying theme of this thesis is to investigate how the network structure, specifically in the context of heterogeneous interactions, drives emergent properties in networked socio-technical systems and how we can leverage this knowledge to improve system performance. With this theme in mind, we propose and analyze stochastic network models focusing on two main thrusts: i) network design to balance sparsity and connectivity for reliable inference in distributed systems and ii) modeling the interplay between network structure and contagion evolution in the emergence of epidemics in social systems.

The first focus of this thesis is to develop and analyze scalable models for generating reliably connected peer-to-peer networks in a distributed fashion. Specifically, we focus on a class of random graph models known as random K-out graphs, which are receiving increasing attention in distributed systems with applications such as distributed learning and the design of next-generation internet architectures. Across these applications, a network with reliable connectivity drives performance (e.g., ensuring reliable communication, imparting good privacy guarantees, or speeding up convergence), while sparsity ensures low communication overhead. We evaluate how various operational constraints, including heterogeneity, resource constraints, stochastic operational environments, and adversarial capture of nodes and edges, impact the connectivity properties of the random K-out graphs. Our results, in the form of deployable theorems that guarantee different notions of connectivity, further underscore the utility of random K-out graphs as a topology design tool for balancing sparsity and connectivity in distributed network design.

The second focus of this thesis is to examine mechanisms that lead to the propagation of contagions, e.g., misinformation and infection, and identify risk factors that can trigger widespread outbreaks. A key determinant of the speed and scale of propagation of a contagion is its propensity to evolve during interactions with different hosts, resulting in multiple strains or variants of the contagion. We develop a framework to analyze the spread of contagions in light of policy interventions such as lockdowns that reduce physical contact in different social settings (e.g., schools and offices). To this end, we analyze multi-strain spreading on multi-layer contact networks, where network layers represent different social settings. We extend our analysis to the case of network models that exhibit high clustering. Our results shed light on the delicate interplay between contagion evolution and the network structure in informing the emergence of epidemics. Further, we demonstrate that reductions to existing models that discount heterogeneity in either the contagion strain or the network layers may lead to incorrect predictions.