11institutetext: Inria Sophia Antipolis, France 22institutetext: Yandex,
Russia 33institutetext: Moscow Institute of Physics and Technology, Russia

# PageRank in Undirected Random Graphs

K. Avrachenkov1 A. Kadavankandy1 Primary author<EMAIL_ADDRESS>
L. Ostroumova Prokhorenkova2,3 and A. Raigorodskii2,3

###### Abstract

PageRank has numerous applications in information retrieval, reputation
systems, machine learning, and graph partitioning. In this paper, we study
PageRank in undirected random graphs with an expansion property. The Chung-Lu
random graph is an example of such a graph. We show that in the limit, as the
size of the graph goes to infinity, PageRank can be approximated by a mixture
of the restart distribution and the vertex degree distribution. We also extend
the result to Stochastic Block Model (SBM) graphs, where we show that there is
a correction term that depends on the community partitioning.

###### Keywords:

PageRank, undirected random graphs, expander graphs, Chung-Lu random graphs,
Stochastic Block Model

##  1 Introduction

PageRank has numerous applications in information retrieval [22, 31, 37],
reputation systems [21, 26], machine learning [4, 5], and graph partitioning
[1, 12]. A large complex network can often be conveniently modeled by a random
graph. It is surprising that not many analytic studies are available for
PageRank in random graph models. We mention the work [6] where PageRank was
analysed in preferential attachment models and the more recent works [10, 11],
where PageRank was analysed in directed configuration models. According to
several studies [18, 20, 29, 36], PageRank and in-degree are strongly
correlated in directed networks such as the Web graph. Apart from some
empirical studies [9, 32], to the best of our knowledge, there is no rigorous
analysis of PageRank on basic undirected random graph models such as the
Erdős-Rényi graph [19] or the Chung-Lu graph [14]. In this paper, we attempt
to fill this gap and show that under certain conditions on the preference
vector and the spectrum of the graphs, PageRank in these models can be
approximated by a mixture of the preference vector and the vertex degree
distribution when the size of the graph goes to infinity. First, we show the
convergence in total variation norm for a general family of random graphs with
expansion property. Then, we specialize the results for the Chung-Lu random
graph model proving the element-wise convergence. We also analyse the
asymptotics of PageRank on Stochastic Block Model (SBM) graphs, which are
random graph models used to benchmark community detection algorithms [24]. In
these graphs the asymptotic expression for PageRank contains an additional
correction term that depends on the community partitioning. This demonstrates
that PageRank captures properties of the graph not visible in the stationary
distribution of a simple random walk.We conclude the paper with numerical
experiments and several future research directions.

##  2 Definitions

Let $G^{(n)}=(V^{(n)},E^{(n)})$ denote a family of random graphs, where
$V^{(n)}$ is a vertex set, $|V^{(n)}|=n$, and $E^{(n)}$ is an edge set,
$|E^{(n)}|=m$. Matrices and vectors related to the graph are denoted by bold
letters, while their components are denoted by non-bold letters. We denote by
$\mathbf{A}^{(n)}$ the associated adjacency matrix with elements

$A^{(n)}_{ij}=\left\\{\begin{array}[]{ll}1,&\mbox{if}\ i\ \mbox{and}\ j\
\mbox{are connected},\\\ 0,&\mbox{otherwise},\end{array}\right.$

In the interest of compactness of notation, the superscript $n$ is dropped
when it is not likely to cause confusion. In this work, since we analyze
PageRank on undirected graphs, we have $\mathbf{A}^{T}=\mathbf{A}$. The
personalized PageRank vector is denoted by $\boldsymbol{\pi}.$ We consider
unweighted graphs; however our analysis easily extends to some families of
weighted undirected graphs. Let $\mathbf{1}$ be a column vector of $n$ ones
and let $\mathbf{d}=\mathbf{A}\mathbf{1}$ be the vector of degrees. It is
helpful to define $\mathbf{D}=\mbox{diag}(\mathbf{d})$, a diagonal matrix with
the degree sequence on its diagonal.

Let $\mathbf{P}=\mathbf{A}\mathbf{D}^{-1}$ be column-stochastic Markov
transition matrix corresponding to the standard random walk on the graph and
let $\mathbf{Q}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ be the
symmetrized transition matrix, whose eigenvalues are the same as those of
$\mathbf{P}.$ Note that the symmetrized transition matrix is closely related
to the normalized Laplacian ${\boldsymbol{\cal
L}}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}=\mathbf{I}-\mathbf{Q}$
[13], where $\mathbf{I}$ is the identity matrix. Further we will also use the
resolvent matrix $\mathbf{R}=[\mathbf{I}-\alpha\mathbf{P}]^{-1}$ and the
symmetrized resolvent matrix $\mathbf{S}=[\mathbf{I}-\alpha\mathbf{Q}]^{-1}$.

Note that since $\mathbf{Q}$ is a symmetric matrix, its eigenvalues
$\lambda_{i},$ $i=1,...,n$ are real and can be arranged in decreasing order,
i.e., $\lambda_{1}\geq\lambda_{2}\geq...$ . In particular, we have
$\lambda_{1}=1$. The value $\delta=1-\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$ is
called the spectral gap.

In what follows, let $K,C$ be arbitrary constants independent of graph size
$n,$ which may change from one line to the next (of course, not causing any
inconsistencies).

For two functions $f(n),g(n),$ $g(n)=O(f(n))$ if $\exists C,N$ such that
$\left|\frac{g(n)}{f(n)}\right|\leq C,$ $\forall n>N$ and $g(n)={o}(f(n))$ if
$\limsup_{n\to\infty}\left|\frac{g(n)}{f(n)}\right|=0.$ Also
$f(n)=\mathrm{\omega}(g(n))$ or $f(n)\gg g(n)$ if $g(n)={o}(f(n)).$

We use $\mathbb{P},\mathbb{E}$ to denote probability and expectation
respectively. An event $E$ is said to hold with high probability (w.h.p.) if
$\exists N$ such that (s.t.) $\mathbb{P}(E)\geq 1-{O}(n^{-c})$ for some $c>0,$
$\forall n>N.$ Recall that if a finite number of events hold true w.h.p., then
so does their intersection. Furthermore, we say that a sequence of random
variables $X_{n}={o}(1)$ w.h.p. if there exists a function $\psi(n)={o}(1)$
such that the event $\\{X_{n}\leq\psi(n)\\}$ holds w.h.p.

In the first part of the paper, we study the asymptotics of PageRank for a
family of random graphs with the following two properties:

###### Property 1

For some $K$ w.h.p., $d^{(n)}_{max}/d^{(n)}_{min}\leq K,$ where
$d^{(n)}_{max}$ and $d^{(n)}_{min}$ are the maximum and minimum degrees,
respectively.

###### Property 2

W.h.p., $\max\\{|\lambda^{(n)}_{2}|,|\lambda^{(n)}_{n}|\\}=o(1).$

The above two properties can be regarded as a variation of the expansion
property. In the standard case of an expander family, one requires the graphs
to be regular and the spectral gap
$\delta=1-\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$ to be bounded away from zero
(see, e.g., [35]). Property 1 is a relaxation of the regularity condition,
whereas Property 2 is stronger than the requirement for the spectral gap to be
bounded away from zero. These two properties allow us to consider several
standard families of random graphs such as ER graphs, regular random graphs
with increasing average degrees, and Chung-Lu graphs. For Chung-Lu graphs
Property 1 imposes some restriction on the degree spread of the graph.

Remark: Property 2 implies that the graph is connected w.h.p., since the
spectral gap is strictly greater than zero.

Later, we study the asymptotics of PageRank for specific classes of random
graphs namely the Chung-Lu graphs, and the Stochastic Block Model. Recall that
the Personalized PageRank vector with preference vector $\mathbf{v}$ is
defined as the stationary distribution of a modified Markov chain with
transition matrix

$\widetilde{\mathbf{P}}=\alpha\mathbf{P}+(1-\alpha)\mathbf{v}\mathbf{1}^{T},$
(1)

where $\alpha$ is the so-called damping factor [22]. In other words,
$\boldsymbol{\pi}$ satisfies

$\boldsymbol{\pi}=\widetilde{\mathbf{P}}\boldsymbol{\pi},\\\ $ (2)

or,

$\boldsymbol{\pi}=(1-\alpha)[\mathbf{I}-\alpha\mathbf{P}]^{-1}\mathbf{v}=(1-\alpha)\mathbf{R}\mathbf{v},$
(3)

where (3) holds when $\alpha<1.$

##  3 Convergence in total variation

We recall that for two discrete probability distributions $u$ and $v$, the
total variation distance $d_{\text{TV}}(u,v)$ is defined as
$d_{\text{TV}}(u,v)=\frac{1}{2}\sum_{i}|u_{i}-v_{i}|.$ This can also be
thought of as the $L^{1}$-norm distance measure in the space of probability
vectors, wherein for $\mathbf{x}\in\mathbb{R}^{n},$ the $L^{1}$-norm is
defined as $\left\lVert\mathbf{x}\right\rVert_{1}=\sum_{i}|x_{i}|.$ Since for
any probability vector $\boldsymbol{\pi},\text{
}\left\lVert\boldsymbol{\pi}\right\rVert_{1}=1$ $\forall n,$ it makes sense to
talk about convergence in 1-norm or TV-distance. Also recall that for a vector
$\mathbf{x}\in\mathbb{R}^{n},$
$\left\lVert\mathbf{x}\right\rVert_{2}=\sqrt{\sum_{i}|x_{i}|^{2}}$ is the
$L^{2}$-norm. Now we are in a position to formulate our first result.

###### Theorem 3.1

Let a family of graphs $G^{(n)}$ satisfy Properties 1 and 2. If, in addition,
$\left\lVert\mathbf{v}\right\rVert_{2}=O(1/\sqrt{n})$, PageRank can be
asymptotically approximated in total variation norm by a mixture of the
restart distribution $\mathbf{v}$ and the vertex degree distribution. Namely,
w.h.p.,

$d_{TV}(\boldsymbol{\pi}^{(n)},\overline{\boldsymbol{\pi}}^{(n)})=o(1)\,\,\text{
as }n\to\infty,$

where

$\overline{\boldsymbol{\pi}}^{(n)}=\frac{\alpha\mathbf{d}^{(n)}}{\textnormal{vol}(G^{(n)})}+(1-\alpha)\mathbf{v},$
(4)

with $\textnormal{vol}(G^{(n)})=\sum_{i}d_{i}^{(n)}$.

Observations:

  1. 1.

This result says that PageRank vector asymptotically behaves like a convex
combination of the preference vector and the stationary vector of a standard
random walk with transition matrix $\mathbf{P};$ with the weight being
$\alpha,$ and that it starts to resemble the random walk stationary vector as
$\alpha$ gets close to $1.$

  2. 2.

One of the possible intuitive explanations of the result of Theorem 3.1 is
based on the observation that when Properties 1 & 2 hold, as $n\to\infty,$ the
random walk mixes approximately in one step and so for any probability vector
$\mathbf{x}$ $\mathbf{P}\mathbf{x}$ is roughly equal to
$\mathbf{d}/\mbox{vol}(G),$ the stationary distribution of the simple random
walk. The proposed asymptotic approximation for PageRank can then be seen to
follow from the series representation of PageRank if we replace
$\mathbf{P}\mathbf{v}$ by $\mathbf{d}/\mbox{vol}(G).$ Note that since
$\mathbf{d}/\textnormal{vol}(G)$ is the stationary vector of the simple random
walk, if $\mathbf{P}\mathbf{v}=\mathbf{d}/\textnormal{vol}(G),$ it also holds
that $\mathbf{P}^{k}\mathbf{v}=\mathbf{d}/\textnormal{vol}(G),\forall k\geq
2.$ Making these substitutions in the series representation of PageRank,
namely

