# Central limit theorem for the principal eigenvalue
and eigenvector of Chung-Lu random graphs

Pierfrancesco Dionigi  Mathematical Institute, Leiden University, P.O. Box
9512, 2300 RA Leiden, The Netherlands<EMAIL_ADDRESS>,  Diego
Garlaschelli  Lorentz Institute for Theoretical Physics, Leiden University,
P.O. Box 9504, 2300 RA Leiden, The Netherlands & IMT School for Advanced
Studies, Piazza S. Francesco 19, 55100 Lucca, Italy
<EMAIL_ADDRESS>,  Rajat Subhra Hazra  ,  Frank den
Hollander  Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA
Leiden, The Netherlands<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Michel Mandjes  Korteweg-de Vries Institute,
University of Amsterdam, P.O. Box 94248, 1090 GE Amsterdam, The Netherlands
<EMAIL_ADDRESS>
###### Abstract.

A Chung-Lu random graph is an inhomogeneous Erdős-Rényi random graph in which
vertices are assigned average degrees, and pairs of vertices are connected by
an edge with a probability that is proportional to the product of their
average degrees, independently for different edges. We derive a central limit
theorem for the principal eigenvalue and the components of the principal
eigenvector of the adjacency matrix of a Chung-Lu random graph. Our derivation
requires certain assumptions on the average degrees that guarantee
connectivity, sparsity and bounded inhomogeneity of the graph.

###### Key words and phrases:

Chung-Lu random graph; adjacency matrix; principal eigenvalue and eigenvector;
central limit theorem

###### 2000 Mathematics Subject Classification:

60B20,60C05, 60K35

PD, RSH, FdH and MM are supported by the Netherlands Organisation for
Scientific Research (NWO) through the Gravitation-grant NETWORKS-024.002.003.
DG is supported by the Dutch Econophysics Foundation (Stichting Econophysics,
Leiden, The Netherlands) and by the European Union - Horizon 2020 Program
under the scheme “INFRAIA-01-2018-2019 - Integrating Activities for Advanced
Communities”, Grant Agreement n.871042, “SoBigData++: European Integrated
Infrastructure for Social Mining and Big Data Analytics”.

##  1\. Introduction, main results and discussion

###  1.1. Introduction

The spectral properties of adjacency matrices play an important role in
various areas of network science. In the present paper we consider an
inhomogeneous version of the Erdős-Rényi random graph called the _Chung-Lu
random graph_ and we derive a central limit theorem for the principal
eigenvalue and eigenvector of its adjacency matrix.

####  1.1.1. Setting

Recall that the homogeneous Erdős-Rényi random graph has vertex set
$[n]=\\{1,\ldots,n\\}$, and each edge is present with probability $p$ and
absent with probability $1-p$, independently for different edges, where
$p\in(0,1)$ may depend on $n$ (in what follows we often suppress the
dependence on $n$ from the notation; the reader is however warned that most
quantities depend on $n$). The average degree is the same for every vertex and
equals $(n-1)p$ when self-loops are not allowed, and $np$ when self-loops are
allowed (and are considered to contribute to the degrees of the vertices). In
[15] the following generalisation of the Erdős-Rényi random graph is
considered, called the Chung-Lu random graph, with the goal to accommodate
general degrees. Given a sequence of degrees $\vec{d}_{n}=(d_{i})_{i\in[n]}$,
consider the random graph $\mathcal{G}_{n}(\vec{d}_{n})$ in which to each pair
$i,j$ of vertices an edge is assigned independently with probability
$p_{ij}=d_{i}d_{j}/m_{1}$, where $m_{1}=\sum_{i=1}^{n}d_{i}$ (for
computational simplicity we allow self-loops). Here, the degrees can act as
vertex weights. Vertices with low weights are more likely to have less
neighbours than vertices with high weights which act as hubs (see [33, Chapter
6] for a general introduction to generalised random graphs). If
$m_{\infty}^{2}\leq m_{1}$ with $m_{\infty}=\max_{i\in[n]}d_{i}$, then
$p_{ij}\leq 1$ for all $i,j\in[n]$, and the sequence $\vec{d}_{n}$ is
_graphical_. Note that in $\mathcal{G}_{n}(\vec{d}_{n})$ the _expected_ degree
of vertex $i$ is $d_{i}$. The classical Erdős-Rényi random graph (with self-
loops) corresponds to $d_{i}=np$ for all $i\in[n]$.

####  1.1.2. Principal eigenvalue and eigenvector

The largest eigenvalue of the adjacency matrix $A$ and its corresponding
eigenvector, written as $(\lambda_{1},v_{1})$, contain important information
about the random graph. Several community detection techniques depend on a
proper understanding of these quantities [32], [25], [1], which in turn play
an important role for various measures of network centrality [26], [27] and
for the properties of dynamical processes (such as the spread of an epidemic)
taking place on networks [12, 28]. For Erdős-Rényi random graphs, it was shown
in [24] that _with high probability_ (whp) $\lambda_{1}$ scales like

$\lambda_{1}\sim\max\\{\sqrt{D_{\infty}},np\\},\qquad n\to\infty,$ (1.1)

where $D_{\infty}$ is the maximum degree. This result was partially extended
to $\mathcal{G}_{n}(\vec{d}_{n})$ in [16], and more recently to a class of
inhomogeneous Erdős-Rényi random graphs in [5], [6]. For a related discussion
on the behaviour of $(\lambda_{1},v_{1})$ in real-world networks, see [12,
28]. In the present paper we analyse the fluctuations of
$(\lambda_{1},v_{1})$. We will be interested specifically in the case where
$\lambda_{1}$ is detached from the bulk, which for Erdős-Rényi random graphs
occurs when $\lambda_{1}\sim np$ whp, and for Chung-Lu random graphs when
$\lambda_{1}\sim m_{2}/m_{1}$, where $m_{2}=\sum_{i\in[n]}d_{i}^{2}$. Note
that the quotient $m_{2}/m_{1}$ arises from the fact that the average
adjacency matrix is rank one and that its only non-zero eigenvalue is
$m_{2}/m_{1}$. Such rank-one perturbations of a symmetric matrix with
independent entries became prominent after the work in [4]. Later studies
extended this work to finite-rank perturbations [3], [7], [11], [10], [20],
[21]. Erdős-Rényi random graphs differ, in the sense that perturbations live
on a scale different from $\sqrt{n}$. For Chung-Lu random graphs we assume
that $m_{2}/m_{1}\to\infty$.

In the setting of inhomogeneous Erdős-Rényi random graphs, finite-rank
perturbations were studied in [13]. In that paper the connection probability
between between $i$ and $j$ is given by $p_{ij}=\varepsilon_{n}f(i/n,j/n)$,
where $f\colon\,[0,1]^{2}\to[0,1]$ is almost everywhere continuous and of
finite rank, $\varepsilon_{n}\in[0,1]$ and $n\varepsilon_{n}\gg(\log n)^{8}$.
However, for a Chung-Lu random graph with a given degree sequence it is not
always possible to construct an almost everywhere continuous function $f$
independent of $n$ such that $\varepsilon_{n}f(i/n,j/n)=d_{i}d_{j}/m_{1}$. In
the present paper we extend the analysis in [13] to Chung-Lu random graphs by
focussing on $(\lambda_{1},v_{1})$. For Erdős-Rényi random graphs it was shown
in [19], [18] that $\lambda_{1}$ satisfies a central limit theorem (CLT) and
that $v_{1}$ aligns with the unit vector. These papers extend the seminal work
carried out in [22].

####  1.1.3. Chung-Lu random graphs

In the present paper, subject to mild assumptions on $\vec{d}_{n}$, we extend
the CLT for $\lambda_{1}$ from Erdős-Rényi random graphs to Chung-Lu random
graphs, and derive a pointwise CLT for $v_{1}$ as well. It was shown in [16]
that if $m_{2}/m_{1}\gg\sqrt{m_{\infty}}\,(\log n)$, then $\lambda_{1}\sim
m_{2}/m_{1}$ whp, while if $\sqrt{m_{\infty}}\gg(m_{2}/m_{1})(\log n)^{2}$,
then $\lambda_{1}=m_{\infty}$ whp. In fact, examples show that a result
similar to (1.1) does not hold, and that $\lambda_{1}$ does not scale like
$\max\\{m_{2}/m_{1},\sqrt{m_{\infty}}\\}$. These facts clearly show that the
behaviour of $\lambda_{1}$ is controlled by subtle assumptions on the degree
sequence. In what follows we stick to a bounded inhomogeneity regime where
$m_{2}/m_{1}\asymp m_{\infty}$.

The behaviour of $v_{1}$ is interesting and challenging, and is of major
interest for applications. One of the crucial properties to look for in
eigenvectors is the phenomenon of localization versus delocalization. An
eigenvector is called localized when its mass concentrates on a small number
of vertices, and delocalized when its mass is approximately uniformly
distributed on the vertices. The complete delocalization picture for Erdős-
Rényi random graphs was given in [19]. In fact, it was proved that
$\lambda_{1}$ is close to the scaled unit vector in the $\ell_{\infty}$-norm.
In the present paper we do not study localization versus delocalization for
Chung-Lu random graphs in detail, but we do show that in a certain regime
there is strong evidence for delocalization because $v_{1}$ is close to the
scaled unit vector. In [9, Corollary 1.3 ] the authors found that the
eigenvectors of a Wigner matrix with independent standard Gaussian entries are
distributed according to a Haar measure on the orthogonal group, and the
coordinates have Gaussian fluctuations after appropriate scaling. Our work
shows that the coordinate-wise fluctuations hold as well for the principal
eigenvector of the non-centered Chung-Lu adjacency matrix and that they are
Gaussian after appropriate centering and scaling.

####  1.1.4. Outline

In Section 1.2 we define the Chung-Lu random graph, state our assumption on
the degree sequence, and formulate two main theorems: a CLT for the largest
eigenvalue and a CLT for its associated eigenvector. In Section 1.3 we discuss
these theorems and place them in their proper context. Section 2 contains the
proof of the CLT of the eigenvalue and Section 3 studies the properties of the
principal eigenvector.

###  1.2. Main results

####  1.2.1. Set-up

Let $\mathbb{G}_{n}$ be the set of simple graphs with $n$ vertices. Let
$\vec{d}_{n}=(d_{i})_{i\in[n]}$ be a sequence of degrees, such that
$d_{i}\in\mathbb{N}$ for all $i\in[n]$ and abbreviate

$m_{k}=\sum_{i\in[n]}(d_{i})^{k},\qquad m_{\infty}=\max_{i\in[n]}d_{i},\qquad
m_{0}=\min_{i\in[n]}d_{i},$

Note that these numbers depend on $n$, but in the sequel we will suppress this
dependence. For each pair of vertices $i,j$ (not necessarily distinct), we add
an edge independently with probability

$p_{ij}=\frac{d_{i}d_{j}}{m_{1}}.$ (1.2)

The resulting random graph, which we denote by $\mathcal{G}_{n}(\vec{d}_{n})$,
is referred to in the literature as the Chung-Lu random graph. In [15] it was
assumed that $m_{\infty}^{2}\leq m_{1}$ to ensure that $p_{ij}\leq 1$. In the
present paper we need sharper restrictions.

######  Assumption 1.1.

