# Power-law hypothesis for PageRank on undirected graphs

Florian Henning 111Eindhoven University of Technology, Department of
Mathematics & Computer Science;
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Remco van der
Hofstad ††footnotemark:  Nelly Litvak ††footnotemark:

###### Abstract

Based on observations in the web-graph, the power-law hypothesis states that
PageRank has a power-law distribution with the same exponent as the in-degree.
While this hypothesis has been analytically verified for many random graph
models, such as directed configuration models and generalized random graphs,
surprisingly it has recently been disproven for the directed preferential
attachment model. In this paper, we prove that in undirected networks, the
graph-normalized PageRank is always upper bounded by the degree. Furthermore,
we prove that the corresponding (asymptotic) lower bound holds true under
reasonable assumptions on the local weak limit, but not in general, and we
provide a counterexample. Our result shows that PageRank always has a lighter
tail than the degree, which contrasts the case of the directed preferential
attachment model, where PageRank has a heavier tail instead. We end the paper
with a discussion, where we extend our results to directed networks with a
bounded ratio of in- and out-degrees, and reflect on our methods by
contrasting the undirected and directed preferential attachment model.

Mathematics Subject Classifications (2020). 05C80 (primary);
60J80, 60B20 (secondary)
Key words. PageRank, Scale-free network, heavy tails, maximally assortative,
local weak convergence.

##  1 Introduction and Results

###  1.1 Introduction

The PageRank algorithm was originally introduced by Page and Brin [14] to rank
web pages by their position in the web-graph, where directed edges are
hyperlinks from one web page to another. An important characteristic of the
topology of the web-graph is the scale-free property, in that the empirical
distribution of both in- and out- degrees is approximately a power law [25].
In the web-graph, it has also been observed that PageRank has a power-law
distribution with approximately the same exponent as that of the in-degree
[28, 17]; these observations gave rise to the so-called power-law hypothesis
that on every directed graph a power-law distribution of the in-degrees
implies a power-law distribution of PageRank with the same exponent. This
hypothesis has been recently proven to fail in the preferential attachment
model [9], one of the models for the web-graph [10, 11, 1]; specifically, the
tail of the limiting PageRank distribution in this model is heavier than that
of the in-degree [9].

For undirected graphs, PageRank is known to correlate highly with the degree.
Analytically, the authors of [7] show that in undirected semi-sparse expanding
graphs, the PageRank-distribution can be asymptotically approximated (w.r.t.
the total variation distance) by a mixture of the restart distribution and the
degree distribution.

##### Main innovation in this paper.

In this paper we analyze the power-law hypothesis in undirected graphs.
Importantly, in the remainder of Section 1, we prove that for every undirected
graph, the graph-normalized PageRank is componentwise bounded from above by
the degree vector (Theorem 1.1). This in particular excludes the asymptotic
PageRank distribution from having heavier tails than the degree distribution,
in contrast to the directed setting [9]. Additionally, we provide a sufficient
condition (Proposition 1.8) for an asymptotic lower bound on the PageRank
distribution. Both bounds together imply that if the graph normalized PageRank
has an asymptotic power law, then its exponent is the same as that of the
degree distribution, provided that the condition for the lower bound is
satisfied. The latter condition, in essence, prevents high-degree vertices
from having too many high-degree neighbors, and we expect it to hold quite
generally in a large class of random graph models and real-world networks. In
Section 2, we explicitly check the assumptions for the lower bound for
unimodular branching process trees and the Pólya point tree. Together with the
results [18, 13, 21] on local weak convergence of the graph-normalized
PageRank distribution, this implies that the power-law hypothesis holds true
for, respectively, the undirected configuration model (Theorem 2.8) and the
undirected preferential model (Theorem 2.9).

To show that, in contrast to the upper bound, the lower bound is not generally
true, in Section 3 we provide an explicit construction (Theorem 3.6) of an
evolving sequence of graphs exhibiting a power-law distribution with any
prescribed exponent, whose associated PageRank distribution does not exhibit a
power-law distribution. Finally, the Discussion Section 4 deals with
extensions (Theorem 4.1 and Proposition 4.3) of the results from Section 1 to
directed networks assuming that the ratios of in- and out-degrees in the graph
are uniformly bounded. The discussion closes with a heuristics on the
different asymptotic behaviour of PageRank for the undirected- and the
directed version of the preferential attachment model, thus explaining how the
change in the PageRank power-law arises for the directed setting, while it
fails to hold for the undirected setting.

###  1.2 Basic notions

First we start with providing the basic notions which will be employed in the
reminder of this paper. For further explanations and introduction to
mathematical models for complex networks, we refer the reader to [20, 21] and
[26].

##### Definitions.

We consider a sequence $(G_{n})_{n\in\mathbb{N}}$ of finite undirected graphs
$G_{n}=(V_{n},E_{n})$ without isolated vertices with respective vertex sets
$V_{n}=[n]:=\\{1,2,\ldots,n\\}$, and edge sets $E_{n}$. We write $i\sim j$ if
two vertices $i,j\in V_{n}$ are connected by an edge. Further,
$\boldsymbol{A}^{(\scriptscriptstyle G_{n})}=(a_{ij}^{(\scriptscriptstyle
G_{n})})_{(i,j)\in[n]}\in\\{0,1\\}^{n\times n}$ denotes the adjacency matrix
of $G_{n}$, which in our undirected case is symmetric. Finally, let
$\boldsymbol{d}^{\scriptscriptstyle(G_{n})}=(d_{i}^{\scriptscriptstyle(G_{n})})_{i\in[n]}$
denote the degree vector corresponding to $G_{n}$. Without loss of generality,
we assume that $d_{i}^{\scriptscriptstyle(G_{n})}\geq 1$ for all $i\in[n]$,
i.e., there are no isolated vertices. From now on, we will omit the
superscript $(G_{n})$ in, e.g., $d_{i}^{\scriptscriptstyle(G_{n})}$ when this
notation is clear from the context.

Throughout the paper, we print vectors and matrices in boldface in contrast to
scalars, and define the partial order ”$\leq$” on $\mathbb{R}^{n}$ as
$\boldsymbol{a}\leq\boldsymbol{b}$ if and only if $a_{i}\leq b_{i}$ for all
$i\in[n]$. As usual,
$\|\boldsymbol{a}\|_{p}:=\left(\sum_{i=1}^{n}|a_{i}|^{p}\right)^{1/p}$ denotes
the $p$-norm, $p\in(0,\infty)$, on $\mathbb{R}^{n}$, where we will also
abbreviate $|\boldsymbol{v}|:=\|\boldsymbol{v}\|_{1}$. Furthermore, by
$\boldsymbol{a}\odot\boldsymbol{b}$ we denote the elementwise (Hadamard)
product of two vectors, i.e.,
$(\boldsymbol{a}\odot\boldsymbol{b})_{i}:=a_{i}b_{i},\quad i\in[n]$. Finally,
$\boldsymbol{1}_{n}\in\mathbb{R}^{n}$ denotes the vector of ones and
$\mathbbm{I}_{n}\in\mathbb{R}^{n\times n}$ the $n$-dimensional identity
matrix. For notational distinction from the above two symbols, we denote the
indicator function on any set $B$ by $\mathbbm{1}_{B}(\cdot)$. We say that a
real-valued random variable $X$ is stochastically bounded from above by a
real-valued random variable $Y$, denoted by $X\preceq Y$, iff
$\mathbb{P}(X\geq x)\leq\mathbb{P}(Y\geq y)$ for every $x\in\mathbb{R}$.
Moreover, we say that (cf. the relation $\leq_{K}$ in [30, P. 27]) a random
vector $\boldsymbol{X}\in\mathbb{R}^{n}$ is stochastically bounded from above
by a random vector $\boldsymbol{Y}\in\mathbb{R}^{n}$, and write
$\boldsymbol{X}\preceq\boldsymbol{Y}$, iff
$\mathbb{P}(\boldsymbol{X}\geq\boldsymbol{x})\leq\mathbb{P}(\boldsymbol{Y}\geq\boldsymbol{x})$
for every $\boldsymbol{x}\in\mathbb{R}^{n}$. Note that if
$\boldsymbol{X}=(X_{i})_{i\in[n]}$ and $\boldsymbol{Y}=(Y_{i})_{i\in[n]}$ have
independent components, then $\boldsymbol{X}\preceq\boldsymbol{Y}$ is
equivalent to $X_{i}\preceq Y_{i}$ for all $i\in[n]$. Finally, for functions
$f,g\colon\mathbb{R}\rightarrow\mathbb{R}$, we write, for
$a\in\mathbb{R}\cup\\{-\infty,+\infty\\}$, that $f=o(g)$ as $x$ tends to $a$
iff $\limsup_{x\rightarrow a}|\frac{f(x)}{g(x)}|=0$ and $f=O(g)$ as $x$ tends
to $a$ iff $\limsup_{x\rightarrow a}|\frac{f(x)}{g(x)}|<\infty$.

##### The PageRank equation.

Define the stochastic matrix
$\boldsymbol{P}=\boldsymbol{P}^{\scriptscriptstyle(G_{n})}=(p_{ij}^{\scriptscriptstyle(G_{n})})_{i,j\in[n]}\in[0,1]^{n\times
n}$ by setting

$p_{ij}:=p_{ij}^{\scriptscriptstyle(G_{n})}=\frac{a_{ij}^{\scriptscriptstyle(G_{n})}}{d_{i}^{\scriptscriptstyle(G_{n})}},$
(1)

where $(a_{ij}^{\scriptscriptstyle(G_{n})})_{i,j\in[n]}$ is the adjacency
matrix of $G_{n}$. Then the graph-normalized PageRank equation with damping
factor $c\in(0,1)$ reads

$\boldsymbol{R}=c\,\boldsymbol{R}\boldsymbol{P}+(1-c)\boldsymbol{1}_{n},\qquad\boldsymbol{R}\in[0,n]^{n}.$
(2)

Note that (2) can be written equivalently in terms of a fixed-point equation
with an irreducible matrix acting on vectors of length $n$, so that the
solution $\boldsymbol{R}$ appears as the Perron-Frobenius eigenvector and is
hence unique. In particular, (2) is uniquely solved for $\boldsymbol{R}$ by

$\boldsymbol{R}=(1-c)\boldsymbol{1}_{n}(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}.$
(3)

Componentwise, the above equation equals the Neumann series

$R_{k}=(1-c)\sum_{s=0}^{\infty}c^{s}\|(\boldsymbol{P}^{s})_{\cdot,k}\|_{1}=(1-c)\sum_{s=0}^{\infty}c^{s}\sum_{j=1}^{n}(\boldsymbol{P}^{s})_{jk},\qquad
k\in[n].$ (4)

###  1.3 Results

####  1.3.1 Upper bound on PageRank

Because of symmetry of the adjacency matrix $\boldsymbol{A}$ of an undirected
graph, the next general upper bound holds true:

######  Theorem 1.1 (PageRank is at most the degree).

Given the degree vector $\boldsymbol{d}$ of any undirected graph
$G_{n}=([n],E_{n})$, the PageRank vector
$\boldsymbol{R}^{\scriptscriptstyle(G_{n})}$ in (2) is componentwise upper
bounded by the degree, i.e.,

$R_{i}^{\scriptscriptstyle(G_{n})}\leq
d_{i}^{\scriptscriptstyle(G_{n})}\qquad\text{for all }i\in[n].$ (5)

Note that Theorem 1.1 does not require any further assumptions on the graph or
the degree sequence. Since the proof of Theorem 1.1 is quite simple, we state
it now. It is based on two lemmas. The first, Lemma 1.2, states that employing
symmetry of the adjacency matrix
$\boldsymbol{A}=\boldsymbol{A}^{\scriptscriptstyle(G_{n})}$ we can go over
from Equation (3) above to an equivalent expression, where the operator
$(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}$ functions from the left instead of
from the right. Afterwards, Lemma 1.3 provides an upper bound for that new
expression.

######  Lemma 1.2 (Solution PageRank for undirected graphs).

Let $G_{n}=(V_{n},E_{n})$ be a finite graph without isolated vertices with
$\\#V_{n}=n$. Then the graph-normalized PageRank equation (2) is solved by the
undirected PageRank equation given by

$\boldsymbol{R}^{\scriptscriptstyle(G_{n})}=(1-c)\boldsymbol{d}^{\scriptscriptstyle(G_{n})}\odot(\mathbbm{I}_{n}-c\boldsymbol{P}^{\scriptscriptstyle(G_{n})})^{-1}\boldsymbol{Q}^{\scriptscriptstyle(G_{n})}\boldsymbol{1}_{n},$
(6)

where
$\boldsymbol{Q}=\boldsymbol{Q}^{\scriptscriptstyle(G_{n})}\in\mathbb{R}^{n\times
n}$ is the diagonal degree matrix defined by $Q_{i,i}=1/d_{i}$.

###### Proof of Lemma 1.2.

To ease readability, we will omit the superscripts $(G_{n})$ in the proof. The
$i$th component, $i\in[n]$, of the PageRank-Equation (2) reads

$R_{i}=c\sum_{j\in[n]}p_{ji}R_{j}+(1-c).$ (7)

Divide both sides of the equation by the respective degree $d_{i}$, and insert
the definition of $p_{ji}$ which implies that
$d_{i}p_{ij}=a_{ij}=a_{ji}=p_{ji}d_{j}$, to obtain

$\begin{split}\frac{R_{i}}{d_{i}}&=c\sum_{j\in[n]}\frac{a_{ji}}{d_{i}d_{j}}R_{j}+\frac{1-c}{d_{i}}=c\sum_{j\in[n]}p_{ij}\frac{R_{j}}{d_{j}}+\frac{1-c}{d_{i}},\end{split}$
(8)

where the second equation follows from symmetry of the adjacency matrix
$\boldsymbol{A}$.

Next define the vector $\boldsymbol{v}$ by $v_{i}:=R_{i}/d_{i},$ for
$i\in[n]$. In matrix-notation, this change of variables transforms equation
(2) to

$\boldsymbol{v}=c\,\boldsymbol{P}\boldsymbol{v}+(1-c)\boldsymbol{Q}\boldsymbol{1}_{n}.$
(9)

As we have $\|c\boldsymbol{P}\|=c\|\boldsymbol{P}\|\leq c<1$, where
$\|\boldsymbol{P}\|:=\sup_{\|\boldsymbol{w}\|_{2}=1}\|\boldsymbol{P}\boldsymbol{w}\|_{2}$
denotes the operator-norm, we can solve (9) for $\boldsymbol{v}$ (see, e.g.,
[4, Section 5.7]) to arrive at

$\boldsymbol{v}=(1-c)(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}\boldsymbol{Q}\boldsymbol{1}_{n},$
(10)

which, by definition of $\boldsymbol{v}$, is in turn equivalent to the
undirected PageRank equation

$\boldsymbol{R}=(1-c)\boldsymbol{d}\odot(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}\boldsymbol{Q}\boldsymbol{1}_{n}.$
(11)

∎

######  Lemma 1.3 (Bound on undirected PageRank equation).

The second factor in (11) satisfies
$(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}\boldsymbol{Q}\boldsymbol{1}_{n}\leq\boldsymbol{1}_{n}/(1-c).$

###### Proof.

From the assumption that $d_{i}\geq 1$ for all $i\in[n],$ we directly have
$\boldsymbol{Q}\boldsymbol{1}_{n}\leq\boldsymbol{1}_{n}$. Then express
$(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}$ in terms of the Neumann series

$(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}=\sum_{s=0}^{\infty}(c\boldsymbol{P})^{s},$
(12)

and employ the fact that $\boldsymbol{P}$ is a (row-)stochastic matrix that
functions from the left to arrive at
$(\mathbbm{I}_{n}-c\boldsymbol{P})^{-1}Q\boldsymbol{1}_{n}\leq\sum_{s=0}^{\infty}c^{s}\boldsymbol{1}_{n}$,
which finishes the proof. ∎

######  Remark 1.4 (Relation to [27]).

The transformation $v_{i}:=R_{i}/d_{i}$ that we use is similar to the
transformation $X_{i}:=\mathcal{C}\mathcal{R}_{i}$ employed in [27] to
describe the limiting PageRank as a solution to a stochastic fixed-point
recursion equation on a suitable weighted branching process tree.
$\blacktriangleleft$

####  1.3.2 Lower bound on PageRank

For the upper bound in Theorem 1.1, we have used that the degree vector is
component-wise lower bounded by $1$ (where we recall that the graph is assumed
to have no isolated vertices). In the context of directed graphs where the
degrees satisfy a power-law distribution, however, the family
$(d_{k}^{\scriptscriptstyle(G_{n})})_{n\in\mathbb{N},\ k\in[n]}$ is clearly
not bounded from above and a reasoning similar to the one in the proof of (5)
will not work to obtain a lower bound on PageRank.

Nonetheless, in Proposition 1.8, below we state a sufficient condition on
rooted random graphs for a lower bound to hold for the respective PageRank at
the root, which we define in Definition 1.6 below. The result of Proposition
1.8 gets its full strength in combination with [18, Theorem 2.1], which shows
that the limiting distribution of the graph-normalized PageRank is determined
by the local limit of the graph sequence. We postpone a brief introduction on
local weak convergence and its implications to PageRank to Section 2, and
define rooted graphs and PageRank on infinite locally-finite graphs:

######  Definition 1.5 (Rooted graphs).

By a rooted graph $G_{\star}$, we mean a pair $(G,\phi)$ such that $G=(V,E)$
is a graph and $\phi\in V$ is a distinguished vertex called the root. We say
that $(G,\phi)$ is locally finite when every vertex in $V$ has a finite
degree.

Let $\mathcal{G}_{\star}$ denote the quotient space of the set of all locally-
finite connected rooted graphs with respect to the equivalence relation
$\cong$ given by root preserving graph-isomorphisms. We endow
$\mathcal{G}_{\star}$ with the Borel-$\sigma$ algebra generated by the local
metric $d_{loc}$ on $\mathcal{G}_{\star}$, which we will define later on in
Definition 2.1 when it is actually needed in the framework of local
convergence. $\blacktriangleleft$

######  Definition 1.6 (Root-PageRank on infinite rooted graph).

Let $G_{\star}=(G,\phi)$ be any representative of an element in
$\mathcal{G_{\star}}$ with degree vector $\boldsymbol{d}$ and adjacency matrix
$\boldsymbol{A}$. Consider the (possibly infinite-dimensional) matrix
$\boldsymbol{P}=(p_{ij})_{i,j\in\mathbb{N}}$ which is analogously to (1)
defined by $p_{ij}=a_{ij}/d_{i}$. The PageRank at the root or Root-PageRank is
the random variable defined analogously to (4) by

$R_{\phi}=R_{\phi}(G)=(1-c)\sum_{s=0}^{\infty}c^{s}\sum_{j\in
V}(\boldsymbol{P}^{s})_{j\phi}.$ (13)

$\blacktriangleleft$

######  Remark 1.7 (Uniqueness Root-PageRank).

By linearity, the function $R_{\phi}$ is indeed a function on the quotient
space $\mathcal{G}_{\star}$ and does not depend on the choice of the
representative element chosen as $G$. $\blacktriangleleft$

For the root-PageRank, we have the following asymptotic lower bound. In its
statement, we write

$d_{\phi}^{\scriptscriptstyle(\geq\alpha)}=d_{\phi}^{\scriptscriptstyle(G_{n},\geq\alpha)}=\\#\\{j\in
V\colon j\sim\phi\text{ and }d_{j}\geq\alpha\\}$ (14)

for the number of neighbors of $d_{\phi}$ having degree at least $\alpha:$

######  Proposition 1.8 (Root-PageRank lower bound).

In the set-up of Definition 1.6 assume that there exist $\alpha>0$ and
$\varepsilon\in(0,1)$ such that, as $k\rightarrow\infty,$

$\mathbb{P}\left(d_{\phi}>k,d_{\phi}^{\scriptscriptstyle(\geq\alpha)}\geq(1-\varepsilon)d_{\phi}\right)=o(\mathbb{P}(d_{\phi}>k)).$
(15)

Then, the solution $R_{\phi}$ to the root-PageRank-equation (13) satisfies

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}\Big{(}d_{\phi}>\frac{\alpha
k}{\varepsilon c(1-c)}\Big{)}\quad\text{as }k\rightarrow\infty.$ (16)

Equation (16) implies that the power-law exponent $\tau_{R}$ of $R_{\phi}$,
when it exists, is at most as large as the power-law exponent $\tau_{d}$ of
$d_{\phi}$. Together with the upper bound in Theorem 1.1, this lower bound
implies that if $d_{\phi}$ follows a power-law with exponent $\tau_{d}$, then
so does $R_{\phi}$. Thus, the power-law hypothesis holds.

In words, (15) means that the probability that the degree of the root is large
and a positive proportion of neighbors of the root $\phi$ has degree at least
$\alpha$ for some fixed, and possibly large, $\alpha$, vanishes compared to
the probability that the degree of the root is large. For (15) to be false,
most of the neighbors of high-degree vertices should have a high degree
themselves as well. This means that the graph is highly assortative in a very
strong sense. For most random graph models, such a property is not true, and
neighbors of high-degree vertices have degrees that are bounded by $\alpha$
with high probability for large $\alpha$. Thus, condition (15) is quite
reasonable.

###### Proof of Proposition 1.8.

By restricting the outer sum in (13) to the first two terms, we obtain

$\mathbb{P}(R_{\phi}>k)\geq\mathbb{P}\Big{(}1-c+c(1-c)\sum_{j\sim\phi}\frac{a_{j\phi}}{d_{j}}>k\Big{)}\geq\mathbb{P}\Big{(}c(1-c)\sum_{j\sim\phi}\frac{1}{d_{j}}>k\Big{)}.$
(17)

Now, a case distinction whether the number of neighbors of the root $\phi$
whose degree is bounded from above by $\alpha$, is bounded from below by
$\varepsilon d_{\phi}$ or not gives

$\displaystyle\mathbb{P}\Big{(}c(1-c)\sum_{j\sim\phi}\frac{1}{d_{j}}>k\Big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}c(1-c)\sum_{j\sim\phi}\frac{1}{d_{j}}>k,\\#\\{j\colon
j\sim\phi\text{ and }d_{j}<\alpha\\}\geq\varepsilon d_{\phi}\Big{)}$ (18)
$\displaystyle\geq\mathbb{P}\Big{(}d_{\phi}>\frac{\alpha}{\varepsilon
c(1-c)}k,\\#\\{j\colon j\sim\phi\text{ and }d_{j}<\alpha\\}\geq\varepsilon
d_{\phi}\Big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}d_{\phi}>\frac{\alpha}{\varepsilon
c(1-c)}k\Big{)}-\mathbb{P}\Big{(}d_{\phi}>\frac{\alpha}{\varepsilon
c(1-c)}k,d_{\phi}^{\scriptscriptstyle(\geq\alpha)}\geq(1-\varepsilon)d_{\phi}\Big{)}.$

By Condition (15),

$\begin{split}\frac{\mathbb{P}(d_{\phi}>l,d_{\phi}^{\scriptscriptstyle(\geq\alpha)}\geq(1-\varepsilon)d_{\phi})}{\mathbb{P}(d_{\phi}>l)}\stackrel{{\scriptstyle
l\rightarrow\infty}}{{\longrightarrow}}0,\end{split}$ (19)

which in combination with (18) gives (16). ∎

We expect Condition (15) to hold very broadly. For its practical application
to branching process trees in Section 2, we provide the following Corollary
1.9, that features two different conditions which imply (15) and are easy to
verify in specific (tree) settings:

######  Corollary 1.9 (Assumoptions implying (15)).

Conditionally on $d_{\phi}=k$, let $\boldsymbol{N}_{\phi,k}\subset\\{j\in
V\colon j\sim\phi\\}$ be a subset of the neighbors of $\phi$ such that the
sequence $(\boldsymbol{N}_{\phi,k})_{k\in\mathbb{N}}$ is almost surely non-
decreasing with $k$ and, almost surely as $k\rightarrow\infty$,

$\bar{n}_{\phi,k}:=\\#\\{j\in V\colon
j\sim\phi\\}\setminus\boldsymbol{N}_{\phi,k}=o(k)$

  1. a)

Fix $k,l$ such that $\mathbb{P}(d_{\phi}=k,\bar{n}_{\phi,k}=l)>0$. Assume
that, conditionally on $d_{\phi}=k$ and $\bar{n}_{\phi,k}=l$, the family
$(d_{j})_{j\in\boldsymbol{N}_{\phi,k}}$ is stochastically bounded from above
by an independent, but not necessarily identically distributed, family
$(\tilde{d_{j}})_{j\in\boldsymbol{N}_{\phi,k}}$ such that there is a uniform
upper bound $C<\infty$ for
$(\mathbb{E}[\tilde{d}_{j}])_{j\in\boldsymbol{N}_{\phi,k}}$ which depends
neither on $k$ nor on $l$. Then Condition (15) holds true for $\alpha=2C$ and
any $\varepsilon<\tfrac{1}{2}$.

  2. b)

Fix $k,l$ such that $\mathbb{P}(d_{\phi}=k,\bar{n}_{\phi,k}=l)>0$. Assume
that, conditionally on $d_{\phi}=k$ and $\bar{n}_{\phi,k}=l$, the family
$(d_{j})_{j\in\boldsymbol{N}_{\phi,k}}=l$ is stochastically bounded from above
by an i.i.d. family $(\tilde{d_{j}})_{j\in\boldsymbol{N}_{\phi,k}}$ of
$\mathbb{N}$-valued random variables, whose distribution depends neither on
$k$ nor on $l$. Then Condition (15) holds true for
$\alpha=\bar{F}_{\tilde{d}_{1}}^{\leftarrow}(\frac{1}{2}):=\min\\{t\in\mathbb{N}_{0}\mid\mathbb{P}(\tilde{d}_{1}\geq
t)\leq\frac{1}{2}\\}$ and any $\varepsilon<\tfrac{1}{2}$.

In both cases a) and b), for any $\beta>2\alpha/[c(1-c)]$,

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}(d_{\phi}>\beta k)\quad\text{as
}k\rightarrow\infty.$

###### Proof of Corollary 1.9.

Let Assumption a) or b) be fulfilled and choose $\alpha$ accordingly. For any
$k\in\mathbb{N}$, consider the family $(Y_{j})_{j\in\boldsymbol{N}_{\phi,k}}$
of independent random variables defined by

$Y_{j}:=\mathbbm{1}_{\\{\tilde{d}_{j}\geq\alpha\\}}.$ (20)

Then

$\mathbb{E}[Y_{j}]=\mathbb{P}(Y_{j}=1)\leq\frac{1}{2},$

which in Case a) follows from the Markov inequality and in Case b) from the
definition of the function $\bar{F}_{\tilde{d}_{1}}^{\leftarrow}$. In
particular, $(Y_{j})_{j\in\boldsymbol{N}_{\phi,k}}$ is stochastically bounded
from above by an i.i.d. family $(Z_{j})_{j\geq 1}$ of
Bernoulli$(\tfrac{1}{2})$-random variables. The remainder of the proof is the
same for both cases.

For all $k\in\mathbb{N}$ with $\mathbb{P}(d_{\phi}=k)>0$, the assumption on
$(\tilde{d}_{j})_{j\in\boldsymbol{N}_{\phi,k}}$ guarantees that

$\displaystyle\mathbb{P}(d_{\phi}^{\scriptscriptstyle(\geq\alpha)}\geq(1-\varepsilon)d_{\phi}\mid
d_{\phi}=k)$ $\displaystyle\leq\mathbb{P}(\\#\\{j\in
d_{\phi}^{\scriptscriptstyle(\geq\alpha)}\cap\boldsymbol{N}_{\phi,k}\\}\geq(1-\varepsilon)d_{\phi}-\bar{n}_{\phi,k}\mid
d_{\phi}=k)$ (21)
$\displaystyle\leq\mathbb{P}(\\#\\{j\in\boldsymbol{N}_{\phi,k}\text{ and
}\tilde{d}_{j}\geq\alpha\\}\geq(1-\varepsilon)d_{\phi}-\bar{n}_{\phi,k}\mid
d_{\phi}=k)$ (22)
$\displaystyle\leq\mathbb{P}\Big{(}\frac{1}{k}\sum_{j\in\boldsymbol{N}_{\phi,k}}Y_{j}\geq
1-\varepsilon-\frac{\bar{n}_{\phi,k}}{k}\mid d_{\phi}=k\Big{)}$ (23)
$\displaystyle\leq\mathbb{P}\Big{(}\frac{1}{k}\sum_{j\in\boldsymbol{N}_{\phi,k}}Z_{j}\geq
1-\varepsilon-\frac{\bar{n}_{\phi,k}}{k}\mid d_{\phi}=k\Big{)}.$ (24)

Here, the second inequality follows from total probability, writing

$\displaystyle\mathbb{P}(\\#\\{j\in\boldsymbol{N}_{\phi,k}\colon
d_{j}\geq\alpha\\}\geq(1-\varepsilon)d_{\phi}-\bar{n}_{\phi,k}\mid
d_{\phi}=k)$ (25)
$\displaystyle=\sum_{l\in\mathbb{N}}\mathbb{P}(\\#\\{j\in\boldsymbol{N}_{\phi,k}\text{
and }d_{j}\geq\alpha\\}\geq(1-\varepsilon)d_{\phi}-\bar{n}_{\phi,k}\mid
d_{\phi}=k,\bar{n}_{\phi,k}=l)\mathbb{P}(\bar{n}_{\phi,k}=l\mid d_{\phi}=k)$
(26)
$\displaystyle\leq\sum_{l\in\mathbb{N}}\mathbb{P}(\\#\\{j\in\boldsymbol{N}_{\phi,k}\text{
and
}\tilde{d}_{j}\geq\alpha\\}\geq(1-\varepsilon)d_{\phi}-\bar{n}_{\phi,k}\mid
d_{\phi}=k,\bar{n}_{\phi,k}=l)\mathbb{P}(\bar{n}_{\phi,k}=l\mid d_{\phi}=k),$

as, conditionally on $d_{\phi}=k$ and $\bar{n}_{\phi,k}=l$, the
$\mathbb{R}^{l}$-valued random vector $(d_{j})_{j\in\boldsymbol{N}_{\phi,k}}$
is stochastically bounded from above by
$(\tilde{d}_{j})_{j\in\boldsymbol{N}_{\phi,k}}$ by assumption. Now choose
$0<\varepsilon<\varepsilon^{*}<\tfrac{1}{2}$, and let $\hat{K}_{1}$ be large
enough such that $1-\varepsilon-\frac{\bar{n}_{\phi,k}}{k}\geq
1-\varepsilon^{*}>\frac{1}{2}=\mathbb{E}[Z_{j}]$ almost surely, for all
$k\geq\hat{K}_{1}$.

For $k\geq\hat{K}_{1}$, a corollary of Cramér’s Theorem (see [16, Remark c
below Theorem 2.2.3]) gives

$\begin{split}\mathbb{P}\Big{(}\frac{1}{k}\sum_{j\in\boldsymbol{N}_{\phi,k}}Z_{j}\geq
1-\varepsilon-\frac{\bar{n}_{\phi,k}}{k}\mid
d_{\phi}=k\Big{)}&\leq\mathbb{P}\Big{(}\frac{1}{\\#\boldsymbol{N}_{\phi,k}}\sum_{j\in\boldsymbol{N}_{\phi,k}}Z_{j}\geq
1-\varepsilon^{*}\mid d_{\phi}=k\Big{)}\cr&\leq
2\exp(-\\#\boldsymbol{N}_{\phi,k}\Lambda^{*}(1-\varepsilon^{*}))\end{split}$
(27)

where
$\Lambda^{*}(1-\varepsilon^{*})=(1-\varepsilon^{*})\log(2(1-\varepsilon^{*}))+\varepsilon^{*}\log(2\varepsilon^{*})>0$
is the minimum of the Legendre transform of the moment generating function of
$Z_{1}$ on the interval $[1-\varepsilon^{*},1]$. As the r.h.s. in (27)
decreases with increasing $k$, we conclude that, for any $l\in\mathbb{N}_{0}$,

$\mathbb{P}\Big{(}\frac{1}{k}\sum_{j\in\boldsymbol{N}_{\phi,k+l}}Z_{j}\geq
1-\varepsilon^{*}\mid d_{\phi}=k+l\Big{)}\leq
2\exp(-\\#\boldsymbol{N}_{\phi,k+l}\Lambda^{*}(1-\varepsilon^{*})),$ (28)

which, in combination with the law of total probability, gives

$\mathbb{P}\Big{(}\frac{1}{k}\sum_{j\in\boldsymbol{N}_{\phi,k}}Z_{j}\geq
1-\varepsilon\mid d_{\phi}\geq k\Big{)}\stackrel{{\scriptstyle
k\rightarrow\infty}}{{\rightarrow}}0\quad\text{exponentially fast.}$ (29)

In combination with (21), this shows that Condition (15) holds for $\alpha$
and $\varepsilon>\tfrac{1}{2}$, which in view of Proposition 1.8 concludes the
proof. ∎

##  2 Applications

In this section we briefly explain the notion of local weak convergence of
random graphs and its implications for the asymptotic of the associated root-
PageRank. This part is mostly based on [18]. Additionally, we define the
notion of power-law decay. Afterwards we prove that the assumptions of
Corollary 1.9 hold true for two particular instances of undirected random
graphs/ branching processes. These are unimodular branching process trees and
the Pólya point tree. This then implies correctness of the power-law
hypothesis for every evolving sequence of undirected graphs which converge
locally weakly to one these two random graphs, in particular the undirected
configuration model and the undirected preferential attachment model.

###  2.1 Local weak convergence and the limiting PageRank distribution

Local weak convergence was introduced in [2, 12] to make the notion that
finite graphs can look like infinite graphs from the perspective of a random
vertex precise. Local weak limits of random graphs are random elements in the
set $\mathcal{G}_{\star}$ of locally-finite connected rooted graphs up to
equivalence by isomorphism (recall Definition 1.6 above). For the concept of
local weak convergence, the following two-step procedure is of relevance:
First we draw a sequence of finite undirected deterministic or random graphs
$G_{n}=(V_{n},E_{n})$ with $\\#V_{n}=n$. Second, for each $n\in\mathbb{N}$ we
choose a vertex $\phi_{n}\in V_{n}$ uniformly at random to obtain a rooted
graph $(G_{n},\phi_{n})$. Local weak convergence of the sequence
$(G_{n})_{n\in\mathbb{N}}$ against a (possibly random)
$G_{\star}\in\mathcal{G}_{\star}$ then means that the double-expectation
(w.r.t. both stages of randomness) of every bounded continuous (w.r.t. the
local metric of Definition 2.1 below) function
$f\colon\mathcal{G}_{\star}\rightarrow\mathbb{R}$ converges to the expectation
of $f$ w.r.t. to the prescribed limiting distribution on
$\mathcal{G}_{\star}$. To make this precise, for any finite graph $G=(V,E)$,
define the (random) probability measure (cf. the measure $\mu_{H}$ in [12,
Page 2]) $\mathcal{P}(G)$ on $\mathcal{G}_{\star}$ by setting

$\mathcal{P}(G):=\frac{1}{\\#V}\sum_{i\in V}\delta_{(G,i)},$ (30)

i.e., $\mathcal{P}(G)$ describes the law of the graph $G$ observed from a
uniformly chosen root among its vertices.

Now we describe the relevant topology on $\mathcal{G}_{\star}$. For a rooted
connected graph $(G,\phi)$ let $B^{(\scriptscriptstyle G)}_{s}(\phi)$ denote
the subgraph of $(G,\phi)$ of vertices at distance at most $s$ from the root
$\phi$.

######  Definition 2.1 (Definition 3.3 in [18]).

The function $d_{loc}$ on $\mathcal{G}_{\star}\times\mathcal{G}_{\star}$,
defined by

$d_{loc}\left((G,\phi),(G^{\prime},\phi^{\prime})\right):=\frac{1}{1+\inf_{s\geq
1}\\{B^{(\scriptscriptstyle G)}_{s}(\phi)\ncong B^{(\scriptscriptstyle
G^{\prime})}_{s}(\phi^{\prime})\\}}$

is called the local metric on $\mathcal{G}_{\star}$. $\blacktriangleleft$

Note that we can adapt the metric $d_{loc}$ to the set-up of marked and, in
particular, directed graphs (see [21, Definition 2.10]). With these notions in
mind, the formal definition of local weak convergence reads as follows:

######  Definition 2.2 (Local weak convergence).

A deterministic or random sequence $(G_{n})_{n\in\mathbb{N}}$ of random graphs
is said to converge locally weakly to a (possibly random) rooted graph
$(G,\phi)\in\mathcal{G}_{\star}$ with law
$\mu\in\mathcal{M}_{1}(\mathcal{G}_{\star},\mathcal{B}(\mathcal{G}_{\star}))$
iff for any bounded function $f\colon\mathcal{G}_{\star}\rightarrow\mathbb{R}$
which is continuous with respect to the topology induced by $d_{loc}$,

$\mathbb{E}[\mathbb{E}_{\mathcal{P}(G_{n})}[f(G_{n},\phi_{n})]]\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\rightarrow}}\mathbb{E}_{\mu}[f(G,\phi)].$ (31)

Here, the outer expectation is taken with respect to the distribution of
$G_{n}$ and the argument $(G_{n},\phi_{n})$ of $f$ is restricted to the
connected component of $\phi_{n}$ in $G_{n}$, which is an element in
$\mathcal{G}_{\star}$. $\blacktriangleleft$

######  Remark 2.3 (Uniqueness of local weak limit).

The space $(\mathcal{G}_{\star},d_{loc})$ is Polish (e.g., [21, Thm. A.7]),
hence the (local) weak limit is unique (e.g., [23, Rem. 13.13]).
$\blacktriangleleft$

######  Remark 2.4 (Convergence of typical neighborhoods).

To prove local weak convergence in the sense of Definition 2.2 above it
suffices to verify (31) for all test functions $f^{H}_{s}$ of the form
$f^{H}_{s}(G,\phi):=\mathbbm{1}_{\\{B_{s}^{(\scriptscriptstyle G)}(\phi)\cong
H_{\star}\\}}$, where $s\geq 1$ and $H_{\star}\in\mathcal{G}_{\star}$. (e.g.,
[21, Thm. 2.15]) $\blacktriangleleft$

Next we relate the above definition to the root-PageRank $R_{\phi}$. By
truncating the outer sum in (13) at some level $N$ (for reasons of continuity)
and carefully controlling errors while letting $N$ and $n$ tend to infinity
[18] proves that (31) actually holds true for test functions of the desired
form $f_{r}(G,\phi):=\mathbbm{1}_{\\{R_{\phi}(G)>r\\}}$. Here $r>0$ is any
continuity point of the cumulative distribution function of the root-PageRank
of the limiting graph:

######  Theorem 2.5 (First part of Theorem 2.1 in [18]).

Let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of deterministic or random graphs
and let $\phi_{n}\in V_{n}$ be chosen uniformly at random. If
$(G_{n})_{n\in\mathbb{N}}$ converges locally weakly to
$(G,\phi)\in\mathcal{G}_{\star}$, then $\mathbb{E}[R_{\phi}(G)]\leq 1$ and

$\begin{split}R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}&\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\rightarrow}}R_{\phi}(G)\quad\text{in distribution,
i.e.,}\cr\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>r)&\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\rightarrow}}\mathbb{P}(R_{\phi}(G)>r)\text{ at any
continuity point $r>0$ of the right-hand side.}\end{split}$ (32)

###  2.2 Power-law decay of degree distribution

Let us recall the following analytic definitions:

######  Definition 2.6 (Power-law distributions).

  1. 1.

A function $\mathcal{L}:(0,\infty)\rightarrow(0,\infty)$ is called slowly
varying at infinity iff for any $a>0,$

$\frac{\mathcal{L}(ax)}{\mathcal{L}(x)}\stackrel{{\scriptstyle
x\rightarrow\infty}}{{\rightarrow}}1.$

  2. 2.

A function $f\colon(0,\infty)\rightarrow(0,\infty)$ is called regularly
varying at infinity with tail index $\alpha>0$ and tail function $\mathcal{L}$
iff $\mathcal{L}$ is slowly varying at infinity and

$f(x)=\mathcal{L}(x)x^{-\alpha}\text{ for all }x\in(0,\infty).$

  3. 3.

A random variable $X$ is said to have a power-law distribution with exponent
$\tau>1$ and tail function $\mathcal{L}$ iff the complementary distribution
function

$\bar{F}_{X}\colon(0,\infty)\rightarrow[0,1]\quad\text{given
by}\quad\bar{F}_{X}(x)=\mathbb{P}(X>x)\ $

is regularly varying at infinity with tail index $\tau-1$ and tail function
$\mathcal{L}$.

  4. 4.

A random variable $X$ satisfies power-law bounds with exponent $\tau>1$ and
tail function $\mathcal{L}$ iff $\mathcal{L}$ is slowly varying at infinity
and there exist constants $0<\underline{a}\leq\bar{a}$ such that

$\underline{a}\mathcal{L}(k)k^{-(\tau-1)}\leq\bar{F}_{X}(k)\leq\bar{a}\mathcal{L}(k)k^{-(\tau-1)}.$

$\blacktriangleleft$

###  2.3 Application to branching-process trees and the configuration model

The unimodular branching-process tree with integrable root-degree distribution
$(p_{k})_{k\in\mathbb{N}}$ is characterized by the property that every vertex
apart from the root has an offspring distribution described by the respective
size-biased distribution $p_{k}^{*}=(k+1)p_{k+1}/\mathbb{E}[d_{\phi}]$ (see
[21, Definition 1.26] or [3] for a relation of that notion to unimodular
groups). As the family of degrees of each of the children of the root is in
particular i.i.d., the unimodular branching process tree clearly meets the
assumptions of Corollary 1.9. Consequently, if the root-degree distribution
$d_{\phi}$ follows a power law, then the limiting root-PageRank associated
with any sequence of undirected random or deterministic graphs which converges
locally weakly to that unimodular branching process tree satisfies power-law
bounds with the same exponent and tail-function (see Theorem 2.8 below).

As a particular application, we consider the undirected configuration model.
The undirected configuration model $\mathrm{CM}_{n}(\boldsymbol{d})$ is a
model for a random graph of size $n$ which has a prescribed degree vector
$\boldsymbol{d}\in\mathbb{N}_{0}^{n}$ as parameter. Each vertex $i\in[n]$ is
assigned $d_{i}$ half-edges. Now, a random graph is sampled by choosing any
permutation
$\varphi\colon\\{1,2,\ldots,|\boldsymbol{d}|\\}\rightarrow\\{1,2,\ldots,|\boldsymbol{d}|\\}$
uniformly at random and afterwards connecting the $j$th half-edge to the
$\varphi(j)$th half -edge, where $j$ runs from $1$ to $|\boldsymbol{d}|$.

######  Condition 2.7 (Degree regularity condition).

Let $D_{n}=d_{\phi_{n}}$ denote the degree of a uniform vertex in $[n]$. We
impose the following two assumptions on the degree sequence:

  1. 1.

$D_{n}\stackrel{{\scriptstyle n\rightarrow\infty}}{{\longrightarrow}}D$ in
distribution;  and

  2. 2.

$\mathbb{E}[D_{n}]\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\longrightarrow}}\mathbb{E}[D]$.

For the directed configuration model, the power-law hypothesis is proven to
hold true [15], and the following theorem states that this is also the case
for the undirected configuration model $\mathrm{CM}_{n}(\boldsymbol{d})$
associated with the sequence $(\boldsymbol{d}_{n})_{n\in\mathbb{N}}$:

######  Theorem 2.8 (Power-law hypothesis for undirected configuration model).

Consider the undirected configuration model
$G_{n}=\mathrm{CM}_{n}(\boldsymbol{d}^{\scriptscriptstyle(G_{n})})$ where the
degree distribution satisfies Condition 2.7. Let $c\in[0,1]$ be a constant.
Then the PageRank vector $\boldsymbol{R}^{\scriptscriptstyle(G_{n})}$
satisfies that, for all $n,k$,

$\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)\leq\mathbb{P}(D_{n}>k),$
(33)

while further, for any $\beta>\frac{4\mathbb{E}[D]}{c(1-c)}$,

$\liminf_{k\rightarrow\infty}\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}{\mathbb{P}(D_{n}>\beta
k)}\geq 1.$ (34)

In particular, if the limiting degree distribution at the root $D$ has a
power-law distribution with any exponent $\tau>1$ and tail function
$\mathcal{L}$, then there is some $0<\underline{a}\leq 1$ such that the
limiting root-PageRank $R_{\phi}$ satisfies the power-law bounds

$\underline{a}\mathcal{L}(k)k^{-(\tau-1)}\leq\mathbb{P}(R_{\phi}>k)\leq\mathcal{L}(k)k^{-(\tau-1)}\quad\text{
for every }k\in(0,\infty).$ (35)

###### Proof.

The upper bound (33) follows directly from Theorem 1.1. By [21, Theorem 4.1],
the undirected configuration model $\mathrm{CM}_{n}(\boldsymbol{d}_{n})$
converges locally in probability, and hence locally weakly, to the unimodular
branching process tree. By Corollary 1.9 a), the limiting root-PageRank
satisfies

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}(D>\beta k)\quad\text{as
}k\rightarrow\infty.$ (36)

On the other hand, by Theorem 2.5 and the Portmanteau lemma (e.g. [23, Thm.
13.16 v]) applied to the respective open interval $(x,\infty)$, for every
$x\in(0,\infty)$,

$\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>x)}{\mathbb{P}(R_{\phi}>x)}\geq
1.$ (37)

Hence, combining (36) and (37) gives

$\begin{split}&\liminf_{k\rightarrow\infty}\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}{\mathbb{P}(D_{n}>\beta
k)}\cr&=\liminf_{k\rightarrow\infty}\left(\frac{\mathbb{P}(R_{\phi}>k)}{\mathbb{P}(D>\beta
k)}\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}{\mathbb{P}(R_{\phi}>k)}\frac{\mathbb{P}(D>\beta
k)}{\mathbb{P}(D_{n}>\beta k)}\right)\geq 1.\end{split}$

Here, convergence in distribution in combination with the fact that both
$D_{n}$ and $D$ are integer-valued guarantees that at any fixed $k$, the
fraction$\frac{\mathbb{P}(D>\beta k)}{\mathbb{P}(D_{n}>\beta k)}$ converges to
$1$ as $n$ tends to infinity. This proves (34). To prove the power-law bounds,
first write

$\frac{\mathbb{P}(D>k)}{\mathbb{P}(R_{\phi}>k)}=\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(D>k)}{\mathbb{P}(D_{n}>k)}\frac{\mathbb{P}(D_{n}>k)}{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}{\mathbb{P}(R_{\phi}>k)},$
(38)

and employ Theorem 1.1 and (37) to conclude the asymptotic upper bound

$\mathbb{P}(R_{\phi}>k)\leq\mathbb{P}(D>k)\qquad\text{ for any }k>0.$ (39)

Now assume that $D$ has a power-law distribution for some $\tau>1$ and some
function $\mathcal{L}$ that is slowly varying at infinity. Then by (36) and
(39) for every $s\in(0,1)$ there is some $K_{s}$ such that

$s\beta^{-(\tau-1)}\mathcal{L}(\beta
k)k^{-(\tau-1)}\leq\mathbb{P}(R_{\phi}>k)\leq\mathcal{L}(k)k^{-(\tau-1)}\quad\text{
for all }k\geq K_{s}.$ (40)

As $\mathcal{L}$ is slowly varying at infinity, for any $\varepsilon\in(0,1)$
we find a $\hat{K}_{\varepsilon}\in\mathbb{N}$ such that $\mathcal{L}(\beta
k)\geq(1-\varepsilon)\mathcal{L}(k)$ for all $k\geq\hat{K}_{\varepsilon}$.
Hence, with

$\underline{a}(\varepsilon,s):=s\beta^{-(\tau-1)}\min\\{\
\min\\{\mathcal{L}(\beta k)\colon
k\in\\{0,\ldots,\max\\{\hat{K}_{\varepsilon},K_{s}\\}\\},1-\varepsilon\
\\}\in(0,1)$ (41)

we obtain

$\underline{a}(s,\varepsilon)\mathcal{L}(k)k^{-(\tau-1)}\leq\mathbb{P}(R_{\phi}>k)\leq\mathcal{L}(k)k^{-(\tau-1)},$
(42)

and any choice of $s,\varepsilon\in(0,1)$ gives the desired power-law bounds
for $R_{\phi}$. ∎

###  2.4 Application to the Pólya point tree and the undirected preferential
attachment model

Let us denote by $\mathrm{PA}^{m,\delta}_{n}$ the version of the preferential
attachment model with parameters $m\in\mathbb{N}$ and $\delta>-1$ without
self-loops at time $n$, in which we start at time $n=2$ with two vertices with
labels $1$ and $2$ and $m$ edges between them and at any time step $n\to n+1$
we subsequently add $m$ edges without creating loops. This is done in $m$ sub-
steps where at any sub-step the attachment rule is updated according to the
new degree distribution. The update rule reads (see [21, (1.3.65)]): for the
$(j+1)$th edge of vertex $v_{n+1}$, attached at time-step $n+1$,

$\mathbb{P}(v_{j+1,n+1}^{(m)}\longrightarrow
v_{i}^{(m)}\mid\mathrm{PA}^{m,\delta}_{n})=\frac{D_{i}(n,j)+\delta}{2m(n-1)+j+\delta
n},$

where $D_{i}(n,j)$ is the degree of vertex $n$ after the $j$th edge of vertex
$v_{n+1}$ has been added. Note that in [21], this model is denoted by
$\mathrm{PA}^{m,\delta}(d)$ where the $d$ abbreviates version d within the
class of considered preferential attachment models; also see the erratum to
[21].

The preferential attachment model converges locally weakly to the Pólya point
tree ([13, Section 2.3.2]), a continuous-time branching process tree to which
our machinery applies as well. We stick to the notions employed in [21,
Chapter 5]. The Pólya point tree is a multi-type branching process, where
labels come from the type space $[0,1]\times\\{y,o\\}$. Here, the first
component refers to the age of a vertex (or date of its birth), where smaller
values mean that the vertex is older. The second component describes whether
the vertex is younger (y) or older (o) with respect to its parent. This
distinction is specific to the undirected model and corresponds to the fact
that in the preferential attachment model, a random vertex has edges to $m$
older neighbors and then starts gaining connections from younger vertices. As
a consequence, the offspring distribution of any vertex has a deterministic
component of a fixed number of older vertices and a random component
describing the number of younger vertices. In the directed version of the
Pólya point tree in [9, Definition 4.4], the directness of edges makes
labelling of vertices superfluous. Formally, the Pólya point tree is defined
recursively as follows:

  1. 1.

The root $\phi$ has age $U_{\phi}\sim\mathrm{Unif}([0,1])$ and no label;

  2. 2.

For the recursion step consider a vertex $w$ (in the Ulam-Harris
representation) with age $A_{w}$. Then the number $m_{-}$ of older vertices
(i.e., having label $o$) depends on the label of $w$ in that $m_{-}(w)=m-1$ if
$w$ has label $y$, while $m_{-}(w)=m$ if $w$ is the root or has label $o$. The
ages of the $m_{-}(w)$ older vertices $w1,\ldots,wm_{-}(w)$ are distributed
according to $A_{wj}=U_{wj}^{\chi}A_{w}<A_{w}$-a.s., where
$(U_{wj})_{j=1}^{m_{-}(w)}$ are i.i.d. Unif$([0,1])$ random variables
independently of everything else and $\chi=\frac{m+\delta}{2m+\delta}<1$.
The younger children of $\omega$ are described by their ages
$(A_{w(m_{-}(w)+j}))_{j\in\mathbb{N}}$, which are the ordered points of a Cox
process on $[A_{w},1]$ with intensity measure $\rho$ described by the
Lebesgue-density

$\rho(dx)=\frac{\Gamma_{w}}{\tau-1}\frac{x^{\frac{1}{\tau-1}-1}}{A_{w}^{\frac{1}{\tau-1}}}dx.$
(43)

Here, $\tau=3+\frac{\delta}{m}$ and

$\Gamma_{w}\sim\begin{cases}\Gamma(m+\delta+1,1)\quad&\text{if }w\text{ has
label }o;\\\ \Gamma(m+\delta,1)\quad&\text{else},\end{cases}$

where $\Gamma(r,\lambda)$ denotes a Gamma-distributed random variable having
density
$f(t)=\mathbbm{1}_{[0,\infty)}(t)\lambda^{r}t^{r-1}{\mathrm{e}}^{-\lambda
t}/\Gamma(r)$.

The Pólya point tree has degree with a power-law distribution (see [20, Eq.
(8.4.11)]), in that there exists a constant $c_{m,\delta}$ such that

$\mathbb{P}(d_{\phi}=k)=c_{m,\delta}k^{-\tau}(1+O(k^{-1})).$

In particular, with $\tilde{a}_{m,\delta}:=\frac{c_{m,\delta}}{\tau-1}$, this
translates into

$\tilde{a}_{m,\delta}k^{-(\tau-1)}(1+O(k^{-1}))\leq\mathbb{P}(d_{\phi}>k)\leq\tilde{a}_{m,\delta}k^{-(\tau-1)}(1+O(k^{-1})).$

######  Theorem 2.9 (Power-law hypothesis for undirected preferential
attachment models).

Consider the undirected preferential attachment model
$G_{n}=PA^{m,\delta}_{n}$, with $m\geq 1$ and $\delta>-m$. Let further
$c\in(0,1)$. Then the PageRank vector
$\boldsymbol{R}^{\scriptscriptstyle(G_{n})}$ with damping factor $c$ satisfies

$\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)\leq\mathbb{P}(d_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)\quad\text{
for all }n\in\mathbb{N}\text{ and all }k\in(0,\infty),$ (44)

while further, for any $\beta>2\lceil 2m+\delta\rceil/[c(1-c)]$,

$\liminf_{k\rightarrow\infty}\liminf_{n\rightarrow\infty}\frac{\mathbb{P}(R_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>k)}{\mathbb{P}(d_{\phi_{n}}^{\scriptscriptstyle(G_{n})}>\beta
k)}\geq 1.$ (45)

In particular, the limiting root-PageRank $R_{\phi}$ has power-law tails with
the same exponent $\tau=3+\delta/m$ as the degree of the root of the Pólya
point tree.

###### Proof of Theorem 2.9.

The general structure of the proof is the same as the one of the proof of
Theorem 2.8, with the main difference being that verifying the assumptions of
Corollary 1.9 for the asymptotic lower bound requires a more extensive
reasoning. So let us focus on this aspect at first.

The preferential attachment model with parameters $m,\delta$ converges locally
weakly to the Pólya point tree (see [13, Theorem 2.2] and [21, Theorem 5.8])
with the respective parameters. We want to verify the Assumption b) of
Corollary 1.9 with $\boldsymbol{N}_{\phi,k}$ being the set of younger children
of the root vertex, ignoring the deterministic number $m$ of older children.
It suffices to stochastically dominate the offspring distribution of the
younger children by an i.i.d. family of $\mathbb{N}$-valued random variables.
Let us first gather some important properties of the underlying Cox-process:

######  Lemma 2.10 (Degree structure of neighbors of the root in preferential
attachment models).

Let $k>m$ be an integer and $t\in(0,1)$. Further let
$\pi\colon\\{m+1,m+2,\ldots,k\\}\rightarrow\\{m+1,m+2,\ldots,k\\}$ be a
permutation chosen uniformly at random and independent of everything else.
Consider the Cox-process $\eta$ describing the birth-times of the younger
children of the root with intensity given by (43).

  1. a)

Conditionally on $U_{\phi}=t$ and $d_{\phi}=k$, the family
$(A_{\pi_{j}})_{j=m+1}^{k}$ of birth-times of the $k-m$ younger children of
the root is i.i.d. $\sim A^{(t)}_{\pi_{m+1}}$ described by the Lebesgue-
density

$f_{t,\tau}(x)=\mathbbm{1}_{[t,1]}(x)\frac{x^{\frac{1}{\tau-1}-1}}{(\tau-1)(1-t^{\frac{1}{\tau-1}})}.$
(46)

  2. b)

For every $t\in(0,1)$ the random variable $A^{(t)}_{\pi_{m+1}}$ is
stochastically bounded from below by the random variable $A^{(0)}_{\pi_{m+1}}$
described by the Lebesgue-density

$f_{0,\tau}(x)=\mathbbm{1}_{[0,1]}(x)\frac{x^{\frac{1}{\tau-1}-1}}{\tau-1}.$
(47)

###### Proof of Lemma 2.10.

