Sharp large-time behavior conjecture for degree evolution

About 8 years old · traced to

Consider the Barabási–Albert model with communities. Fix a vertex τ\tau that is not isolated in the initial graph, let YTY_T be its degree at time TT, and let θℓτ∗\theta^*_{\ell_\tau} be the rate parameter associated with its community.

Sharp large-time behavior conjecture. For τ\tau fixed,

lim⁡T→∞YT(T/τ)θℓτ∗=Walmost surely,\lim_{T\to\infty}\frac{Y_T}{(T/\tau)^{\theta^*_{\ell_\tau}}}=W\quad\text{almost surely},

where WW is a random variable satisfying P{W>0}=1\mathbb{P}\{W>0\}=1.

The preceding proposition establishes only the logarithmic growth rate, so this conjecture asks for a positive almost-sure limiting multiplicative constant and would give a sharper description of the degree evolution.

References

Primary source

Bruce Hajek and Suryanarayana Sankagiri, “Community Recovery in a Preferential Attachment Graph”, arXiv:1801.06818 (2018).

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.