$\boldsymbol{\pi}=(1-\alpha)\left(\mathbf{I}+\alpha\mathbf{P}+\alpha^{2}\mathbf{P}^{2}+\ldots\right)\mathbf{v},$
(5)

we obtain

$\displaystyle\boldsymbol{\pi}$
$\displaystyle=(1-\alpha)\mathbf{v}+(1-\alpha)\alpha(1+\alpha+\alpha^{2}+\ldots)\frac{\mathbf{d}}{\textnormal{vol}(G)}$
$\displaystyle=(1-\alpha)\mathbf{v}+\alpha\frac{\mathbf{d}}{\textnormal{vol}(G)}.$

  3. 3.

The condition on the 2-norm of the preference vector $\mathbf{v}$ can be
viewed as a constraint on its allowed localization.

Proof of Theorem 3.1: First observe from (1) that when $\alpha=0,$ we have
$\widetilde{\mathbf{P}}=\mathbf{v}\mathbf{1}^{T},$ hence from (2) we obtain
$\boldsymbol{\pi}=\mathbf{v},$ since $\mathbf{1}^{T}\boldsymbol{\pi}=1.$
Similarly for the case $\alpha=1,$ $\widetilde{\mathbf{P}}=\mathbf{P}$ and so
$\boldsymbol{\pi}$ in this case is just the stationary distribution of the
original random walk, which is well-defined and equals
$\frac{\mathbf{d}}{\textnormal{vol}(G)}$ since by Property 2 the graph is
connected. Examining (4) for these two cases we can see that the statement of
the theorem holds trivially for both $\alpha=0$ and $\alpha=1.$ In what
follows, we consider the case $0<\alpha<1.$ We first note that the matrix
$\mathbf{Q}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ can be written as
follows by Spectral Decomposition Theorem [7]:

$\mathbf{Q}=\mathbf{u}_{1}\mathbf{u}_{1}^{T}+\sum_{i=2}^{n}\lambda_{i}\mathbf{u}_{i}\mathbf{u}_{i}^{T},$
(6)

where $1=\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$ are the
eigenvalues and $\\{\mathbf{u}_{1},\mathbf{u}_{2},\ldots\mathbf{u}_{n}\\}$
with $\mathbf{u}_{i}\in\mathbf{R}^{n}$ and
$\left\lVert\mathbf{u}_{i}\right\rVert_{2}=1$ are the corresponding orthogonal
eigenvectors of $\mathbf{Q}.$ Recall that
$\mathbf{u}_{1}=\mathbf{D}^{1/2}\mathbf{1}/\sqrt{\mathbf{1}^{T}\mathbf{D}\mathbf{1}}$
is the Perron–Frobenius eigenvector. Next, we rewrite (3) in terms of the
matrix $\mathbf{Q}$ as follows

$\boldsymbol{\pi}=(1-\alpha)\mathbf{D}^{1/2}[\mathbf{I}-\alpha\mathbf{Q}]^{-1}\mathbf{D}^{-1/2}\mathbf{v}.$
(7)

Substituting (6) into (7), we obtain

$\displaystyle\boldsymbol{\pi}$
$\displaystyle=(1-\alpha)\mathbf{D}^{1/2}\left(\frac{1}{1-\alpha}\mathbf{u}_{1}\mathbf{u}_{1}^{T}+\sum_{i=2}^{n}\frac{1}{1-\alpha\lambda_{i}}\mathbf{u}_{i}\mathbf{u}_{i}^{T}\right)\mathbf{D}^{-1/2}\mathbf{v}$
$\displaystyle=\mathbf{D}^{1/2}\mathbf{u}_{1}\mathbf{u}_{1}^{T}\mathbf{D}^{-1/2}\mathbf{v}+(1-\alpha)\mathbf{D}^{1/2}\left(\sum_{i\neq
1}\frac{1}{1-\alpha\lambda_{i}}\mathbf{u}_{i}\mathbf{u}_{i}^{T}\right)\mathbf{D}^{-1/2}\mathbf{v}.$

Let us denote the error vector by
$\boldsymbol{\epsilon}=\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}$. Note
that since
$\mathbf{u}_{1}=\frac{\mathbf{D}^{1/2}\mathbf{1}}{\sqrt{\textnormal{vol}(G)}},$
we can write $\overline{\boldsymbol{\pi}}$ as

$\displaystyle\overline{\boldsymbol{\pi}}$
$\displaystyle=\alpha\frac{\mathbf{d}}{\textnormal{vol}(G)}+(1-\alpha)\mathbf{v}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{=}}\alpha\frac{\mathbf{D}\mathbf{1}\mathbf{1}^{T}\mathbf{v}}{\textnormal{vol}(G)}+(1-\alpha)\mathbf{D}^{1/2}\mathbf{D}^{-1/2}\mathbf{v}$
$\displaystyle=\alpha\mathbf{D}^{1/2}\frac{\mathbf{D}^{1/2}\mathbf{1}}{\sqrt{\textnormal{vol}(G)}}\frac{\mathbf{1}^{T}\mathbf{D}^{1/2}}{\sqrt{\textnormal{vol}(G)}}\mathbf{D}^{-1/2}\mathbf{v}+(1-\alpha)\mathbf{D}^{1/2}\mathbf{D}^{-1/2}\mathbf{v}$
$\displaystyle=\alpha\mathbf{D}^{1/2}\mathbf{u}_{1}\mathbf{u}_{1}^{T}\mathbf{D}^{-1/2}\mathbf{v}+(1-\alpha)\mathbf{D}^{1/2}\mathbf{D}^{-1/2}\mathbf{v},$

where in (a) above we used the fact that $\mathbf{1}^{T}\mathbf{v}=1,$ since
$\mathbf{v}$ is a probability vector. Then, we can write
$\boldsymbol{\epsilon}$ as

$\displaystyle\boldsymbol{\epsilon}$
$\displaystyle=\boldsymbol{\pi}-\alpha\mathbf{D}^{1/2}\mathbf{u}_{1}\mathbf{u}_{1}^{T}\mathbf{D}^{-1/2}\mathbf{v}-(1-\alpha)\mathbf{D}^{1/2}\mathbf{I}\mathbf{D}^{-1/2}\mathbf{v}$
$\displaystyle=(1-\alpha)\mathbf{D}^{1/2}\left(\sum_{i\neq
1}\frac{\mathbf{u}_{i}\mathbf{u}_{i}^{T}}{1-\alpha\lambda_{i}}-(\mathbf{I}-\mathbf{u}_{1}\mathbf{u}_{1}^{T})\right)\mathbf{D}^{-1/2}\mathbf{v}$
$\displaystyle=(1-\alpha)\mathbf{D}^{1/2}\left(\sum_{i\neq
1}\mathbf{u}_{i}\mathbf{u}_{i}^{T}\frac{\alpha\lambda_{i}}{1-\alpha\lambda_{i}}\right)\mathbf{D}^{-1/2}\mathbf{v}.$
(8)

Now let us bound the $L^{1}$-norm
$\left\lVert\boldsymbol{\epsilon}\right\rVert_{1}$ of the error:

$\displaystyle\left\lVert\boldsymbol{\epsilon}\right\rVert_{1}/(1-\alpha)$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{\leq}}\sqrt{n}\|\boldsymbol{\epsilon}\|_{2}/(1-\alpha)$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(b)}}{\leq}}\sqrt{n}\|\mathbf{D}^{1/2}\|_{2}\left\|\sum_{i\neq
1}\mathbf{u}_{i}\mathbf{u}_{i}^{T}\frac{\alpha\lambda_{i}}{1-\alpha\lambda_{i}}\right\|_{2}\|\mathbf{D}^{-1/2}\|_{2}\|\mathbf{v}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(c)}}{\leq}}\sqrt{d_{max}/d_{min}}\sqrt{n}\max_{i>1}\left|\frac{\alpha\lambda_{i}}{1-\alpha\lambda_{i}}\right|\left\lVert\mathbf{v}\right\rVert_{2}$
$\displaystyle\leq C\sqrt{d_{max}/d_{min}}\max(|\lambda_{2}|,|\lambda_{n}|)$
(9)

where in (a) we used the fact that for any vector
$\mathbf{x}\in\mathbb{R}^{n},$
$\|\mathbf{x}\|_{1}\leq\sqrt{n}\|\mathbf{x}\|_{2}$ by Cauchy-Schwartz
inequality. In (b) we used the submultiplicative property of matrix norms,
i.e.,
$\left\lVert\mathbf{A}\mathbf{B}\right\rVert_{2}\leq\left\lVert\mathbf{A}\right\rVert_{2}\left\lVert\mathbf{B}\right\rVert_{2}$.
We obtain (c) by noting that the norm of a diagonal matrix is the leading
diagonal value and the fact that for a symmetric matrix the 2-norm is the
largest eigenvalue in magnitude. The last inequality is obtained by noting
that the assumption $\lambda_{i}=o(1)$ w.h.p. $\forall i>1$ implies that
$\exists N$ s.t. $\forall n>N,$ $|1-\alpha\lambda_{i}|>C$ for some constant C
and the fact that $\left\lVert\mathbf{v}\right\rVert_{2}=O(1/\sqrt{n}).$

Observing that $d_{max}/d_{min}$ is bounded w.h.p. by Property 1 and
$\max(|\lambda_{2}|,|\lambda_{n}|)=o(1)$ w.h.p. by Property 2 we obtain our
result. ∎

Note that in the case of standard PageRank, $v_{i}=1/n,1\leq i\leq n,$ and
hence $\left\lVert\mathbf{v}\right\rVert_{2}=O(1/\sqrt{n}),$ but Theorem 3.1
also admits more general preference vectors than the uniform one.

###### Corollary 1

The statement of Theorem 3.1 also holds with respect to the weak convergence,
i.e., for any function $f$ on $V$ such that $\max_{x\in V}|f(x)|\leq 1,$

$\sup\left\\{\sum_{v}f(v)\pi_{v}-\sum_{v}f(v)\overline{\pi}_{v}\right\\}=o(1)\quad\mbox{w.h.p.}$

Proof: This follows from Theorem 3.1 and the fact that the left-hand side of
the above equation is upper bounded by
$2\,d_{\text{TV}}(\boldsymbol{\pi}_{n},\overline{\boldsymbol{\pi}}_{n})$ [30].
∎

##  4 Chung-Lu random graphs

In this section, we study the PageRank for the Chung-Lu model [14] of random
graphs. These results naturally hold for ER graphs also. The spectral
properties of Chung-Lu graphs have been studied extensively in a series of
papers by Fan Chung et al [15, 16].

###  4.1 Chung-Lu Random Graph Model

Let us first provide a definition of the Chung-Lu random graph model.

###### Definition 1

Chung-Lu Random Graph Model A Chung-Lu graph $\mathcal{G}(w)$ with an expected
degree vector $\mathbf{w}=(w_{1},w_{2},\ldots w_{n})$, where $w_{i}$ are
positive real numbers, is generated by drawing an edge between any two
vertices $v_{i}$ and $v_{j}$ independently of all other pairs, with
probability $p_{ij}=\frac{w_{i}w_{j}}{\sum_{k}w_{k}}.$ To ensure that the
probabilities $p_{ij}$ are well-defined, we need
$\max_{i}w_{i}^{2}\leq\sum_{k}w_{k}$.