Statement a) is a folklore property of Poisson- and Cox-processes, noting that
the random scalar factor $\Gamma_{\phi}$ in the intensity measure $\rho$ in
(43) does not exhibit any temporal dependence. In more detail, let
$\rho_{y,t}$ denote the intensity measure $\rho$ of the process $\eta$ in (43)
conditioned on $\Gamma_{\phi}=y$ and $U_{\phi}=t$, which is an inhomogeneous
Poisson process. By standard arguments (e.g. [24, Proposition 3.5]), this
Poisson process is distributed as a mixed binomial process on $[t,1]$ with
sampling distribution described by the density
$f_{t,\tau}(x)=\frac{\rho_{y,t}(dx)}{\rho_{y,t}([t,1])}$ and mixing
distribution $\mathrm{Poi}(\rho_{y,t}([t,1]))$. Hence, we have that
conditional on $U_{\phi}=t$, $d_{\phi}=k$ and $\Gamma_{\phi}=y$ the family
$(A_{\pi_{j}})_{j=m+1}^{k}$ is i.i.d. $\sim A^{(t)}_{\pi_{m+1}}$ with density
$f_{t,\tau}$, which does not depend on $y$. In particular, for any measurable
$g\colon\mathbb{R}^{k-m}\rightarrow\mathbb{R}$,

$\mathbb{E}\Big{[}g\left((A_{\pi_{j}})_{j=m+1}^{k}\right)\mid
d_{\phi}=k,U_{\phi},\Gamma_{\phi}\Big{]}=\mathbb{E}\Big{[}g\left((A_{\pi_{j}})_{j=m+1}^{k}\right)\mid
d_{\phi}=k,U_{\phi}\Big{]}\quad\text{a.s.},$

because by the factorization Lemma (e.g. [23, Corollary 1.97]) and the fact
that $f_{t,\tau}$ does not depend on $y$ the l.h.s. is already measurable
w.r.t.
$\sigma(\\{d_{\phi}=k\\},U_{\phi})\subseteq\sigma(\\{d_{\phi}=k\\},U_{\phi},\Gamma_{\phi})$.
This implies that, for all Borel-measurable $B_{m+1},\ldots,B_{k}$,

$\begin{split}\mathbb{P}\left(\bigcap_{j=m+1}^{k}\\{A_{\pi_{j}}\in
B_{j}\\}\mid
d_{\phi}=k,\,U_{\phi}\right)&=\mathbb{P}\left(\bigcap_{j=m+1}^{k}\\{A_{\pi_{j}}\in
B_{j}\\}\mid
d_{\phi}=k,\,U_{\phi},\,\Gamma_{\phi}\right)\cr=\prod_{j=m+1}^{k}\mathbb{P}\left(A_{\pi_{j}}\in
B_{j}\mid
d_{\phi}=k,\,U_{\phi},\,\Gamma_{\phi}\right)&=\prod_{j=m+1}^{k}\mathbb{P}\left(A_{\pi_{j}}\in
B_{j}\mid d_{\phi}=k,\,U_{\phi}\right)\quad\text{a.s.}\end{split}$ (48)

In particular, the family $(A_{\pi_{j}})_{j\in\\{m+1,m+2,\ldots,k\\}}$ is
independent conditional on $d_{\phi}=k$ and $U_{\phi}$.

To prove Statement b), we note that, for every $t\in(0,1)$ and all
$x\in\mathbb{R}$,

$\begin{split}\mathbb{P}(A^{(t)}_{\pi_{m+1}}\geq
x)&=\mathbbm{1}_{(-\infty,t)}(x)+\mathbbm{1}_{[t,1]}(x)\frac{1-x^{\frac{1}{\tau-1}}}{1-t^{\frac{1}{\tau-1}}}\cr&\geq\mathbbm{1}_{(-\infty,0)}(x)+\mathbbm{1}_{[0,1]}(x)(1-x^{\frac{1}{\tau-1}})=\mathbb{P}(A^{(0)}_{\pi_{m+1}}\geq
x).\end{split}$ (49)

Hence, $A^{(0)}_{\pi_{m+1}}\preceq A^{(t)}_{\pi_{m+1}}$. ∎

######  Lemma 2.11 (I.i.d. structure of younger neighbors in preferential
attachment models).

Conditional on $d_{\phi}=k$ and $U_{\phi}=t$, the degrees
$(d_{\pi_{j}})_{j\in\\{m+1,m+2,\ldots,k\\}}$ of the younger children of the
root are i.i.d., where we have for every $n\geq m$

$\mathbb{P}(d_{\pi_{m+1}}=n\mid
d_{\phi}=k,U_{\phi}=t)=\int_{t}^{1}\mathbb{P}(d_{\pi_{m+1}}=n\mid
A_{\pi_{m+1}}=x)\mathbb{P}^{A_{\pi_{m+1}}^{(t)}}(dx),$

independently of $k$. Here, $\mathbb{P}^{A_{\pi_{m+1}}^{(t)}}$ denotes the
distribution of $A_{\pi_{m+1}}$ conditional on $U_{\phi}=t$ and $d_{\phi}=k$.
Moreover, conditional on $d_{\phi}=k$ and $U_{\phi}=t,$ the degrees
$(d_{\pi_{j}})_{j\in\\{m+1,m+2,\ldots,k\\}}$ are stochastically bounded from
above by the i.i.d.-family $(\tilde{d}_{j})_{j\in\\{m+1,m+2,\ldots,k\\}}$
with, for every $n\geq m$,

$\begin{split}\mathbb{P}(\tilde{d}_{m+1}=n)&=\int_{0}^{1}\mathbb{P}(d_{\pi_{m+1}}=n\mid
A_{\pi_{m+1}}=x)\mathbb{P}^{A_{\pi_{m+1}}^{(0)}}(dx)\end{split}$ (50)

independently of $k$ and $t$. In particular, for every $n\geq m$,

$\mathbb{P}(\tilde{d}_{m+1}=n)=\frac{m+\delta}{(n+\delta)(n+\delta+1)}.$ (51)

###### Proof of Lemma 2.11.

We start by recalling two properties that directly follow from the definition
of the Pólya point tree:

  * $\rhd$

Conditionally on $d_{\phi}=k$ and $(A_{\pi_{j}})_{j=m+1}^{k}$, the random
variables $d_{\pi_{m+1}},d_{\pi_{m+2}},\ldots,d_{\pi_{k}}$ describe the total
number of points of independent Cox-processes and are thus independent random
variables.

  * $\rhd$

Further conditioning on $U_{\phi}$ does not add any information. More
precisely, for any measurable $g\colon\mathbb{R}^{k-m}\rightarrow\mathbb{R}$
the conditional expectation of $g((d_{\pi_{j}})_{j=m+1}^{k})$ given
$d_{\phi}=k$, $(A_{\pi_{j}})_{j=m+1}^{k}$ and additionally $U_{\phi}$ is
already measurable w.r.t. $d_{\phi}=k$ and $(A_{\pi_{j}})_{j=m+1}^{k}$.

By these two properties, we conclude that, for any integers
$n_{m+1},\ldots,n_{k}$,

$\begin{split}&\mathbb{P}(d_{\pi_{m+1}}=n_{m+1},\ldots,d_{\pi_{k}}=n_{k}\mid
d_{\phi}=k,U_{\phi}=t)\cr&=\int_{(0,1)^{k-m}}\mathbb{P}(d_{\pi_{m+1}}=n_{m+1},\ldots,d_{\pi_{k}}=n_{k}\mid(A_{\pi_{j}})_{j=m+1}^{k}=(x_{j})_{j=m+1}^{k},d_{\phi}=k,U_{\phi}=t)\cr&\qquad\qquad\times\mathbb{P}(A_{\pi_{m+1}}\in
dx_{m+1},\ldots,A_{\pi_{k}}\in dx_{k}\mid
d_{\phi}=k,U_{\phi}=t)\cr&=\int_{(0,1)^{k-m}}\mathbb{P}(d_{\pi_{m+1}}=n_{m+1},\ldots,d_{\pi_{k}}=n_{k}\mid(A_{\pi_{j}})_{j=m+1}^{k}=(x_{j})_{j=m+1}^{k},d_{\phi}=k)\cr&\qquad\qquad\times\mathbb{P}(A_{\pi_{m+1}}\in
dx_{m+1},\ldots,A_{\pi_{k}}\in dx_{k}\mid
d_{\phi}=k,U_{\phi}=t)\cr&=\int_{(0,1)^{k-m}}\prod_{j=m+1}^{k}\mathbb{P}(d_{\pi_{j}}=n_{j}\mid(A_{\pi_{j}})_{j=m+1}^{k}=(x_{j})_{j=m+1}^{k},d_{\phi}=k)\cr&\qquad\qquad\times\mathbb{P}(A_{\pi_{m+1}}\in
dx_{m+1},\ldots,A_{\pi_{k}}\in dx_{k}\mid
d_{\phi}=k,U_{\phi}=t).\cr\end{split}$ (52)

By construction of the Pólya point tree, the conditional distribution of each
random variable $d_{\pi_{j}}$ given $(A_{\pi_{l}})_{l\in\\{m+1,\ldots,k\\}}$
and $d_{\phi}=k$ is already measurable w.r.t. $A_{\pi_{j}}$. Hence, the last
expression of (52) equals

$\begin{split}&\int_{(0,1)^{k-m}}\prod_{j=m+1}^{k}\mathbb{P}(d_{\pi_{j}}=n_{j}\mid
A_{\pi_{j}}=x_{j})\mathbb{P}(A_{\pi_{m+1}}\in dx_{m+1},\ldots,A_{\pi_{k}}\in
dx_{k}\mid d_{\phi}=k,U_{\phi}=t).\cr\end{split}$ (53)

Now employ Lemma 2.10 to conclude that $A_{\pi_{m+1}},\ldots,A_{\pi_{k}}$ are
i.i.d. given $d_{\phi}=k,U_{\phi}=t$. By Fubini’s Theorem, (53) thus equals

$\begin{split}&\int_{(0,1)}\mathbb{P}(A_{\pi_{m+1}}\in dx_{m+1}\mid
d_{\phi}=k,U_{\phi}=t)\ldots\int_{(0,1)}\mathbb{P}(A_{\pi_{k}}\in dx_{k}\mid
d_{\phi}=k,U_{\phi}=t)\cr&\qquad\qquad\times\prod_{j=m+1}^{k}\mathbb{P}(d_{\pi_{j}}=n_{j}\mid
A_{\pi_{j}}=x_{j})\cr&=\prod_{j=m+1}^{k}\int_{(0,1)}\mathbb{P}(d_{\pi_{j}}=n_{j}\mid
A_{\pi_{j}}=x_{j})\mathbb{P}(A_{\pi_{j}}\in dx_{j}\mid
d_{\phi}=k,U_{\phi}=t).\end{split}$ (54)

This proves the conditional independence with, for every $n\geq m$,

$\begin{split}&\mathbb{P}(d_{\pi_{m+1}}=n\mid
d_{\phi}=k,U_{\phi}=t)=\int_{t}^{1}\mathbb{P}(d_{\pi_{m+1}}=n\mid
A_{\pi_{m+1}}=x)\mathbb{P}^{A_{\pi_{m+1}}^{(t)}}(dx).\end{split}$ (55)

Next, for the stochastic bound (50), we first note that by (43), for any
$0<\underline{x}\leq\bar{x}<1$, the intensity $\rho([A_{\pi_{m+1}},1])$
conditionally on $A_{\pi_{m+1}}=\bar{x}$ is stochastically bounded from above
by the intensity $\rho([A_{\pi_{m+1}},1])$ conditionally on
$A_{\pi_{m+1}}=\underline{x}$. Hence, also $d_{\pi_{m+1}}$ conditionally on
$A_{\pi_{m+1}}=\bar{x}$ is stochastically bounded from above by
$d_{\pi_{m+1}}$ conditionally on $A_{\pi_{m+1}}=\underline{x}$. This means
that, for every fixed $n\geq m$, the function
$g_{n}\colon(0,1)\rightarrow[0,1];\ x\mapsto\mathbb{P}(d_{\pi_{m+1}}<n\mid
A_{\pi_{m+1}}=x)$ is non-decreasing. Hence, from $A_{\pi_{m+1}}^{(0)}\preceq
A_{\pi_{m+1}}^{(t)}$ it follows
$\mathbb{E}[g_{n}(A_{\pi_{m+1}}^{(0)})]\leq\mathbb{E}[g_{n}(A_{\pi_{m+1}}^{(t)})]$
for every $t\in(0,1)$ (e.g., [30, Theorem 1.2.2] or [29, Equation 1.A.7]).
This implies that
$\mathbb{P}(\tilde{d}_{m+1}<n)\leq\mathbb{P}(d_{\pi_{m+1}}<n\mid
d_{\phi}=k,U_{\phi}=t)$ for all possible choices of $k,n$ and $t$ and thus
proves the proposed stochastic bound.

To calculate the probability mass function of $\tilde{d}_{m+1}$, we insert the
expression

$\mathbb{P}(d_{\pi_{m+1}}=n\mid
A_{\pi_{m+1}}=x)=\frac{\Gamma(n+\delta)}{(n-m)!\Gamma(m+\delta)}\left(1-x^{\frac{1}{\tau-1}}\right)^{n-m}x^{\frac{m+\delta}{\tau-1}}$

as given in [21, Equation 5.3.10] and the density
$f_{0,\tau}(x)=\frac{x^{2-\tau}}{\tau-1}$ into (50), which gives

$\mathbb{P}(\tilde{d}_{m+1}=n)=\frac{1}{\tau-1}\frac{\Gamma(n+\delta)}{(n-m)!\Gamma(m+\delta)}\int_{0}^{1}\left(1-x^{\frac{1}{\tau-1}}\right)^{n-m}x^{\frac{m+\delta+2-\tau}{\tau-1}}dx.$
(56)

Substituting $u=x^{\frac{1}{\tau-1}}$, i.e., $dx=(\tau-1)u^{\tau-2}$ in the
integral in (56) we arrive at

$\begin{split}\int_{0}^{1}\left(1-x^{\frac{1}{\tau-1}}\right)^{n-m}x^{(m+\delta+2-\tau)/(\tau-1)}dx&=(\tau-1)\int_{0}^{1}u^{m+\delta}(1-u)^{n-m}du\cr&=(\tau-1)\frac{\Gamma(m+\delta+1)\Gamma(n-m+1)}{\Gamma(n+\delta+2)},\end{split}$
(57)

which leads to

