Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process

arXiv1601.06448MaRDI QIDQ6269675FDOQ6269675

Authors: Varun Jog, Po-Ling Loh 

Publication date: 24 January 2016

Abstract: We investigate centrality and root-inference properties in a class of growing random graphs known as sublinear preferential attachment trees. We show that a continuous time branching processes called the Crump-Mode-Jagers (CMJ) branching process is well-suited to analyze such random trees, and prove that almost surely, a unique terminal tree centroid emerges, having the property that it becomes more central than any other fixed vertex in the limit of the random growth process. Our result generalizes and extends previous work establishing persistent centrality in uniform and linear preferential attachment trees. We also show that centrality may be utilized to generate a finite-sized $1-epsilon$ confidence set for the root node, for any $epsilon>0$ in a certain subclass of sublinear preferential attachment trees.

Mathematics Subject Classification ID

Combinatorial probability (60C05)

This page was built for publication: Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6269675)