论文标题
根寻找算法和约旦中心性在种植随机树中的持久性
Root finding algorithms and persistence of Jordan centrality in growing random trees
论文作者
论文摘要
我们考虑种植随机树的模型$ \ {\ MATHCAL {t} _f（n）：N \ geq 1 \} $，由附件函数驱动的模型动力学$ f：\ Mathbb {Z} _+\ to \ to \ Mathbb {r Mathbb {r} {r} _+$。在每个阶段，一个新的顶点进入系统，并连接到当前树中的顶点$ v $，概率与$ f成正比（\ text {geger}（v））$。这项研究的主要目的是了解root查找算法的性能。在过去的几年中，在使用基于约旦的中心度量度及其变体来开发根发现算法的技术方面出现了大量的作品（例如，Bubeck，Devroye和Lugosi或Jog and Loh的工作）。鉴于一棵未标记的未经标记的树，一个人计算了树上每个顶点的约旦中心性和固定预算$ k $输出的最佳$ k $顶点（按约旦中心衡量）。在附件功能$ f $的一般条件下，我们得出了预算$ k（ε）$的必要和足够的界限，以便以概率至少$1-ε$恢复根。对于诸如线性优先附件和均匀附件之类的规范示例，这些总体结果为预算提供了匹配的上限和下限。我们还证明了最佳$ k $ jordan中心的任何$ k $的持续存在，即，几乎肯定存在有限的随机时间$ n^*$，以至于$ n \ geq n^*$ $ k $ - $ k $ - optimal jordan中心的身份$ \ \ \ \ \ \ \ {\ nathcal {\ mathcal {描述此度量的鲁棒性特性。独立兴趣证明中的关键技术成分包括足够的条件，以实现（适当规范化的）连续分支过程的限制，其中模型$ \ {\ nathcal {\ nathcal {t} _f（n）：n \ geq n^*\} $可以被递增的cervernece rescections rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits rigits。
We consider models of growing random trees $\{\mathcal{T}_f(n):n\geq 1\}$ with model dynamics driven by an attachment function $f:\mathbb{Z}_+\to \mathbb{R}_+$. At each stage a new vertex enters the system and connects to a vertex $v$ in the current tree with probability proportional to $f(\text{degree}(v))$. The main goal of this study is to understand the performance of root finding algorithms. A large body of work (e.g. the work of Bubeck, Devroye and Lugosi or Jog and Loh) has emerged in the last few years in using techniques based on the Jordan centrality measure and its variants to develop root finding algorithms. Given an unlabelled unrooted tree, one computes the Jordan centrality for each vertex in the tree and for a fixed budget $K$ outputs the optimal $K$ vertices (as measured by Jordan centrality). Under general conditions on the attachment function $f$, we derive necessary and sufficient bounds on the budget $K(ε)$ in order to recover the root with probability at least $1-ε$. For canonical examples such as linear preferential attachment and uniform attachment, these general results give matching upper and lower bounds for the budget. We also prove persistence of the optimal $K$ Jordan centers for any $K$, i.e. the existence of an almost surely finite random time $n^*$ such that for $n \geq n^*$ the identity of the $K$-optimal Jordan centers in $\{\mathcal{T}_f(n):n\geq n^*\}$ does not change, thus describing robustness properties of this measure. Key technical ingredients in the proofs of independent interest include sufficient conditions for the existence of exponential moments for limits of (appropriately normalized) continuous time branching processes within which the models $\{\mathcal{T}_f(n):n\geq n^*\}$ can be embedded, as well as rates of convergence results to these limits.