Throughout the paper we need two assumptions on $\vec{d}_{n}$ as $n\to\infty$:

  1. (D1)

Connectivity and sparsity: There exists a $\xi>2$ such that

$(\log n)^{2\xi}\ll m_{\infty}\ll n^{1/2}.$

  2. (D2)

Bounded inhomogeneity: $m_{0}\asymp m_{\infty}$.

$\spadesuit$

The lower bound in Assumption 1.1(D1) guarantees that the random graph is
connected whp and that it is not too sparse. The upper bound is needed in
order to have $m_{\infty}={{\mathrm{o}}}(\sqrt{m_{1}})$, which implies that
(1.2) is well defined. Assumption 1.1(D2) is a restriction on the
inhomogeneity of the model and requires that the smallest and the largest
degree are comparable.

######  Remark 1.2.

The lower bound on $m_{\infty}$ in Assumption 1.1(D1) can be seen as an
adaptation to our setting of the main condition in [16, Theorem 2.1] for the
asymptotics of $\lambda_{1}$. As mentioned in Section 1.1, under the
assumption

$\frac{m_{2}}{m_{1}}\gg\sqrt{m_{\infty}}\,(\log n)^{\xi},$

[16] shows that $\lambda_{1}=[1+{{\mathrm{o}}}(1)]\,m_{2}/m_{1}$ whp. It is
easy to see that the above condition together with Assumption 1.1(D2) gives
the lower bound in Assumption 1.1(D1). $\spadesuit$

######  Remark 1.3.

When $m_{\infty}\ll n^{1/6}$, [33, Theorem 6.19] implies that our results also
hold for the _Generalized Random Graph_ (GRG) model with the same average
degrees. This model is defined by choosing connection probabilities of the
form

$p_{ij}=\frac{d_{i}d_{j}}{m_{1}+d_{i}d_{j}},$

and arises in statistical physics as the _canonical ensemble_ constrained on
the expected degrees, which is also called the _canonical configuration
model_. Note that in the above connection probability, $d_{i}$ plays the role
of a hidden variable, or a Lagrange multiplier controlling the expected degree
of vertex $i$, but does not in general coincide with the expected degree
itself. However, under the assumptions considered here, $d_{i}$ does coincide
with the expected degree asymptotically. The reader can find more about GRG
and their use in [33, Chapter 6], and about their role in statistical physics
in [31]. In the corresponding _microcanonical ensemble_ the degrees are not
only fixed in their expectation but they take a precise deterministic value,
which corresponds to the _microcanonical configuration model_. The two
ensembles were found to be _nonequivalent_ in the limit as $n\to\infty$ [30].
This result was shown to imply a finite difference between the expected values
of the largest eigenvalue $\lambda_{1}$ in the two models [17] when the degree
sequence was chosen to be constant ($d_{i}=d$ for all $i\in[n]$). In this
latter case the canonical ensemble reduces to the Erdős-Rényi random graph
with $p=d/n$, while the microcanonical ensemble reduces to the $d$-regular
random graph model. Although ensemble nonequivalence is not our main focus
here, we will briefly relate some of our results to this phenomenon.
$\spadesuit$

####  1.2.2. Notation

Let $A$ be the adjacency matrix of $\mathcal{G}_{n}(\vec{d}_{n})$ and
$\mathbb{E}[A]$ its expectation. The $(i,j)$-th entry of $\mathbb{E}[A]$
equals to $p_{ij}$ in (1.2). The $(i,j)$-th entry of $A-\mathbb{E}[A]$ is an
independent centered Bernoulli random variable with parameter $p_{ij}$. Let
$\lambda_{1}\geq\ldots\geq\lambda_{n}$ be the eigenvalues of $A$ and let
$v_{1},\ldots,v_{n}$ be the corresponding eigenvectors. The vector $e$ will
the $n\times 1$ row vector given by

$e=\frac{1}{\sqrt{m_{1}}}(d_{1},\cdots,d_{n})^{t},$ (1.3)

where $t$ stands for transpose. It is easy to see that $\mathbb{E}[A]=ee^{t}$.

######  Definition 1.4.

Following [19], we say that an event $\mathcal{E}$ holds _with high
probability_ (whp) when there exist $\xi>2$ and $\nu>0$ such that

$\mathbb{P}(\mathcal{E})\leq\mathrm{e}^{-\nu(\log n)^{\xi}}.$ (1.4)

Note that this is different from the classical notion of whp, because it comes
with a specific rate. We write $\stackrel{{\scriptstyle
w}}{{\longrightarrow}}$ to denote weak convergence as $n\to\infty$, and use
the symbols ${{\mathrm{o}}},\mathrm{O}$ to denote asymptotic order for
sequences of real numbers.

####  1.2.3. CLT for the principal eigenvalue

Our first theorem identifies two terms in the expectation of the largest
eigenvalue, and shows that the largest eigenvalue follows a central limit
theorem.

######  Theorem 1.5.

Under Assumption 1.1, the following hold:

  * (I)

$\mathbb{E}[\lambda_{1}]=\frac{m_{2}}{m_{1}}+\frac{m_{1}m_{3}}{m_{2}^{2}}+{{\mathrm{o}}}(1),\qquad
n\to\infty.$

  * (II)

$\frac{m_{2}}{m_{1}}\left(\frac{\lambda_{1}-\mathbb{E}[\lambda_{1}]}{\sigma_{1}}\right)\stackrel{{\scriptstyle
w}}{{\longrightarrow}}\mathcal{N}(0,2),\qquad n\to\infty,$

where

$\displaystyle\sigma_{1}^{2}=\sum_{i,j}(p_{ij})^{3}(1-p_{ij})\sim\frac{m_{3}^{2}}{m_{1}^{3}},\qquad
n\to\infty.$

####  1.2.4. CLT for the principal eigenvector

Our second theorem shows that the principal eigenvector is parallel to the
normalised degree vector, and is close to this vector in $\ell^{\infty}$-norm.
It also identifies the expected value of the components of the principal
eigenvector, and shows that the components follow a central limit theorem.

######  Theorem 1.6.

Let $\tilde{e}=e\sqrt{m_{1}/m_{2}}$ be the $\ell^{2}$-nomalized degree vector.
Let $v_{1}$ be the eigenvector corresponding to $\lambda_{1}$ and let
$v_{1}(i)$ denote the $i$-th coordinate of $v_{1}$. Under Assumption 1.1, the
following hold:

  * (I)

$\langle v_{1},\tilde{e}\rangle=1+{{\mathrm{o}}}(1)$ as $n\to\infty$ whp.

  * (II)

$\|v_{1}-\tilde{e}\|_{\infty}\leq\mathrm{O}\left(\frac{(\log
n)^{\xi}}{\sqrt{nm_{\infty}}}\right)$ as $n\to\infty$ whp.

  * (III)

$\mathbb{E}[v_{1}(i)]=\frac{d_{i}}{\sqrt{m_{2}}}+\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right)$ as $n\to\infty$.

Moreover, if the lower bound in Assumption 1.1(D1) is strengthened to $(\log
n)^{4\xi}\ll m_{\infty}$, then for all $i\in[n]$,

  * (IV)

$\frac{m_{2}}{m_{1}}\left(\frac{v_{1}(i)-d_{i}/\sqrt{m_{2}}}{s_{1}(i)}\right)\stackrel{{\scriptstyle
w}}{{\longrightarrow}}\mathcal{N}(0,1),\qquad n\to\infty,$

where

$s_{1}^{2}(i)=\sum_{j}d_{j}^{2}p_{ij}(1-p_{ij})\sim
d_{i}\frac{m_{3}}{m_{1}},\qquad n\to\infty.$

###  1.3. Discussion

We place the theorems in their proper context.

1. Theorems 1.5–1.6 provide a CLT for $\lambda_{1},v_{1}$. We note that $m_{2}/m_{1}$ is the leading order term in the expansion of $\lambda_{1}$, while $m_{1}m_{3}/m_{2}^{2}$ is a correction term. We observe that Theorem 1.5(I) does not follow from the results in [16], because the largest eigenvalue need not be uniformly integrable and also the second order expansion is not considered there. We also note that in Theorem 1.5(II) the centering of the largest eigenvalue, $\mathbb{E}[\lambda_{1}]$, cannot be replaced by its asymptotic value as the error term is not compatible with the required variance.

2. The lower bound in Assumption 1.1(D1) is needed to ensure that the random graph is connected, and is crucial because the largest eigenvalue is very sensitive to connectivity properties. Assumption 1.1(D2) is needed to control the inhomogeneity of the random graph. It plays a crucial role in deriving concentration bounds on the central moments $\langle e,(A-\mathbb{E}[A])^{k}e\rangle$, $k\in\mathbb{N}$, with the help of a result from [19]. Further refinements may come from different tools, such as the non-backtracking matrices used in [5], [6]. While Assumption 1.1(D1) appears to be close to optimal, Assumption 1.1(D2) is far from optimal. It would be interesting to allow for empirical degree distributions that converge to a limiting degree distribrution with a power law tail.

3. As already noted, if the expected degrees are all equal to each other, i.e., $d_{i}=d$ for all $i\in[n]$, then the Chung-Lu random graph, or canonical configuration model, reduces to the homogeneous Erdős-Rényi random graph with $p=d/n$, while the corresponding microcanonical configuration model reduces to the homogeneous $d$-regular random graph model (here, all models allow for self-loops). This implies that, for the homogeneous Erdős-Rényi random graph with connection probability $p\gg(\log n)^{2\xi}/n$, $\xi>2$, Theorem 1.5(I) reduces to

$\mathbb{E}[\lambda_{1}]=np+1+{{\mathrm{o}}}(1),\qquad n\to\infty,$

while Theorem 1.5(II) reduces to

$\frac{1}{\sqrt{p}}\left(\lambda_{1}-\mathbb{E}[\lambda_{1}]\right)\stackrel{{\scriptstyle
w}}{{\longrightarrow}}\mathcal{N}(0,2),\qquad n\to\infty.$

Both these properties were derived in [18] for homogeneous Erdős-Rényi random
graphs and also for rank-1 perturbations of Wigner matrices. In [17], the fact
that $\mathbb{E}[\lambda_{1}]$ in the canonical ensemble differs by a finite
amount from the corresponding expected value (here, $d=np$) in the
microcanonical ensemble ($d$-regular random graph) was shown to be a signature
of ensemble nonequivalence.

4. In case $d_{i}=d$ for all $i\in[n]$, Theorem 1.6(III) reduces to the following CLT, which was not covered by [18] and [17].

######  Corollary 1.7.

For the Erdős-Rényi random graph with $(\log n)^{4\xi}/n\ll p\ll n^{-1/2}$ for
some $\xi>2$,

$n\sqrt{\frac{p}{1-p}}\left(v_{1}(i)-\frac{1}{\sqrt{n}}\right)\stackrel{{\scriptstyle
w}}{{\longrightarrow}}\mathcal{N}(0,1),\qquad n\to\infty.$

Note that, in the corresponding microcanonical ensemble ($d$-regular random
graph), $v_{1}$ coincides with the constant vector where $v_{1}(i)=1/\sqrt{n}$
for all $i\in[n]$. Therefore in the canonical ensemble each coordinate
$v_{1}(i)$ has Gaussian fluctuations around the corresponding deterministic
value for the microcanonical ensemble. This behaviour is similar to the
degrees having, in the canonical configuration model, either Gaussian (in the
dense setting) or Poisson (in the sparse setting) fluctuations around the
corresponding deterministic degrees for the microcanonical configuration model
[23].