In the following, let $w_{\max}=\max_{i}w_{i}$ and $w_{\min}=\min_{i}w_{i}.$
Below we specify a corollary of Theorem 3.1 as applied to these graphs. But
before that we need the following lemmas about Chung-Lu graphs mainly taken
from [15, 16].

###### Lemma 1

If the expected degrees $w_{1},w_{2},\ldots w_{n}$ satisfy
$w_{\min}\gg\log(n),$ then in $\mathcal{G}(w)$ we have, w.h.p.,
$\max_{i}|\frac{d_{i}}{w_{i}}-1|=o(1)$.

In the proof we use Bernstein Concentration Lemma [8]:

###### Lemma 2

(Bernstein Concentration Lemma [8]) If $Y_{n}=X_{1}+X_{2}+\ldots X_{n},$ where
$X_{i}$ are independent random variables such that $|X_{i}|\leq b$ and if
$B_{n}^{2}=\mathbb{E}(Y_{n}-\mathbb{E}(Y_{n}))^{2}$ then

$\mathbb{P}\\{|Y_{n}-\mathbb{E}(Y_{n})|\geq\epsilon\\}\leq
2\exp\frac{-\epsilon^{2}}{2(B_{n}^{2}+b\epsilon/3)},$

for any $\epsilon>0.$

Proof of Lemma 1: This result is shown in the sense of convergence in
probability in the proof of [16, Theorem 2]; using Lemma 2 we show the result
holds w.h.p. By a straight forward application of Lemma 2 to the degrees
$d_{i}$ of the Chung-Lu graph we obtain

$\mathbb{P}\left(\max_{1\leq i\leq
n}\left|\frac{d_{i}}{w_{i}}-1\right|\geq\beta\right)\leq\frac{2}{n^{c/4-1}},\quad\mbox{if}\quad\beta\geq\sqrt{\frac{c\log(n)}{w_{\min}}}=o(1)$

if $w_{\min}\gg\log(n)$.∎We present below a perturbation result for the
eigenvalues of Hermitian matrices, called Weyl’s inequalities, which we will
need for our proofs.

###### Lemma 3

[25, Theorem 4.3.1] Let $\mathbf{A},\mathbf{B}\in\mathbb{R}^{n\times n}$ be
Hermitian and let the eigenvalues $\lambda_{i}(\mathbf{A}),$
$\lambda_{i}(\mathbf{B})$ and $\lambda_{i}(\mathbf{A}+\mathbf{B})$ be arranged
in decreasing order. For each $k=1,2,\ldots n$ we have

$|\lambda_{k}(\mathbf{A}+\mathbf{B})-\lambda_{k}(\mathbf{A})|\leq\|\mathbf{B}\|_{2},$

where $\|\mathbf{B}\|_{2}$ is the induced 2-norm or the spectral norm of
$\mathbf{B}.$

The following lemma is an application of Theorem 5 in [15].

###### Lemma 4

If $w_{\max}\leq Kw_{\min},$ for some $K>0$ and
$\overline{w}=\sum_{k}w_{k}/n\gg\log^{6}(n)$, then for $\mathcal{G}(w)$ we
have almost surely (a.s.)

$\left\lVert\mathbf{C}\right\rVert_{2}=\frac{2}{\sqrt{\overline{w}}}(1+o(1)),$

where
$\mathbf{C}=\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}-\boldsymbol{\chi}^{T}\boldsymbol{\chi}$,
$\mathbf{W}=\mbox{diag}(\mathbf{w}),$ and
$\mathbf{\chi}_{i}=\sqrt{w_{i}/\sum_{k}w_{k}}$ is a row vector.

Proof: It can be verified that when $w_{\max}\leq Kw_{\min}$ and
$\overline{w}\gg\log^{6}(n),$ the condition in [15, Theorem 5], namely,
$w_{\min}\gg\sqrt{\overline{w}}\log^{3}(n),$ is satisfied and hence the result
follows.∎

###### Lemma 5

For $\mathcal{G}(w)$ with $w_{\max}\leq Kw_{\min},$ and
$\overline{w}\gg\log^{6}(n),$

$\max(\lambda_{2}(\mathbf{P}),-\lambda_{n}(\mathbf{P}))=o(1)\quad\mbox{w.h.p.},$

where $\mathbf{P}$ is Markov matrix.

Proof: Recall that $\mathbf{Q}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$
is the normalized adjacency matrix. We want to be able to bound the
eigenvalues $\lambda_{i},i\geq 2$ of $\mathbf{Q}.$ We do this in two steps.
Using Lemmas 1 and 3 we first show that if we replace the degree matrix
$\mathbf{D}$ in the expression for $\mathbf{Q}$ by the expected degree matrix
$\mathbf{W}=\mathbb{E}(\mathbf{D}),$ the eigenvalues of the resulting matrix
are close to those of $\mathbf{Q}.$ Then, using Lemma 4 we show that the
eigenvalues of $\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}$ roughly coincide
with those of $\boldsymbol{\chi}^{T}\boldsymbol{\chi},$ which is a unit rank
matrix and hence only has a single non-zero eigenvalue. Thus we arrive at the
result of Lemma 5. Now we give the detailed proof.

The first step,
$\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|_{2}=o(1)$ w.h.p.
follows from Lemma 1 and the same argument as in the last part of the proof of
Theorem 2 in [16]. We present the steps in the derivation here for the sake of
completeness.

Since the 2-norm of a diagonal matrix is the maximum diagonal in absolute
value, we have

$\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}-\mathbf{I}\|_{2}=\max_{\\{i=1,2,\ldots\\}}\left|\sqrt{\frac{d_{i}}{w_{i}}}-1\right|\leq\max_{\\{i=1,2,\ldots\\}}\left|{\frac{d_{i}}{w_{i}}}-1\right|=o(1),$
(10)

by Lemma 1. Also observe that

$\|\mathbf{Q}\|_{2}=\max_{\\{i=1,2,\ldots
n\\}}|\lambda_{i}(\mathbf{Q})|=\max_{\\{i=1,2,\ldots
n\\}}|\lambda_{i}(\mathbf{P})|=1.$ (11)

We now proceed to bound the norm of the difference
$\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|$ as follows

$\displaystyle\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|_{2}$
(12) $\displaystyle=$
$\displaystyle\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}$
$\displaystyle=$
$\displaystyle\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}$
$\displaystyle=$
$\displaystyle\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}+\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{=}}$
$\displaystyle\|(\mathbf{I}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2})\mathbf{Q}\|_{2}+\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}(\mathbf{I}-\mathbf{D}^{1/2}\mathbf{W}^{-1/2})\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(b)}}{\leq}}$
$\displaystyle\|(\mathbf{I}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2})\|_{2}\|\mathbf{Q}\|_{2}+\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\|_{2}\|\mathbf{Q}\|_{2}\|\mathbf{I}-\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(c)}}{=}}$ $\displaystyle
o(1)+(1+o(1))o(1)=o(1)\quad w.h.p.,$

where (a) follows from triangular inequality of norms, in (b) we used
submultiplicativity of matrix norms, and (c) follows from (10), (11) and the
fact that
$\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\|_{2}\leq\|\mathbf{I}\|_{2}+\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}-\mathbf{I}\|_{2}=(1+o(1)).$

By Lemma 3 we have for any $i,$

$|\lambda_{i}(\mathbf{Q})-\lambda_{i}(\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2})|\leq\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|_{2}=o(1),$
(13)

by (12). Furthermore, using Lemma 3 and the fact that
$\lambda_{i}(\boldsymbol{\chi}^{T}\boldsymbol{\chi})=0$ for $i>1,$ we have for
$i\geq 2,$

$\displaystyle|\lambda_{i}(\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2})|$
(14) $\displaystyle=$
$\displaystyle|\lambda_{i}(\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2})-\lambda_{i}(\boldsymbol{\chi}^{T}\boldsymbol{\chi})|\leq\|\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}-\boldsymbol{\chi}^{T}\boldsymbol{\chi}\|_{2}$
$\displaystyle=$ $\displaystyle o(1),$

where the last inequality follows from Lemma 4.
Now recall that
$\max(\lambda_{2}(\mathbf{P}),-\lambda_{n}(\mathbf{P}))=\max_{\\{i\geq
2\\}}|\lambda_{i}(\mathbf{Q})|.$ We have for any $i,$

$\displaystyle|\lambda_{i}(\mathbf{Q})|\leq|\lambda_{i}(\mathbf{Q})-\lambda_{i}(\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2})|+||\lambda_{i}(\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2})|,$
(15)

which implies from (13) and (14):

$\max_{\\{i\geq 2\\}}|\lambda_{i}(\mathbf{Q})|=o(1).$

∎Armed with these lemmas we now present the following corollary of Theorem 3.1
in the case of Chung-Lu graphs.

###### Corollary 2

Let $\left\lVert\mathbf{v}\right\rVert_{2}=O(1/\sqrt{n}),$ and
$\alpha\in(0,1).$ Then PageRank $\boldsymbol{\pi}$ of the Chung-Lu graph
$\mathcal{G}(w)$ can asymptotically be approximated in TV distance by
$\overline{\boldsymbol{\pi}},$ defined in Theorem 3.1, if
$\overline{w}\gg\log^{6}(n)$ and $w_{\max}\leq Kw_{\min}$ for some $K$ that
does not depend on $n.$

Proof: Using Lemma 1 and the condition that $w_{\max}\leq Kw_{\min},$ one can
show that $\exists K^{{}^{\prime}}$ s.t. $\frac{d_{max}}{d_{min}}\leq
K^{{}^{\prime}}$ w.h.p. Then the result is a direct consequence of Lemma 5 and
the inequality from (9).∎

We further note that this result also holds for ER graphs
$\mathcal{G}(n,p_{n})$ with $n$ nodes and edge probability $p_{n}$ such that
$np_{n}\gg\log^{6}(n),$ where we have $(w_{1},w_{2},\ldots
w_{n})=(np_{n},np_{n},\ldots np_{n}).$

###  4.2 Element-wise Convergence

In Corollary 2 we proved the convergence of PageRank in TV distance for Chung-
Lu random graphs. Note that since each component of PageRank could decay to
zero as the graph size grows to infinity, this does not necessarily guarantee
convergence in an element-wise sense. In this section, we provide a proof for
our convergence conjecture to include the element-wise convergence of the
PageRank vector. Here we deviate slightly from the spectral decomposition
technique and eigenvalue bounds used hitherto, and instead rely on well-known
concentration bounds to bound the error in convergence.

Let
$\overline{\boldsymbol{\Pi}}=\mbox{diag}\\{\overline{\pi}_{1},\overline{\pi}_{2},\ldots\overline{\pi}_{n}\\}$
be a diagonal matrix whose diagonal elements are made of the components of the
approximated PageRank vector and
$\widetilde{\boldsymbol{\delta}}=\overline{\boldsymbol{\Pi}}^{-1}(\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}),$
i.e.,
$\widetilde{\delta}_{i}=(\pi_{i}-\overline{\pi}_{i})/\overline{\pi}_{i}=\epsilon_{i}/\overline{\pi}_{i},$
where $\boldsymbol{\epsilon}$ is the unnormalized error defined in Section 3.
Then using (8) we obtain

$\widetilde{\delta}_{i}=\left((1-\alpha)v_{i}+\alpha\frac{d_{i}}{\text{vol(G)}}\right)^{-1}\left[\mathbf{D}^{1/2}\sum_{j\neq
1}\frac{\alpha\lambda_{j}}{1-\alpha\lambda_{j}}\mathbf{u}_{j}\mathbf{u}_{j}^{T}\mathbf{D}^{-1/2}\mathbf{v}\right]_{i}.$

