12th MSJ-SI,Fukuoka, Japan, 31/07–09/08, 2019.

Frank den Hollander
Leiden University, The Netherlands

I. SPECTRASTRUCTURE AND FUNCTIONALITYCOMPLEX NETWORKS:What can be said about the spectrum of theadjacency matrix of a large inhomogeneous
Erdős-Rényi random graph?

QUESTION ADDRESSED IN THIS TALK:

Spectra of random matrices have been analysed for almosta century. In recent years, many interesting results havebeen derived for spectra of random matrices associatedwith networks.

Rajat Hazra

Matteo Sfragara

Submitted to Random Matrices: Theory and Applications

Preprint [arXiv:1807.10112]

Arijit Chakrabarty

Erdős-Rényi random graphN →∞lim N εN = ∞.

i, jN N

,1 ≤ i, j ≤ N,independently for different edges. Write P for the law ofERN .

εN f



2. Fix N ∈ N, and consider the inhomogeneous ErdösRényi random graph ERN on N vertices where an edge isplaced between the pair of vertices {i, j} with probability

Let f : [0, 1]×[0, 1] → [0, ∞) be a continuous function suchthat f (x, y) = f (y, x) for all x, y ∈ [0, 1].

N →∞lim εN = 0,1. Let (εN )N ∈N be a sequence of positive numbers suchthat§ SETTINGwhich is a random probability distribution on R.

N1 X
ESD(AN ) =δλi(AN ),N i=1

The empirical spectral

1 ≤ i ≤ N,

for the real eigenvalues of AN .
distribution of AN is defined asλi(AN ),3. Let AN be the adjacency matrix of ERN . Writeminx,y∈[0,1]N εN

f (x, y) > 0,q= µ.

Zhu 2018

then µ is absolutely continuous with respect to Lebesgue
measure. The density of µ can be characterised implicitly
via an integral equation for its Stieltjes transform.

Furthermore, iflim ESD ANN →∞

There exists a compactly supported symmetric probability
measure µ on R such that, weakly in P-probability,

THEOREM 1:§ SCALING

x, y ∈ [0, 1],

U = UNIF[0, 1],µs = standard Wigner semicircle law,

µr = LAW[r(U )],and  denotes free multiplicative convolution.

whereµ = µr  µs ,If f is of product form, thenTHEOREM 2:

for some continuous function r : [0, 1] → [0, ∞).

f (x, y) = r(x)r(y),It is possible to identify µ whenand only if the distribution is the Wigner semicircle law.

distribution is normal, the free cumulants of degree ≥ 2 are all zero if

Just as the cumulants of degree ≥ 2 are all zero if and only if theby non-crossing partitions.

replace the classical cumulants, in the sense that partitions are replaced

the normal law in classical probability. The so-called free cumulants

In free probability, the Wigner semicircle law takes over the role ofWigner 1955

combinatorics from free probability, . . .

centering, Gaussianisation, perturbation, decoupling,

Key ingredients of the proof are:

Theorems 1–2 can be generalized to the situation wherethe function f is random, depends on N and converges toa deterministic limit as N → ∞.

THEOREM 3:statistics for social networks

Let ρ denote a probability measure on [0, ∞) with bounded
support. Let (Ri)1≤i≤N be i.i.d. random variables drawn
from ρ. Think of Ri as the sociability index of individual i.

Consider a community of N individuals, represented by thevertices in ERN . Data is available about which individuals
are acquainted. Based on this data, the sociability patternof the community has to be inferred statistically.

§ APPLICATION 1∀ 1 ≤ i, j ≤ N.

0Z ∞xρ(dx) = 1.

The statistical inference problem is to estimate ρ from AN .
To standardise ρ, we assume that

Suppose that i, j are acquainted with probability εN RiRj ,which is represented by an edge in ERN between vertices
i, j. The data that is available is the adjacency matrix AN .

0 ≤ εN RiRj ≤ 1Pick N so large thatN εNq= ρ  µs.

v
uu
Nlim ESD t
A N  = ρ  µs .
2N →∞Tr(AN )

In practice, εN is unknown, which can be worked aroundby arguing that, weakly in P-probability,

N →∞lim ESD AN

Theorem 3 gives that, weakly in P-probability,N
1 X
δRi = ρ,lim
N →∞ N
i=1Since, weakly P-a.s.,Indeed, since the moments of µs are known, the momentsof ρ can be recursively computed from the moments ofρ  µs. Since ρ is compactly supported, it can in turn becomputed via its moments.

The procedure is that ρ  µs can be statistically estimatedfrom AN . Subsequently, ρ can be estimated because themoments of ρ  µs are functions of the moments of ρ andµs .

soft configuration model

hard configuration model

is a sequence of positive integers of which we only requirethat it is graphical, i.e., there is at least one simple graphmatching these degrees.

∗ = {d∗ }d~Ni 1≤i≤N

Let SN be the set of simple graphs on N vertices. We fix
the degrees of all the vertices, namely, vertex i has degreed∗i , where§ APPLICATION 2

di(G)PN (G),G∈SN

PN (G) log PN (G),soft configuration model

PN models a random graph of which we have no priorinformation other than the average degrees.

is maximal.

−X(II) The entropy of PN , defined byequals d∗i for all i ≤ i ≤ N .

G∈SNX(I) The average degree of vertex i, defined by

The Gibbs canonical ensemble PN is the unique probability
distribution on SN with the following two properties:

NX

G ∈ SN ,1≤i<j≤N(p∗ij )AN [G](i,j) (1−p∗ij )1−AN [G](i,j), G ∈ SN ,p∗ij =,∗∗1 + xi xjx∗i x∗j∗x∗i = e−θi ,1 ≤ i 6= j ≤ N.

where AN [G] is the adjacency matrix of G, and

PN (G) =Y

Reparametrisation yields∗ = {θ ∗ }where θ~Ni 1≤i≤N is the unique sequence of Lagrange
multipliers such that property (I) is satisfied.

1
PN (G) =exp −θi∗di(G) ,ZN (θ~ ∗)i=1Property (II) forces PN to take the form Jaynes 19571≤j≤N
j6=iXp∗ij ,
1 ≤ i ≤ N,

lim mN = ∞,

N →∞

N →∞

√lim mN / N = 0.

1≤i≤NmN = max d∗i .

We focus on the regime

Abbreviate

which constitutes a set of N equations for N unknowns.

d∗i =Property (I) requires that

andThenPickwithd∗i .

lim N εN = ∞,N →∞N → ∞,

p∗ij = [1 + o(1)] εN (d∗i /mN )(d∗j /mN ).

lim εN = 0,

N →∞

,

1≤i≤NX

σNεN = m2N /σN .

σN =p∗ij = [1 + o(1)]d∗i d∗jIt turns out that in this regime

Squartini, de Mol, den Hollander, Garlaschelli 2015

N εN = ρ  µs.

qThis identifies the scaling of the ESD for the network thatis modeled by the soft configuration model as a functionof the imposed average degrees.

N →∞lim ESD ANfor some probability measure ρ, Theorem 3 gives that,weakly in P-probability,

N1 X
lim
δd∗/mN = ρi
N →∞ N
i=1

Under the assumption that

Networks with a community structure

CHALLENGE: