Multi-armed bandits (MAB) are commonly used in sequential online decision-making when the reward of each decision is an unknown random variable. In practice however, the typical goal of maximizing total reward may be less important than minimizing the total cost of the decisions taken, subject to a reward constraint. For example, we may seek to make decisions that have at least the reward of a reference ``default'' decision, with as low a cost as possible. This problem was recently introduced in the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework. MAB-CS is broadly applicable to problem domains where a primary metric (cost) is constrained by a secondary metric (reward), and the rewards are unknown. In our work, we address variants of MAB-CS including ones with reward constrained by the reward of a known reference arm or by the subsidized best reward. We introduce the Pairwise-Elimination (PE) algorithm for the known reference arm variant and generalize PE to PE-CS for the subsidized best reward variant. Our instance-dependent analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret, making our policies the first with such a guarantee. Moreover, by comparing our upper and lower bound results we establish that PE is order-optimal for all known reference arm problem instances. Finally, experiments are conducted using the MovieLens 25M and Goodreads datasets for both PE and PE-CS revealing the effectiveness of PE and the superior balance between performance and reliability offered by PE-CS compared to baselines from the literature.

Recent advances in large language models (LLMs) have enabled automated dataset labeling with minimal human supervision. While majority voting across multiple LLMs can improve label reliability by mitigating individual model biases, it incurs high computational costs due to repeated querying. In this work, we propose a novel online framework, Cost-aware Majority Voting (CaMVo), for efficient and accurate LLM-based dataset annotation. CaMVo adaptively selects a subset of LLMs for each data instance based on contextual embeddings, balancing confidence and cost without requiring pre-training or ground-truth labels. Leveraging a LinUCB-based selection mechanism and a Bayesian estimator over confidence scores, CaMVo estimates a lower bound on labeling accuracy for each LLM and aggregates responses through weighted majority voting. Our empirical evaluation on the MMLU and IMDB Movie Review datasets demonstrates that CaMVo achieves comparable or superior accuracy to full majority voting while significantly reducing labeling costs. This establishes CaMVo as a practical and robust solution for cost-efficient annotation in dynamic labeling environments.

Federated learning has recently gained popularity as a framework for distributed clients to collaboratively train a machine learning model using local data. While traditional federated learning relies on a central server for model aggregation, recent advancements adopt a decentralized framework, enabling direct model exchange between clients and eliminating the single point of failure. However, existing decentralized frameworks often assume all clients train a shared model. Personalizing each client’s model can enhance performance, especially with heterogeneous client data distributions. We propose FedSPD, an efficient personalized federated learning algorithm for the decentralized setting, and show that it learns accurate models in low-connectivity networks. To provide theoretical guarantees on convergence, we introduce a clustering-based framework that enables consensus on models for distinct data clusters while personalizing to unique mixtures of these clusters at different clients. This flexibility, allowing selective model updates based on data distribution, substantially reduces communication costs compared to prior work on personalized federated learning in decentralized settings. Experimental results on real-world datasets show that FedSPD outperforms multiple decentralized variants of existing personalized federated learning algorithms in scenarios with low-connectivity networks.

Multi-armed bandits is a sequential decision-making problem where an agent must choose between multiple actions to maximize its cumulative reward over time, while facing uncertainty about the rewards associated with each action. The challenge lies in balancing the exploration of potentially higher-rewarding actions with the exploitation of known high-reward actions. We consider a multi-armed bandit problem with probes, where before pulling an arm, the decision-maker is allowed to probe one of the K arms for a cost$c\geq 0$to observe its reward. We introduce a new regret definition that is based on the expected reward of the optimal action. We develop UCBP, a novel algorithm that utilizes this strategy to achieve a gap-independent regret upper bound that scales with the number of rounds T as$ O(\sqrt {KT\log T})$, and an order optimal gap-dependent upper bound of$ O(K\log T)$. As a baseline, we introduce UCB-naive-probe, a naive UCB-based approach which has a gap-independent regret upper bound of$O(K\sqrt {T\log T})$, and gap-dependent regret bound of$O(K^{2}\log T)$; and TSP, the Thompson sampling version of UCBP. In empirical simulations, UCBP outperforms UCB-naive-probe, and performs similarly to TSP, verifying the utility of UCBP and TSP algorithms in practical settings.

The study of influence propagation over networks has received increasing attention in many scientific domains. In particular, the linear threshold model is widely studied due to its ability to capture the mechanism by which multiple sources of exposure are required for nodes in the network to take action. Most existing research on influence propagation concentrate on asingletopic spreading in isolation over the network. However, real-life social contagions often involvemultipletopics spreading simultaneously in acorrelatedmanner; e.g., different conspiracy theories, political opinions on taxes, immigration, gun control, etc. In this work, we propose amulti-dimensional threshold model with correlated influencesas an extension of the classical linear threshold model to incorporate multiple correlated topics spreading simultaneously over networks. We provide analytical results that accurately predict the threshold, probability, and expected size ofglobalcascades, i.e., cases where asignificantfraction of the population getsinfluenced. Through extensive simulations, we demonstrate that our analytical results match the numerical results near-perfectly in the finite node regime. These results reveal the interplay between the underlying network structure, the correlation among spreading topics, and the heterogeneous thresholds on thefinalresults of the propagation.

The study of complex contagions over networks has been receiving increasing attention across many scientific domains. Especially, linear threshold models are widely studied due to the ability to capture the mechanism that multiple sources of exposure are required for nodes in the network to take action. Most related works on influence propagation only concentrate on a single content spreading over networks. However, complex contagions usually involve multiple correlated contents spreading simultaneously, demonstrating significant implications for many real-life systems. In this work, we propose a multi-dimensional threshold model as an extension of the classical linear threshold model to incorporate multiple correlated contents spreading simultaneously over networks. We also provide analytical results that accurately predict probability of emergence of global cascades for correlated contents. These results reveal the interplay between the underlying network structure and contents' correlation on the spreading processes. Thus, our work advances analysis, prediction and control strategies for complex contagions over networks,

We examine a$K-\mathbf{armed}$multi-armed bandit problem involving probes, where the agent is permitted to probe one arm for a cost$c\geq 0$to observe its reward before making a pull. We identify the optimal strategy for deciding whether to probe or pull an arm. In the case of probing an arm, we also make a decision on which arm to pull after observing the probe's outcome. Additionally, we introduce a novel regret definition based on the expected reward of the optimal action. We propose UCBP, a novel algorithm that utilizes this strategy. UCBP achieves a gap-independent regret upper bound in$T$rounds that scales with$\mathcal{O}(\sqrt{KT\log T})$, and an order optimal gap-dependent upper bound that scales with$\mathcal{O}(K\log T)$. We provide UCB-naive-probe, a naive UCB-based approach which has a gap-independent regret upper bound on the order of$O(K\sqrt{T\log T})$, and gap-dependent regret on the order of$O(K^{2}\log T)$as a baseline. We provide empirical simulations to verify the utility of the UCBP algorithms in practical settings, and show that UCBP outperforms UCB-naive-probe in simulations.

Among popular social media platforms, Reddit stands out for its decentralized approach to moderation and community management. Due to this and its community-based network structure, Reddit provides a unique environment for studying the diffusion of knowledge and beliefs over social media. While assortativity, polarization, and user behavior have been examined within empirical contexts, having the ability to model the impacts of different moderation policies and rules across communities could provide useful insights for limiting the spread of misinformation. In this work, we introduce an agent-based model of Reddit interactions and moderating actions. By simulating interactions at the user level and specifying user-specific attributes, our model allows practitioners to conduct experiments with various types of actors and moderators and study their potential impact on Reddit-facilitated discussions and information diffusion. Additionally, subreddit-specific attributes enable communities to have different standards and thresholds for user conduct. To validate this model, we rely on an empirical dataset of over 100K posts and 800K comments across three U.S. political events in addition to user surveys and studies.

Modeling spreading processes over complex networks has been receiving increasing attention. For example, bond percolation models considering population heterogeneity have been used to derive insights into disease spread and misinformation control. However, most works on spreading processes with population heterogeneity only concentrate on single-layer contact networks. To study how the course of a spreading process changes due to multiple layers of contact networks (e.g., neighborhood vs. schools or Twitter vs. Facebook) while considering population heterogeneity from a principled, mathematical lens, we propose the Multi-layer Mask model based on SIR dynamics. We derive analytical expressions for three fundamental epidemiological quantities: the probability of emergence, the epidemic threshold, and the expected epidemic size. Analytical results are shown to be in near-perfect agreement with the numerical results obtained through extensive simulations. These results reveal the impact of the structure of the multi-layer contact network, viral transmission dynamics, and population heterogeneity on the final state of the spreading process. Thus, they might help develop mitigation and control strategies for disease spread and information diffusion.

We consider a graph property known as$r$-robustness, a robustness metric that plays a key role in analyzing consensus dynamics. It was previously shown that in the presence of adversarial nodes, consensus can be reached in an$r$-robust network for sufficiently large$r$. Further,$r$-robustness is a stronger property than$r$-connectivity, hence it is also useful in many applications where robustness of networks to disruptions such as adversarial attacks or node failures is of practical interest. In this paper, we study$r$-robustness of random K-out graphs, which have been used in many applications including random (pairwise) key predistribution in wireless sensor networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. Significantly improving an earlier result, we provide a set of conditions for$K$and$n$that ensure, with high probability (whp), the$r$-robustness of the random K-out graph. Simulation results are used to verify the results. To demonstrate the viability of our results in practical applications, we compare our results with the results from Erdös-Rényi and the Barabási-Albert random graph models.

Cascading failures are a common phenomenon in complex networked systems, where failures at only a few nodes may trigger a process of sequential failures. We investigate the robustness against cascading failures in systems carrying flows or loads that contain multiple interdependent networks, e.g., power grid, transportation system, etc. In these systems, the coupling coefficients between the networks, which determine how the flow from failed components gets redistributed across the networks, is a key factor affecting the robustness against cascading failures. Prior work has introduced the step-wise optimization (SWO) strategy that dynamically adjusts the coupling coefficients during the course of the cascading failures in an effort to preserve the network size. SWO has been shown to have good performance against cascading failures on synthetic data. In this paper, we show the optimality of the SWO strategy under certain conditions on the flow and capacity distributions of the nodes. We also show, via simulations, that the SWO strategy performs well under various real-world network topologies as well.

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.

Real-time access to overhead Low-Earth Orbit (LEO) satellite imagery from a handheld device can have transformative applications: tracking wild-fire, natural disasters and weather events. Today, real-time access to images from LEO satellites overhead is challenging to obtain. LEO satellite ground receivers are bulky, expensive and sparsely deployed in the world. Despite the exponential increase in LEO small satellites orbiting the planet today-there is a significant time gap between an image capture on such a satellite and users who need it the most in remote and ecologically-sensitive regions. This paper presents SelfieStick, a novel satellite receiver system that explores reducing this barrier of access to real-time satellite imagery data using a single low cost (< $ 30) tiny receiver. SelfieStick's core approach takes advantage of the multiplicity of overhead Low-Earth Orbit satellites due to their exponential rise in recent years. While signals from such satellites may be individually weak, especially at a low-cost receiver, SelfieStick stitches together noisy RF captures containing underlying images of the same part of the Earth across many such satellites to generate clean Earth images. This is made possible by combining weak signals in the RF domain (rather than the traditional image domain) after appropriately transforming and aligning the RF signals accounting for different satellite perspectives, their orbits and wireless channels. A detailed experimental evaluation on the RTL-SDR platform on satellite captures from the NOAA constellation demonstrates a PSNR improvement of 5 dB through combining of images across 10 satellites.

We study a sequential resource allocation problem where, at each round, the decision-maker needs to allocate its limited budget among different available entities. In doing so, the decision-maker obtains the reward for each entity in that round. The goal of the decision-maker is to maximize the expected cumulative reward or equivalently minimize cumulative regret over a total of T rounds. Sequential resource allocation can be modeled as a combinatorial bandit by viewing the allocation of a budget to an entity as a base arm. In the context of resource allocation, the rewards received under different budget allocations are likely to be correlated. We propose a novel correlated combinatorial bandit framework that explicitly models such correlations. We develop a novel Correlated-UCB algorithm for online resource allocation, which yields significantly reduced regret relative to correlation-agnostic algorithms. In certain cases, our proposed algorithm even achieves bounded regret, which is an order-wise reduction in the regret relative to the correlation-agnostic approach, which incurs logarithmic regret under all scenarios. We validate these performance gains through experiments on several applications such as online power allocation across wireless channels, job scheduling in multi-server systems and online channel assignment for the slotted ALOHA protocol.

We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter θ*. This problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden θ*and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classic bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C and TS-C algorithms (structured bandit versions of UCB and Thompson Sampling, respectively) pull only a subset of the sub-optimal arms O(log T ) times while the other sub-optimal arms (referred to as non-competitive arms) are pulled O(1) times. As a result, in cases where all sub-optimal arms are noncompetitive, which can happen in many practical scenarios, the proposed algorithms achieve bounded regret.

The spread of COVID-19 has been among the most devastating events affecting the health and well-being of humans worldwide since World War II. A key scientific goal concerning COVID-19 is to develop mathematical models that help us to understand and predict its spreading behavior, as well as to provide guidelines on what can be done to limit its spread. In this paper, we discuss how our recent work on a multiple-strain spreading model with mutations can help address some key questions concerning the spread of COVID-19. We highlight the recent reports on a mutation of SARS-CoV-2 that is thought to be more transmissible than the original strain and discuss the importance of incorporating mutation and evolutionary adaptations (together with the network structure) in epidemic models. We also demonstrate how the multiple-strain transmission model can be used to assess the effectiveness of mask-wearing in limiting the spread of COVID-19. Finally, we present simulation results to demonstrate our ideas and the utility of the multiple-strain model in the context of COVID-19.

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.

Should you decide to launch a nano-satellite today in Low-Earth Orbit (LEO), the cost of renting ground station communication infrastructure is likely to significantly exceed your launch costs. While space launch costs have lowered significantly with innovative launch vehicles, private players, and smaller payloads, access to ground infrastructure remains a luxury. This is especially true for smaller LEO satellites that are only visible at any location for a few tens of minutes a day and whose signals are extremely weak, necessitating bulky and expensive ground station infrastructure.

