Connectivity threshold conjecture for heterogeneous random key graphs

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)=cnlognn\Lambda_m(n)=c_n\frac{\log n}{n} with limncn=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

limnαmd(n)logn=0,\lim_{n\to\infty}\alpha_{md}(n)\log n=0,

or

limnαmd(n)logn=α(0,],limnαmm(n)logn=α(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

limnP[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.

Sources & referencesView supporting material

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.