We are living amidst a pandemic caused by a ravaging coronavirus and an accompanying pandemic of misinformation that has strained our economy and socio-political institutions. A key scientific goal is to examine mechanisms that lead to the widespread propagation of contagions, e.g., misinformation and pathogens, and identify risk factors that can trigger widespread outbreaks. A common phenomenon underlying the spread of disease and misinformation epidemics is the evolution of the contagion as it propagates, leading to the emergence of different strains, e.g., through genetic mutations in pathogens and alterations in the information content. Recent studies have revealed that models that do not account for heterogeneity in transmission risks associated with different strains of the circulating contagion can lead to inaccurate predictions. However, existing results on multi-strain spreading assume that the network has a vanishingly small clustering coefficient, whereas, clustering is widely known to be a fundamental property of real-world social networks. In this work, we investigate spreading processes that entail evolutionary adaptations on random graphs with tunable clustering and arbitrary degree distributions. We derive a mathematical framework that predicts the epidemic threshold and the probability of emergence as functions of the characteristics of the spreading object, the evolutionary pathways of the pathogen/misinformation, and the structure of the underlying network as given by the joint degree distribution of single-edges and triangles. To the best of our knowledge, our work is the first to jointly characterize the impact of clustering and evolution on the emergence of epidemic outbreaks. We supplement our theoretical finding with numerical simulations and case studies, shedding light on how clustering can offer pathways for mutation, thereby altering the course of the epidemic.

Random K-out graphs are receiving attention as a model to construct sparse yet well-connected topologies in distributed systems including sensor networks, federated learning, and cryptocurrency networks. In response to the growing heterogeneity in emerging real-world networks, where nodes differ in resources and requirements, inhomogeneous random K-out graphs were proposed recently. In this model, first, each of the$n$nodes is classified as type-1 (respectively, type-2) with probability$\mu $(respectively,$1-\mu$) independently from the others, where$0 < \mu < 1$. Next, each type-1 (respectively, type-2) node draws 1 arc towards a node (respectively,$K_{n}$arcs towards$K_{n}$distinct nodes) selected uniformly at random. The orientation of the arcs is ignored yielding the inhomogeneous random K-out graph, denoted by$\mathbb {H}(n;\mu,K_{n})$. It was recently established that$\mathbb {H}(n;\mu,K_{n})$is connected with high probability (whp) if and only if$K_{n}=\omega (1)$. Motivated by practical settings where establishing links is costly and only a bounded choice of$K_{n}$is feasible ($K_{n} = O(1)$), we study the size of the largest connected sub-network of$\mathbb {H}(n;\mu,K_{n})$. We first show that the trivial condition of$K_{n} \geq 2$for all$n$is sufficient to ensure that$\mathbb {H}(n;\mu,K_{n})$contains a giant component of size$n-O(1)$whp. Next, to model settings where nodes can fail or get compromised, we investigate the size of the largest connected sub-network in$\mathbb {H}(n;\mu,K_{n})$when$d_{n}$nodes are selected uniformly at random and removed from the network. We show that if$d_{n}=O(1)$, a giant component of size$n- {O}(1)$persists for all$K_{n} \geq 2$whp. Further, when$d_{n}=o(n)$nodes are removed from$\mathbb {H}(n;\mu,K_{n})$, the remaining nodes contain a giant component of size$n(1-o(1))$whp for all$K_{n} \geq 2$. We present numerical results to demonstrate the size of the largest connected component when the number of nodes is finite.

Random K-out graphs are receiving increasing attention as a model to construct sparse, yet well connected topologies in a fully distributed fashion with applications in modeling sensor networks secured by random pairwise key predistribution schemes, decentralized learning, and cryptocurrency networks. A random K-out graph over a set of n nodes is constructed as follows. Each node draws an edge towards K distinct nodes selected uniformly at random. The orientation of the edges is then ignored, yielding an undirected graph. Existing results on connectivity of random K-out graphs focus on an asymptotic setting where the number of nodes is infinite. In the asymptotic setting, it is known that random K-out graphs get connected for any K ≥ 2, and thus achieve connectivity easily, i.e., with far fewer edges (O(n)) as compared to classical random graph models including Erdős-Rényi graphs (O(n log n)). However, practical deployment of random K-out graphs as a tool for topology design requires an understanding of the connectivity of these graphs when the number of nodes is finite.In this work, we derive upper and lower bounds for probability of connectivity in random K-out graphs when the number of nodes is finite. Our matching upper and lower bounds prove that the probability of connectivity is $1 - \Theta \left( {1/{n^{{K^2} - 1}}} \right)$ for all K ≥ 2. Our work is the first to provide an upper bound on the probability of connectivity, which shows that further improvement on the order of n in the lower bound is not possible. Our corresponding lower bound significantly improves the existing ones. Together, our bounds provide a more precise characterization of the probability of connectivity, and reveal that random K-out graphs are an efficient way to construct a connected network topology when the number of nodes is finite. Through numerical simulations, we show that our bounds closely mirror the empirically observed probability of connectivity.