We consider a multi-armed bandit framework where the rewards obtained by pulling different arms are correlated. We develop a unified approach to leverage these reward correlations and present fundamental generalizations of classic bandit algorithms to the correlated setting. We present a unified proof technique to analyze the proposed algorithms. Rigorous analysis of C-UCB (the correlated bandit versions of Upper-confidence-bound) reveals that the algorithm end up pulling certain sub-optimal arms, termed as non-competitive, only O(1) times, as opposed to the O(logT) pulls required by classic bandit algorithms such as UCB, TS etc. We present regret-lower bound and show that when arms are correlated through a latent random source, our algorithms obtain order-optimal regret. We validate the proposed algorithms via experiments on the MovieLens and Goodreads datasets, and show significant improvement over classical bandit algorithms.

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.

Multi-armed bandit models are widely studied sequential decision-making problems that exemplify the exploration-exploitation trade-off. We study a novel correlated multi-armed bandit model where the rewards obtained from the arms are functions of a common latent random variable. We propose and analyze the performance of the C-UCB algorithm that leverages the correlations between arms to reduce the cumulative regret (i.e., to increase the total reward obtained after T rounds). Unlike the standard UCB algorithm that pulls all sub-optimal arms O(log T) times, the C-UCB algorithm takes only O(1) times to identify that some arms, which we refer to as non-competitive arms, are optimal. Thus, we effectively reduce a K-armed bandit problem to a C + 1-armed bandit problem with C <; K denoting the number of competitive, where C can be computed from the reward functions. A key consequence is that when C = 0, our algorithm achieves a constant (i.e., O(1)) regret instead of the standard O(log T) scaling with the number of rounds T . Establishing lower bounds for the regret, we show that the C-UCB algorithm is order-wise optimal and demonstrate its superiority against other algorithms via numerical simulations.

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.

Complex contagion models have been developed to understand a wide range of social phenomena such as adoption of cultural fads, the diffusion of belief, norms, and innovations in social networks, and the rise of collective action to join a riot. Most existing works focus on contagions where individuals’ states are represented by binary variables, and propagation takes place over a single isolated network. However, characterization of an individual’s standing on a given matter as a binary state might be overly simplistic as most of our opinions, feelings, and perceptions vary over more than two states. Also, most real-world contagions take place over multiple networks (e.g., Twitter and Facebook) or involve multiplex networks where individuals engage in different types of relationships (e.g., co-worker, family, etc.). To this end, this paper studies multi-stage complex contagions that take place over multi-layer or multiplex networks. Under a linear threshold based contagion model, we first give analytic results for the expected size of global cascades, i.e., cases where a randomly chosen node can initiate a propagation that eventually reaches a positive fraction of the whole population. Then, analytic results are confirmed by an extensive numerical study. In addition, we demonstrate how the dynamics of complex contagions is affected by the structural properties of the networks. In particular, we reveal an interesting connection between the assortativity of a network and the impact of hyper-active nodes on the cascade size.

Spread of influence is one of the most widely studied propagation processes in the literature on complex networks. Examples include the rise of collective action to join a riot and diffusion of beliefs, norms, and cultural fads, to name a few. Most existing works on modeling influence propagation consider a single content (e.g., an opinion, decision, product, political view, etc.) spreading over a network independent from everything else. However, most real-life examples involve multiple correlated contents spreading simultaneously and exhibiting positive (e.g., opinions on same-sex marriage and gun control) or negative (e.g., opinions on universal health care and tax-relief for the “rich”) correlation. To accommodate these cases, this paper proposes the vector threshold model, as an extension of the widely used Watts threshold model for complex contagions. Here, the state of a node is represented by a binary vector representing their opinion on a number of content items. Nodes switch their states based on the influence they receive from their neighbors in the network. The influence is represented by a vector containing the proportion of neighbors who support each content; both positively and negatively correlated contents can be captured in this formulation by using different rules for switching node states. Our main result is concerned with the expected size of global cascades, i.e., cases where a randomly chosen node can initiate a propagation that eventually reaches a positive fraction of the whole population. We also derive conditions on network structure for global cascades to be possible. Analytic results are supported by a numerical study.

We investigate the connectivity of inhomogeneous random K-out graphs, denoted H(n;μ,Kn), where each of the n nodes is assigned to a class i = 1, ..., r independently according to a probability distribution μ = {μ1, ..., μr}. Each class-i node chooses Ki,ndistinct nodes uniformly at random from among all other nodes. A pair of nodes are adjacent in H(n;μ,Kn) if at least one selects the other. Without loss of generality, we assume that K1,n≤ K2,n≤ ... ≤ Kr,n. From earlier results on homogeneous random K-out graphs (where all nodes choose the same number K of nodes), it is known that H(n;μ,Kn) is connected with high probability (whp) if Kn≥ 2. In this paper, we study the case where K1,n= 1 and seek conditions on K2,n, ..., Kr,n, and μ such that the resulting graph is connected. We show that H(n;μ,Kn) is connected whp if Kr,nis chosen such that limn→∞Kr,n= ∞. However, any bounded choice of the sequence Kr,ngives a positive probability of H(n;μ,Kn) being not connected. A numerical study is provided to validate our results in the finite node regime.