Therefore, using $\mathbf{v}^{\prime}$ to denote
$n\mathbf{D}^{-1/2}\mathbf{v}$ we can bound
$\left\lVert\widetilde{\boldsymbol{\delta}}\right\rVert_{\infty}=\max_{i}|\widetilde{\delta}_{i}|$
as follows

$\displaystyle\left\lVert\widetilde{\boldsymbol{\delta}}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{\min_{i}\left((1-\alpha)v_{i}+\alpha\frac{d_{i}}{\textnormal{vol}(G)}\right)}\left\|\mathbf{D}^{1/2}\sum_{j\neq
1}\frac{\alpha\lambda_{j}}{1-\alpha\lambda_{j}}\mathbf{u}_{j}\mathbf{u}_{j}^{T}\mathbf{D}^{-1/2}\mathbf{v}\right\|_{\infty}$
(16) $\displaystyle\leq\frac{\sum_{i}d_{i}/n}{\alpha
d_{\min}}\sqrt{d_{max}}\left\lVert\sum_{j\neq
1}\frac{\alpha\lambda_{j}}{1-\alpha\lambda_{j}}\mathbf{u}_{j}\mathbf{u}_{j}^{T}\mathbf{v}^{\prime}\right\rVert_{\infty}.$
(17)

Here $d_{\min}$ denotes $\min_{i}d_{i}.$ To obtain (17) we used the
submultiplicativity property of matrix norms, the fact that
$\|\mathbf{D}^{1/2}\|_{\infty}=\sqrt{\max_{i}d_{i}}=\sqrt{d_{\max}}$ and the
fact that $v_{i}\geq 0,\forall i\in V.$

Define $\widetilde{\mathbf{Q}}=\mathbf{Q}-\mathbf{u}_{1}\mathbf{u}_{1}^{T},$
the restriction of the matrix $\mathbf{Q}$ to the orthogonal subspace of
$\mathbf{u}_{1}.$

###### Lemma 6

For a Chung-Lu random graph $\mathcal{G}(w)$ with expected degrees
$w_{1},\ldots w_{n}$, where $w_{\max}\leq Kw_{\min}$ and $w_{\min}\gg\log(n),$
we have w.h.p.,

$\left\lVert\widetilde{\mathbf{Q}}\mathbf{v}^{\prime}\right\rVert_{\infty}=o(1/\sqrt{w_{\min}}),$

when $v_{i}=O(1/n)\ \forall i.$

This lemma can be proven by a few applications of Lemma 1 and Bernstein’s
concentration inequality. To keep the train of thought intact, please refer to
Appendix 0.A for a detailed proof of this lemma.

In the next lemma we prove an upper bound on the infinity norm of the matrix
$\mathbf{S}=(\mathbf{I}-\alpha\mathbf{Q})^{-1}.$

###### Lemma 7

Under the conditions of Lemma 6,
$\left\lVert\mathbf{S}\right\rVert_{\infty}\leq C$ w.h.p., where $\mathbf{C}$
is a number independent of $n$ that depends only on $\alpha$ and $K$.

Proof: Note that
$\mathbf{S}=(\mathbf{I}-\alpha\mathbf{Q})^{-1}=\mathbf{D}^{-1/2}(\mathbf{I}-\alpha\mathbf{P})^{-1}\mathbf{D}^{1/2}.$
Therefore,
$\left\lVert\mathbf{S}\right\rVert_{\infty}\leq\sqrt{\frac{d_{max}}{d_{min}}}\left\lVert(\mathbf{I}-\alpha\mathbf{P})^{-1}\right\rVert_{\infty}$
and the result follows since
$\left\lVert(\mathbf{I}-\alpha\mathbf{P})^{-1}\right\rVert_{\infty}\leq\frac{1}{1-\alpha}$
[28] and using Lemma 1. ∎Now we are in a position to present our main result
in this section.

###### Theorem 4.1

Let $v_{i}=O(1/n)\,\,\forall i,$ and $\alpha<1.$ PageRank $\boldsymbol{\pi}$
converges element-wise to
$\overline{\boldsymbol{\pi}}=(1-\alpha)\mathbf{v}+\alpha\mathbf{d}/\textnormal{vol}(G),$
in the sense that $\max_{i}\
(\pi_{i}-\overline{\pi}_{i})/\overline{\pi}_{i}=o(1)$ w.h.p., on the Chung-Lu
graph $\mathcal{G}(w)$ with expected degrees $\\{w_{1},w_{2},\ldots w_{n}\\}$
such that $w_{\min}>\log^{c}(n)$ for some $c>1$ and $w_{\max}\leq Kw_{\min},$
for some $K,$ a constant independent of $n.$

Proof: Define $\mathbf{Z}=\sum_{i\neq
1}\frac{\alpha\lambda_{i}}{1-\alpha\lambda_{i}}\mathbf{u}_{i}\mathbf{u}_{i}^{T}.$
We then have:

$\displaystyle\mathbf{Z}$
$\displaystyle=\sum_{i=1}^{n}\frac{\alpha\lambda_{i}}{1-\alpha\lambda_{i}}\mathbf{u}_{i}\mathbf{u}_{i}^{T}-\frac{\alpha}{1-\alpha}\mathbf{u}_{1}\mathbf{u}_{1}^{T}$
$\displaystyle=(\mathbf{I}-\alpha\mathbf{Q})^{-1}\alpha\mathbf{Q}-\frac{\alpha}{1-\alpha}\mathbf{u}_{1}\mathbf{u}_{1}^{T}$
$\displaystyle=\mathbf{S}\left[\alpha\mathbf{Q}-\frac{\alpha}{1-\alpha}(\mathbf{I}-\alpha\mathbf{Q})\mathbf{u}_{1}\mathbf{u}_{1}^{T}\right]$
$\displaystyle=\alpha\mathbf{S}\widetilde{\mathbf{Q}}$ (18)

Now from (17) we have

$\displaystyle\left\lVert\widetilde{\boldsymbol{\delta}}\right\rVert_{\infty}$
$\displaystyle\leq
C\frac{\sum_{i}d_{i}/n}{d_{\min}}\sqrt{d_{max}}\|\mathbf{S}\widetilde{\mathbf{Q}}\mathbf{v}^{{}^{\prime}}\|_{\infty}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{\leq}}C\frac{\sum_{i}d_{i}/n}{d_{\min}}\sqrt{d_{max}}o(1/\sqrt{w_{\min}})$
$\displaystyle\leq
C\frac{d_{\max}}{d_{\min}}\sqrt{w_{\max}(1+o(1))}\frac{1}{\sqrt{w_{\min}}}o(1)$
$\displaystyle=C\frac{w_{\max}}{w_{\min}}\sqrt{\frac{w_{\max}}{w_{\min}}}(1+o(1))o(1)$
$\displaystyle=C\left(\frac{w_{\max}}{w_{\min}}\right)^{\frac{3}{2}}o(1)$
$\displaystyle\leq Co(1)\quad\mbox{w.h.p.},$

where in (a) we used (18) and Lemmas 6 and 7. The rest of the inequalities are
obtained by repeatedly using the fact that $d_{\max}=w_{\max}(1+o(1))$ and
$d_{min}=w_{\min}(1+o(1)),$ from Lemma 1. The last step follows from the
assumption that $w_{\max}\leq Kw_{\min}$ for some constant $K.$∎

######  Corollary 1 (ER Graphs)

For an ER graph $\mathcal{G}(n,p_{n})$ such that $np_{n}\gg\log(n),$ we have
that asymptotically the personalized PageRank $\boldsymbol{\pi}$ converges
pointwise to $\overline{\boldsymbol{\pi}}$ for $\mathbf{v}$ such that
$v_{i}=O(1/n).$

##  5 Asymptotic PageRank for the Stochastic Block Model

In this section, we extend the analysis of PageRank to Stochastic Block Models
(SBM) with constraints on average degrees. The SBM is a random graph model
that reflects the community structure prevalent in many online social
networks. It was first introduced in [24] and has been analyzed subsequently
in several works, specifically in the community detection literature,
including [17],[27], [33], [3] and several extensions thereof as in [23] and
[38], and the references therein.

For the sake of simplicity we focus on an SBM graph with two communities, but
the idea of the proof extends easily to generalizations of this simple model.

###### Definition 1

[Stochastic Block Model (SBM) with two communities]: An SBM graph
$\mathcal{G}(m,n-m,p,q)$ with two communities is an undirected graph on a set
of disjoint vertices $C_{1},C_{2}$ such that $C_{1}\cup C_{2}=V,$ and let
$|C_{1}|=m$ and $|C_{2}|=n-m$. Furthermore, if two vertices $i,j\in
C_{k},k=1,2$, then $\mathbb{P}((i,j)\in E)=p$, if $i\in C_{1}$ and $j\in
C_{2}$, then $\mathbb{P}((i,j)\in E)=q.$ The probabilities $p,q$ may scale
with $n$ and we assume that $m>n/2$ and $p>q;$ this last assumption is
necessary for modeling the community structure of a network.

Remark: For the sake of simplicity, we assume that the edge probabilities
within both communities are equal to $p,$ but this is a minor assumption and
can be generalised so that community 1 has a different edge probability to
community 2.

For an SBM graph we use $w_{\max}$ and $w_{\min}$ to denote the maximum and
the minimum expected degrees of the nodes respectively. From Definition 1, by
our assumption on $m,p$ and $q,$ we have $w_{\max}=mp+(n-m)q$ and
$w_{\min}=(n-m)p+mq.$ Note that our results only depend on these two
parameters. We present our main result on SBM graphs in the following theorem.

###### Theorem 5.1

For a Stochastic Block Model with $w_{\min}=\mathrm{\omega}(\log^{3}(n))$ and
$\frac{w_{\max}}{w_{\min}}\leq C,$ PageRank with preference vector
$\mathbf{v}$ such that $\|\mathbf{v}\|_{2}=O(\frac{1}{\sqrt{n}})$ satisfies

$\|\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}_{\textnormal{SBM}}\|_{\text{TV}}=o(1)$

w.h.p., where

$\overline{\boldsymbol{\pi}}_{\textnormal{SBM}}=(1-\alpha)\left(\mathbf{I}-\alpha\overline{\mathbf{P}}\right)^{-1}\mathbf{v}.$
(19)

Here $\overline{\mathbf{P}}$ represents the “average” Markov matrix given as
$\overline{\mathbf{P}}=\overline{\mathbf{A}}\mathbf{W}^{-1}$ where
$\mathbf{W}=\mathbb{E}(\mathbf{D})$ and
$\overline{\mathbf{A}}=\mathbb{E}(\mathbf{A}).$

Discussion: Let us look at the permissible values of $m,p,q$ under the
assumptions in the above theorem. Recall that we have $w_{\min}=(n-m)p+mq>nq.$
Therefore the condition on the growth of minimum expected degree is met, for
example, if $q=\omega(\log^{3}(n)/n).$ On the other hand we have

$\frac{w_{\max}}{w_{\min}}=\frac{mp+(n-m)q}{(n-m)p+mq}=\frac{\frac{m}{n-m}\frac{p}{q}+1}{\frac{m}{n-m}+\frac{p}{q}}\quad,$

which remains bounded if either $m/(n-m)$ or $p/q$ tends to infinity, but not
both.

The following corollary of Theorem 5.1 gives an interesting expression for
PageRank for an SBM graph with two equal-sized communities.

###### Corollary 2

For an SBM graph as in Definition 1, with $m=n/2,$ (n assumed to be even) such
that $p+q\gg\log^{3}(n)/n$ the PageRank vector $\boldsymbol{\pi}$ with
preference vector $\mathbf{v}$ such that
$\|\mathbf{v}\|_{2}=O(\frac{1}{\sqrt{n}})$ satisfies