$\begin{split}\mathbb{P}(\tilde{d}_{m+1}=n)&=\frac{\Gamma(n+\delta)}{(n-m)!\Gamma(m+\delta)}\frac{\Gamma(m+\delta+1)\Gamma(n-m+1)}{\Gamma(n+\delta+2)}\cr&=\frac{\Gamma(n+\delta)\Gamma(m+\delta+1)}{\Gamma(m+\delta)\Gamma(n+\delta+2)}=\frac{m+\delta}{(n+\delta)(n+\delta+1)}.\end{split}$
(58)

∎

Continuation of the proof of Theorem 2.9. As its distribution does not
explicitly depend on the “internal” random variable $U_{\phi}$, the family
$(\tilde{d}_{j})_{j\in\\{m+1,m+2,\ldots,k\\}}$ is a suitable stochastic upper
bound in the sense of Corollary 1.9 b). In particular, we can condition on
$U_{\phi}$ in the second inequality of (21) and similarly to (25) employ total
expectation. For the scaling factor $\beta$ we need to calculate
$\min\\{t\in\mathbb{N}\mid\mathbb{P}(\tilde{d}_{1}\geq t)\leq 1/2\\}$. By
using a telescoping sum identity, we obtain

$\begin{split}\mathbb{P}(\tilde{d}_{m+1}\geq
t)&=(m+\delta)\sum_{n=t}^{\infty}\frac{1}{(n+\delta)(n+\delta+1)}=(m+\delta)\sum_{n=t}^{\infty}\left(\frac{1}{n+\delta}-\frac{1}{(n+\delta)+1}\right)\cr&=\frac{m+\delta}{t+\delta},\end{split}$
(59)

hence $\mathbb{P}(\tilde{d}_{m+1}\geq t)\leq 1/2$ is equivalent to
$t\geq\lceil 2m+\delta\rceil$. From Corollary 1.9 b) we thus obtain that for
every $\beta>2\lceil 2m+\delta\rceil$

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}(d_{\phi}>\beta k)\quad\text{ as
}k\rightarrow\infty.$

The remainder of the proof of Theorem 2.9 is a minor modification of that of
Theorem 2.8. ∎

##  3 A counterexample on the lower bound

Condition (15) in Proposition 1.8 can be violated once the dependencies
between the degrees of the neighbors of a vertex become too large, as we show
in this section. We show that, for any prescribed power-law distribution
$p=(p_{k})_{k\in\mathbb{N}}$, there exists a sequence
$(\tilde{G}_{n}^{(p)})_{n\geq n_{p}}$, $n_{p}\in\mathbb{N}$, of connected
graphs whose degree distribution converges to $p$, whereas the corresponding
PageRank at a uniformly chosen root converges to one in probability. This
implies that there is no general non-trivial asymptotic lower bound on the
PageRank vector.

Our construction follows a two-step procedure: First we construct disconnected
graphs $G_{n}$ described as the disjoint union of $o(n)$ many degree-regular
graphs of appropriate size depending on $(p_{k})_{k\in\mathbb{N}}$. The
corresponding PageRank-matrix $\boldsymbol{P}^{(\scriptscriptstyle G_{n})}$ is
doubly-stochastic, and therefore the PageRank vector of such graph has all
elements equal to 1. This step is explained in Section 3.1. Afterwards we
connect the formerly disjoint components by adding $o(n)$ edges. After showing
that our specific choice of $G_{n}$ converges locally weakly, we then employ
Theorem 2.5 and uniqueness of the local weak limit to conclude that the
PageRank associated with the so-obtained connected graphs converges in
probability to $1$. This step is explained in Section 3.2.

###  3.1 Disjoint unions of regular graphs

Let us start by formalizing the above ideas:

######  Definition 3.1 (Degree-regular circulant graph).

Let $2\leq k<n$ be integers such that $k$ is even. Then let $G_{k,n}$ denote
the $k$-regular graph with $n$ vertices which is constructed as follows (see
the graphs $G_{2,10}$, $G_{4,8}$ and $G_{6,7}$ in Figure 1 for an
illustration).

  * $\rhd$

The set of vertices is identified with the one-dimensional torus
$\mathbb{Z}_{n}=\mathbb{Z}/n\mathbb{Z}$.

  * $\rhd$

Every vertex $i\in\mathbb{Z}_{n}$ is connected by an edge to the vertices
$i\pm 1,i\pm 2,\ldots,i\pm k/2$.

The graph is circulant in that cyclic permutations of its vertices are graph-
automorphisms.

######  Definition 3.2 (Disjoint union of degree-regular graphs).

Let $n\geq 2$. Let $p=(p_{k})_{k\in\mathbb{N}}$ be any probability mass
function such that $p_{k}=0$ for all odd $k$, and set
$N_{k,n}:=N^{(p)}_{k,n}:=\lfloor np_{k}\rfloor.$ Let
$(M_{n})_{n\in\mathbb{N}}$ be sequence in $\mathbb{N}$ that diverges to
infinity slowly enough, so that it in particular satisfies that

$N_{k,n}\geq k+1\quad\text{for all }k\in[M_{n}].$ (60)

Let $n_{p}:=\min\\{n\in\mathbb{N}\colon M_{n}\geq 2\\}$. For every $n\geq
n_{p}$ let $G_{n}^{(p)}:=\coprod_{k\in[M_{n}]}G_{k,N_{k,n}}$ denote the graph
constructed as the non-empty disjoint union of the circulant graphs
$G_{2,N_{2,n}},\ldots,G_{M_{n},N_{M_{n},n}}$, where we note that
$\\#G_{n}^{(p)}=n(1+o(1))$ as $n\rightarrow\infty$.
Further, we obtain $\tilde{G}^{(p)}_{n}$ by connecting two formerly disjoint
$G_{k,N_{k,n}}$ whose degrees differ minimally, to turn $G_{n}^{(p)}$ into a
connected graph $\tilde{G}^{(p)}_{n}$. As each component of $G_{n}^{(p)}$ is
invariant under all cyclic permutations, the concrete choice of these
$M_{n}-1$ edges is irrelevant up to isomorphisms.

$G_{2,10}$$G_{4,8}$$G_{6,7}$ Figure 1: An illustration for Definitions 3.1 and
3.2: The graph $G_{n}$ with $n=25$ vertices corresponding to the vector
$(N_{2,25},N_{4,25},N_{6,25})=(10,8,7)$ consists of three disjoint regular
circulant graphs, which are constructed according to Definition 3.1, of sizes
$10,8$ and $7$ and respective degrees $2,4$ and $6$. To make the graph
connected, in the second step we add the two dashed edges to obtain the
connected graph $\tilde{G}_{25}$.

The sequence of disconnected graphs constructed in Definition 3.2 above has
the desired properties:

######  Proposition 3.3 (Degree and PageRank structure union of disconnected
graphs).

Let $p=(p_{k})_{k\in\mathbb{N}}$ be any probability mass function such that
$p_{k}=0$ for all odd $k$ and $X^{(p)}$ be distributed according to $p$. Then
for the graphs $(G_{n}^{(p)})_{n\geq n_{p}}$ described in Definition 3.2,

  1. (a)

$\lim_{n\rightarrow\infty}\mathbb{P}(d_{\phi_{n}}^{\scriptscriptstyle(G_{n}^{(p)})}=k)=p_{k}$.

  2. (b)

$R_{v}^{\scriptscriptstyle(G_{n}^{(p)})}=1$ for every $n\geq n_{p}$ and $v\in
V(G_{n}^{(p)})$.

###### Proof of Proposition 3.3.

Statement (a) follows directly from the construction of the graphs
$G^{(p)}_{n}$. Statement (b) is a consequence of the fact that the
corresponding PageRank-matrix $\boldsymbol{P}^{(\scriptscriptstyle
G_{n}^{(p)})}$ is doubly-stochastic. ∎

######  Remark 3.4.

We may replace the circulant regular graphs $G_{k,n}$ in Definition 3.2 by any
degree-regular graphs of the prescribed degree and size provided that the
sequence $(G_{n}^{(p)})_{n\in\mathbb{N}}$ converges in the local weak sense.
The concrete choice from Definition 3.1 above provides a specific illustrative
example for which the local weak convergence is easy to prove (see Proposition
3.5 below), at the price that only regular graphs of even degree occur.
$\blacktriangleleft$

###  3.2 Connecting the disjoint components

We next study the local weak limits of $G_{n}^{(p)}$ and
$\tilde{G}^{(p)}_{n}$:

######  Proposition 3.5 (Local limit of disjoint unions of circulant graphs,
and their connected versions).

Let $p=(p_{k})_{k\in\mathbb{N}}$ be any degree distribution such that
$p_{k}=0$ for all odd $k$. Then, $(G_{n}^{(p)})_{n\in\mathbb{N}}$ described in
Definition 3.2 converges locally weakly to a rooted graph
$(G_{\infty}^{(p)},\phi)$. In particular, also the sequence
$(\tilde{G}^{(p)}_{n})_{n\in\mathbb{N}}$ of connected graphs converges locally
weakly to the same limit $(G_{\infty}^{(p)},\infty)$.

###### Proof of Proposition 3.5.

By Remark 2.4 above, for fixed $k\in 2\mathbb{N}$, the sequence
$(G_{k,n})_{n\geq n_{p},M_{n}\geq k}$ converges locally weakly to the graph
$(G_{k,\infty},\phi)$ on $\mathbb{Z}$ with $\phi\equiv 0$, where two vertices
in $G_{k,\infty}$ are connected by an edge iff their distance is at most $k/2$
(see Figure 2 for the specific graph $G_{4,\infty}$). Hence, the sequence
$G_{n}^{(p)}$ converges locally weakly to the random rooted graph
$(G_{\infty}^{(p)},0)$ which equals $(G_{k,\infty},0)$ with probability
$\lim_{n\rightarrow\infty}N_{k,n}/n=p_{k}$.

As each component of $G_{n}^{(p)}$ is invariant under all cyclic permutations,
the concrete choice of these $M_{n}-1$ edges is irrelevant up to isomorphisms.
The operation of adding edges affects the degree of $o(n)$ vertices and thus,
by Remark 2.4, does not change the local weak limit.

0$\mathbb{Z}$$\cong$ Figure 2: Illustration of the proof of Proposition 3.5:
Any ball of radius $r<\lfloor n/2\rfloor$ in graph-distance (indicated by the
dotted rectangle) around any vertex in $G_{k,n}$ is isomorphic to the
respective ball around $0$ in $G_{k,\infty}$. On the other hand, for given
$r\geq 1$ we can choose $n\geq\lceil 2r\rceil$ so that each ball of radius $r$
in $G_{k,n}$ is isomorphic to the respective ball around $0$ in
$G_{k,\infty}$.

∎

From Propositions 3.3 and 3.5 we obtain the following theorem that produces a
counter example to the power-law hypothesis:

######  Theorem 3.6 (PageRank of connected unions of circulant graphs).

Let $p=(p_{k})_{k\in\mathbb{N}}$ be any probability mass function such that
$p_{k}=0$ for odd $k$. Then for the graphs $(\tilde{G}_{n}^{(p)})_{n\geq
n_{p}}$,

  1. (a)

$\lim_{n\rightarrow\infty}\mathbb{P}(d_{\phi_{n}}=k)=p_{k}$. In particular, if
$p$ is a power-law, then $d_{\phi_{n}}$ converges in distribution to a power-
law with the same tail-index.

  2. (b)

$\boldsymbol{R}^{\scriptscriptstyle(\tilde{G}_{n}^{(p)})}_{\phi_{n}}\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\longrightarrow}}1$ in probability.

###### Proof of Theorem 3.6.

As $M_{n}=o(n)$, Statement (a) follows readily from Statement a) of
Proposition 3.3. By Statement (b) of Proposition 3.3, we know that
$\boldsymbol{R}^{\scriptscriptstyle(G_{n}^{(p)}))}_{\phi_{n}}\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\longrightarrow}}1$ in probability and in distribution.
By Proposition 3.5, the sequence $(\tilde{G}_{n}^{(p)}))_{n\in\mathbb{N}}$ of
connected graphs converges locally weakly to the same random graph
$(G_{\infty},\phi)$ as the sequence $(G_{n}^{(p)}))_{n\in\mathbb{N}}$. Hence,
employing Theorem 2.5, we conclude that the sequences
$(\boldsymbol{R}^{\scriptscriptstyle(\tilde{G}_{n}^{(p)}))}_{\phi_{n}})$ and
$(\boldsymbol{R}^{\scriptscriptstyle(G_{n}^{(p)}))}_{\phi_{n}})$ have the same
limit $R^{\scriptscriptstyle(G_{\infty})}_{\phi}$ in distribution. As the
distributional limit of real-valued random variables is unique (e.g., [23,
Remark 13.13]) we conclude that
$\boldsymbol{R}^{\scriptscriptstyle(\tilde{G}_{n}^{(p)}))}_{\phi_{n}}\stackrel{{\scriptstyle
n\rightarrow\infty}}{{\rightarrow}}1$ in distribution. In particular,
convergence in distribution to a constant limit implies convergence in
probability (e.g., [19, Section 7.2 Thm. 4]), which finishes the proof. ∎

##  4 Discussion and open problems

In this section, we provide a discussion of our results and state some open
problems. We start in Section 4.1 by discussing extensions of our work to
directed graphs. In Section 4.2, we provide an intuitive explanation why the
power-law hypothesis holds true for undirected preferential attachment models,
while it fails for their directed versions. We close in Section 4.3 by giving
conclusions and open problems.

###  4.1 Extensions to directed setting

In this section, we investigate to what extent our results extend to the
directed setting. We discuss both a setting in which the PageRank can be upper
bounded by the in-degree, as well as an extension of our counter example. We
start by recalling how the PageRank vector is defined in the directed setting.

For a directed graph $G_{n}=(V_{n},\vec{E_{n}})$ with $\\#V_{n}=n$, in-degree
vector $\boldsymbol{d}^{-}=(d_{i}^{-})_{i\in V_{n}}$, and out-degree vector
$\boldsymbol{d}^{+}=(d_{i}^{+})_{i\in V_{n}},$ the directed analogue of (1) is
defined as

$p^{\scriptscriptstyle(G_{n})}_{ij}:=\frac{a_{ij}^{\scriptscriptstyle(G_{n})}}{d_{i}^{+}},$
(61)

and the graph-normalized PageRank equation reads

$\boldsymbol{R}^{\scriptscriptstyle(G_{n})}=c\,\boldsymbol{R}^{\scriptscriptstyle(G_{n})}\boldsymbol{P}^{\scriptscriptstyle(G_{n})}+(1-c)\boldsymbol{1}_{n},\quad\boldsymbol{R}^{\scriptscriptstyle(G_{n})}\in[0,n]^{n}.$
(62)