Random K-out graphs, denoted$\mathbb{H}(n;K)$, are generated by each of the$n$nodes drawing$K$out-edges towards$K$distinct nodes selected uniformly at random, and then ignoring the orientation of the arcs. Recently, random K-out graphs have been used in applications as diverse as random (pairwise) key predistribution in ad-hoc networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. In many applications, connectivity of the random K-out graph when some of its nodes are dishonest, have failed, or have been captured is of practical interest. We provide a comprehensive set of results on the connectivity and giant component size of$\mathbb{H}(n;K_{n},\gamma_{n})$, i.e., random K-out graph when$\gamma_{n}$of its nodes, selected uniformly at random, are deleted. First, we derive conditions for$K_{n}$and$n$that ensure, with high probability (whp), the connectivity of the remaining graph when the number of deleted nodes is$\gamma_{n}=\Omega(n)$and$\gamma_{n}=o(n)$, respectively. Next, we derive conditions for$\mathbb{H}(n;K_{n}, \gamma_{n})$to have a giant component, i.e., a connected subgraph with$\Omega(n)$nodes, whp. This is also done for different scalings of$\gamma_{n}$and upper bounds are provided for the number of nodes outside the giant component. Simulation results are presented to validate the usefulness of the results in the finite node regime.

Inhomogeneous random K-out graphs were recently introduced to model heterogeneous sensor networks secured by random pairwise key predistribution schemes. First, each of the n nodes is classified as type-1 (respectively, type-2) with probability 0narcs towards Kndistinct nodes) selected uniformly at random, and then the orientation of the arcs is ignored. It was recently established that the inhomogeneous random K-out graph is 1-connected asymptotically almost surely (a.a.s.) if and only if Kn=ω(1). In this work, we analyze the k-connectivity of inhomogeneous random K-out graphs; i.e., with k=1, 2,⋯, the property that the network remains connected despite the removal of any k-1 nodes or links. We first establish a zero-one law for the property that the minimum node degree is at least k. In particular, we present scaling conditions on μ and Knsuch that the resulting graph has minimum degree at least k with probability approaching one (respectively, zero) constituting the one-law (respectively, zero-law), as the number of nodes gets large. We show that for k=2, 3,⋯, we need to set Kn= \frac 11-μ(logn +(k-2)loglogn + ω(1)) for the network to have a minimum node degree of at least k a.a.s. Next, we prove that having Kn= \frac 11-μ(logn +(k-2)loglogn + ω(1)) also ensures that the graph is k-connected a.a.s., meaning that the zero-one laws for minimum node degree and k-connectivity coincide. We present simulation results to demonstrate the usefulness of the results in the finite node regime. The results given here indicate an interesting fact about inhomogeneous random K-out graphs, i.e., that the number of additional edges needed to go from 1-connectivity to k-connectivity with k ≥ 2 is unexpectedly larger as compared to many classical random graph models studied before.

Random key predistribution schemes serve as a viable solution for facilitating secure communication in Wireless Sensor Networks (WSNs). We analyze reliable connectivity of a heterogeneous WSN under the random pairwise key predistribution scheme of Chan et al. According to this scheme, each of the n sensor nodes is classified as type-1 (respectively, type-2) with probability μ (respectively, 1- μ) where 0nbe selected such that resulting network exhibits certain desirable properties with high probability. Of particular interest is the strength of connectivity often studied in terms of k-connectivity; i.e., with k = 1, 2, ... , the property that the network remains connected despite the removal of any k - 1 nodes or links.In this paper, we answer this question by analyzing the inhomogeneous random K-out graph model naturally induced under the heterogeneous pairwise scheme. It was recently established that this graph is 1-connected asymptotically almost surely (a.a.s.) if and only if Kn1 = ω(1). Here, we show that for k = 2, 3, ... , we need to set Kn= 1/1-μ(log n + (k - 2) log log n + ω(1)) for the network to be k-connected a.a.s. The result is given in the form of a zero-one law indicating that the network is a.a.s. not k-connected when Kn= 1/1-μ(log n + (k - 2) log log n - ω(1)). We present simulation results to demonstrate the usefulness of the results in the finite node regime.

We study the secure and reliable connectivity of wireless sensor networks under the heterogeneous pairwise key predistribution scheme. This scheme was recently introduced as an extension of the random pairwise key predistribution scheme of Chan et al. to accommodate networks where the constituent sensors have different capabilities or requirements for security and connectivity. For simplicity, we consider a heterogeneous network where each of the n sensors is classified as type-1 (respectively, type-2) with probability μ (respectively, 1-μ) where 0<; μ<; 1. Each type-1 (respectively, type-2) node selects 1 (respectively, Kn) other nodes uniformly at random to be paired with; according to the pairwise scheme each pair is then assigned a unique pairwise key so that they can securely communicate with each other. We establish critical conditions on n, μ, and Kn such that the resulting network has minimum node degree of at least k with high probability in the limit of large network size. Our result constitutes a zero-one law for the minimum node degree of the recently introduced inhomogeneous random K-out graph model. This constitutes a crucial step towards establishing a similar zero-one law for the k-connectivity of the graph; i.e., for the property that the network remains connected despite the failure of any k-1 nodes or links. We present numerical results that indicate the usefulness of our results in selecting the parameters of the scheme in practical settings with finite number of sensors.