$\|\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}_{\textnormal{SBM}}\|_{TV}\to
0$

w.h.p as $n\to\infty$ where

$\overline{\boldsymbol{\pi}}_{\textnormal{SBM}}=\alpha\frac{1}{n}\mathbf{1}+(1-\alpha)\left(\mathbf{v}+\frac{\alpha\beta}{1-\alpha\beta}(\mathbf{v}^{T}\mathbf{u})\mathbf{u}\right),$
(20)

where $\beta\coloneqq\frac{p-q}{p+q},$ and $\mathbf{u}\in\mathbb{R}^{n}$ is a
unit vector such that $u_{i}=\frac{1}{\sqrt{n}},$ for $i\in C_{1}$ and
$u_{i}=-\frac{1}{\sqrt{n}}$ for $i\in C_{2}.$

Proof: With equal-sized communities, i.e., $m=n/2$, we have
$w_{\max}=w_{\min}=\frac{n}{2}(p+q).$ Therefore the conditions of Theorem 5.1
are satisfied if $p+q\gg\log^{3}(n)/n.$ Observe that the expected adjacency
matrix can be written as
$\overline{\mathbf{A}}=\frac{p+q}{2}\mathbf{1}\mathbf{1}^{T}+\frac{n}{2}(p-q)\mathbf{u}\mathbf{u}^{T}.$
Furthermore, $\mathbf{W}=\frac{n}{2}(p+q)\mathbf{I}.$ Therefore
$\overline{\mathbf{P}}=\overline{\mathbf{A}}\mathbf{W}^{-1}=\frac{1}{n}\mathbf{1}\mathbf{1}^{T}+\frac{p-q}{p+q}\mathbf{u}\mathbf{u}^{T}.$
From (19), the asymptotic PageRank
$\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}$ is therefore given as

$\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}=\alpha\overline{\mathbf{P}}\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}+(1-\alpha)\mathbf{v}.$

Consequently,
$\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}=\frac{\alpha}{n}\mathbf{1}+\alpha\beta\mathbf{u}\mathbf{u}^{T}\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}+(1-\alpha)\mathbf{v},$
or
$\left[\mathbf{I}-\alpha\beta\mathbf{u}\mathbf{u}^{T}\right]\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}=\frac{\alpha}{n}\mathbf{1}+(1-\alpha)\mathbf{v}.$
By Woodbury Matrix Inversion Lemma in [25],
$\left[\mathbf{I}-\alpha\beta\mathbf{u}\mathbf{u}^{T}\right]^{-1}=\mathbf{I}+\frac{\alpha\beta}{1-\alpha\beta}\mathbf{u}\mathbf{u}^{T}.$
Hence we obtain
$\overline{\boldsymbol{\pi}}_{\textnormal{sbm}}=\frac{\alpha}{n}\mathbf{1}+(1-\alpha)\left(\mathbf{v}+\frac{\alpha\beta}{1-\alpha\beta}(\mathbf{u}^{T}\mathbf{v})\mathbf{u}\right),$
using the fact that $\mathbf{u}$ and $\mathbf{1}$ are orthogonal vectors. ∎The
above corollary asserts that on an SBM matrix the PageRank is well
approximated in the asymptotic regime of large graph size by the convex
combination of the uniform probability vector $\frac{1}{n}\mathbf{1}$, which
is the asymptotic stationary distribution of a simple random walk on the SBM
graph, and a linear combination of the preference vector $\mathbf{v}$ and the
projection of the preference vector onto the community partitioning vector
$\mathbf{u}.$ Thus in this simple scenario of SBM graphs with equally sized
communities, we observe that PageRank incorporates information about the
community structure, in the form of a term correlated with the partition
vector $\mathbf{u},$ as opposed to the usual random walk, which misses this
information. It can also be inferred from (20) that if the correlation between
the preference vector $\mathbf{v}$ and $\mathbf{u}$ is large, e.g., when the
seed set of PageRank is chosen to be in one of the communities, the resulting
PageRank will display a clear delineation of the communities. This provides a
mathematical rationale for why PageRank works for semi-supervised graph
partitioning [5], at least in the asymptotic regime.

To prove Theorem 5.1 we need the following Lemmas, whose proofs are given in
Appendix 0.B.

###### Lemma 8

For an SBM graph $\mathcal{G}(m,n-m,p,q),$ when
$w_{\min}=\mathrm{\omega}(\log^{3}(n))$ it can be shown that for some $C,$

$\max_{1\leq i\leq n}\left|\frac{D_{i}}{\mathbb{E}(D_{i})}-1\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}\text{ w.h.p}.$

The proof of this lemma follows from applying Bernstein’s concentration lemma
to the degrees of SBM graph. The proof is given in Appendix 0.B.1.

For ease of notation, let
$\overline{\mathbf{Q}}=\mathbf{W}^{-1/2}\mathbb{E}(\mathbf{A})\mathbf{W}^{-1/2},$
where $\mathbf{W}=\mathbb{E}(\mathbf{D}).$ As before
$\mathbf{Q}=\mathbf{D}^{1/2}\mathbf{A}\mathbf{D}^{1/2}.$ We need the following
concentration result on $\mathbf{Q}.$

###### Lemma 9

For an SBM graph for which $w_{\min}=\mathrm{\omega}(\log^{3}(n)),$ and
$\frac{w_{\max}}{w_{\min}}\leq C$ for some $C,$ it can be shown that

$\|\mathbf{Q}-\overline{\mathbf{Q}}\|_{2}=C\frac{\sqrt{\log(n)w_{\max}}}{w_{\min}}=o(1)$

w.h.p.

We prove this lemma in Appendix 0.B.2.
Proof of Theorem 5.1: We write the error between $\boldsymbol{\pi}$ and
$\overline{\boldsymbol{\pi}}$ as follows

$\displaystyle\boldsymbol{\delta}$
$\displaystyle=\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}$
$\displaystyle=(1-\alpha)\left[\mathbf{D}^{1/2}(\mathbf{I}-\alpha\mathbf{Q})^{-1}\mathbf{D}^{-1/2}-\mathbf{W}^{1/2}(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\mathbf{W}^{-1/2}\right]\mathbf{v}$
$\displaystyle=(1-\alpha)\biggl{[}\mathbf{W}^{1/2}\left((\mathbf{I}-\alpha{\mathbf{Q}})^{-1}-(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\right)\mathbf{W}^{-1/2}\biggr{]}\mathbf{v}+$
$\displaystyle(1-\alpha)\biggl{[}\mathbf{D}^{1/2}(\mathbf{I}-\alpha\mathbf{Q})^{-1}\mathbf{D}^{-1/2}-\mathbf{W}^{1/2}(\mathbf{I}-\alpha\mathbf{Q})^{-1}\mathbf{W}^{-1/2}\biggr{]}\mathbf{v},$
(21)

where in the last equality we added and subtracted
$\mathbf{W}^{1/2}(\mathbf{I}-\alpha\mathbf{Q})^{-1}\mathbf{W}^{-1/2}$ and
reordered terms. Now we analyse the two terms in square brackets in the last
equality in (21), which we denote $T_{1}$ and $T_{2},$ respectively. Notice
that we have $\|\boldsymbol{\delta}\|_{1}\leq\|T_{1}\|_{1}+\|T_{2}\|_{1}.$
Next we show that as $n\to\infty,$ $\|T_{1}\|_{1}$ and $\|T_{2}\|_{1}$ are
$o(1)$ separately and consequently we obtain the result of the theorem.

Let us first consider $T_{1}.$ We have

$\displaystyle T_{1}$
$\displaystyle=(1-\alpha)\biggl{[}\mathbf{W}^{1/2}\left((\mathbf{I}-\alpha{\mathbf{Q}})^{-1}-(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\right)\mathbf{W}^{-1/2}\biggr{]}\mathbf{v}$
$\displaystyle=(1-\alpha)\mathbf{W}^{1/2}(\mathbf{I}-\alpha{\mathbf{Q}})^{-1}\left(\overline{\mathbf{Q}}-\mathbf{Q}\right)(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\mathbf{W}^{-1/2}\mathbf{v},$

which we obtained by factoring out $(\mathbf{I}-\alpha{\mathbf{Q}})^{-1}$ and
$(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}$ on the left and right sides of
the square brackets. Next we focus on the 2-norm of $T_{1}.$

$\displaystyle\|T_{1}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{\leq}}(1-\alpha)\sqrt{w_{\max}}\|(\mathbf{I}-\alpha{\mathbf{Q}})^{-1}\|_{2}\|\overline{\mathbf{Q}}-\mathbf{Q}\|_{2}\|(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\|_{2}\frac{1}{\sqrt{w_{\min}}}\|\mathbf{v}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(b)}}{\leq}}\frac{1}{1-\alpha}\sqrt{\frac{w_{\max}}{w_{\min}}}\|\mathbf{Q}-\overline{\mathbf{Q}}\|_{2}\|\mathbf{v}\|_{2}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(c)}}{\leq}}C\frac{\sqrt{\log(n)w_{\max}}}{w_{\min}\sqrt{n}}$
$\displaystyle=C\sqrt{\frac{\log(n)}{nw_{\max}}}\frac{w_{\max}}{w_{\min}}.$

This proves $\|T_{1}\|_{1}\leq\sqrt{n}\|T_{1}\|_{2}\leq
C\sqrt{\frac{\log(n)}{w_{\max}}}\frac{w_{\max}}{w_{\min}}=o(1),$111By Cauchy
Schwartz inequality on norms. from the assumptions of the theorem. Here in (a)
we used the submultiplicative property of matrix norms and the fact that
2-norm of diagonal matrices is the maximum diagonal element in magnitude. The
inequality (b) follows because
$\|(\mathbf{I}-\alpha{\mathbf{Q}})^{-1}\|_{2}\leq\frac{1}{1-\alpha}$ and
$\|(\mathbf{I}-\alpha\overline{\mathbf{Q}})^{-1}\|_{2}\leq\frac{1}{1-\alpha}$
and step (c) follows from Lemma 9 and the assumption that
$\|\mathbf{v}\|_{2}=O(1/\sqrt{n})$.

Next we analyse the second term $T_{2}.$ For ease of notation we denote
$\widetilde{\mathbf{R}}=\mathbf{W}^{1/2}\left(\mathbf{I}-\alpha\mathbf{Q}\right)^{-1}\mathbf{W}^{-1/2}.$
Then by simple algebraic manipulations

$\displaystyle T_{2}$
$\displaystyle=(1-\alpha)\left[\mathbf{D}^{1/2}\left(\mathbf{I}-\alpha\mathbf{Q}\right)^{-1}\mathbf{D}^{-1/2}-\mathbf{W}^{1/2}\left(\mathbf{I}-\alpha\mathbf{Q}\right)^{-1}\mathbf{W}^{-1/2}\right]\mathbf{v}$
$\displaystyle=(1-\alpha)\left(\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\widetilde{\mathbf{R}}\mathbf{W}^{1/2}\mathbf{D}^{-1/2}-\widetilde{\mathbf{R}}\right)\mathbf{v}$
$\displaystyle=(1-\alpha)\left(\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\widetilde{\mathbf{R}}\left(\mathbf{W}^{1/2}\mathbf{D}^{-1/2}-\mathbf{I}\right)+\left(\mathbf{D}^{1/2}\mathbf{W}^{-1/2}-\mathbf{I}\right)\widetilde{\mathbf{R}}\right)\mathbf{v},$

where the last step is obtained by adding and subtracting
$\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\widetilde{\mathbf{R}}.$