5. In [14] the empirical spectral distribution of $A$ was considered under the assumption that

$(m_{\infty})^{2}/m_{1}\ll 1\ll n(m_{\infty})^{2}/m_{1},$

which is weaker than Assumption 1.1. It was shown that if
$\mu_{n}\stackrel{{\scriptstyle w}}{{\longrightarrow}}\mu$ with
$\mu_{n}=n^{-1}\sum_{i=1}^{n}\delta_{d_{i}/m_{\infty}}$ and $\mu$ some
probability distribution on $\mathbb{R}$, then

$\mathrm{ESD}\left(\frac{A}{\sqrt{n(m_{\infty})^{2}/m_{1}}}\right)\stackrel{{\scriptstyle
w}}{{\longrightarrow}}\mu\boxtimes\mu_{\mathrm{sc}}$

with $\mu_{\mathrm{sc}}$ the Wigner semicircle law and $\boxtimes$ the free
multiplicative convolution. Since $\mu\boxtimes\mu_{\mathrm{sc}}$ is compactly
supported, this shows that the scaling for the largest eigenvalue and the
spectral distribution are different.

##  2\. Proof of Theorem 1.5

In what follows we use the well-known method of writing the largest eigenvalue
of a matrix as a rank-1 perturbation of the centered matrix. This method was
previously successfully employed in [22, 29, 19].

Given the adjacency matrix $A$ of our graph $G$, we can write
$A=H+\mathbb{E}[A]$ with $H=A-\mathbb{E}[A]$. Let $v_{1}$ be the eigenvector
associated with the eigenvalue $\lambda_{1}$. Then

$Av_{1}=\lambda_{1}v_{1},\quad(H+\mathbb{E}[A])v_{1}=\lambda_{1}v_{1},\quad(\lambda_{1}I-H)v_{1}=\mathbb{E}[A]v_{1}.$

Using that $\mathbb{E}[A]=ee^{t}$, we have $(\lambda_{1}I-H)v_{1}=\left\langle
e,v_{1}\right\rangle e$, where $I$ is the $n\times n$ identity matrix. It
follows that if $\lambda_{1}$ is not an eigenvalue of $H$, then the matrix
$(\lambda_{1}I-H)$ is invertible, and so

$v_{1}=\left\langle e,v_{1}\right\rangle(\lambda_{1}I-H)^{-1}e.$ (2.1)

Eliminating the eigenvector $v_{1}$ from the above equation, we get

$1=\left\langle e,(\lambda_{1}I-H)^{-1}e\right\rangle,$

where we use that $\left\langle e,v_{1}\right\rangle\neq 0$ (since
$\lambda_{1}$ is not an eigenvalue of $H$). Note that this can be expressed as

$\lambda_{1}=\left\langle
e,\left(I-\frac{H}{\lambda_{1}}\right)^{-1}e\right\rangle=\sum_{k=0}^{\infty}\left\langle
e,\left(\frac{H}{\lambda_{1}}\right)^{k}e\right\rangle\quad whp,$ (2.2)

where the validity of the series expansion will be an immediate consequence of
Lemma 2.2 below.

Section 2.1 derives bounds on the spectral norm of $H$. Section 2.2 analyses
the expansion in (2.2) and prove the scaling of $\mathbb{E}[\lambda_{1}]$.
Section 2.3 is devoted to the proof of the CLT for $\lambda_{1}$, Section 3 to
the proof of the CLT for $v_{1}$. In the expansion we distinguish three
ranges: (i) $k=0,1,2$; (ii) $3\leq k\leq L$; (iii) $L<k<\infty$, where

$L=\lfloor\log n\rfloor.$

We will show that (i) controls the mean and the variance in both CLTs, while
(ii)-(iii) are negligible error terms.

###  2.1. The spectral norm

In order to study $\lambda_{1}$, we need good bounds on the spectral norm of
$H$. The spectral norm of matrices with inhomogeneous entries has been studied
in a series of papers [5], [6], [2] for different density regimes.

An important role is played by $\lambda_{1}(\mathbb{E}[A])$. In recent
literature this quantity has been shown to play a prominent role in the so-
called BBP-transition [4]. Given our setting (1.2), it is easy to see that

$\lambda_{1}(\mathbb{E}[A])=\frac{m_{2}}{m_{1}},$ (2.3)

while all other eigenvalues of $\mathbb{E}[A]$ are zero.

######  Remark 2.1.

Since $m_{0}\leq\frac{m_{2}}{m_{1}}\leq m_{\infty}$, Assumption 1.1(D2)
implies that

$\frac{m_{2}}{m_{1}}\asymp m_{\infty}.$ (2.4)

$\spadesuit$

We start with the following lemma, which ensures concentration of
$\lambda_{1}$ and is a direct consequence of the results in [6] (which match
Assumption 1.1).

######  Lemma 2.2.

Under Assumption 1.1, whp

$\left|\frac{\lambda_{1}(A)-\lambda_{1}(\mathbb{E}[A])}{\lambda_{1}(\mathbb{E}[A])}\right|=\mathrm{O}\left(\frac{1}{\sqrt{m_{\infty}}}\right),\qquad
n\to\infty,$

and consequently

$\frac{\lambda_{1}(A)}{\lambda_{1}\left(\mathbb{E}[A]\right)}\overset{\mathbb{P}}{\to}1,\qquad
n\to\infty.$

###### Proof.

In the proof it is understood that all statements hold whp in the sense of
(1.4). Let $A=H+\mathbb{E}[A]$. Due to Weyl’s inequality, we have that

$\lambda_{1}(\mathbb{E}[A])-\|H\|\leq\lambda_{1}(A)\leq\lambda_{1}(\mathbb{E}[A])+\|H\|.$

From [6, Theorem 3.2] we know that there is a universal constant $C>0$ such
that

$\mathbb{E}\left[\|H\|\right]\leq\sqrt{m_{\infty}}\left(2+\frac{C}{q}\sqrt{\frac{\log
n}{1\vee\log\left(\frac{\sqrt{\log n}}{q}\right)}}\right),$

where

$q=\sqrt{m_{\infty}}\wedge n^{1/10}\kappa^{-1/9}$

with $\kappa$ defined by

$\kappa=\max_{ij}\frac{p_{i}j}{m_{\infty}/n}=\frac{nm_{\infty}}{m_{1}}.$

Thanks to Assumption 1.1(D2), we have $\kappa=\mathrm{O}(1)$. By Remark 3.1 of
[6, Remark 3.1] (which gives us that $q=\sqrt{m_{\infty}}$ for $n$ large
enough) and Assumption 1.1, we get that

$\mathbb{E}\left[\|H\|\right]\leq\begin{cases}\sqrt{m_{\infty}}\left(2+\frac{C\sqrt{\log
n}}{\sqrt{m_{\infty}}}\right),\qquad(\log n)^{2\xi}\leq\sqrt{m_{\infty}}\leq
n^{1/10}\kappa^{-1/9},\\\\[5.69046pt]
\sqrt{m_{\infty}}\left(2+\frac{C^{\prime}\sqrt{\log
n}}{n^{1/10}}\right),\qquad\sqrt{m_{\infty}}\geq
n^{1/10}\kappa^{-1/9}.\end{cases}$ (2.5)

Using [8, Example 8.7] or [6, Equation 2.4] (the Talagrand inequality), we
know that there exists a universal constant $c>0$ such that

$\mathbb{P}\left(\left|\|H\|-\mathbb{E}[\|H\|]\right|>t\right)\leq
2\mathrm{e}^{-ct^{2}}.$

For $t=\sqrt{\nu(\log n)^{\xi}}$,

$\mathbb{E}[\|H\|]-\sqrt{\nu}(\log
n)^{\xi/2}\leq\|H\|\leq\mathbb{E}[\|H\|]+\sqrt{\nu}(\log n)^{\xi/2}.$ (2.6)

Thus, we have

$\left|\lambda_{1}(A)-\lambda_{1}(\mathbb{E}[A])\right|\leq\|H\|\leq\sqrt{m_{\infty}}(2+{{\mathrm{o}}}(1))+\sqrt{\nu}(\log
n)^{\xi/2}.$ (2.7)

Using that $\lambda_{1}(\mathbb{E}[A])=m_{2}/m_{1}$, we have that whp the
following bound holds:

$\left|\frac{\lambda_{1}(A)-\lambda_{1}(\mathbb{E}[A])}{\lambda_{1}({\rm
E}[A])}\right|\leq\frac{\sqrt{m_{\infty}}}{m_{2}/m_{1}}\left(2+{{\mathrm{o}}}(1)\right)+\frac{\sqrt{\nu}(\log
n)^{\xi/2}}{m_{2}/m_{1}}=\mathrm{O}\left(\frac{\sqrt{m_{\infty}}}{m_{2}/m_{1}}\right).$

Via Assumption 1.1 and (2.4) the claim follows. ∎

######  Remark 2.3.

  * (a)

The proof of Lemma 2.2 works well if we replace Assumption 1.1(D2) by a milder
condition. Indeed, the former is directly linked to the parameter $\kappa$
that appears in the proof of Lemma 2.2 and in the proof of [6, Theorem 3.2],
which contains a more general condition on the inhomogeneity of the degrees.

  * (b)

Note that a consequence of proof of Lemma 2.2 is that whp

$\frac{\|H\|}{\lambda_{1}(A)}\leq 1-C_{0}$ (2.8)

for some $C_{0}\in(0,1)$. This allows us to claim that whp the inverse

$\left(I-\frac{H}{\lambda_{1}(A)}\right)^{-1}$ (2.9)

exists.

$\spadesuit$

######  Lemma 2.4.

Let $1\leq k\leq L$. Then, under Assumption 1.1, whp

$\left|\left\langle e,H^{k}e\right\rangle-{\mathbb{E}}\left[\left\langle
e,H^{k}e\right\rangle\right]\right|\leq
C\frac{m_{2}}{m_{1}}\frac{m_{\infty}^{\frac{k}{2}}(\log n)^{k\xi}}{\sqrt{n}},$

i.e.,

$\max_{1\leq k\leq L}\mathbb{P}\left(\left|\left\langle
e,H^{k}e\right\rangle-{\mathbb{E}}\left[\left\langle
e,H^{k}e\right\rangle\right]\right|>\frac{C(\log
n)^{k\xi}m_{\infty}^{\frac{k}{2}}}{\sqrt{n}}\frac{m_{2}}{m_{1}}\right)\leq\mathrm{e}^{-\nu(\log
n)^{\xi}},\qquad n\geq n_{1}(\nu,\xi).$

Lemma 2.4 is a generalization to the inhomogeneous setting of [19, Lemma 6.5].
We skip the proof because it requires a straightforward modification of the
arguments in [19].

######  Lemma 2.5.

Under Assumption 1.1, for $2\leq k\leq L$, there exists a constant $C>0$ such
that

$\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]\leq\frac{m_{2}}{m_{1}}(Cm_{\infty})^{k/2}.$
(2.10)

###### Proof.