We consider secure and reliable connectivity in wireless sensor networks that utilize the heterogeneous random key predistribution scheme. We model the unreliability of wireless links by an on/off channel model that induces an Erdos-Rényi graph, while the heterogeneous scheme induces an inhomogeneous random key graph. The overall network can thus be modeled by the intersection of both graphs. We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model, so that with high probability: i) all of its nodes are connected to at least k other nodes, i.e., the minimum node degree of the graph is no less than k, and ii) the graph is k-connected, i.e., the graph remains connected even if any k - 1 nodes leave the network. These results are shown to complement and generalize several previous results in the literature. We also present numerical results to support our findings in the finitenode regime. Finally, we demonstrate via simulations that our results are also useful when the on/off channel model is replaced with the more realistic disk communication model.

We consider a wireless sensor network secured by a heterogeneous random key predistribution scheme and investigate its reliability against both link and node failures. The heterogeneous random key predistribution scheme is a lightweight security mechanism proposed to secure sensor networks that include nodes with varying levels of resources, features, or connectivity requirements; e.g., regular nodes vs. cluster heads. To capture the reliability of the network against both link and node failures, we consider the case when each link fails independently with probability 1 - α and present conditions (in the form of zero-one laws) on how to scale the parameters of the resulting network so that it is k-connected with high probability, i.e., the network remains connected even if any k - 1 nodes fail or leave the network. Collectively, we obtain a network that is reliable against the probabilistic failure of each link and against the failure of any k - 1 nodes. We present numerical results to support these conditions in the finite-node regime.

We study the connectivity of a random graph formed by the intersection of an inhomogeneous random key graph with an inhomogeneous Erdös-Rényi graph. The former graph is naturally induced by a heterogeneous random key predistribution scheme introduced for securing wireless sensor network communications. In this scheme, nodes are divided into r classes according to a probability distribution μ = {μ1,..., μr}, and a class-i sensor is assigned Ki cryptographic keys that are selected uniformly at random from a common pool of P keys. The latter graph represents a heterogeneous on/off channel model, where the wireless channel between a class-j node and a class-j node is on (resp. off) with probability αij(resp. 1 - αij) independently from others. We present conditions on how to scale the parameters of the intersection model so that it is connected with high probability as the number of nodes gets large. The result is given in the form of a zero-one law and is supported by a numerical study in the finite-node regime.

Low-Power Wide Area Networks (LP-WANs) are an attractive emerging platform to connect the Internet-of-things. LP-WANs enable low-cost devices with a 10-year battery to communicate at few kbps to a base station, kilometers away. But deploying LP-WANs in large urban environments is challenging, given the sheer density of nodes that causes interference, coupled with attenuation from buildings that limits signal range. Yet, state-of-the-art techniques to address these limitations demand inordinate hardware complexity at the base stations or clients, increasing their size and cost.

We investigate k-connectivity in secure wireless sensor networks under the random pairwise key predistribution scheme with unreliable links. When wireless communication links are modeled as independent on-off channels, this amounts to analyzing a random graph model formed by intersecting a random K-out graph and an Erdös-Rényi graph. We present conditions on how to scale the parameters of this intersection model so that the resulting graph is k-connected with probability approaching to one (resp. zero) as the number of nodes gets large. The resulting zero-one law is shown to improve and sharpen the previous result on the 1-connectivity of the same model. We also provide numerical results to support our analysis.

We consider wireless sensor networks under a heterogeneous random key predistribution scheme and an on-off channel model. The heterogeneous key predistribution scheme has recently been introduced by Yağan - as an extension to the Eschenauer and Gligor scheme - for the cases when the network consists of sensor nodes with varying level of resources and/or connectivity requirements, e.g., regular nodes vs. cluster heads. The network is modeled by the intersection of the inhomogeneous random key graph (induced by the heterogeneous scheme) with an Erdös-Rényi graph (induced by the on/off channel model). We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model so that with high probability all of its nodes are connected to at least k other nodes; i.e., the minimum node degree of the graph is no less than k. We also present numerical results to support our results in the finite-node regime. The numerical results suggest that the conditions that ensure k-connectivity coincide with those ensuring the minimum node degree being no less than k.

We consider a new random key predistribution scheme for securing heterogeneous wireless sensor networks. Each of the n sensors in the network is classified into r classes according to a probability distribution μ = {μ1,...μr} Before deployment, a class-i sensor is assigned Kicryptographic keys that are selected uniformly at random from a pool of P keys. Once deployed, a pair of sensors can communicate securely if and only if they have a key in common. The communication topology of this network is modeled by an inhomogeneous random key graph. We establish scaling conditions on the parameters P and {K1,...,Kr} so that this graph is connected with high probability. The result is given in the form of a zero-one law with the number of sensors n growing unboundedly large. Our result is shown to complement and improve those given by Godehardt et al. and Zhao et al. for the same model, therein referred to as the general random intersection graph.

