Connectivity threshold conjecture for heterogeneous random key graphs

At least 9 years old · documented by

Let rr be the number of classes, let μ=(μ1,μ2,…,μr)\pmb{\mu}=(\mu_1,\mu_2,\ldots,\mu_r) be a probability distribution with μi>0\mu_i>0 for i=1,…,ri=1,\ldots,r, and let K1,…,Kr,PK_1,\ldots,K_r,P and α=(αij)\pmb{\alpha}=(\alpha_{ij}) be the scaling functions specified in the conjecture. Assume the scaling condition Λm(n)=cnlog⁡nn\Lambda_m(n)=c_n\frac{\log n}{n} with lim⁡n→∞cn=c>0\lim_{n\to\infty}c_n=c>0, and write αmd(n)\alpha_{md}(n) and αmm(n)\alpha_{mm}(n) for the corresponding minimum cross-class and within-class link probabilities. Suppose either

lim⁡n→∞αmd(n)log⁡n=0,\lim_{n\to\infty}\alpha_{md}(n)\log n=0,

or

lim⁡n→∞αmd(n)log⁡n=α∗∈(0,∞],lim⁡n→∞αmm(n)log⁡n=α∗∗∈(0,∞].\lim_{n\to\infty}\alpha_{md}(n)\log n=\alpha^*\in(0,\infty],\qquad \lim_{n\to\infty}\alpha_{mm}(n)\log n=\alpha^{**}\in(0,\infty].

Connectivity threshold conjecture. Possibly under some additional conditions, the heterogeneous random graph H(n;μ,Θn)\mathbb{H}(n;\pmb{\mu},\pmb{\Theta}_n) should satisfy

lim⁡n→∞P[H(n;μ,Θn) is connected]={0,c<1,1,c>1.\lim_{n\to\infty}\mathbb{P}\left[\mathbb{H}(n;\pmb{\mu},\pmb{\Theta}_n)\text{ is connected}\right] = \begin{cases} 0,&c<1,\\ 1,&c>1. \end{cases}

The conjecture proposes that connectivity has the same zero-one threshold as the absence of isolated nodes. The zero-law for connectivity already follows from the isolated-node result, while the one-law remains to be established, potentially subject to additional conditions.

References

Primary source

Rashad Eletreby and Osman Yağan, “Node Isolation of Secure Wireless Sensor Networks under a Heterogeneous Channel Model”, arXiv:1610.07576 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.