Let $\mathcal{E}$ be the high probability event defined by (2.6), i.e.,

$\|H\|\leq{\rm E}[\|H\|]+\sqrt{\nu}(\log n)^{\xi/2}\leq
m_{\infty}\left(1+\mathrm{O}\left(\frac{(\log
n)^{\xi/2}}{m_{\infty}}\right)\right).$

Due to Assumption 1.1(D1) we can bound the right-hand side by $Cm_{\infty}$.
Since $\|e\|_{2}^{2}=m_{2}/m_{1}$, on this event we have

$\mathbb{E}\left[\left(\left\langle e,H^{k}e\right\rangle\right){\bf
1}_{\mathcal{E}}\right]\leq\|e\|_{2}^{2}\,\mathbb{E}[\|H\|^{k}{\bf
1}_{\mathcal{E}}]\\\ \leq\frac{m_{2}}{m_{1}}(Cm_{\infty})^{k/2}.$

We show that the expectation when evaluated on the complementary event is
negligible. Indeed, observe that

$\displaystyle\mathbb{E}\left[\left\langle e,H^{k}e\right\rangle\right]$
$\displaystyle=\mathbb{E}\left(\sum_{i_{1},\ldots,i_{k+1}=1}^{n}e_{i_{1}}e_{i_{k+1}}\prod_{j=1}^{k}H(i_{j},i_{j+1})\right)^{2}$
$\displaystyle\leq\left(\frac{n^{k+1}m_{\infty}^{2}}{m_{1}}\right)^{2}\leq
C\mathrm{e}^{(2k+2)\log n}\leq\mathrm{e}^{2(\log n)^{2}},$

where in the last inequality we use that
$m_{\infty}={{\mathrm{o}}}(\sqrt{m_{1}})$. This, combined with the exponential
decay of the event $\mathcal{E}^{c}$, gives

$\mathbb{E}\left[\left\langle e,H^{k}e\right\rangle{\bf 1}_{A^{c}}\right]\leq
C\mathrm{e}^{-\nu(\log n)^{\xi}},$

and so the claim follows. ∎

###  2.2. Expansion for the principal eigenvalue

We denote the event in Lemma 2.2 by $\mathcal{E}$, which has high probability.
As noted in Remark 2.3(b), $I-\frac{H}{\lambda_{1}}$ is invertible on
$\mathcal{E}$. Hence, expanding on $\mathcal{E}$, we get

$\lambda_{1}=\sum_{k=0}^{\infty}\left\langle
e,\frac{H^{k}}{\lambda_{1}^{k}}e\right\rangle.$

We split the sum into two parts:

$\lambda_{1}=\sum_{k=0}^{L}\frac{\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}+\sum_{k=L+1}^{\infty}\frac{\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}.$ (2.11)

First we show that we may ignore the second sum. To that end we observe that,
by Assumption 1.1 (D1), on the event $\mathcal{E}$ we can estimate

$\displaystyle\left|\sum_{k=L+1}^{\infty}\frac{\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}\right|$
$\displaystyle\leq\sum_{k=L+1}^{\infty}\frac{\|e\|_{2}^{2}\|H\|^{k}}{\lambda_{1}^{k}}\leq\sum_{k=L+1}^{\infty}\frac{m_{2}}{m_{1}}\frac{m_{\infty}^{k/2}}{(Cm_{2}/m_{1})^{k}}$
$\displaystyle\leq\sum_{k=L+1}^{\infty}\frac{C^{\prime}}{m_{\infty}^{k/2-1}}=\mathrm{O}\left(\mathrm{e}^{-c\log\sqrt{n}}\right).$
(2.12)

Because of (2.12) and the fact that $\mathbb{E}(\left\langle
e,He\right\rangle)=0$, (2.11) reduces to

$\displaystyle\lambda_{1}$
$\displaystyle=\sum_{k=3}^{L}\frac{\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]}{\lambda_{1}^{k}}+\sum_{k=3}^{L}\frac{\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]}{\lambda_{1}^{k}}$
$\displaystyle\qquad+\left\langle
e,e\right\rangle+\frac{1}{\lambda_{1}}\left\langle
e,He\right\rangle+\frac{1}{\lambda_{1}^{2}}\left\langle
e,H^{2}e\right\rangle+{{\mathrm{o}}}(1).$

Next, we estimate the second sum in the above equation. Using Lemma 2.2, we
get

$\displaystyle\left|\sum_{k=3}^{L}\frac{\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]}{\lambda_{1}^{k}}\right|$
$\displaystyle\leq\sum_{k=3}^{L}\frac{Cm_{\infty}^{\frac{k}{2}}(\log
n)^{k\xi}}{\sqrt{n}(m_{2}/m_{1})^{k-1}}\leq\sum_{k=3}^{L}\frac{C(\log
n)^{k\xi}}{\sqrt{n}m_{\infty}^{k/2-1}}\leq\mathrm{O}\left(\frac{C(\log
n)^{\xi+1}}{\sqrt{nm_{\infty}}}\right)={{\mathrm{o}}}(1).$

From Lemma 2.5 we have

$\sum_{k=3}^{L}\frac{\mathbb{E}\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}\leq\sum_{k=3}^{L}\frac{\frac{m_{2}}{m_{1}}(Cm_{\infty})^{k/2}}{\left(m_{2}/m_{1}\right)^{k}}=\mathrm{O}\left(\frac{1}{\sqrt{m_{\infty}}}\right)={{\mathrm{o}}}(1),$

where the last estimate follows from Assumption 1.1(D1). Hence, on
$\mathcal{E}$,

$\lambda_{1}=\left\langle e,e\right\rangle+\frac{1}{\lambda_{1}}\left\langle
e,He\right\rangle+\frac{\left\langle
e,H^{2}e\right\rangle}{\lambda_{1}^{2}}+{{\mathrm{o}}}(1).$

Iterating the expression for $\lambda_{1}$ in the right-hand side, we get

$\displaystyle\lambda_{1}$ $\displaystyle=\left\langle
e,e\right\rangle+\left\langle e,He\right\rangle\left(\left\langle
e,e\right\rangle+\frac{1}{\lambda_{1}}\left\langle
e,He\right\rangle+\frac{1}{\lambda_{1}^{2}}\left\langle
e,H^{2}e\right\rangle+{{\mathrm{o}}}(1)\right)^{-1}$
$\displaystyle\quad+\left\langle e,H^{2}e\right\rangle\left(\left\langle
e,e\right\rangle+\frac{1}{\lambda_{1}}\left\langle
e,He\right\rangle+\frac{1}{\lambda_{1}^{2}}\left\langle
e,H^{2}e\right\rangle+{{\mathrm{o}}}(1)\right)^{-2}+{{\mathrm{o}}}(1),$

Expanding the second and third term we get,

$\displaystyle\lambda_{1}$ $\displaystyle=\left\langle
e,e\right\rangle+\frac{\left\langle e,He\right\rangle}{\left\langle
e,e\right\rangle}\left(1-\frac{\left\langle
e,He\right\rangle}{\lambda_{1}\left\langle
e,e\right\rangle}-\frac{\left\langle
e,H^{2}e\right\rangle}{\lambda_{1}^{2}\left\langle
e,e\right\rangle}+{{\mathrm{o}}}(1)\right)$
$\displaystyle\quad+\frac{\left\langle e,H^{2}e\right\rangle}{(\left\langle
e,e\right\rangle)^{2}}\left(1-\frac{2\left\langle
e,He\right\rangle}{\lambda_{1}\left\langle
e,e\right\rangle}-\frac{2\left\langle
e,H^{2}e\right\rangle}{\lambda_{1}^{2}\left\langle
e,e\right\rangle}+{{\mathrm{o}}}(1)\right)+{{\mathrm{o}}}(1),$
$\displaystyle=\left\langle e,e\right\rangle+\frac{\left\langle
e,He\right\rangle}{\left\langle e,e\right\rangle}-\frac{\left\langle
e,He\right\rangle^{2}}{\lambda_{1}\left\langle
e,e\right\rangle^{2}}+\frac{\left\langle e,H^{2}e\right\rangle}{\left\langle
e,e\right\rangle^{2}}+{{\mathrm{o}}}(1).$

Here we use that $\left\langle e,e\right\rangle=m_{2}/m_{1}\to\infty$, and we
ignore several other terms because they are small whp, for example,

$\frac{\left\langle e,He\right\rangle\left\langle
e,H^{2}e\right\rangle}{\lambda_{1}^{2}\left\langle
e,e\right\rangle^{2}}=\mathrm{O}\left(\frac{m_{\infty}^{3/2}}{(m_{2}/m_{1})^{4}}\right)={{\mathrm{o}}}(1).$

One more iteration gives

$\displaystyle\lambda_{1}$ $\displaystyle=\left\langle
e,e\right\rangle+\frac{\left\langle e,He\right\rangle}{\left\langle
e,e\right\rangle}+\frac{\left\langle e,H^{2}e\right\rangle}{\left\langle
e,e\right\rangle^{2}}$ $\displaystyle\quad-\frac{\left\langle
e,He\right\rangle^{2}}{\left\langle e,e\right\rangle^{2}}\left(\left\langle
e,e\right\rangle+\frac{1}{\lambda_{1}}\left\langle
e,He\right\rangle+\frac{1}{\lambda_{1}^{2}}\left\langle
e,H^{2}e\right\rangle+{{\mathrm{o}}}(1)\right)^{-1}+{{\mathrm{o}}}(1)$
$\displaystyle=\left\langle e,e\right\rangle+\frac{\left\langle
e,He\right\rangle}{\left\langle e,e\right\rangle}+\frac{\left\langle
e,H^{2}e\right\rangle}{\left\langle e,e\right\rangle^{2}}-\frac{\left\langle
e,He\right\rangle^{2}}{\left\langle e,e\right\rangle^{3}}+\frac{\left\langle
e,H^{2}e\right\rangle^{2}\left\langle
e,He\right\rangle}{\lambda_{1}\left\langle
e,e\right\rangle^{3}}+\frac{\left\langle
e,H^{2}e\right\rangle^{3}}{\lambda_{1}^{2}\left\langle
e,e\right\rangle^{3}}+{{\mathrm{o}}}(1).$

###### Proof of Theorem 1.5 (I).

Since the probability of $\mathcal{E}^{c}$ decays exponentially with $n$,
taking the expectation of the above term and using that
$\mathbb{E}[e^{\prime}We]=0$, we obtain

$\displaystyle\mathbb{E}[\lambda_{1}]=\left\langle
e,e\right\rangle+\frac{\mathbb{E}[\left\langle
e,H^{2}e\right\rangle]}{\left\langle
e,e\right\rangle^{2}}-\frac{\mathbb{E}[\left\langle
e,He\right\rangle^{2}]}{\left\langle
e,e\right\rangle^{3}}+{{\mathrm{o}}}(1)=\frac{m_{2}}{m_{1}}+\frac{m_{1}m_{3}}{m_{2}^{2}}-\frac{m_{3}^{2}}{m_{2}^{3}}+{{\mathrm{o}}}(1).$

Note that

$\frac{m_{3}^{2}}{m_{2}^{2}}\leq\frac{m_{\infty}^{2}}{n}={{\mathrm{o}}}(1),\qquad\frac{m_{1}m_{3}}{m_{2}^{2}}\leq\left(\frac{m_{\infty}}{m_{0}}\right)^{4}=\mathrm{O}(1),$