Now we have
$\|\mathbf{D}^{1/2}\mathbf{W}^{-1/2}-\mathbf{I}\|_{2}=\max_{i}\left|\sqrt{\frac{d_{i}}{w_{i}}}-1\right|\leq\max_{i}\left|\frac{d_{i}}{w_{i}}-1\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}$ w.h.p. by Lemma 8 and similarly
$\|\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}\leq\|\mathbf{D}^{1/2}\mathbf{W}^{-1/2}-\mathbf{I}\|_{2}+\|\mathbf{I}\|_{2}\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}+1.$ In addition
$\|\mathbf{W}^{1/2}\mathbf{D}^{-1/2}-\mathbf{I}\|_{2}=\max_{i}\left|\sqrt{\frac{w_{i}}{d_{i}}}-1\right|\leq\max_{i}\left|\frac{w_{i}}{d_{i}}-1\right|.$
It can be shown that since $\max_{i}\left|\frac{d_{i}}{w_{i}}-1\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}$ w.h.p. (by Lemma 8), then
$\max_{i}\left|\frac{w_{i}}{d_{i}}-1\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}$ w.h.p.222This follows since we can write
$\frac{d_{i}}{w_{i}}=1+\eta_{i}$, with
$\max_{i}|\eta_{i}|=O\left(\sqrt{\frac{\log(n)}{w_{\min}}}\right)=o(1)$
w.h.p., then
$\frac{w_{i}}{d_{i}}=\frac{1}{1+\eta_{i}}=1-\eta_{i}+O(\eta_{i}^{2}),$ hence
$\max_{i}|\frac{w_{i}}{d_{i}}-1|=O(\max_{i}|\eta_{i}|)=O\left(\sqrt{\frac{\log(n)}{w_{\min}}}\right)=o(1)$
w.h.p. Therefore
$\|\mathbf{W}^{1/2}\mathbf{D}^{-1/2}\|_{2}\leq\|\mathbf{W}^{1/2}\mathbf{D}^{-1/2}-\mathbf{I}\|_{2}+\|\mathbf{I}\|_{2}\leq
C\sqrt{\frac{\log(n)}{w_{\min}}}+1$ w.h.p. Using the above facts and denoting
$\delta=C\sqrt{\frac{\log(n)}{w_{\min}}}$ we obtain

$\displaystyle\|T_{2}\|_{2}$
$\displaystyle\leq\left(\|\mathbf{D}^{\frac{1}{2}}\mathbf{W}^{-\frac{1}{2}}\|_{2}\|\widetilde{\mathbf{R}}\|_{2}\|\mathbf{W}^{\frac{1}{2}}\mathbf{D}^{-\frac{1}{2}}-\mathbf{I}\|_{2}+\|\mathbf{D}^{\frac{1}{2}}\mathbf{W}^{-\frac{1}{2}}-\mathbf{I}\|_{2}\|\widetilde{\mathbf{R}}\|_{2}\right)\|\mathbf{v}\|_{2}$
$\displaystyle\leq
C(\delta(\delta+1)\frac{1}{1-\alpha}+\delta)\frac{1}{1-\alpha}\sqrt{\frac{w_{\max}}{nw_{\min}}}$
(22) $\displaystyle\leq C\delta\sqrt{\frac{w_{\max}}{nw_{\min}}}\mbox{w.h.p.}$
(23)

Hence we have $\|T_{2}\|_{1}\leq\sqrt{n}\|T_{2}\|_{2}\leq
C\delta\sqrt{\frac{w_{\max}}{w_{\min}}}$ w.h.p., which from our assumptions is
$o(1).$ Here in (22) we used the fact that

$\|\widetilde{\mathbf{R}}\|_{2}=\|\mathbf{W}^{1/2}\left(\mathbf{I}-\alpha\mathbf{Q}\right)^{-1}\mathbf{W}^{-1/2}\|_{2}\leq\sqrt{\frac{w_{\max}}{w_{\min}}}\|\mathbf{I}-\alpha\mathbf{Q}\|_{2}\leq\frac{1}{1-\alpha}\sqrt{\frac{w_{\max}}{w_{\min}}}\leq
C,$

and that $\|\mathbf{v}\|_{2}\leq C/\sqrt{n},$ for some $C.$ ∎ Remark: This
method of proof can be extended to similar models like the Stochastic Block
Model with multiple communities and their generalizations, e.g., Random Dot
Product Graphs [2].

##  6 Experimental Results

Figure 1: Log-log plot of maximum normalized error for ER and Chung-Lu graphs

In this section, we provide experimental evidence to further illustrate the
analytic results obtained in the previous sections. In particular, we
simulated ER graphs with $p_{n}=C\frac{\log^{7}(n)}{n}$ and Chung-Lu graphs
with the degree vector $w$ sampled from a geometric distribution so that the
average degree $\overline{w}=cn^{1/3},$ clipped such that
$w_{\max}=7w_{\min}$, for various values of graph size, and plotted the
maximum of normalized error $\widetilde{\delta}$ and TV distance error
$\left\lVert\delta\right\rVert_{1}$, respectively, in Figures 1 and 2. As
expected, both these errors decay as functions of $n,$ which illustrates that
the PageRank vector does converge to the asymptotic value.

Figure 2: Log-log plot of TV distance error for ER and Chung-Lu graphs

In the spirit of further exploration, we have also conducted simulations on
power-law graphs with exponent $\beta=4$ using the Chung-Lu graph model with
$w_{i}=ci^{-1/(\beta-1)},$ for $i_{0}\leq i\leq n+i_{0}$ with

