Inhomogeneous Models for Random Graphs and Spreading Processes: Applications in Wireless Sensor Networks and Social Networks

Random graphs are of great interest as a modeling framework for a wide variety of real-world complex networks, such as social networks, information networks, scientific collaboration networks, and technological networks. In this thesis, we focus on two specific application areas of random graph theory, namely, i) modeling secure connectivity of large-scale wireless sensor networks utilizing random predistribution of cryptographic keys, and ii) modeling real-world social networks. Although these two areas are tied together with random graphs, they are inherently dierent and each one poses distinct research problems that rise naturally in the corresponding context. Hence, we will tackle each of them separately and focus on the relevant
research problems in each area. In the first part of the thesis, we focus on the role of random graphs in providing a modeling framework for secure connectivity of large-scale, heterogeneous wireless sensor networks utilizing random predistribution of cryptographic keys. In this part, we propose a novel composite random graph obtained by the intersection of inhomogeneous random key graphs with
Erdos-Renyi graphs as a model for a large scale wireless sensor network secured by the heterogeneous random key predistribution scheme under a uniform on-o channel model. We derive scaling conditions on the model parameters so that with high probability i) the network has no isolated nodes, ii) is connected, iii) the minimum node degree is no less than k, and iv) the network is k-connected. We then proceed by generalizing the uniform on-o channel model to
a heterogeneous on-o channel model where the wireless link availability between two nodes is determined based on their respective classes. This induces a novel composite random graph model formed by the intersection of inhomogeneous random key graphs with inhomogeneous Erdos-Renyi graphs. We derive scaling conditions on the model parameters such that with high probability i) the network has no isolated nodes, and ii) is connected. We close this part
by proposing inhomogeneous random K-out graphs as a novel modeling framework for secure connectivity of large-scale, heterogeneous wireless sensor networks utilizing random pairwise key predistribution schemes. We derive scaling conditions on the model parameters such that
with high probability the resulting network is connected.
In the second part of the thesis, we look at random graphs as models for real-world social networks. In contrast to the first part where we mainly focus on proposing novel random graph models, herein, we utilize existing random graph models of social networks to understand how infectious diseases (or, information) that entail evolutionary adaptations propagate in social contexts. In particular, we consider the propagation of inhomogeneous spreading processes,
governed by the multiple-strain model, on contact networks modeled by i) random graphs with arbitrary degree distributions (generated by the configuration model) and ii) random graphs with clustering. The former graphs capture the skewed degree sequences observed in real-world
social networks, yet it has a vanishing clustering coefficient in the limit of large network size. The latter model generalizes the former as it could also generate graphs with non-trivial clustering, hence, it resembles real-world social networks that are typically clustered. We start by investigating the propagation of spreading processes governed by the multiple-strain model on random graphs with arbitrary degree distributions. We propose a mathematical theory that characterizes the expected epidemic size and the epidemic threshold as functions of the structure of the underlying contact network, the properties of the spreading process, and the evolutionary pathways of the propagating object. We also present extensive simulation results on synthetic and real-world contact networks to validate our theory and reveal the
significant shortcomings of the classical epidemic models that do not capture evolutionary adaptations. We then investigate the propagation of the same class of spreading processes, yet on random graphs with clustering. We propose a mathematical theory that accurately captures
the probability of emergence (the probability that the spreading process would eventually reach a positive fraction of the nodes) and the epidemic threshold as functions of the structure of the underlying contact network (which takes clustering into consideration), the properties of the
spreading process, and the evolutionary pathways of the propagating object. Our theoretical results are validated by a simulation study that also reveals the impact of clustering on the probability of emergence and the epidemic threshold.
A common takeaway from both parts of the thesis is that homogeneous models are more resource-efficient than their inhomogeneous counterparts, despite the fact that the latter facilitate a broader modeling framework that accurately captures real-world networks and spreading processes. In particular, in the first part of the thesis, we show that in some cases, inhomogeneous random graph models require orders of magnitude more resources (e.g., number of cryptographic keys per sensor node) than their homogeneous counterparts to be connected with high probability. In addition, in the second part of the thesis, we show that inhomogeneous models for spreading processes entailing evolutionary adaptations (on random
graphs with arbitrary degree distribution) could achieve (depending on the initial strain) a lower probability of emergence at a given mean degree as compared to a homogeneous spreading process without evolution.