and so we can write

$\mathbb{E}[\lambda_{1}]=\frac{m_{2}}{m_{1}}+\frac{m_{1}m_{3}}{m_{2}^{2}}+{{\mathrm{o}}}(1).$
(2.13)

∎

###  2.3. CLT for the principal eigenvalue

Again consider the high probability event on which (2.9) holds. Recall that
from the series decomposition in (2.11) we have

$\displaystyle\lambda_{1}$ $\displaystyle=\frac{\left\langle
e,He\right\rangle}{\lambda_{1}}+\sum_{k=0}^{L}\frac{\mathbb{E}\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}+\sum_{k=2}^{L}\frac{\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}+\sum_{k>L}\frac{\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}.$ (2.14)

######  Lemma 2.6.

The equation

$x=\sum_{k=0}^{L}\frac{\mathbb{E}\left\langle e,H^{k}e\right\rangle}{x^{k}}$
(2.15)

has a solution $x_{0}$ satisfying

$\lim_{n\to\infty}\frac{x_{0}}{m_{2}/m_{1}}=1.$

###### Proof.

Define the function $h\colon\,(0,\infty)\to\mathbb{R}$ by

$h(x)=\sum_{k=0}^{\log n}\frac{\mathbb{E}\left\langle
e,H^{k}e\right\rangle}{x^{k}}.$

Since $\mathbb{E}[e^{\prime}He]=0$, we have

$h\left(\frac{xm_{2}}{m_{1}}\right)=\frac{m_{2}}{m_{1}}+\sum_{k=2}^{\log
n}\frac{\mathbb{E}\left\langle e,H^{k}e\right\rangle}{(xm_{2}/m_{1})^{k}}.$

For $x>0$,

$\displaystyle\left|\sum_{k=2}^{\log n}\frac{\mathbb{E}[\left\langle
e,H^{k}e\right\rangle]}{(xm_{2}/m_{1})^{k}}\right|$
$\displaystyle\leq\sum_{k=2}^{\infty}\frac{1}{(xm_{2}/m_{1})^{k}}\frac{m_{2}}{m_{1}}(Cm_{\infty})^{k/2}$
$\displaystyle={{\mathrm{o}}}\left(\frac{m_{2}}{m_{1}}\sum_{k=2}^{\infty}\frac{1}{x^{k}(\log
n)^{k\xi}}\right)={{\mathrm{o}}}\left(\frac{m_{2}}{m_{1}}x^{-2}\right).$

This shows that

$\lim_{n\to\infty}\frac{1}{m_{2}/m_{1}}\sum_{k=0}^{\log
n}\frac{\mathbb{E}\left\langle e,H^{k}e\right\rangle}{(xm_{2}/m_{1})^{k}}=1.$

Hence, for any $0<\delta<1$,

$\lim_{n\to\infty}\frac{1}{m_{2}/m_{1}}\left[\frac{m_{2}}{m_{1}}(1+\delta)-h\left((1+\delta)\frac{m_{2}}{m_{1}}\right)\right]=\delta.$

So, for large enough $n$,

$h\left((1+\delta)\frac{m_{2}}{m_{1}}\right)<\frac{m_{2}}{m_{1}}(1+\delta).$

Similarly, for any $0<\delta<1$,

$h\left((1-\delta)\frac{m_{2}}{m_{1}}\right)>\frac{m_{2}}{m_{1}}(1-\delta).$

This shows that there is a solution for (2.15), which lies in the interval
$[\frac{m_{2}}{m_{1}}(1-\delta),\frac{m_{2}}{m_{1}}(1-\delta)]$. ∎

######  Lemma 2.7.

Let $x_{0}$ be a solution for (2.15). Define

$R_{n}=\lambda_{1}-x_{0}-\frac{\left\langle e,He\right\rangle}{m_{2}/m_{1}}.$

Then

$R_{n}={{\mathrm{o}}}_{\mathbb{P}}\left(\frac{m_{3}}{m_{2}\sqrt{m_{1}}}\right),\qquad\mathbb{E}\left[|R_{n}|\right]={{\mathrm{o}}}\left(\frac{m_{3}}{m_{2}\sqrt{m_{1}}}\right).$

###### Proof of Theorem 1.5 (II).

From the previous lemmas we have

$\lambda_{1}=x_{0}+\frac{\left\langle e,He\right\rangle}{m_{2}/m_{1}}+R_{n}.$

Therefore

$\mathbb{E}[\lambda_{1}]=x_{0}+\mathbb{E}[R_{n}]$

and

$\lambda_{1}-\mathbb{E}[\lambda_{1}]=\frac{\left\langle
e,He\right\rangle}{m_{2}/m_{1}}+{{\mathrm{o}}}\left(\frac{m_{3}}{m_{2}\sqrt{m_{1}}}\right).$

Hence

$\frac{m_{2}}{m_{1}}\left(\lambda_{1}-\mathbb{E}[\lambda_{1}]\right)=\left\langle
e,H,e\right\rangle+{{\mathrm{o}}}\left(\frac{m_{3}}{m_{1}^{3/2}}\right).$
(2.16)

Observe that

$\left\langle
e,He\right\rangle=\sum_{i,j=1}^{N}h_{i,j}\frac{d_{i}d_{j}}{m_{1}}=2\sum_{i\leq
j}h_{i,j}\frac{d_{i}d_{j}}{m_{1}}$

Let

$\sigma_{1}^{2}=\sum_{i\leq
j}\mathrm{Var}\left(\frac{2}{m_{1}}h_{i,j}d_{i}d_{j}\right)=\sum_{i\leq
j}\frac{4d_{i}^{3}d_{j}^{3}}{m_{1}^{3}}\left(1-\frac{d_{i}d_{j}}{m_{1}}\right)\sim
2\frac{m_{3}^{2}}{m_{1}^{3}}\left(1+\mathrm{O}\left(\frac{m_{\infty}^{2}}{n}\right)\right),$

where we use the symmetry of the expression in the last equality. We can apply
Lyapunov’s central limit theorem, because $\\{h_{i,j}\colon\,i\leq j\\}$ is an
independent collection of random variables and Lyapunov’s condition is
satisfied, i.e.,

$\displaystyle\lim_{n\to\infty}\frac{1}{\sigma_{n}^{3}}\sum_{i>j}{\mathbb{E}}\left[\left|H(i,j)d_{i}d_{j}\right|^{3}\right]\leq
K\lim_{n\to\infty}\frac{m_{1}^{3/2}}{m_{3}^{3}}\frac{m_{4}^{2}}{m_{1}}=0,$

where $K$ is a constant that does not depend on $n$. Hence

$\frac{m_{1}^{3/2}\left\langle
e,He\right\rangle}{\sqrt{2}m_{3}}\overset{w}{\longrightarrow}N(0,1).$

Returning to the eigenvalue equation in (2.16) and dividing by $\sigma_{1}$,
we have

$\frac{\sqrt{m_{1}}{m_{2}}}{m_{3}}\left(\lambda_{1}-{\rm
E}[\lambda_{1}]\right)=\frac{m_{1}^{3/2}\left\langle
e,He\right\rangle}{m_{3}}+{{\mathrm{o}}}(1)\overset{w}{\longrightarrow}N(0,2).$

∎

We next prove Lemma 2.7, on which the proof of the central limit theorem
relied.

###### Proof.

Note that by (2.14) and (2.15) we can write

$\lambda_{1}-x_{0}=\frac{\left\langle
e,He\right\rangle}{\lambda_{1}}+\sum_{k=2}^{L}\mathbb{E}\left\langle
e,H^{k}e\right\rangle\left(\frac{1}{\lambda_{1}^{k}}-\frac{1}{x_{0}^{k}}\right)+L_{n},$
(2.17)

where

$L_{n}=\sum_{k=2}^{L}\frac{\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}+\sum_{k>L}\frac{\left\langle
e,H^{k}e\right\rangle}{\lambda_{1}^{k}}.$

Thanks to Lemma 2.2, Lemma 2.4 and (2.12) we have

$L_{n}=\mathrm{O}\left(\frac{m_{\infty}(\log
n)^{2\xi}}{\sqrt{n}m_{2}/m_{1}}\right).$

Note that $L_{n}={{\mathrm{o}}}(\frac{m_{3}}{m_{2}\sqrt{m_{1}}})$. Indeed,
using $m_{3}\geq nm_{0}^{3}$ and Assumption 1.1(D1), we get

$\frac{m_{\infty}(\log
n)^{2\xi}m_{2}\sqrt{m_{1}}}{\sqrt{n}(m_{2}/m_{1})m_{3}}\leq\frac{m_{\infty}^{5/2}n^{3/2}(\log
n)^{2\xi}}{\sqrt{n}m_{0}nm_{0}^{3}(\log n)^{\xi}}=\frac{m_{\infty}^{5/2}(\log
n)^{\xi}}{m_{0}^{4}}=\mathrm{O}\left(\frac{(\log
n)^{\xi}}{m_{0}^{3/2}}\right).$

Observe that (2.17) can be rearranged as

$(\lambda_{1}-x_{0})=\frac{\left\langle
e,He\right\rangle}{\lambda_{1}}-\sum_{k=2}^{L}(\lambda_{1}-x_{0})\mathbb{E}\left\langle
e,H^{k}e\right\rangle\lambda_{1}^{-k}x_{0}^{-k}\sum_{j=0}^{k-1}x_{0}^{k-1-j}+L_{n}.$

Hence, bringing the second term from the right to the left, we have

$(\lambda_{1}-x_{0})\left[1+\sum_{k=2}^{L}\mathbb{E}\left\langle
e,H^{k}e\right\rangle\lambda_{1}^{-k}x_{0}^{-k}\sum_{j=0}^{k-1}x_{0}^{k-1-j}\right]=\frac{\left\langle
e,He\right\rangle}{\lambda_{1}}+L_{n}.$

Using the bounds on $\lambda_{1}$ and $x_{0}$, we get

$\displaystyle\left|\sum_{k=2}^{L}\mathbb{E}\left\langle
e,H^{k}e\right\rangle\lambda_{1}^{-k}x_{0}^{-k}\sum_{j=0}^{k-1}x_{0}^{k-1-j}\right|\leq\sum_{k=2}^{L}\frac{k}{(m_{2}/m_{1})^{k+1}}\mathbb{E}\left\langle
e,H^{k}e\right\rangle$
$\displaystyle\leq\sum_{k=2}^{L}\frac{k}{(m_{2}/m_{1})^{k+1}}\frac{m_{2}}{m_{1}}(Cm_{\infty})^{k/2}=\mathrm{O}\left(\frac{m_{\infty}}{(m_{2}/m_{1})^{2}(\log
n)^{2\xi-1}}\right)={{\mathrm{o}}}(1).$

We can therefore write

$\lambda_{1}-x_{0}=\frac{\left\langle e,He\right\rangle}{\lambda_{1}}+L_{n},$

where $L_{n}={{\mathrm{o}}}_{P}(\frac{m_{3}}{m_{2}\sqrt{m_{1}}})$. Finally, to
go to $R_{n}$, note that