We introduce a new random key predistribution scheme for securing heterogeneous wireless sensor networks. Each of the n sensors in the network is classified into r classes according to some probability distribution μ = {μ1, . . . , μr}. Before deployment, a class-i sensor is assigned Kicryptographic keys that are selected uniformly at random from a common pool of P keys. Once deployed, a pair of sensors can communicate securely if and only if they have a key in common. We model the communication topology of this network by a newly defined inhomogeneous random key graph. We establish scaling conditions on the parameters P and {K1, . . . , Kr} so that this graph: 1) has no isolated nodes and 2) is connected, both with high probability. The results are given in the form of zero-one laws with the number of sensors n growing unboundedly large; critical scalings are identified and shown to coincide for both graph properties. Our results are shown to complement and improve those given by Godehardt et al. and Zhao et al. for the same model, therein referred to as the general random intersection graph.

We investigate the resiliency of wireless sensor networks against sensor capture attacks when the network uses the random pairwise key distribution scheme of Chan et al. We present conditions on the model parameters so that the network is: 1) unassailable and 2) unsplittable, both with high probability, as the number n of sensor nodes becomes large. Both notions are defined against an adversary who has unlimited computing resources and full knowledge of the network topology, but can only capture a negligible fraction o(n) of sensors. We also show that the number of cryptographic keys needed to ensure unassailability and unsplittability under the pairwise key predistribution scheme is an order of magnitude smaller than it is under the key predistribution scheme of Eschenauer and Gligor.

We investigate k-connectivity in secure wireless sensor networks under the random pairwise key predistribution scheme with unreliable links; a network is said to be k-connected if it remains connected despite the failure of any of its (k - 1) nodes or links. With wireless communication links modeled as independent on-off channels, this amounts to analyzing a random graph model formed by intersecting a random K-out graph and an Erdös-Rényi graph. We present conditions on how to scale the parameters of this intersection model so that the resulting graph is k-connected with probability approaching to one (resp. zero) as the number of nodes gets large. The resulting zero-one law is shown to improve and sharpen the previous result on the 1-connectivity of the same model. We also provide numerical results to support our analysis and show that even in the finite node regime, our results can provide useful guidelines for designing sensor networks that are secure and reliable.

The Eschenauer-Gligor (EG) random key predistri-bution scheme has been widely recognized as a typical approach to secure communications in wireless sensor networks (WSNs). However, there is a lack of precise probability analysis on the reliable connectivity of WSNs under the EG scheme. To address this, we rigorously derive the asymptotically exact probability of k-connectivity in WSNs employing the EG scheme with unreliable links represented by independent on/off channels, where k-connectivity ensures that the network remains connected despite the failure of any (k-1) sensors or links. Our analytical results are confirmed via numerical experiments, and they provide precise guidelines for the design of secure WSNs that exhibit a desired level of reliability against node and link failures.

Random key graphs form a class of random intersection graphs that are naturally induced by the random key predistribution scheme of Eschenauer and Gligor for securing wireless sensor network (WSN) communications. Random key graphs have received much attention recently, owing in part to their wide applicability in various domains, including recommender systems, social networks, secure sensor networks, clustering and classification analysis, and cryptanalysis to name a few. In this paper, we study connectivity properties of random key graphs in the presence of unreliable links. Unreliability of graph links is captured by independent Bernoulli random variables, rendering them to be on or off independently from each other. The resulting model is an intersection of a random key graph and an Erdos-Renyi graph, and is expected to be useful in capturing various real-world networks; e.g., with secure WSN applications in mind, link unreliability can be attributed to harsh environmental conditions severely impairing transmissions. We present conditions on how to scale this model's parameters so that: 1) the minimum node degree in the graph is at least k and 2) the graph is k-connected, both with high probability as the number of nodes becomes large. The results are given in the form of zero-one laws with critical thresholds identified and shown to coincide for both graph properties. These findings improve the previous results by Rybarczyk on k-connectivity of random key graphs (with reliable links), as well as the zero-one laws by Yagan on one-connectivity of random key graphs with unreliable links.

We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent ON/OFF channels. Modeling the network by an intersection of a random K-out graph and an Erdos-Rényi graph, we present scaling conditions (on the number of nodes n, the scheme parameter K, and the probability p of a wireless channel being on), such that the resulting graph contains no nodes with a degree less than k with high probability. Results are given in the form of zero-one laws with n getting large, and are shown to improve the previous results by Yagan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero) in the same model. Through simulations, the established zero-one laws are also shown to hold for the property of k-connectivity, i.e., the property that graph remains connected despite the deletion of any k - 1 nodes or edges.