$c=\frac{\beta-2}{\beta-1}dn^{1/(\beta-1)},$
$i_{0}=n\left[\frac{d(\beta-1}{m(\beta-2)}\right]$

Please refer to [15] for details. We set max degree $m=n^{1/3}$ and average
degree $d=n^{1/6}.$ In Figure 3 we observe that for this graph the max-norm of
the relative error does not converge to zero. On the other hand the TV-norm
seems to converge to zero with graph size, albeit very slowly. Note that these
graphs satisfy Property 2 [15], but they do not satisfy Property 1. Therefore
at this point, it is not possible to conclude whether the assumption of
bounded variation of degrees is necessary for the convergence to hold. It
might be interesting to investigate in detail the asymptotic behavior of
PageRank in undirected power-law graphs.

Figure 3: Log-log plot of TV distance and maximum error for power-law graphs
Figure 4: Log-log plot of TV distance and maximum relative error for ER-graph
when $v=e_{1}$

Furthermore, we also see that in the case $\mathbf{v}=\mathbf{e}_{i},$ the
standard unit vector, for some $i$ we do not have the conjectured convergence,
as can be seen on Figure 4 in the case of ER graphs. It can also be seen from
our analysis that if $v_{k}=1$ for some $k,$ the quantity
$\left\lVert\widetilde{Q}D^{-1/2}v\right\rVert_{\infty},$ becomes:

$\max_{i}\left|\sum_{j}\left(\frac{A_{ij}}{\sqrt{d_{i}d_{j}}}-\frac{\sqrt{d_{i}d_{j}}}{\sum_{l}d_{l}}\right)v_{j}/\sqrt{d_{j}}\right|=\max_{i}\frac{1}{\sqrt{d_{i}}d_{k}}\left|A_{ik}-\frac{d_{i}d_{k}}{\sum_{l}d_{l}}\right|,\vspace{-0.1cm}$

which is $O\left(\frac{1}{\sqrt{w_{\min}}w_{k}}\right)$ and does not fall
sufficiently fast. We simulated an SBM matrix with two communities of equal
size, with $p=0.1$ and $q=0.01.$ In Figure 5 we plot the maximum normalized
error and the TV-distance error against graph size on a log-log plot. As
expected both errors go to zero for large graph sizes.

Figure 5: Log-log plot of maximum normalized error and TV-distance error for
an SBM graph

##  7 Conclusions

In this work, we have shown that when the size of a graph tends to infinity,
the PageRank vector lends itself to be approximated by a mixture of the
preference vector and the degree distribution, for a class of undirected
random graphs including the Chung-Lu graph. We expect that these findings will
shed more light on the behaviour of PageRank on undirected graphs, and
possibly help to optimize the PageRank operation, or suggest further
modifications to better capture local graph properties. We also obtain an
asymptotic expression for the PageRank on SBM graphs. It is seen that this
asymptotic expression contains information about community partitioning in the
simple case of SBM with equal-sized communities. It would be interesting to
study the implications of our results for community detection algorithms.

## Acknowledgements

We would like to thank Nelly Litvak for stimulating discussions on the topic
of the paper. The work of K. Avrachenkov and A. Kadavankandy was partly funded
by the French Government (National Research Agency, ANR) through the
“Investments for the Future” Program reference #ANR-11-LABX-0031-01 and the
work of L. Ostroumova Prokhorenkova and A. Raigorodskii was supported by
Russian Science Foundation (# 16-11-10014).

## References

  * [1] Andersen, R., Chung, F., and Lang, K. Local graph partitioning using pagerank vectors. In Proceedings of IEEE FOCS, 2006.
  * [2] Athreya, A., Priebe, C. E., Tang, M., Lyzinski, V., Marchette, D. J., and Sussman, D. L. (2013). A limit theorem for scaled eigenvectors of random dot product graphs. Sankhya A, 1-18.
  * [3] Avrachenkov, K., Cottatellucci, L., and Kadavankandy, A. Spectral properties of random matrices for stochastic block model. In Proceedings of WiOpt Workshop PhysComNet, 2015.
  * [4] Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S.K., and Smirnova, E. Pagerank based clustering of hypertext document collections. In _Proceedings of ACM SIGIR_ , pp. 873–874, 2008.
  * [5] Avrachenkov, K., Gonçalves, P., Mishenin, A., and Sokol, M. Generalized optimization framework for graph-based semi-supervised learning. In _Proceedings of SIAM Conference on Data Mining_ , vol. 9, 2012.
  * [6] Avrachenkov, K., and Lebedev, D. PageRank of scale-free growing networks. Internet Mathematics, 3(2), 207-231, 2006.
  * [7] Bhatia, R. Matrix analysis. Springer Science and Business Media, vol. 169, 2013.
  * [8] Billingsley, P. Probability and measure. John Wiley & Sons, 2008.
  * [9] Boudin, F. A comparison of centrality measures for graph-based keyphrase extraction. In Proceedings of the International Joint Conference on Natural Language Processing (IJCNLP), 2013.
  * [10] Chen, N., Litvak, N., and Olvera-Cravioto, M. PageRank in scale-free random graphs. In Proceedings of WAW, 2014.
  * [11] Chen, N., Litvak, N., and Olvera-Cravioto, M. Generalized PageRank on directed configuration networks. Random Structures & Algorithms 2016.
  * [12] Chung, F. A local graph partitioning algorithm using heat kernel PageRank. In Proceedings of WAW 2009.
  * [13] Chung, F. Spectral graph theory. American Mathematical Soc, v.92, 1997.
  * [14] Chung, F., and Lu, L. The average distances in random graphs with given expected degrees. PNAS, v.99(25), 15879-15882, 2002.
  * [15] Chung, F., Lu, L., and Vu, V. Spectra of random graphs with given expected degrees. PNAS, v.100(11), 6313-6318, 2003.
  * [16] Chung, F., and Radcliffe, M. On the spectra of general random graphs. The electronic journal of combinatorics, 18(1), 2011.
  * [17] Condon A. and Karp R. Algorithms for graph partitioning on the planted partition model, Random Structures and Algorithms, vol. 18, 2001, pp.116–140.
  * [18] Ding, C., He, X., Husbands, P., Zha, H., and Simon, H.D. PageRank, HITS and a unified framework for link analysis. In Proceedings of ACM SIGIR, 2002.
  * [19] Erdős, P., and Rényi, A. On random graphs. Publicationes Mathematicae Debrecen, v.6, 290-297, 1959.
  * [20] Fortunato, S., Boguna, M., Flammini, A., and Menczer, F. Approximating PageRank from in-degree. In Proceedings of WAW, 2008.
  * [21] Gkorou, D., Vinko, T., Pouwelse, J., and Epema, D. Leveraging node properties in random walks for robust reputations in decentralized networks. In Proceedings of IEEE Peer-to-Peer Computing (P2P), 2013.
  * [22] Haveliwala, T.H. Topic-sensitive pagerank. In Proceedings of WWW, 517-526, 2002.
  * [23] Heimlicher, S., Lelarge M., and Massoulié, L. Community detection in the labelled stochastic block model. arXiv preprint arXiv:1209.2910 (2012).
  * [24] Holland, Paul W., Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks 5.2 (1983): 109-137.
  * [25] Horn, R.A., and Johnson, C.R. Matrix analysis. Cambridge university press, 2012.
  * [26] Kamvar, S.D., Schlosser, M.T., and H. Garcia-Molina, H. The eigentrust algorithm for reputation management in p2p networks. In Proceedings of WWW, 2003.
  * [27] Karrer, B. and Newman M.E.J. Stochastic blockmodels and community structure in networks. Physical Review E 83.1 (2011): 016107.
  * [28] Langville, A.N., and Meyer, C.D. Deeper inside pagerank. Internet Mathematics, 1(3), 335-380, 2004.
  * [29] Litvak, N., Scheinhardt, W. R., and Volkovich, Y. In-degree and PageRank: Why do they follow similar power laws? Internet mathematics, 4(2-3), 175-198, 2007.
  * [30] Levin, D.A., Peres, Y., and Wilmer, E.L. Markov chains and mixing times. American Mathematical Soc., 2009.
  * [31] Page, L., Brin, S., Motwani, R., and Winograd, T. PageRank: Bringing order to the web. Stanford Digital Libraries Working Paper, v.72, 1997.
  * [32] Perra, N. and Fortunato, S. Spectral centrality measures in complex networks. Phys. Rev. E 78, 036107, 2008.
  * [33] Rohe, K., Chatterjee, S. and Yu, B. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics (2011): 1878-1915.
  * [34] Tropp, Joel A. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12.4 (2012): 389-434.
  * [35] Vadhan, S. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, v.7(1-3), pp.1-336, Now publishers, 2012.
  * [36] Volkovich, Y., and Litvak, N. Asymptotic analysis for personalized web search. Adv. Appl. Prob., 42(2), 577-604, 2010.
  * [37] Yeh, E., Ramage, D., Manning, C. D., Agirre, E., and Soroa, A. WikiWalk: random walks on Wikipedia for semantic relatedness. In Proceedings of the Workshop on Graph-based Methods for Natural Language Processing, 2009.
  * [38] Zhao, Y., Levina E., and Zhu J. Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics (2012): 2266-2292.

##  Appendix 0.A Proof of Lemma 6

From Lemma 1, we have for Chung-Lu graphs that: $d_{i}=w_{i}(1+\epsilon_{i})$,
where $\eta\equiv\max_{i}\epsilon_{i}=o(1)$ with high probability. In the
proof we assume explicitly that $v_{i}=1/n,$ but the results hold in the
slightly more general case where $v_{i}=O(1/n)$ uniformly $\forall i$, i.e.,
$\exists K$ such that $\max_{i}nv_{i}\leq K.$ It can be verified easily that
all the bounds that follow hold in this more general setting. The event
$\\{\eta=o(1)\\},$ holds w.h.p. asymptotically from Lemma 1. In this case, we
have

$\sum_{j}\left(\frac{A_{ij}}{\sqrt{d_{i}d_{j}}}-\frac{\sqrt{d_{i}d_{j}}}{\sum_{i}d_{i}}\right)\frac{v_{j}}{\sqrt{d_{j}}}=\sum_{j}\left(\frac{A_{ij}}{\sqrt{d_{i}d_{j}}}-\frac{\sqrt{d_{i}d_{j}}}{\sum_{k}d_{k}}\right)\frac{v_{j}}{\sqrt{w_{j}}}(1+\varepsilon_{j})$

where $\varepsilon_{j}$ is the error of convergence, and we have
$\max_{j}\varepsilon_{j}=O(\eta)$. Therefore,

$\displaystyle\left\lVert\widetilde{\mathbf{Q}}\mathbf{v}^{\prime}\right\rVert_{\infty}$
$\displaystyle\leq\left\lVert\widetilde{\mathbf{Q}}\mathbf{q}\right\rVert_{\infty}+\max_{i}\varepsilon_{i}\left\lVert\widetilde{\mathbf{Q}}\mathbf{q}\right\rVert_{\infty}$
$\displaystyle\leq\left\lVert\widetilde{\mathbf{Q}}\mathbf{q}\right\rVert_{\infty}(1+o(1))\quad\mbox{w.h.p.},$
(24)

where $\mathbf{q}$ is a vector such that $q_{i}=\frac{nv_{i}}{\sqrt{w_{i}}}.$
Furthermore, we have w.h.p.

$\displaystyle\frac{A_{ij}}{\sqrt{d_{i}d_{j}}}-\frac{\sqrt{d_{i}d_{j}}}{\sum_{k}d_{k}}$
$\displaystyle=\frac{A_{ij}}{\sqrt{w_{i}(1+\epsilon_{i})w_{j}(1+\epsilon_{j})}}-\frac{\sqrt{w_{i}(1+\epsilon_{i})w_{j}(1+\epsilon_{j})}}{\sum_{k}w_{k}(1+\epsilon_{k})}$
$\displaystyle=\frac{A_{ij}}{\sqrt{w_{i}w_{j}}}\left(1+O(\epsilon_{i})+O(\epsilon_{j})\right)-\frac{\sqrt{w_{i}w_{j}}}{\sum_{k}w_{k}}\left(\frac{1+O(\epsilon_{i})+O(\epsilon_{j})}{1+O(\eta)}\right)$
$\displaystyle=\left(\frac{A_{ij}}{\sqrt{w_{i}w_{j}}}-\frac{\sqrt{w_{i}w_{j}}}{\sum_{k}w_{k}}\right)(1+\delta_{ij}),$

where $\delta_{ij}$ is the error in the $ij^{\text{th}}$ term of the matrix
and $\delta_{ij}=O(\eta)$ uniformly, so that $\max_{ij}\delta_{ij}=o(1)$
w.h.p. Consequently, defining
$\widetilde{\overline{Q}}_{ij}=\frac{A_{ij}}{\sqrt{w_{i}w_{j}}}-\frac{\sqrt{w_{i}w_{j}}}{\sum_{k}w_{k}}$
we have:

$\displaystyle\left\lVert\widetilde{\mathbf{Q}}\mathbf{q}\right\rVert_{\infty}$
$\displaystyle\leq\left\lVert\widetilde{\overline{\mathbf{Q}}}\mathbf{q}\right\rVert_{\infty}+\max_{i}|\sum_{j}\widetilde{\overline{Q}}_{ij}\delta_{ij}q_{j}|$
$\displaystyle\leq\left\lVert\widetilde{\overline{\mathbf{Q}}}\mathbf{q}\right\rVert_{\infty}+O(\eta)\max_{i}\frac{1}{\sqrt{w_{\min}}}\sum_{j}|\widetilde{\overline{\mathbf{Q}}}_{ij}|$
$\displaystyle\leq\left\lVert\widetilde{\overline{\mathbf{Q}}}\mathbf{q}\right\rVert_{\infty}+o(1)\frac{1}{\sqrt{w_{\min}}}\left(C\sqrt{\frac{w_{\max}}{w_{\min}}}+\frac{w_{\max}}{w_{\min}}\right)$
(25)
$\displaystyle\leq\left\lVert\widetilde{\overline{\mathbf{Q}}}\mathbf{q}\right\rVert_{\infty}+o(1/\sqrt{w_{\min}})$
(26)

where in (25) we used the fact the $O(\eta)$ is a uniform bound on the error
and it is $o(1)$ w.h.p. and $\max_{j}q_{j}\leq\frac{1}{\sqrt{w_{\min}}}.$ In
(25) we also used the fact that

$\displaystyle\max_{i}\sum_{j}|\widetilde{\overline{Q}}_{ij}|$
$\displaystyle\leq\max_{i}\sum_{j}\frac{A_{ij}}{\sqrt{w_{i}w_{j}}}+\sum_{j}\frac{\sqrt{w_{i}w_{j}}}{\sum_{k}w_{k}}$
$\displaystyle\leq\max_{i}\frac{1}{\sqrt{w_{\min}}}\frac{d_{i}}{\sqrt{w_{i}}}+\max_{i}\frac{\sqrt{w_{i}w_{\max}}}{w_{\min}}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{(a)}}{\leq}}C\sqrt{\frac{w_{i}}{w_{\min}}}+\frac{w_{\max}}{w_{\min}}$
$\displaystyle\leq
C\sqrt{\frac{w_{\max}}{w_{\min}}}+\frac{w_{\max}}{w_{\min}},$

where $C$ is some constant. In (a) above we used the fact that w.h.p.
$d_{i}=w_{i}(1+o(1)),$ by Lemma 1, hence $\exists C$ such that $\forall n$
large enough $d_{i}\leq Cw_{i}.$

Now we proceed to bound
$\left\lVert\widetilde{\overline{\mathbf{Q}}}\mathbf{q}\right\rVert_{\infty}.$
Substituting for $q_{i}=\frac{1}{\sqrt{w_{i}}},$ we get

$\displaystyle\sum_{j}\frac{1}{\sqrt{w_{j}}}\left(\frac{A_{ij}}{\sqrt{w_{i}w_{j}}}-\frac{\sqrt{w_{i}w_{j}}}{\sum_{k}w_{k}}\right)=\sum_{j}\frac{1}{w_{j}\sqrt{w_{i}}}\left(A_{ij}-\frac{w_{i}w_{j}}{\sum_{i}w_{i}}\right)$
$\displaystyle\equiv\frac{1}{\sqrt{w_{i}}}X_{i}.$ (27)

We seek to bound $\max_{i}|X_{i}|$:

$X_{i}=\sum_{j}\frac{1}{w_{j}}\left(A_{ij}-\frac{w_{i}w_{j}}{\sum_{i}w_{i}}\right).$

Furthermore,
$\mathbb{E}(X_{i}^{2})=\sum_{j}\frac{1}{w_{j}^{2}}\mathbb{E}(A_{ij}-p_{ij})^{2},$
with $p_{ij}=\frac{w_{i}w_{j}}{\sum w_{i}}.$ So,
$\mathbb{E}(X_{i}^{2})=\sum_{j}\frac{1}{w_{j}^{2}}p_{ij}(1-p_{ij})\leq\frac{w_{i}}{\sum_{i}w_{i}}\sum_{j}\frac{1}{w_{j}}\leq
n\frac{p_{i}}{w_{\min}},$ where $p_{i}=\frac{w_{i}}{\sum_{i}w_{i}},$ and
$\frac{A_{ij}}{w_{j}}\leq 1/w_{\min}.$ Therefore using Bernstein Concentration
Lemma for $\epsilon<n\max_{i}p_{i}$:

