Consistent estimation in general sublinear preferential attachment trees
Recently there has been much interest in studying large-scale real-world networks and attempting to model their properties using random graphs. This paper is a good contribution to statistical inference in models of randomly growing networks. The following is the model analysed. ``The network starts at stage \(n=2\) with two nodes \(v_1\) and \(v_2\) connected by a single edge. Next it evolves recursively by adding nodes \(v_3,v_4,\dots\) which each connect by a single edge to a single node of the existing network. The incoming nodes choose the node to which they connect by a probabilistic mechanism. Given the network with nodes \(v_1,\dots,v_n\), having degrees \(d_1(n),\dots,d_n(n)\) (the degree of a node is the number of edges connected to that node), the node \(v_{n+1}\) connects to the existing node \(v_i\in\{v_1,\dots,v_n\}\) with probability proportional to \(f(d_i(n))\), i.e., with probability \[ \frac{f(d_i(n))}{\sum_{j=1}^nf(d_j(n))}. \] Here \(f:\mathbb{N}_+\to\mathbb{R}_+\) is a given function, which we call the \textit{preferential attachment} (PA) function, and we refer to \(f(d_i(n))\) as the \textit{preference} for node \(v_i\) at stage \(n\). The PA function \(f\) is typically assumed to be non-decreasing, so that nodes of higher degrees inspire more incoming connections. This explains the name preferential attachment model. After the incoming node \(v_{n+1}\) has made its choice, the network evolves to the stage of \(n+1\) nodes and the scheme repeats with the set of existing nodes \(\{v_1,\dots,v_n\}\) and the incoming node \(v_{n+2}\). The recursive procedure may be repeated to reach any number of nodes. Consider \(r_k\) as the rescaled version of \(f(k)\) for each \(k\), that is \[ r_k:=\frac{f(k)}{\sum_{j=1}^{\infty}f(j)p_{j}}, \] where \((p_{j})_{j=1}^{\infty}\) is the limiting degree distribution. A new estimator of a PA sublinear function \(f\), from an observed realization of a network, is proposed: For each \(n\), and \(k=1,\dots,n\) define \[ \hat{r}_{k}(n)=\frac{N_{>k}(n)}{N_{k}(n)}, \] where \(N_{>k}(n)\) denotes the number of nodes of degree strictly larger than \(k\) at time \(n\), and \(N_{k}(n)\) denotes the number of nodes of degree \(k\). The main result of this paper is the following theorem. Define a function \(\rho_{f}:(0,\infty)\to[0,\infty]\) by \[ \rho_{f}(\lambda):=\sum_{l=1}^{\infty}\prod_{k=1}^{l}\frac{f(k)}{\lambda+f(k)}. \] Theorem. If there exists an open neighborhood \(U\) of \(1\), such that \(U\subset\{f(\lambda)\mid \lambda\in(0,\infty)\}\), then for any \(k\), \[ \hat{r}_{k}(n)\mathop{\longrightarrow}\limits_{n\to\infty}r_{k}\text{ almost surely.} \] The authors present a numerical illustration of the behavior of the empirical estimator. To summarize, ``the exact performance of the estimator depends on the true PA function and the degrees of interest -- if the true PA function increases slowly with respect to the degree, then it is easier to estimate the preference of low degrees, and harder to estimate the preference of high degrees and vice versa. The paper ends with the exposition of some open problems among which it is conjectured that for fixed \(k\), \[ \sqrt{n}(\hat{r}_{k}(n)-r_{k})\mathop{\longrightarrow}\limits^{d}N(0,\sigma_{k}^2), \] where \(\sigma_{k}^2\) only depends on \(f\) and \(k\) and \(\mathop{\longrightarrow}\limits^{d}\) denotes convergence in distribution. The paper is hard to understand because it is not well organized. Concepts are used before their definition. However, the proofs of the mathematical results are rigorous.
- Consistency of Hill estimators in a linear preferential attachment model
- On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees
- Fitting the linear preferential attachment model
- Non-parametric estimation of the preferential attachment function from one network snapshot
- Vertices of high degree in the preferential attachment tree
- On the total variation regularized estimator over a class of tree graphs
- Change point detection in network models: preferential attachment and long range dependence
- Correlated randomly growing graphs
- Inference for the degree distributions of preferential attachment networks with zero-degree nodes
- On the asymptotic normality of estimating the affine preferential attachment network models with random initial degrees
- Consistency of Hill estimators in a linear preferential attachment model
- Convergence properties of the degree distribution of some growing network models
- Asymptotic normality of in- and out-degree counts in a preferential attachment model
- Non-parametric estimation of the preferential attachment function from one network snapshot
- Asymptotic normality of degree counts in a preferential attachment model
- Statistical Properties of Loss Rate Estimators in Tree Topology
- Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Inference in balanced community modulated recursive trees
- On the impossibility of detecting a late change-point in the preferential attachment random graph model
This page was built for publication: Consistent estimation in general sublinear preferential attachment trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412263)