$R_{n}=\lambda_{1}-x_{0}-\frac{\left\langle
e,He\right\rangle}{m_{2}/m_{1}}=\left\langle
e,He\right\rangle\left(\frac{1}{\lambda_{1}}-\frac{1}{m_{2}/m_{1}}\right)+L_{n}.$
(2.18)

To bound $R_{n}$, it is enough to show that the first term on the right-hand
side is whp bounded by $\frac{m_{3}}{m_{2}\sqrt{m_{1}}}$. Using Lemma 2.4 (for
$k=1$) and (2.7), we have whp

$\frac{\left|\left\langle
e,He\right\rangle\right||\lambda_{1}-m_{2}/m_{1}|}{\lambda_{1}m_{2}/m_{1}}\leq\frac{\sqrt{m_{\infty}}(\log
n)^{\xi}}{\sqrt{n}}\frac{\sqrt{m_{\infty}}}{(m_{2}/m_{1})}.$ (2.19)

Using again Assumption 1.1(D1), $m_{3}\geq nm_{0}^{3}$, $m_{1}\leq
nm_{\infty}$ and $m_{2}\leq nm_{\infty}^{2}$, we get that

$\frac{m_{\infty}(\log
n)^{\xi}}{\sqrt{n}(m_{2}/m_{1})}\frac{m_{2}\sqrt{m_{1}}}{m_{3}}\leq\left(\frac{m_{\infty}}{m_{0}}\right)^{3}\frac{c}{\sqrt{m_{\infty}}}={{\mathrm{o}}}(1).$

This controls the right-hand side of (2.19), and hence
$R_{n}={{\mathrm{o}}}(\frac{m_{3}}{m_{2}\sqrt{m_{1}}})$ whp.

We want to show that the latter is negligible both pointwise and in
expectation. We already have that this is so whp on $R_{n}$. We want to show
that the same bound holds in expectation. Let $\mathcal{A}$ be the high
probability event of Lemma 2.2 and 2.4, and write

$\mathbb{E}[|R_{n}|]=\mathbb{E}[|R_{n}|\textbf{1}_{\mathcal{A}^{c}}]+\mathbb{E}[|R_{n}|\textbf{1}_{\mathcal{A}}],$

where $\textbf{1}_{\mathcal{A}}$ is the indicator function of the event
$\mathcal{A}$. Since all the bounds hold on the high probability event
$\mathcal{A}$, it is immediate that

$\mathbb{E}[|R_{n}|\textbf{1}_{\mathcal{A}}]={{\mathrm{o}}}\left(\frac{m_{3}}{\sqrt{m_{1}}m_{2}}\right).$

The remainder can be bounded via the Cauchy-Schwarz inequality, namely,

$\mathbb{E}[|R_{n}|\textbf{1}_{\mathcal{A}^{c}}]\leq\left(\mathbb{E}[|R_{n}|^{2}]\mathbb{E}[\textbf{1}_{\mathcal{A}^{c}}]\right)^{\frac{1}{2}}\leq\left(\mathbb{E}\left[|R_{n}|^{2}\right]e^{-\nu(\log
n)^{\xi}}\right)^{\frac{1}{2}}.$

We see that if $\mathbb{E}[|R_{n}|^{2}]={{\mathrm{o}}}(\mathrm{e}^{-\nu(\log
n)^{\xi}})$, then we are done. Expanding, we see that

$\mathbb{E}[|R_{n}|^{2}]=\mathbb{E}\left[\left|\lambda_{1}-x_{0}-\frac{\left\langle
e,He\right\rangle}{m_{2}/m_{1}}\right|^{2}\right]\leq n^{C}$

for some $C>0$, where we use that

$\displaystyle\mathbb{E}[(\lambda_{1}^{2})]\leq\mathbb{E}[\Tr
A^{2}]=\sum_{i,j=1}^{N}\mathbb{E}[(A(i,j))^{2}]\leq m_{\infty}n$

and the trivial bound $|\left\langle e,He\right\rangle|\leq n^{C_{*}}$ for
some $C_{*}<C$. Hence we have
$\left(\mathbb{E}[|R_{n}|^{2}]\mathbb{E}[\textbf{1}_{A^{c}}]\right)^{\frac{1}{2}}\leq\mathrm{e}^{-\nu(\log
n)^{\xi}}$ and

$\mathbb{E}[|R_{n}|]={{\mathrm{o}}}\left(\frac{m_{3}}{\sqrt{m_{1}}m_{2}}\right).$

∎

##  3\. Proof of Theorem 1.6

In this section we study the properties of the principal eigenvector. Let
$v_{1}$ be the normalized principal eigenvector, i.e., $\|v_{1}\|=1$, and let
$e$ be as defined in (1.3). Recall from (2.1) that

$\lambda_{1}\left(1-\frac{H}{\lambda_{1}}\right)v_{1}=e\langle
e,v_{1}\rangle,$

and after inversion (which is possible on the high probability event) we have

$v_{1}=\frac{\langle e,v_{1}\rangle}{\lambda_{1}}(1-H/\lambda_{1})^{-1}e.$

If $K$ denotes the normalization factor, then we can rewrite the above
equation whp as the series

$v_{1}=\frac{K}{\lambda_{1}}\sum_{k=0}^{\infty}\frac{H^{k}e}{\lambda_{1}^{k}}.$
(3.1)

Our first step is to determine the value of $K$ in (3.1). We adapt the results
from [19] to derive a component-wise central limit theorem in the
inhomogeneous setting described by (1.2) under Assumption 1.1. By the
normalization of $v$,

$1=\langle
v_{1},v_{1}\rangle=\frac{K^{2}}{\lambda_{1}^{2}}\left\langle\sum_{k=0}^{\infty}\frac{H^{k}}{\lambda_{1}^{k}}e,\sum_{\ell=0}^{\infty}\frac{H^{\ell}}{\lambda_{1}^{\ell}}e\right\rangle=\frac{K^{2}}{\lambda_{1}^{2}}\sum_{k=0}^{\infty}\frac{(k+1)\left\langle
e,{H^{k}}e\right\rangle}{\lambda_{1}^{k}},$ (3.2)

where we use the symmetry of $H$.

The following lemma settles Theorem 1.6(I).

######  Lemma 3.1.

Under Assumption 1.1, and with $\tilde{e}=e\sqrt{\frac{m_{1}}{m_{2}}}$, whp

$\langle\tilde{e},v_{1}\rangle=1+{{\mathrm{o}}}(1).$ (3.3)

###### Proof.

Recall that $L=\lfloor\log n\rfloor$. We rewrite (3.2) as

$\begin{split}\left(\frac{\lambda_{1}}{K}\right)^{2}&=\sum^{L}_{k=0}\frac{(k+1)}{\lambda_{1}^{k}}\,\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]+\sum_{k=1}^{L}\frac{(k+1)}{\lambda_{1}^{k}}\left|\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]\right|\\\
&\qquad\qquad+\sum_{k=L+1}^{\infty}\frac{(k+1)}{\lambda_{1}^{k}}\left\langle
e,H^{k}e\right\rangle.\end{split}$ (3.4)

We first show that the last two parts are negligible and then show that the
main term of the first part is the term with $k=0$, i.e., $\langle
e,e\rangle=m_{2}/m_{1}$.

The last term in (3.4) is dealt with as follows. Using (2.8), we have whp

$\begin{split}\sum_{k=L+1}^{\infty}\frac{(k+1)}{\lambda^{k}}\left\langle
e,H^{k}e\right\rangle&\leq\sum_{k=L+1}^{\infty}(k+1)\frac{\|e\|^{2}\|H\|^{k}}{(m_{2}/m_{1})^{k}}\leq\frac{m_{2}}{m_{1}}\sum_{k=L+1}^{\infty}(k+1)(1-C_{0})^{k}\\\
&\leq\frac{m_{2}}{m_{1}}(\log n+2)\mathrm{e}^{-c^{\prime}\log
n}\frac{1}{C_{0}^{2}}\end{split}$

with $c^{\prime}=-\log(1-C_{0})$, where we use that
$\sum_{k=0}^{\infty}(k+1)(1-c)^{k}=1/c^{2}$ for $|1-c|<1$.

We tackle the second sum in (3.4) by using Lemma 2.4. Indeed, whp we have

$\begin{split}\sum_{k=1}^{L}\frac{(k+1)}{\lambda_{1}^{k}}\left|\left\langle
e,H^{k}e\right\rangle-\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]\right|&\leq\sum_{k=1}^{L}(k+1)\frac{Cm_{\infty}^{k/2}(\log
n)^{k\xi}}{\sqrt{n}}\left(\frac{m_{2}}{m_{1}}\right)^{1-k}\\\
&\leq\frac{C^{\prime}\sqrt{m_{\infty}}(\log n)^{\xi}(\log
n+1)}{\sqrt{n}}\leq\frac{C^{\prime}\sqrt{m_{\infty}}(\log
n)^{2\xi}}{\sqrt{n}},\end{split}$

where the constant varies in each step. By Assumption 1.1(D1), the last term
goes to zero.

As to the first term, note that by (2.5) for $k\geq 3$ we have

$\displaystyle\sum^{L}_{k=3}\frac{(k+1)}{\lambda_{1}^{k}}\mathbb{E}\left[\left\langle
e,H^{k}e\right\rangle\right]$
$\displaystyle\leq\sum_{k=3}^{L}(k+1)\left(\frac{m_{2}}{m_{1}}\right)^{-k+1}(Cm_{\infty})^{k/2}$
$\displaystyle\leq\sum_{k=3}^{L}\frac{Cm_{\infty}^{k/2}}{(m_{2}/m_{1})^{(k-1)}}=\mathrm{O}\left(\frac{1}{\sqrt{m_{\infty}}}\right).$

The term with $k=1$ is zero, while for $k=2$ we have

$3\frac{\mathbb{E}\langle e,H^{2}e\rangle}{\lambda^{2}_{1}}\leq
c\frac{m_{1}m_{3}}{m_{2}^{2}}=\mathrm{O}\left(1\right)$

for some constant $c$. After substituting these results into (3.4), we find

$\left(\frac{\lambda_{1}}{K}\right)^{2}=\frac{m_{2}}{m_{1}}\left(1+\mathrm{O}\left(\frac{1}{m_{2}/m_{1}}\right)\right)$
(3.5)

and the proof follows by normalizing the vector $e$ and using (3.1). ∎

The following lemma is an immediate consequence of (3.1) and Lemma 3.1.

######  Lemma 3.2.

Under Assumptions 1.1, whp

$v_{1}=\left(1+\mathrm{O}\left(\frac{m_{1}}{m_{2}}\right)\right)\sqrt{\frac{m_{1}}{m_{2}}}\sum_{k=0}^{\infty}\frac{H^{k}}{\lambda_{1}^{k}}e.$
(3.6)

In order to estimate how the components of $v_{1}$ concentrate, we need the
following lemma.

######  Lemma 3.3.

For $1\leq k\leq L$, whp

$|H^{k}e(i)|=\left|\frac{1}{\sqrt{m_{1}}}\sum_{i_{1},\dots,i_{k}}h_{ii_{1}}h_{i_{1}i_{2}}\dots
h_{i_{k-1}i_{k}}d_{i_{k}}\right|\leq\frac{m_{\infty}}{\sqrt{m_{1}}}\left((\log
n)^{\xi}\sqrt{m_{\infty}}\right)^{k}.$