The q-composite key predistribution scheme [2] is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Prior work [5], [13], [44] explores topological properties of WSNs employing the q-composite scheme for q = 1 with unreliable communication links modeled as independent on/off channels. In this paper, we investigate topological properties related to the node degree in WSNs operating under the q-composite scheme and the on/off channel model. Our results apply to general q and are stronger than those reported for the node degree in prior work even for the case of q being 1. Specifically, we show that the number of nodes with an arbitrary degree asymptotically converges to a Poisson distribution, present the asymptotic probability distribution for the minimum degree of the network, and establish the asymptotically exact probability for the property that the minimum degree is at least an arbitrary value. Numerical experiments confirm the validity of our analytical findings.

We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent on/off channels. Modeling the network by an intersection of a random K-out graph and an Erdös-Rényi graph, we present scaling conditions (on the number of nodes, the scheme parameter K, and the probability of a wireless channel being on) such that the resulting graph contains no node with degree less than k with high probability, when the number of nodes gets large. Results are given in the form of a zero-one law and are shown to improve the previous results by Yağan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of k-connectivity; i.e., the property that graph remains connected despite the deletion of any k - 1 nodes or edges.

We consider random threshold graphs where the fitness variables are exponentially distributed. Simulations show that the zero-one law for graph connectivity exhibits a sharp phase transition. We formalize this observation by providing exact asymptotics for the width of the phase transition in the many node regime.

Random key predistribution scheme of Eschenauer and Gligor (EG) is a typical solution for ensuring secure communications in a wireless sensor network (WSN). Connectivity of the WSNs under this scheme has received much interest over the last decade, and most of the existing work is based on the assumption of unconstrained sensor-to-sensor communications. In this paper, we study the k-connectivity of WSNs under the EG scheme with physical link constraints; k-connectivity is defined as the property that the network remains connected despite the failure of any (k - 1) sensors. We use a simple communication model, where unreliable wireless links are modeled as independent on/off channels, and derive zero-one laws for the properties that i) the WSN is k-connected, and ii) each sensor is connected to at least k other sensors. These zero-one laws improve the previous results by Rybarczyk on the k-connectivity under a fully connected communication model. Moreover, under the on/off channel model, we provide a stronger form of the zero-one law for the 1-connectivity as compared to that given by Yağan.

We explore the scaling properties for graph connectivity in random threshold graphs. In the many node limit, we provide a complete characterization for the existence and type of the underlying zero-one laws, and identify the corresponding critical scalings. These results are consequences of well-known facts in Extreme Value Theory concerning the asymptotic behavior of running maxima on i.i.d. random variables. In the important special case of exponentially distributed fitness, we show that the (essentially unique) critical scaling which ensures a power-law degree distribution, does not result in graph connectivity in the asymptotically almost sure (a.a.s.) sense.

We study the diffusion of information in an overlaying social-physical network. Specifically, we consider the following set-up: There is a physical information network where information spreads amongst people through conventional communication media (e.g., face-to-face communication, phone calls), and conjoint to this physical network, there are online social networks where information spreads via web sites such as Facebook, Twitter, FriendFeed, YouTube, etc. We quantify the size and the critical threshold of information epidemics in this conjoint social-physical network by assuming that information diffuses according to the SIR epidemic model. One interesting finding is that even if there is no percolation in the individual networks, percolation (i.e., information epidemics) can take place in the conjoint social-physical network. We also show, both analytically and experimentally, that the fraction of individuals who receive an item of information (started from an arbitrary node) is significantly larger in the conjoint social-physical network case, as compared to the case where the networks are disjoint. These findings reveal that conjoining the physical network with online social networks can have a dramatic impact on the speed and scale of information diffusion.

We investigate the secure connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan, Perrig, and Song. Unlike recent work carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as independent on/off channels. We present conditions on how to scale the model parameters so that the network 1) has no secure node that is isolated and 2) is securely connected, both with high probability, when the number of sensor nodes becomes large. The results are given in the form of zero-one laws, and exhibit significant differences with corresponding results in the full-visibility case. Through simulations, these zero-one laws are shown to also hold under a more realistic communication model, namely the disk model.

We investigate the connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan Under the assumption of full visibility, this reduces to studying the connectivity in the so-called random K-out graph H (n;K); here, n is the number of nodes and K <; n is an integer parameter affecting the number of keys stored at each node. We show that if K ≥ 2 (respectively, K=1), the probability that H (n;K) is a connected graph approaches 1 (respectively, 0) as n goes to infinity. For the one-law this is done by establishing an explicitly computable lower bound on the probability of connectivity. Using this bound, we see that with high probability, network connectivity can already be guaranteed (with K ≥ 2) by a relatively small number of sensors. This corrects earlier predictions made on the basis of a heuristic transfer of connectivity results available for Erdös-Rényi graphs.