####  4.1.1 Upper bound in directed setting with bounded ratio of in- and out-
degrees

The simple proof of Theorem 1.1 is based on employing the symmetry of the
adjacency matrix, which is a stronger assumption than requiring the in- and
out-degree vector to coincide. However, to extend the scope of Theorem 1.1
similar to (8) and omitting the $G_{n}$-dependency in notation, we can write

$\begin{split}\frac{R_{i}}{d_{i}^{-}}&=c\sum_{j\in[n]}\frac{a_{ji}}{d_{i}^{-}d_{j}^{+}}R_{j}+\frac{1-c}{d_{i}^{-}}=c\sum_{j\in[n]}\frac{d_{j}^{-}}{d_{j}^{+}}\frac{a_{ji}}{d_{i}^{-}}\frac{R_{j}}{d_{j}^{-}}+\frac{1-c}{d_{i}^{-}}\cr&=c\sum_{j\in[n]}\frac{d_{j}^{-}}{d_{j}^{+}}p^{\text{rev}}_{ji}\frac{R_{j}^{-}}{d_{j}}+\frac{1-c}{d_{i}^{-}},\end{split}$
(63)

where

$p^{\text{rev}}_{ij}:=\frac{a_{ji}}{d_{i}^{-}}$ (64)

defines a stochastic matrix $\boldsymbol{P}^{\text{rev}}.$ Now assume that
there is exists a $K<\infty$ such that

$\max_{i\in[n]}\frac{d_{i}^{-}}{d_{i}^{+}}\leq K.$ (65)

Then defining $\boldsymbol{v}^{\text{dir}}$ by
$v_{i}^{\text{dir}}:=R_{i}/d_{i}^{-}$ for $i\in[n]$, we obtain from (63)

$\boldsymbol{v}\leq
c\,K\boldsymbol{P}^{\text{rev}}\boldsymbol{v}+(1-c)\boldsymbol{Q}\boldsymbol{1}_{n}.$
(66)

In case that $\|cK\boldsymbol{P}^{\text{rev}}\|<1$, which is certainly
satisfied when $c<1/K$, we can invert the operator
$\mathbbm{I}_{n}-cK\boldsymbol{P}$, to obtain

$(1-c)(\mathbbm{I}_{n}-c\boldsymbol{P}^{\text{rev}})^{-1}\boldsymbol{Q}\boldsymbol{1}_{n}\leq\boldsymbol{v}\leq(1-c)(\mathbbm{I}_{n}-cK\boldsymbol{P}^{\text{rev}})^{-1}\boldsymbol{Q}\boldsymbol{1}_{n},$
(67)

which is a generalization of (10). Now, for the upper bound in (67), we
proceed as in the remainder of the proof of Theorem 1.1 to obtain the
following result:

######  Theorem 4.1 (Upper bound on PageRank for bounded ratio of in- and out-
degrees).

Let $G_{n}=(V_{n},\vec{E}_{n})$ be any any directed graph with $\\#V_{n}=n$
such that $m_{n}:=\min_{i\in V_{n}}d_{i}^{-}\geq 1$ and $K_{n}:=\max_{i\in
V_{n}}\frac{d_{i}^{-}}{d_{i}^{+}}<\frac{m_{n}}{c}$. Then

$R_{i}^{\scriptscriptstyle(G_{n})}\leq\frac{K_{n}}{m_{n}}d_{i}^{-}\quad\text{for
all }i\in V_{n}.$ (68)

A special case of Theorem 4.1 arises for directed Eulerian graphs, in which
$d_{i}^{+}=d_{i}^{-}\geq 1$ for all $i\in V_{n}$, and for which
$K_{n}=m_{n}=1.$ On the other hand, the directed version of the preferential
attachment model clearly fails the assumption of a bounded ratio of out- and
in-degrees, which aligns with the known result that the limiting root-PageRank
for that model has heavier tails than the in-degree of the root ([9, Theorem
3.1]).

######  Remark 4.2 (Interpretation of $\boldsymbol{P}^{\mathrm{rev}}$).

In view of the random surfer interpretation (see [14, Section 2.1.2]) of the
PageRank vector as the stationary distribution of a random walker who at each
step with probability $c$ chooses one of the outgoing edges uniformly at
random and with probability $1-c$ jumps to a vertex chosen uniformly at random
from the entire vertex set $V_{n}$, the matrix $\boldsymbol{P}^{\mathrm{rev}}$
describes the reversed random walk, in which the random walker follows edges
in the opposite direction. Such random walk, too, was employed for
characterizing other vertex centrality measures, e.g. CheiRank centrality
[31]. $\blacktriangleleft$

####  4.1.2 Lower bound in directed setting

[18, Theorem 2.1] relates local weak convergence of graph sequences to
convergence in distribution of the associated root-PageRank. This theorem
covers the case of directed graphs as well, with a specific form of local
convergence (where we consider the in-components and keep the out-degrees of
vertices as vertex marks). Taking that into account, an inspection of the
proof of Proposition 1.8 immediately leads to the following generalization,
where we now introduce

$d_{\phi}^{\scriptscriptstyle(-,\geq\alpha)}=\\#\\{j\mid
j\rightarrow\phi\text{ and }d^{+}_{j}\geq\alpha\\}.$

######  Proposition 4.3 (Lower bound on PageRank for directed graphs).

Let $G=(V,\vec{E},\phi)$ be an infinite rooted directed random graph with in-
degree vector $\boldsymbol{d}^{-}$ and out-degree vector $\boldsymbol{d}^{+}$
which arises as the local weak limit of a sequence $(G_{n})_{n\in\mathbb{N}}$
of directed graphs. Let further $R_{\phi}$ denote the limiting (in
distribution) root-PageRank. Assume that there are $\alpha>0$ and
$\varepsilon>0$ such that, as $k\rightarrow\infty,$

$\mathbb{P}\left(d^{-}_{\phi}>k,d_{\phi}^{\scriptscriptstyle(-,\geq\alpha)}\geq(1-\varepsilon)d^{-}_{\phi}\right)=o(\mathbb{P}(d^{-}_{\phi}>k)).$
(69)

Then,

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}\Big{(}d^{-}_{\phi}>\frac{\alpha}{\varepsilon
c(1-c)}k\Big{)}\quad\text{as }k\rightarrow\infty.$ (70)

Also Corollary 1.9 can be obviously generalized to the directed setting, but
we refrain from doing so.

As a particular application of Proposition 4.3, we directly obtain the bound

$\mathbb{P}(R_{\phi}>k)\geq(1+o(1))\mathbb{P}(d_{\phi}^{-}>\beta
k)\quad\text{as }k\rightarrow\infty$

for the limiting root-PageRank of the directed version of the preferential
attachment model, for any $\beta>1/[c(1-c)]$. To see this, note that in the
directed version of the Pólya point tree ([9, Definition 4.4]), each vertex
has out-degree $1$, so (69) is fulfilled for any choices of $\alpha>1$ and
$0<\varepsilon<1$. However, this lower bound is not sharp, as the tails of the
limiting root-PageRank are actually heavier than those of the in-degree ([9,
Theorem 3.1])

###  4.2 Intuition for the difference in directed and undirected preferential
attachment models

It is surprising that the tail of the PageRank is drastically different in the
directed and undirected preferential attachment models. Indeed, in the
directed model, PageRank has a heavier tail than the degrees [9]. Furthermore,
the authors in [5] prove that this result persists in multi-type preferential
attachment networks and even in multi-type uniform attachment networks. In the
latter case, surprisingly, the degree-distribution of the vertices of each
type is geometric, while PageRank, for all types, has a power law distribution
with the same exponent for each type of vertices [5, Theorem 5.3(b)]. At the
same time, our Theorem 1.1 states that in any undirected graph, PageRank
cannot have a heavier tail than the degree. An intuitive explanation of this
drastic difference between directed and undirected graphs stems from the fact
that PageRank of a vertex is proportional to the sum of the probabilities of
all paths leading to this vertex [8]; consequently, the limiting distribution
of PageRank is defined by the sum of the probabilities of all paths leading to
the root vertex in the local weak limit. Such path-counting arguments have
been successfully applied also, e.g., to the personalized PageRank with
restarts on undirected graphs [6]. In the directed preferential attachment
model, the local weak limit is a directed tree, and the sum of the
probabilities of all (directed) paths to the root equals the discounted tree
size. Specifically, the size of the generation at distance $l$ from the root,
is discounted by the factor $(c/m)^{l}$ with $m$ being the constant and
deterministic out-degree. Furthermore, this tree is a realization of a
continuous-time branching process, stopped at a random time (more precisely,
this random time has an exponential distribution with parameter equal to the
growth rate of the process, i.e., the so-called Malthusian parameter). Up to
that random time, the degree of the root grows exponentially in time, but the
discounted tree size grows exponentially as well, at a faster rate. These
growth rates enter the power-law exponent making the tail of PageRank heavier
than that of the degree.

In contrast, in the undirected preferential attachment model, a step on the
path through vertex $v$ is discounted by the factor $c/d_{v}$. Our analysis
shows that this difference is crucial: it makes PageRank of the root grow at
most as fast as its degree. Note also that in the undirected model, the sum of
the probabilities of all paths to the root is not the same as the discounted
tree size because edges can be traversed both ways. This makes the path
counting in the undirected case more difficult, but this is not the feature
that affects the power law exponent of PageRank because each extra step is
penalized by the factor $c$.

Altogether, we believe that the differences between the directed and
undirected models are educational, and their better understanding will lead to
new results in the future.

###  4.3 Conclusion and outlook

The upper bound for PageRank stated in Theorem 1.1 holds true for every finite
undirected graph. It also extends to the case of directed graphs with a
bounded ratio of degrees. On the contrary, the counter-example presented in
Theorem 3.6 shows that a similar lower bound fails when the degrees of
vertices are equal to those of their neighbors (i.e., maximal degree-degree
correlations). Proposition 1.8 provides a sufficient assumption for an
asymptotic lower bound, which is particularly easy to check for sequences of
graphs which converge to (branching-process) trees in the local weak sense.
Combining Theorem 1.1 and Proposition 1.8, we obtain a statement on the
asymptotic behavior of PageRank which holds under assumptions that are
reasonably simple to check in applications, which is one of the strengths of
the result.

Compared to the related work in e.g., [22, 15, 27], the proofs in the present
paper are not based on studying a stochastic fixed-point equation on a
suitable (marked) branching-process tree, but instead rely on applying the
recent result of [18] on convergence in distribution for the root-PageRank
associated with locally weakly converging sequences of graphs. This
simplification, however, comes at the expense of a somewhat weaker result, in
that we cannot identify the asymptotic constant $a$ such that
$\mathbb{P}(R_{\phi}>k)=a\mathbb{P}(d_{\phi}>k)(1+o(1))$ as
$k\rightarrow\infty.$ It would be of interest to identify such a constant in
general like it is the case, e.g., for the directed configuration model ([15,
Theorems 6.4 & 6.6]).

It remains an open question whether the sufficient Condition (15) in
Proposition 1.8 for the respective asymptotic lower bound actually is an if
and only if condition. Moreover, we believe Condition (15) to hold much more
generally than for the tree-scenarios considered in the applications, with the
counterexample presented in Theorem 3.6 being a rather artificial exception.
It would hence be of interest to further examine the scope of our main result.

##### Acknowledgements.

The work of RvdH and NL is supported in part by the Netherlands Organisation
for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