The proof of this lemma is a direct consequence of Lemma 2.4, is similar to
[19, Lemma 7.10] and therefore we skip it. An immediate corollary of the above
estimate is the delocalized behaviour of the largest eigenvector stated in
Theorem 1.6(II).

######  Lemma 3.4.

Let $v_{1}$ be the normalized principal eigenvector, and
$\tilde{e}=e\sqrt{\frac{m_{1}}{m_{2}}}$. Then whp

$\|v_{1}-\tilde{e}\|_{\infty}\leq\mathrm{O}\left(\frac{(\log
n)^{\xi}}{\sqrt{nm_{\infty}}}\right).$

###### Proof.

Recall from (3.4) that

$v_{1}(i)=\frac{K}{\lambda_{1}}\sum_{k=0}^{\infty}\frac{H^{k}e(i)}{\lambda_{1}^{k}}=\frac{K}{\lambda_{1}}e(i)+\frac{K}{\lambda_{1}}\sum_{k=1}^{L}\frac{H^{k}e(i)}{\lambda_{1}^{k}}+\frac{K}{\lambda_{1}}\sum_{k=L+1}^{\infty}\frac{H^{k}e(i)}{\lambda_{1}^{k}}.$

The last term is negligible whp, because it is the tail sum of a geometrically
decreasing sequence. For the sum over $1\leq k\leq L$ fwe can use Lemma 3.3
and the fact that $K/\lambda_{1}=\sqrt{\frac{m_{1}}{m_{2}}}+{{\mathrm{o}}}(1)$
whp. So we have

$\frac{K}{\lambda_{1}}\sum_{k=1}^{L}\frac{H^{k}e(i)}{\lambda_{1}^{k}}\leq\frac{m_{\infty}}{\sqrt{n}m_{0}}\frac{(\log
n)^{\xi}}{\sqrt{m_{\infty}}}\leq\mathrm{O}\left(\frac{(\log
n)^{\xi}}{\sqrt{nm_{\infty}}}\right).$

The first term whp is

$\frac{K}{\lambda_{1}}e(i)=\tilde{e}(i)+{{\mathrm{o}}}(1)$

and the error is uniform over all $i$. Indeed, whp

$\left|\frac{K}{\lambda_{1}}e(i)-\frac{K}{m_{2}/m_{1}}e(i)\right|\leq\frac{Kd_{i}}{\sqrt{m_{1}}}\frac{\left|\lambda_{1}-m_{2}/m_{1}\right|}{(m_{2}/m_{1})^{2}}\leq\sqrt{\frac{m_{2}}{m_{1}}}\frac{cm^{3/2}_{\infty}}{\sqrt{m_{0}n}}\frac{c^{\prime}}{m_{\infty}^{2}}=\mathrm{O}\left(\frac{1}{\sqrt{nm_{\infty}}}\right),$
(3.7)

where we use Assumption 1.1, Remark 2.1 and (2.7). Since the detailed
computations are similar to the previous arguments, we skip the details. ∎

We next prove the central limit theorem for the components of the eigenvector
stated in Theorem 1.6(IV).

######  Theorem 3.5.

Under Assumption 1.1, with the extra assumtion $m_{\infty}\gg(\log n)^{4\xi}$,

$\sqrt{\frac{m_{2}^{3}}{d_{i}m_{3}m_{1}}}\Big{(}v_{1}(i)-\frac{d_{i}}{\sqrt{m_{2}}}\Big{)}\overset{w}{\rightarrow}\mathcal{N}(0,1).$

###### Proof.

First we compute $\mathbb{E}[v_{1}(i)]$, and afterwards we show that the CLT
holds componentwise.

We use the law of total expectation. Conditioning on the high probability
event $\mathcal{E}$ in Lemma 2.2, we can write the expectation of the
normalized eigenvector $v_{1}$ as

$\mathbb{E}[v_{1}(i)]=\mathbb{E}[v_{1}(i)|\mathcal{E}]\,\mathbb{P}(\mathcal{E})+\mathbb{E}[v_{1}(i)|\mathcal{E}^{c}]\,\mathbb{P}(\mathcal{E}^{c}).$

Because the components of a normalized $n$-dimensional vector are bounded, we
know that

$\mathbb{E}[v_{1}(i)]=\mathbb{E}[v_{1}(i)|\mathcal{E}]\,\mathbb{P}(\mathcal{E})+\mathrm{O}\left(e^{-c_{\nu}(\log
n)^{\xi}}\right)$

for some suitable constant $c_{\nu}>0$, dependent on $\nu$ and on the the
bound on $v_{1}(i)$. On $\mathcal{E}$, we can expand $v_{1}$ as

$\displaystyle
v_{1}(i)=\frac{K}{\lambda_{1}}\left(e(i)+\frac{(He)(i)}{\lambda_{1}}+\frac{(H^{2}e)(i)}{\lambda_{1}^{2}}+\sum_{k=3}^{\infty}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right).$

Using the notation $\mathbb{E}_{\mathcal{E}}$ for the conditional expectation
on the event $\mathcal{E}$, we have

$\displaystyle\mathbb{E}_{\mathcal{E}}[v_{1}(i)]=\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}e(i)\right]+\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\frac{(He)(i)}{\lambda_{1}}\right]++\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\sum_{k=2}^{\infty}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right].$

For the first term we have, using (3.5),

$\displaystyle\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}e_{i}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{E}}\left[\frac{1}{\sqrt{m_{2}/m_{1}}}e_{i}\right]+\mathrm{O}\left(\frac{d_{i}}{\sqrt{m_{1}}(m_{2}/m_{1})^{3/2}}\right)=\frac{d_{i}}{\sqrt{m_{2}}}+\mathrm{O}\left(\frac{d_{i}}{\sqrt{m_{1}}(m_{2}/m_{1})^{3/2}}\right).$

For the term corresponding to $k=1$, we know that $\mathbb{E}[(He)(i)]=0$ by
construction on the whole space. However, under the event $\mathcal{E}$ we can
show that its contribution is exponentially negligible. We have

$\displaystyle\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\frac{(He)(i)}{\lambda_{1}}\right]=\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}\lambda_{1}}\right]=\mathbb{E}_{\mathcal{E}}\left[\frac{\left(1+\mathrm{O}\left(\frac{1}{m_{2}/m_{1}}\right)\right)}{\sqrt{m_{2}/m_{1}}}\left(\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}(m_{2}/m_{1})}\right.\right.$
$\displaystyle\left.\left.+\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}}\frac{|\lambda_{1}-(m_{2}/m_{1})|}{(m_{2}/m_{1})^{2}}\right)\right].$

Since $m_{2}/m_{1}\to\infty$, there exists a constant $\tilde{C}$ such that

$\frac{\left(1+\mathrm{O}\left(1/(m_{2}/m_{1})\right)\right)}{\sqrt{m_{2}/m_{1}}}\leq\tilde{C}\frac{1}{\sqrt{m_{2}/m_{1}}}.$

We can therefore write

$\displaystyle\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}\lambda_{1}}\right]$
$\displaystyle\leq\tilde{C}\frac{1}{\sqrt{m_{2}/m_{1}}}\mathbb{E}_{\mathcal{E}}\left[\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}(m_{2}/m_{1})}+\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}}\frac{|\lambda_{1}-(m_{2}/m_{1})|}{(m_{2}/m_{1})^{2}}\right]$
$\displaystyle\leq\mathbb{E}_{\mathcal{E}}\left[\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}(m_{2}/m_{1})}\right]+\mathbb{E}_{\mathcal{E}}\left[\frac{\sum_{j}h_{ij}d_{j}}{\sqrt{m_{1}}}\frac{|\lambda_{1}-(m_{2}/m_{1})|}{(m_{2}/m_{1})^{2}}\right]$
$\displaystyle\leq\mathbb{E}_{\mathcal{E}}\left[\sum_{j}h_{ij}d_{j}\right]\left(\frac{1}{\sqrt{m_{1}}(m_{2}/m_{1})}+\frac{\sqrt{m_{\infty}}}{\sqrt{m_{1}}(m_{2}/m_{1})}\right).$

Here we use (2.7) to bound the difference $|\lambda_{1}-(m_{2}/m_{1})|$. Next,
write

$\displaystyle 0$
$\displaystyle=\mathbb{E}\left[\sum_{j}h_{ij}d_{j}\right]=\mathbb{E}_{\mathcal{E}}\left[\sum_{j}h_{ij}d_{j}\right]\mathbb{P}(\mathcal{E})+\mathbb{E}_{\mathcal{E}^{c}}\left[\sum_{j}h_{ij}d_{j}\right]\mathbb{P}(\mathcal{E}^{c})$
$\displaystyle\leq\mathbb{E}_{\mathcal{E}}\left[\sum_{j}h_{ij}d_{j}\right]\mathbb{P}(\mathcal{E})+m_{1}\mathbb{P}(\mathcal{E}^{c})=\mathbb{E}_{\mathcal{E}}\left[\sum_{j}h_{ij}d_{j}\right]\mathbb{P}(\mathcal{E})+\mathrm{O}\left(e^{-c_{\nu}(\log
n)^{\xi}}\right),$

where $c_{\nu}$ is a constant depending on $\nu$, and we use that
$|h_{ij}|\leq 1$ and $m_{1}=\mathrm{O}\left(e^{3/2\log n}\right)$. We can
therefore conclude that

$\mathbb{E}_{\mathcal{E}}\left[\frac{(He)(i)}{\lambda_{1}}\right]=\mathrm{O}\left(e^{-c^{\prime}_{\nu}(\log
n)^{\xi}}\right),$

where $c^{\prime}_{\nu}>0$ is a suitable constant depending on $\nu$, and
possibly different from $c_{\nu}$.

To bound the remaining expectation terms, we use Lemma 3.3, which gives a
bound on $(H^{k}e)(i)$ on the event $\mathcal{E}$. As before, we break up the
sum into two contributions:

$\displaystyle\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\sum_{k=2}^{\infty}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right]=\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\sum_{k=2}^{L}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right]+\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\sum_{k=L}^{\infty}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right].$

For the second term we have

$\displaystyle\sum_{k=L+1}^{\infty}\frac{\left(H^{k}e\right)(i)}{\lambda_{1}^{k}}\leq
C\sqrt{\frac{m_{2}}{m_{1}}}\,\mathrm{e}^{-C_{c}\log n},$ (3.8)

where we use (2.8) and $C_{c}=|\log(1-C_{0})|$. The first term can be bounded
via Lemma 3.3, which gives

$\displaystyle\sum_{k=2}^{L}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}$
$\displaystyle\leq\sum_{k=2}^{L}\frac{m_{\infty}\left((\log
n)^{\xi}\sqrt{m_{\infty}}\right)^{k}}{\sqrt{m_{1}}(m_{2}/m_{1})^{k}}=\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{1}}}\right).$ (3.9)

Using the above bounds, taking expectations and using (3.5), we get

$\mathbb{E}_{\mathcal{E}}\left[\frac{K}{\lambda_{1}}\sum_{k=2}^{\infty}\frac{(H^{k}e)(i)}{\lambda_{1}^{k}}\right]=\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right).$

Thus, we have obtained that

$\mathbb{E}[v_{1}(i)]=\frac{d_{i}}{\sqrt{m_{2}}}+\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right),$