$\displaystyle\mathbb{P}\left(\max_{i}|\sum_{j}(A_{ij}-p_{ij})/w_{j}|\geq\epsilon\right)$
$\displaystyle\leq
n\max_{i}\exp(-\frac{\epsilon^{2}}{2(p_{i}n/w_{\min})+\epsilon/w_{\min}})$
$\displaystyle\leq
n\max_{i}\exp(-\frac{w_{\min}\epsilon^{2}}{2(np_{i}+\epsilon)})$
$\displaystyle\leq n\exp(-\epsilon^{2}w_{\min}/(4n\max_{i}p_{i}))$
$\displaystyle\leq n\exp(\frac{-\epsilon^{2}\text{vol}w_{\min}}{4w_{\max}n}),$
(28)

where $\frac{\text{vol}}{n}=\frac{\sum_{i}w_{i}}{n}\geq w_{\min}.$ It can be
verified that when $\epsilon=\frac{1}{(\overline{w})^{\alpha}}$, for some
$\alpha>0,$ the RHS of (28) can be upper bounded by $n^{-(\gamma K-1)},$ if
$\overline{w}\geq(\gamma\log(n))^{\frac{1}{1-2\alpha}},$ for some large enough
$\gamma$, which can be easily satisfied if $w_{\min}\gg O(\log^{c}(n)),$ for
some $c>1,$ where $K$ is a constant such that $w_{\max}\leq Kw_{\min}.$ Thus,
finally, from (27) and (26) we have
$\left\lVert\widetilde{\mathbf{Q}}\mathbf{q}\right\rVert_{\infty}=o(1/\sqrt{w_{\min}}),$
w.h.p., and therefore from (24), we get
$\left\lVert\widetilde{\mathbf{Q}}\mathbf{v}^{\prime}\right\rVert_{\infty}=o(1/\sqrt{w_{\min}}).$

∎

##  Appendix 0.B Proof of Lemmas in Section 5

###  0.B.1 Proof of Lemma 8

The proof is an application of Bernstein’s Concentration Lemma. Note that for
$1\leq i\leq m,$ $D_{i}=\sum_{j}A_{ij}$ . Here the mean degree
$\mathbb{E}(D_{i})=mp+(n-m)q=t_{1},$ and the variance
$B^{2}_{n}=mp(1-p)+(n-m)q(1-q)\leq t_{1}$ for $i\leq m.$ Similarly for $i>m,$
$\mathbb{E}(D_{i})=mq+(n-m)p=t_{2}$ is and variance $\mbox{Var}[{D_{i}}]\leq
t_{2}.$ Then, the minimum average degree $w_{\min}=\min(t_{1},t_{2}).$ By
Bernstein’s Lemma, for $\epsilon=C\sqrt{\frac{\log(n)}{w_{\min}}},$

$\displaystyle\mathbb{P}\left(\max_{1\leq i\leq m}|D_{i}-t_{1}|\geq\epsilon
t_{1}\right)$ $\displaystyle\leq
2m\exp\left(\frac{-\epsilon^{2}t_{1}^{2}}{2(t_{1}\epsilon/3+t_{1})}\right)$
$\displaystyle=2m\exp\left(\frac{-\epsilon^{2}t_{1}}{1+\epsilon/3}\right)$
$\displaystyle=O(n^{-c}),$

for some $c.$ Hence $\max_{1\leq i\leq
m}\left|\frac{D_{i}-t_{1}}{t_{1}}\right|\leq C\sqrt{\frac{\log(n)}{w_{\min}}}$
w.h.p. Similarly

$\max_{1+m\leq i\leq n/2}\left|\frac{D_{i}-t_{2}}{t_{2}}\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}},\mbox{ w.h.p}.$

Combining the two bounds above we get,

$\max_{1\leq i\leq n}\left|\frac{D_{i}}{\mathbb{E}(D_{i})}-1\right|\leq
C\sqrt{\frac{\log(n)}{w_{\min}}},\text{ w.h.p}.$ (29)

∎

###  0.B.2 Proof of Lemma 9

To prove Lemma 9 we need the following lemma on the spectral norm of the
difference between the adjacency matrix and its mean.

###### Lemma 10

For an SBM matrix $G(m,n-m,p,q)$ with adjacency matrix $\mathbf{A}$ and
$\overline{\mathbf{A}}=\mathbb{E}(\mathbf{A}),$ there exists a constant $K$
s.t.

$\|\mathbf{A}-\overline{\mathbf{A}}\|_{2}\leq K\sqrt{\log(n)w_{max}},\mbox{
w.h.p.},$

where $w_{max}=\max(m,n-m)p+\min(m,n-m)q$ is the maximum average degree, if
$w_{\max}=\mathrm{\omega}(\log^{3}(n)).$

To prove this Lemma we need the Matrix Bernstein Concentration result, which
we state below for the sake of completeness:

###### Lemma 11

[34, Theorem 1.4]. Let $\mathbf{S}_{1},\mathbf{S}_{2},\ldots\mathbf{S}_{t}$ be
independent random matrices with common dimension $d_{1}\times d_{2}.$ Assume
that each matrix has bounded deviation from its mean, i.e.,

$\|\mathbf{S}_{k}-\mathbb{E}(\mathbf{S}_{k})\|\leq R,\text{ for each
}k=1,\ldots n.$

Let $\mathbf{Z}=\sum_{k=1}^{t}\mathbf{S}_{k}$ and introduce a variance
parameter

$\sigma^{2}_{\mathbf{Z}}=\max\left\\{\|\mathbb{E}\left((\mathbf{Z}-\mathbb{E}(\mathbf{Z}))(\mathbf{Z}-\mathbb{E}(\mathbf{Z}))^{H}\right)\|,\|\mathbb{E}\left((\mathbf{Z}-\mathbb{E}(\mathbf{Z}))^{H}(\mathbf{Z}-\mathbb{E}(\mathbf{Z}))\right)\|\right\\}.$

Then

$\mathbb{P}\\{\|\mathbf{Z}-\mathbb{E}(\mathbf{Z})\|>t\\}\leq(d_{1}+d_{2}).\exp\left(\frac{-t^{2}/2}{\sigma^{2}_{\mathbf{Z}}+Rt/3}\right),$
(30)

$\text{ for all }t\geq 0.$

Proof of Lemma 10: With $\mathbf{Z}=\mathbf{A},$ in Lemma 11, we can decompose
$\mathbf{Z}$ as sums of Hermitian matrices
$\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}},$ $\mathbf{Z}=\sum_{1\leq
i^{{}^{\prime}}<j^{{}^{\prime}}\leq
n}\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}}$ such that:

$(\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}})_{ij}=\begin{cases}A_{i^{{}^{\prime}}j^{{}^{\prime}}}\text{
if }i=i^{{}^{\prime}},j=j^{{}^{\prime}},\\\
A_{i^{{}^{\prime}}j^{{}^{\prime}}}\text{ if
}i=j^{{}^{\prime}},j=i^{{}^{\prime}},\\\ 0\text{ otherwise.}\end{cases}$ (31)

Notice that if $\mathbf{x}\neq 0,$
$\|(\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}}-\mathbb{E}(\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}}))\mathbf{x}\|_{2}=|2x_{i^{{}^{\prime}}}x_{j^{{}^{\prime}}}(A_{i^{{}^{\prime}}j^{{}^{\prime}}}-\mathbb{E}(A_{i^{{}^{\prime}}j^{{}^{\prime}}}))|<|x_{i^{{}^{\prime}}}^{2}+x_{j^{{}^{\prime}}}^{2}|.$
Consequently
$\|\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}}-\mathbb{E}(\mathbf{S}_{i^{{}^{\prime}}j^{{}^{\prime}}})\|_{2}<1,$
giving $R=1$ in the statement of Lemma 30. Let
$\mathbf{Y}=\mathbb{E}\left((\mathbf{Z}-\mathbb{E}\mathbf{Z})^{H}(\mathbf{Z}-\mathbb{E}\mathbf{Z})\right),$
then

$Y_{ij}=\begin{cases}v_{1}&\text{ if }i=j,i\leq m,\\\ v_{2}&\text{ if
}i=j,i>m,\\\ 0&\text{ otherwise},\end{cases}$ (32)

where $v_{1}=mp(1-p)+q(1-q)(n-m),v_{2}=(n-m)p(1-p)+mq(1-q).$ Therefore
$\sigma^{2}_{\mathbf{Z}}=\max(v_{1},v_{2})=\max(n-m,m)p+\min(n-m,m)q=\sigma^{2}.$
By our assumptions on the probabilities,
$\sigma^{2}=\mathrm{\omega}(\log^{3}(n)).$ Thus it follows that

$\displaystyle\mathbb{P}(\|\mathbf{A}-\overline{\mathbf{A}}\|\geq t\sigma)$
$\displaystyle\leq
2n\exp\left(\frac{-t^{2}\sigma^{2}}{2\sigma^{2}+t\sigma/3}\right)$
$\displaystyle\leq 2n\exp(-t^{2}/3),$

if $\sigma>t.$ The RHS is $O(n^{-c})$ if $t>\sqrt{r\log(n)},$ for some $r.$
∎Finally we are in a position to prove Lemma 9
Proof of Lemma 9: We prove this result in two steps. First we show that

$\|\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|_{2}=C\sqrt{\frac{\log(n)}{w_{\min}}}=o(1).$
(33)

Observe that

$\displaystyle\|\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}-\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}\|_{2}=\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|$
$\displaystyle=\|\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}+\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}\mathbf{D}^{1/2}\mathbf{W}^{-1/2}\|_{2}$
$\displaystyle=\|(\mathbf{I}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2})\mathbf{Q}+\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\mathbf{Q}(\mathbf{I}-\mathbf{D}^{1/2}\mathbf{W}^{-1/2})\|_{2}$
$\displaystyle\leq\delta+(1+\delta)\delta,$

where $\delta=\max_{i}\left|\frac{d_{i}}{w_{i}}-1\right|.$ In the last line we
used the fact that
$\|\mathbf{Q}\|_{2}=1,\|\mathbf{I}-\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\|_{2}=\max_{i}\left|\sqrt{\frac{d_{i}}{w_{i}}}-1\right|\leq\max_{i}\left|\frac{d_{i}}{w_{i}}-1\right|$
and

$\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}\|_{2}\leq\|\mathbf{W}^{-1/2}\mathbf{D}^{1/2}-\mathbf{I}\|_{2}+\|\mathbf{I}\|_{2}\leq\delta+1.$

By Lemma 8, $\delta\leq C\sqrt{\frac{\log(n)}{w_{\min}}}=o(1)$ w.h.p. Next we
show that

$\|\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}-\mathbf{W}^{-1/2}\overline{\mathbf{A}}\mathbf{W}^{-1/2}\|_{2}\leq\frac{C\sqrt{\log(n)w_{\max}}}{w_{\min}}=o(1).$
(34)

Now using Lemma 10 we have

$\displaystyle\|\mathbf{W}^{-1/2}\mathbf{A}\mathbf{W}^{-1/2}-\mathbf{W}^{-1/2}\overline{\mathbf{A}}\mathbf{W}^{-1/2}\|$
$\displaystyle\leq\frac{\|\mathbf{A}-\overline{\mathbf{A}}\|_{2}}{w_{\min}}$
$\displaystyle\leq\frac{c\sqrt{\log(n)w_{\max}}}{w_{\min}}$
$\displaystyle=o(1),\mbox{ w.h.p.},$

if $w_{\min}=\mathrm{\omega}(\sqrt{\log(n)w_{\max}}),$ which is satisfied when
$w_{\max}\leq Cw_{\min}$ for some $C,$ and
$w_{\max}=\mathrm{\omega}(\log^{3}(n)).$ The result of Lemma 9 then follows
from (33) and (34) by applying the triangular inequality.∎