## References

  * [1] Lada A. Adamic and Bernardo A. Huberman  “Power-Law Distribution of the World Wide Web”  In _Science_ 287.5461, 2000, pp. 2115–2115  DOI: 10.1126/science.287.5461.2115a
  * [2] D. Aldous and J.M. Steele  “The objective method: probabilistic combinatorial optimization and local weak convergence”  In _Probability on discrete structures_ 110, Encyclopaedia Math. Sci.  Springer, 2004, pp. 1–72  DOI: 10.1007/978-3-662-09444-0˙1
  * [3] David Aldous and Russell Lyons  “Processes on unimodular random networks”  In _Electron. J. Probab._ 12, 2007, pp. no. 541454–1508  DOI: 10.1214/EJP.v12-463
  * [4] Hans Wilhelm Alt  “Linear functional analysis” An application-oriented introduction, Universitext  Springer-Verlag London, Ltd., London, 2016, pp. xii+435  DOI: 10.1007/978-1-4471-7280-2
  * [5] Nelson Antunes, Sayan Banerjee, Shankar Bhamidi and Vladas Pipiras  “Attribute network models, stochastic approximation, and network sampling and ranking algorithms”  In _Preprint_ , 2023  arXiv:2304.08565
  * [6] Konstantin Avrachenkov, Remco Hofstad and Marina Sokol  “Personalized PageRank with node-dependent restart”  In _Mosc. J. Comb. Number Theory_ 4.4, 2014, pp. 5–20
  * [7] Konstantin Avrachenkov, Arun Kadavankandy, Liudmila Ostroumova Prokhorenkova and Andrei Raigorodskii  “PageRank in undirected random graphs”  In _Algorithms and models for the web graph_ 9479, Lecture Notes in Comput. Sci.  Springer, Cham, 2015, pp. 151–163  DOI: 10.1007/978-3-319-26784-5˙12
  * [8] Konstantin Avrachenkov and Nelly Litvak  “The effect of new links on Google PageRank”  In _Stoch. Models_ 22.2, 2006, pp. 319–331  DOI: 10.1080/15326340600649052
  * [9] Sayan Banerjee and Mariana Olvera-Cravioto  “PageRank asymptotics on directed preferential attachment networks”  In _Ann. Appl. Probab._ 32.4, 2022, pp. 3060–3084  DOI: 10.1214/21-aap1757
  * [10] Albert-László Barabási and Réka Albert  “Emergence of Scaling in Random Networks”  In _Science_ 286.5439, 1999, pp. 509–512  DOI: 10.1126/science.286.5439.509
  * [11] Albert-László Barabási, Réka Albert and Hawoong Jeong  “Scale-free characteristics of random networks: the topology of the world-wide web”  In _Physica A: Statistical Mechanics and its Applications_ 281.1, 2000, pp. 69–77  DOI: 10/dcxxgr
  * [12] Itai Benjamini and Oded Schramm  “Recurrence of distributional limits of finite planar graphs”  In _Electron. J. Probab._ 6, 2001, pp. no. 2313  DOI: 10.1214/EJP.v6-96
  * [13] Noam Berger, Christian Borgs, Jennifer T. Chayes and Amin Saberi  “Asymptotic behavior and distributional limits of preferential attachment graphs”  In _Ann. Probab._ 42.1, 2014, pp. 1–40  DOI: 10.1214/12-AOP755
  * [14] Sergey Brin and Lawrence Page  “The anatomy of a large-scale hypertextual Web search engine” Proceedings of the Seventh International World Wide Web Conference  In _Computer Networks and ISDN Systems_ 30.1, 1998, pp. 107–117  DOI: 10/dgjh27
  * [15] Ningyuan Chen, Nelly Litvak and Mariana Olvera-Cravioto  “Generalized PageRank on directed configuration networks”  In _Random Structures Algorithms_ 51.2, 2017, pp. 237–274  DOI: 10.1002/rsa.20700
  * [16] Amir Dembo and Ofer Zeitouni  “Large deviations techniques and applications” Corrected reprint of the second (1998) edition 38, Stochastic Modelling and Applied Probability  Springer-Verlag, Berlin, 2010, pp. xvi+396  DOI: 10/bcszkm
  * [17] Santo Fortunato, Marián Boguñá, Alessandro Flammini and Filippo Menczer  “Approximating PageRank from In-Degree”  In _Algorithms and Models for the Web-Graph_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 59–71  DOI: 10.1007/978-3-540-78808-9˙6
  * [18] Alessandro Garavaglia, Remco Hofstad and Nelly Litvak  “Local weak convergence for PageRank”  In _Ann. Appl. Probab._ 30.1, 2020, pp. 40–79  DOI: 10.1214/19-AAP1494
  * [19] Geoffrey R Grimmett and David R Stirzaker  “Probability and Random Processes”  Oxford University Press, 2001  DOI: 10.1093/oso/9780198572237.001.0001
  * [20] Remco Hofstad  “Random Graphs and Complex Networks. Vol. 1” [43], Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, Cambridge, 2017, pp. xvi+321  DOI: 10.1017/9781316779422
  * [21] Remco Hofstad  “Random Graphs and Complex Networks. Vol. 2”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2024  DOI: 10.1017/9781316795552
  * [22] Predrag R. Jelenković and Mariana Olvera-Cravioto  “Information ranking and power laws on trees”  In _Adv. in Appl. Probab._ 42.4, 2010, pp. 1057–1093  DOI: 10/dbwcrb
  * [23] Achim Klenke  “Probability theory”, Universitext  Springer, London, 2020, pp. xiv+716  DOI: 10.1007/978-3-030-56402-5
  * [24] Günter Last and Mathew Penrose  “Lectures on the Poisson process” 7, Institute of Mathematical Statistics Textbooks  Cambridge University Press, Cambridge, 2017, pp. xx+293  DOI: 10.1017/9781316104477
  * [25] Steve Lawrence and C. Giles  “Searching the World Wide Web”  In _Science_ 280.5360 American Association for the Advancement of Science, 1998, pp. 98–100  DOI: 10.1126/science.280.5360.98
  * [26] Mark Newman  “Networks”  Oxford University Press, Oxford, 2018, pp. xi+780  DOI: 10.1093/oso/9780198805090.001.0001
  * [27] Mariana Olvera-Cravioto  “PageRank’s behavior under degree correlations”  In _Ann. Appl. Probab._ 31.3, 2021, pp. 1403–1442  DOI: 10.1214/20-aap1623
  * [28] Gopal Pandurangan, Prabhakar Raghavan and Eli Upfal  “Using PageRank to characterize web structure”  In _Internet Math._ 3.1, 2006, pp. 1–20
  * [29] Moshe Shaked and J. Shanthikumar  “Stochastic orders”, Springer Series in Statistics  Springer, New York, 2007, pp. xvi+473  DOI: 10/b2vmrd
  * [30] Dietrich Stoyan  “Comparison methods for queues and other stochastic models”, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics  John Wiley & Sons, Ltd., Chichester, 1983, pp. xiii+217
  * [31] Alexander O Zhirov, Oleg V Zhirov and Dima L Shepelyansky  “Two-dimensional ranking of Wikipedia articles”  In _The European Physical Journal B_ 77 Springer, 2010, pp. 523–531  DOI: 10.1140/epjb/e2010-10500-7


* [235] Z. Zhu, S. Peng, V. Larsson, W. Xu, H. Bao, Z. Cui, M. R. Oswald, and M. Pollefeys, “Nice-slam: Neural implicit scalable encoding for slam,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * [236] A. Rosinol, J. J. Leonard, and L. Carlone, “Nerf-slam: Real-time dense monocular slam with neural radiance fields,” _arXiv preprint arXiv:2210.13641_ , 2022.
  * [237] A. Rosinol, A. Violette, M. Abate, N. Hughes, Y. Chang, J. Shi, A. Gupta, and L. Carlone, “Kimera: from slam to spatial perception with 3d dynamic scene graphs,” 2021.
  * [238] J. Wald, H. Dhamo, N. Navab, and F. Tombari, “Learning 3d semantic scene graphs from 3d indoor reconstructions,” _CoRR_ , vol. abs/2004.03967, 2020\. [Online]. Available: https://arxiv.org/abs/2004.03967
  * [239] S.-C. Wu, J. Wald, K. Tateno, N. Navab, and F. Tombari, “SceneGraphFusion: Incremental 3d scene graph prediction from RGB-d sequences,” in _2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE, jun 2021.
  * [240] A. Rosinol, A. Gupta, M. Abate, J. Shi, and L. Carlone, “3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans,” in _Robotics: Science and Systems XVI_. Robotics: Science and Systems Foundation, jul 2020.
  * [241] Z. Ravichandran, L. Peng, N. Hughes, J. D. Griffith, and L. Carlone, “Hierarchical representations and explicit memory: Learning effective navigation policies on 3d scene graphs using graph neural networks,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, may 2022.
  * [242] C. Agia, K. Jatavallabhula, M. Khodeir, O. Miksik, V. Vineet, M. Mukadam, L. Paull, and F. Shkurti, “Taskography: Evaluating robot task planning over large 3d scene graphs,” in _Conference on Robot Learning_. PMLR, 2022, pp. 46–58.
  * [243] S. Looper, J. Rodriguez-Puigvert, R. Siegwart, C. Cadena, and L. Schmid, “3d vsg: Long-term semantic scene change prediction through 3d variable scene graphs,” 2022.
  * [244] M. Castillo-Lopez, P. Ludivig, S. A. Sajadi-Alamdari, J. L. Sánchez-López, M. A. Olivares-Méndez, and H. Voos, “A real-time approach for chance-constrained motion planning with dynamic obstacles,” _CoRR_ , vol. abs/2001.08012, 2020. [Online]. Available: https://arxiv.org/abs/2001.08012
  * [245] V. Lefkopoulos, M. Menner, A. Domahidi, and M. N. Zeilinger, “Interaction-aware motion prediction for autonomous driving: A multiple model kalman filtering scheme,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 1, pp. 80–87, 2021.
  * [246] J. Fang, F. Wang, P. Shen, Z. Zheng, J. Xue, and T.-s. Chua, “Behavioral intention prediction in driving scenes: A survey,” _arXiv preprint arXiv:2211.00385_ , 2022.
  * [247] A. Rasouli and J. K. Tsotsos, “Autonomous vehicles that interact with pedestrians: A survey of theory and practice,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 3, pp. 900–918, mar 2020.
  * [248] J. Guo, U. Kurup, and M. Shah, “Is it safe to drive? an overview of factors, metrics, and datasets for driveability assessment in autonomous driving,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 8, pp. 3135–3151, aug 2020.
  * [249] W. Wang, L. Wang, C. Zhang, C. Liu, and L. Sun, “Social interactions for autonomous driving: A review and perspectives,” _Foundations and Trends® in Robotics_ , vol. 10, no. 3-4, pp. 198–376, 2022.
  * [250] J.-Y. Kwak, B. C. Ko, and J.-Y. Nam, “Pedestrian intention prediction based on dynamic fuzzy automata for vehicle driving at nighttime,” _Infrared Physics & Technology_, vol. 81, pp. 41–51, mar 2017.
  * [251] Y. Xing, C. Lv, H. Wang, H. Wang, Y. Ai, D. Cao, E. Velenis, and F.-Y. Wang, “Driver lane change intention inference for intelligent vehicles: Framework, survey, and challenges,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 5, pp. 4377–4390, may 2019.
  * [252] Z. Fang and A. M. Lopez, “Intention recognition of pedestrians and cyclists by 2d pose estimation,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 11, pp. 4773–4783, nov 2020.
  * [253] R. Izquierdo, A. Quintanar, I. Parra, D. Fernandez-Llorca, and M. A. Sotelo, “Experimental validation of lane-change intention prediction methodologies based on CNN and LSTM,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, oct 2019.
  * [254] A. Rasouli, T. Yau, M. Rohani, and J. Luo, “Multi-modal hybrid architecture for pedestrian action prediction,” in _2022 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, jun 2022.
  * [255] P. R. G. Cadena, Y. Qian, C. Wang, and M. Yang, “Pedestrian graph +: A fast pedestrian crossing prediction model based on graph convolutional networks,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 11, pp. 21 050–21 061, nov 2022.
  * [256] L. Achaji, J. Moreau, T. Fouqueray, F. Aioun, and F. Charpillet, “Is attention to bounding boxes all you need for pedestrian action prediction?” in _2022 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, jun 2022.
  * [257] C. Li, S. H. Chan, and Y.-T. Chen, “Who make drivers stop? towards driver-centric risk assessment: Risk object identification via causal inference,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, oct 2020.
  * [258] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “Carla: An open urban driving simulator,” in _Conference on robot learning_. PMLR, 2017, pp. 1–16.
  * [259] K. Zhou, Z. Liu, Y. Qiao, T. Xiang, and C. C. Loy, “Domain generalization: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pp. 1–20, 2022.
  * [260] A. Rudenko, L. Palmieri, M. Herman, K. M. Kitani, D. M. Gavrila, and K. O. Arras, “Human motion trajectory prediction: A survey,” _The International Journal of Robotics Research_ , vol. 39, no. 8, pp. 895–935, July 2020.
  * [261] Y. Huang, J. Du, Z. Yang, Z. Zhou, L. Zhang, and H. Chen, “A Survey on Trajectory-Prediction Methods for Autonomous Driving,” _IEEE Transactions on Intelligent Vehicles_ , vol. 7, no. 3, pp. 652–674, Sept. 2022\.
  * [262] S. Mozaffari, O. Y. Al-Jarrah, M. Dianati, P. Jennings, and A. Mouzakitis, “Deep Learning-Based Vehicle Behavior Prediction for Autonomous Driving Applications: A Review,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 1, pp. 33–47, Jan. 2022.
  * [263] D. Ridel, E. Rehder, M. Lauer, C. Stiller, and D. Wolf, “A Literature Review on the Prediction of Pedestrian Behavior in Urban Scenarios,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , Nov. 2018, pp. 3105–3112.
  * [264] X. Chang, P. Ren, P. Xu, Z. Li, X. Chen, and A. Hauptmann, “A comprehensive survey of scene graphs: Generation and application,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 1, pp. 1–26, jan 2023.
  * [265] C. Huang, O. Mees, A. Zeng, and W. Burgard, “Audio Visual Language Maps for Robot Navigation,” Mar. 2023.
  * [266] K. M. Jatavallabhula, A. Kuwajerwala, Q. Gu, M. Omama, T. Chen, S. Li, G. Iyer, S. Saryazdi, N. Keetha, A. Tewari, J. B. Tenenbaum, C. M. de Melo, M. Krishna, L. Paull, F. Shkurti, and A. Torralba, “ConceptFusion: Open-set Multimodal 3D Mapping,” Feb. 2023.
  * [267] M. A. Cornejo-Lupa, Y. Cardinale, R. Ticona-Herrera, D. Barrios-Aranibar, M. Andrade, and J. Diaz-Amado, “OntoSLAM: An Ontology for Representing Location and Simultaneous Mapping Information for Autonomous Robots,” _Robotics_ , vol. 10, no. 4, p. 125, Dec. 2021.
  * [268] H. Bavle, J. L. Sanchez-Lopez, M. Shaheer, J. Civera, and H. Voos, “Situational graphs for robot navigation in structured indoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9107–9114, 2022.
  * [269] ——, “S-graphs+: Real-time localization and mapping leveraging hierarchical representations,” 2023.

  *[SA]: Situational Awareness
  *[SLAM]: Simultaneous Localization and Mapping
  *[AI]: Artificial Intelligence
  *[DL]: Deep Learning
  *[S-Graph]: Situational Graph
  *[GNSS]: Global Navigation Satellite Systems
  *[GPS]: Global Positioning System
  *[IMUs]: Inertial Measurement Unit
  *[IMU]: Inertial Measurement Unit
  *[RTK]: Real-Time Kinematic
  *[DVS]: Dynamic Vision Sensor
  *[DAVIS]: Dynamic and Active-pixel Vision Sensor
  *[ATIS]: Asynchronous Time-based Image Sensor
  *[LIDARs]: Light Detection and Ranging
  *[LIDAR]: Light Detection and Ranging
  *[RF]: Radio Frequency
  *[SIFT]: Scale-Invariant Feature Transform
  *[SURF]: Speeded-Up Robust Features
  *[HOG]: Histogram of Oriented Gradients
  *[SVM]: Support Vector Machines
  *[CNNs]: Convolutional Neural Network
  *[CNN]: Convolutional Neural Network
  *[SVMs]: Support Vector Machines
  *[NN]: Neural Network
  *[RoI]: Region of Interest
  *[EKF]: Extended Kalman Filter
  *[UKF]: Unscented Kalman Filter
  *[MCL]: Monte Carlo Localization
  *[MHE]: Moving Horizon Estimation
  *[VO]: Visual Odometry
  *[EKFs]: Extended Kalman Filter
  *[VIO]: Visual-Inertial Odometry
  *[SDF]: Signed Distance Field
  *[ESDF]: Euclidean Signed Distance Field
  *[TSDF]: Truncated Signed Distance Field
  *[DSG]: Dynamic Scene Graph
  *[DSGs]: Dynamic Scene Graph
  *[GNN]: Graph Neural Network
  *[AV]: Autonomous Vehicle
  *[RNN]: Recurrent Neural Network
  *[GNNs]: Graph Neural Network