which settles Theorem 1.6(III).

We can write

$v_{1}(i)-\frac{d_{i}}{\sqrt{m_{2}}}=\frac{\left(1+\mathrm{O}\left(\frac{1}{m_{2}/m_{1}}\right)\right)e(i)}{\sqrt{m_{2}/m_{1}}}-\frac{d_{i}}{\sqrt{m_{2}}}+\frac{K}{\lambda_{1}}\frac{(He)(i)}{\lambda_{1}}+\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right),$

where we replace the last terms of the expansion of $v_{1}$ by the bounds
derived above (note that these bounds are of the same order as the ones
obtained for the same terms in expectation). The first term of the centered
quantity $v_{1}(i)-d_{i}/\sqrt{m_{2}}$ is given by

$\frac{\left(1+\mathrm{O}\left(\frac{1}{m_{2}/m_{1}}\right)\right)e(i)}{\sqrt{m_{2}/m_{1}}}=\mathrm{O}\left(\frac{d_{i}}{\sqrt{m_{1}}(m_{2}/m_{1})^{3/2}}\right).$

This last error can be easily seen to be ${{\mathrm{o}}}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right)$. We can therefore write

$v_{1}(i)-\mathbb{E}[v_{1}(i)]=\frac{K}{\lambda_{1}}\frac{(He)(i)}{\lambda_{1}}+\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{2}}}\right).$

We proceed to show that the first term on the right-hand side of the above
equality gives a CLT when the expression is rescaled by an appropriate
quantity, and the error term goes to zero. It turns out that

$s_{n}^{2}(i)=\mathrm{Var}\left(\sum_{j}h_{ij}d_{j}\right)=\sum_{j}\frac{d_{i}d^{3}_{j}}{m_{1}}\left(1+\mathrm{O}\left(\frac{1}{m_{0}}\right)\right)\sim\frac{d_{i}m_{3}}{m_{1}}.$

Multiplying by $\sqrt{\frac{m_{2}^{3}}{d_{i}m_{3}m_{1}}}$, we have

$\sqrt{\frac{m_{2}^{3}}{d_{i}m_{3}m_{1}}}\Big{(}v_{1}(i)-\langle\tilde{e},v_{1}\rangle\tilde{e}(i)\Big{)}=\frac{1}{s_{n}}\sum_{j}h_{ij}d_{j}+\mathrm{O}\left(\sqrt{\frac{m_{2}^{2}(\log
n)^{4\xi}}{d_{i}m_{3}m_{1}}}\right).$

The error term is

$\sqrt{\frac{m_{2}^{2}(\log
n)^{4\xi}}{d_{i}m_{3}m_{1}}}=\mathrm{O}\left(\frac{(\log
n)^{2\xi}}{\sqrt{m_{0}}}\right)={{\mathrm{o}}}(1),$

where last inequality follows from the assumption that $m_{0}\gg(\log
n)^{4\xi}$. We now apply Lindeberg’s CLT to the term
$\frac{\sum_{j}h_{ij}d_{j}}{s_{n}}$. The Lindeberg condition for the CLT reads

$\lim_{n\to\infty}\frac{1}{s_{n}^{2}(i)}\sum_{j}^{n}\mathbb{E}\left[(h_{ij}d_{j})^{2}\,{\bf
1}_{\\{|h_{ij}d_{j}|\geq\epsilon s_{n}(i)\\}}\right]=0.$ (3.10)

Defining $\sigma^{2}_{j}(i)={\rm Var}(h_{ij}d_{j})$, we note that

$\lim_{n\to\infty}\frac{\sigma^{2}_{j}(i)}{s^{2}_{n}(i)}=\lim_{n\to\infty}\frac{d_{i}d_{j}^{3}m_{1}}{m_{1}m_{3}d_{i}}\leq\lim_{n\to\infty}\frac{m_{\infty}^{3}}{m_{3}}\leq\lim_{n\to\infty}\frac{m_{\infty}^{3}}{nm_{0}^{3}}=0.$

Let us finally examine the event

$|h_{ij}d_{j}|\geq\epsilon
s_{n}(i)=\epsilon\sqrt{\frac{d_{i}m_{3}}{m_{1}}}\iff|h_{ij}|\geq\epsilon\sqrt{\frac{m_{3}}{m_{1}}\frac{d_{i}}{d_{j}^{2}}}.$

By definition, $|h_{ij}|<1$. If we show that

$\lim_{n\to\infty}\sqrt{\frac{m_{3}}{m_{1}}\frac{d_{i}}{d_{j}^{2}}}=\infty,$

then for all $\epsilon>0$ there exists $n_{\epsilon}$ such that the event

$\epsilon\sqrt{\frac{m_{3}}{m_{1}}\frac{d_{i}}{d_{j}^{2}}}>1>|h_{ij}|$

has probability $1$. Indeed,

$\lim_{n\to\infty}\epsilon\sqrt{\frac{m_{3}}{m_{1}}\frac{d_{i}}{d_{j}^{2}}}>\lim_{n\to\infty}\epsilon\sqrt{\frac{nm_{0}^{4}}{nm_{\infty}^{3}}}\geq\lim_{n\to\infty}\epsilon\,C\sqrt{m_{0}}=\infty$

for a suitable constant $C$. Thus, (3.10) holds. ∎

## References

  * [1] E. Abbe.  Community detection and stochastic block models: recent developments.  The Journal of Machine Learning Research, 18(1):6446–6531, 2017\.
  * [2] J. Alt, R. Ducatez, and A. Knowles.  Extremal eigenvalues of critical Erdős–Rényi graphs.  The Annals of Probability, 49(3):1347–1401, 2021.
  * [3] Z. Bai and J.-F. Yao.  Central limit theorems for eigenvalues in a spiked population model.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 44(3):447–474, 2008.
  * [4] J. Baik, G. Ben Arous, and S. Péché.  Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices.  The Annals of Probability, 33(5):1643–1697, Sept. 2005.
  * [5] F. Benaych-Georges, C. Bordenave, and A. Knowles.  Largest eigenvalues of sparse inhomogeneous Erdős–Rényi graphs.  The Annals of Probability, 47(3):1653–1676, 2019.
  * [6] F. Benaych-Georges, C. Bordenave, and A. Knowles.  Spectral radii of sparse random matrices.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 56(3):2141 –2161, 2020.
  * [7] F. Benaych-Georges, A. Guionnet, and M. Maida.  Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices.  Electronic Journal of Probability, 16(0):1621–1662, 2011.
  * [8] S. Boucheron, G. Lugosi, and P. Massart.  Concentration Inequalities: A Nonasymptotic Theory of Independence.  Oxford University Press, Oxford, 1st ed edition, 2013.
  * [9] P. Bourgade and H.-T. Yau.  The eigenvector moment flow and local quantum unique ergodicity.  Communications in Mathematical Physics, 350(1):231–278, 2017.
  * [10] M. Capitaine, C. Donati-Martin, and D. Féral.  The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations.  The Annals of Probability, 37(1):1 – 47, 2009.
  * [11] M. Capitaine, C. Donati-Martin, and D. Féral.  Central limit theorems for eigenvalues of deformations of Wigner matrices.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(1):107 – 133, 2012.
  * [12] C. Castellano and R. Pastor-Satorras.  Relating topological determinants of complex networks to their spectral properties: structural and dynamical effects.  Physical Review X, 7(4):041024, 2017.
  * [13] A. Chakrabarty, S. Chakraborty, and R. S. Hazra.  Eigenvalues outside the bulk of inhomogeneous Erdős–Rényi random graphs.  Journal of Statistical Physics, 181(5):1746–1780, 2020.
  * [14] A. Chakrabarty, R. S. Hazra, F. den Hollander, and M. Sfragara.  Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs.  Random Matrices Theory and Applications, 10:2150009, 2021.
  * [15] F. Chung and L. Lu.  Connected components in random graphs with given expected degree sequences.  Annals of Combinatorics, 6(2):125–145, 2002.
  * [16] F. Chung, L. Lu, and V. Vu.  Eigenvalues of random power law graphs.  Annals of Combinatorics, 7(1):21–33, 2003.
  * [17] P. Dionigi, D. Garlaschelli, F. den Hollander, and M. Mandjes.  A spectral signature of breaking of ensemble equivalence for constrained random graphs.  Electronic Communications in Probability, 26(none), Jan. 2021.
  * [18] L. Erdős, A. Knowles, H.-T. Yau, and J. Yin.  Spectral statistics of Erdős–Rényi graphs II: eigenvalue spacing and the extreme eigenvalues.  Communications in Mathematical Physics, 314(3):587–640, 2012.
  * [19] L. Erdős, A. Knowles, H. T. Yau, and J. Yin.  Spectral statistics of Erdős–Rényi graphs I: Local semicircle law.  Annals of Probability, 41:2279–2375, 2013.
  * [20] D. Féral and S. Péché.  The largest eigenvalue of rank one deformation of large wigner matrices.  Communications in Mathematical Physics, 272(1):185–228, 2007.
  * [21] D. Féral and S. Péché.  The largest eigenvalues of sample covariance matrices for a spiked population: Diagonal case.  Journal of Mathematical Physics, 50(7):073302, 2009.
  * [22] Z. Füredi and J. Komlós.  The eigenvalues of random symmetric matrices.  Combinatorica, 1(3):233–241, 1981.
  * [23] D. Garlaschelli, F. den Hollander, and A. Roccaverde.  Covariance Structure Behind Breaking of Ensemble Equivalence in Random Graphs.  Journal of Statistical Physics, 173(3-4):644–662, Nov. 2018.
  * [24] M. Krivelevich and B. Sudakov.  The largest eigenvalue of sparse random graphs.  Combinatorics, Probability and Computing, 12(1):61–72, 2003.
  * [25] C. M. Le, E. Levina, and R. Vershynin.  Concentration of random graphs and application to community detection.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 2925–2943. World Scientific, 2018.
  * [26] T. Martin, X. Zhang, and M. E. Newman.  Localization and centrality in networks.  Physical review E, 90(5):052808, 2014.
  * [27] M. E. Newman.  Finding community structure in networks using the eigenvectors of matrices.  Physical review E, 74(3):036104, 2006.
  * [28] R. Pastor-Satorras and C. Castellano.  Eigenvector localization in real networks and its implications for epidemic spreading.  Journal of Statistical Physics, 173(3):1110–1123, 2018.
  * [29] S. Péché.  The largest eigenvalue of small rank perturbations of Hermitian random matrices.  Probability Theory and Related Fields, 134(1):127–173, Jan. 2006\.
  * [30] T. Squartini, J. de Mol, F. den Hollander, and D. Garlaschelli.  Breaking of Ensemble Equivalence in Networks.  Physical Review Letters, 115(26):268701, Dec. 2015.
  * [31] T. Squartini and D. Garlaschelli.  Analytical maximum-likelihood method to detect patterns in real networks.  New Journal of Physics, 13(8):083001, 2011.
  * [32] A. M. Tulino and S. Verdú.  Random matrix theory and wireless communications.  Foundations and Trends in Communications and Information Theory, 1(1):1–182, 2004.
  * [33] R. van der Hofstad.  Random Graphs and Complex Networks Vol 1.  Cambridge University Press, Cambridge, 2017.