We study the diffusion behavior of real-time information. Typically, real-time information is valuable only for a limited time duration, and hence needs to be delivered before its “deadline.” Therefore, real-time information is much easier to spread among a group of people with frequent interactions than between isolated individuals. With this insight, we consider a social network which consists of many cliques and information can spread quickly within a clique. Furthermore, information can also be shared through online social networks, such as Facebook, twitter, Youtube, etc. We characterize the diffusion of real-time information by studying the phase transition behaviors. Capitalizing on the theory of inhomogeneous random networks, we show that the social network has a critical threshold above which information epidemics are very likely to happen. We also theoretically quantify the fractional size of individuals that finally receive the message. The numerical results indicate that real-time information could be much easier to propagate in a social network when large size cliques exist.

We investigate the connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan et al. Under the assumption of full visibility, this reduces to studying connectivity in the so-called random K-out graph H(n;K); here n is the number of nodes and K < n is an integer parameter affecting the number of keys stored at each node. We show that if K ≥ 2 (resp. K = 1), the probability that H(n; K) is a connected graph approaches 1 (resp. 0) as n goes to infinity. This is done by establishing an explicitly computable lower bound on the probability of connectivity. From this bound we conclude that with K ≥ 2, the connectivity of the network can already be guaranteed by a relatively small number of sensors with very high probability. This corrects an earlier analysis based on a heuristic transfer of classical connectivity results for Erdős-Rényi graphs.

We investigate the secure connectivity of wireless sensor networks under the random key distribution scheme of Eschenauer and Gligor. Unlike recent work which was carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as on/off channels. We present conditions on how to scale the model parameters so that the network: 1) has no secure node which is isolated and 2) is securely connected, both with high probability when the number of sensor nodes becomes large. The results are given in the form of full zero-one laws, and constitute the first complete analysis of the EG scheme under non-full visibility. Through simulations, these zero-one laws are shown to be valid also under a more realistic communication model (i.e., the disk model). The relations to the Gupta and Kumar's conjecture on the connectivity of geometric random graphs with randomly deleted edges are also discussed.

The random key graph is a random graph naturally associated with the random key predistribution scheme introduced by Eschenauer and Gligor in the context of wireless sensor networks (WSNs). For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here complement and strengthen recent work on this conjecture by Blackburn and Gerke. In particular, the results are given under conditions which are more realistic for applications to WSNs.

We consider a cyber-physical system consisting of two interacting networks, i.e., a cyber network overlaying a physical network. It is envisioned that these systems are more vulnerable to attacks since node failures in one network may result in (due to the interdependence) failures in the other network, causing a cascade of failures that would potentially lead to the collapse of the entire infrastructure. The robustness of interdependent systems against this sort of catastrophic failure hinges heavily on the allocation of the (interconnecting) links that connect nodes in one network to nodes in the other network. In this paper, we characterize the optimum inter-link allocation strategy against random attacks in the case where the topology of each individual network is unknown. In particular, we analyze the “regular” allocation strategy that allots exactly the same number of bidirectional internetwork links to all nodes in the system. We show, both analytically and experimentally, that this strategy yields better performance (from a network resilience perspective) compared to all possible strategies, including strategies using random allocation, unidirectional interlinks, etc.

We investigate the secure connectivity of wireless sensor networks under the pairwise key distribution scheme of Chan et al.. Unlike recent work which was carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as on/off channels. We present conditions on how to scale the model parameters so that the network i) has no secure node which is isolated, and ii) is securely connected, both with high probability when the number of sensor nodes becomes large. The results are given in the form of zero-one laws, and exhibit significant differences with corresponding results in the full visibility case.

We investigate the security of wireless sensor networks under the pairwise key distribution scheme of Chan et al. [2]. We present conditions on how to scale the model parameters so that the network is i) unassailable, and ii) unsplittable, both with high probability, as the number of sensor nodes becomes large. We show that the required number of secure keys to be stored in the memory of each sensors is an order of magnitude smaller than what is required for the Eschenauer-Gligor scheme [5].

The pairwise key distribution scheme of Chan et al. is a randomized key predistribution scheme which enables cryptographic protection in wireless sensor networks (WSNs). This pairwise scheme has many advantages over other randomized key predistribution schemes but has been deemed non-scalable due to (i) the large number of keys required to ensure secure connectivity; and (ii) implementation difficulties when sensors are required to be deployed in multiple stages. Here, we address this issue by proposing an implementation of the pairwise scheme that supports the gradual deployment of sensor nodes in several consecutive phases. We show how the scheme parameter should be adjusted with the number n of sensors so that secure connectivity is maintained in the network throughout all the stages of the deployment. We also discuss briefly the relation between the scheme parameter and the amount of memory that each sensor needs to spare for storing their keys. By showing that O(log n) many keys per node suffice to achieve secure connectivity at every step of the deployment, we confirm the scalability of the pairwise scheme in the context of WSNs.

The random key graph is the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We report on recent results concerning a conjectured zero-one law for graph connectivity, and provide an outline for its proof.

We consider the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the absence of isolated nodes, and complement it by a Poisson convergence for the number of isolated nodes. Leveraging earlier results and analogies with Erdos-Renyi graphs, we explore similar results for the property of graph connectivity.