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

Frank den Hollander
Leiden University, The Netherlands

COMPLEX NETWORKS:STRUCTURE AND FUNCTIONALITY
III. EXPLORATION

Search algorithms on networks are important tools for theorganisation of large data sets. A key example is Google
PageRank, which assigns a weight to each element of ahyperlinked set of documents, such as the World Wide
Web, with the purpose of measuring its relative importancewithin the set.

§ SEARCHING ON NETWORKS

The weights are assigned via exploration and are obtained
recursively. A hyperlink counts as a vote of support: apage that is linked to by many pages with a high rank
receives a high rank itself.

§ SEARCHING ON COMPLEX NETWORKSB Search algorithms are modelled as random walks, moving
along the network by randomly picking an edge incident tothe vertex currently visited and jumping to the vertex at
the other end.

B Complex networks are modelled as random graphs, wherethe vertices and the edges are chosen according to someprobability distribution.

B Networks are modelled as graphs, consisting of a set ofvertices and a set of edges connecting pairs of vertices.

The answer to this question is important because it tells
us how long the search algorithm must run.

How long does it take the random walk to
explore the random graph properly?

KEY QUESTION

This line of research is very recent in the mathematics
literature.

For random walks on static random graphs, the mixing
time has been the subject of intensive study. However,since many networks are dynamic in nature, it is natural to
study random walks on dynamic random graphs.

The mixing time of a random walk is the timeit needs to approach its stationary distribution.

Hakan Guldas

Stochastic Processes and Applications 2019

Annals of Applied Probability 2018

Papers:Luca Avena

Remco van der HofstadIn this talk we consider a discrete-time dynamic versionof the configuration model, where at each unit of time acertain fraction of the edges is rewired.

The configuration model is a random graph with aprescribed degree sequence. It is popular becauseof its mathematical tractability and its flexibility
in modelling real-world networks.

§ CONFIGURATION MODEL

i=1NX

di = even.

,1 ≤ i ≤ N,

and does not depend on the outcome of the draw.

j=1 djdπ(i) = PN i

We draw a random graph uniformly from the set G(d~N ).
The outcome may have self-loops and multiple edges. The
stationary distribution of the random walk equals

d~N = (di)N
i=1 ,Let G(d~N ) denote the set of all graphs on N vertices witha prescribed degree sequence

STATIC VERSIONExample with N = 6 and d~N = (1, 3, 1, 3, 2, 4)

One way to generate the random graph is by randomly
pairing half-edges:

1= limN →∞cPN
i=1 log di ,PN
i=1 diN → ∞,Berestycki, Lubetzky, Peres and Sly 2018

Ben-Hamou and Salez 2017

Lubetsky and Sly 2010

subject to certain regularity assumptions on the degrees.

with[1 + o(1)] c log N,

For random walk on the static configuration model, themixing time is known to be3. After the rewiring, let the random walk make a step toa randomly chosen neighbouring vertex.

2. Rewire these edges by breaking them into half-edges
and pairing these half-edges again randomly.

1. Draw edges randomly with probability αN ∈ (0, 1).

For fixed N , draw a starting graph η and a starting vertex
i, and proceed as follows. At each time t ∈ N:

DYNAMIC VERSION

Bold edges on the right are the newly formed edges.

Bold edges on the left are the ones chosen to be rewired.

→• limN →∞ αN = 0, i.e., the dynamics is slow.

• The random walk is non-backtracking, i.e., immediate
jumps back along edges are not allowed.

• The degrees must be moderate, i.e., not too large.

KEY ASSUMPTIONS

j=1|Pη,i(Xt = j) − π(j)|to denote total variation distance between the distributionof Xt and the stationary distribution π.

Dη,i(t) = 12NX

Let Xt denote the location of the random walk at timet ∈ N, and write

Let Pη,i denote probability with respect to the joint processof random graph and random walk with starting graph ηand starting vertex i.

§ MIXING TIME

subcritical regime(3) limN →∞ αN (log N )2 = 0

critical regime(2) limN →∞ αN (log N )2 = β ∈ (0, ∞)supercritical regime(1) limN →∞ αN (log N )2 = ∞It turns out that there is are three regimes:

TRICHOTOMY

(1 − o(1), s ∈ [0, c),o(1),s ∈ [c, ∞).

Here, c is the constant in the static version.

(2s ∈ [0, ∞).

e−βs /2 + o(1), s ∈ [0, c),o(1),s ∈ [c, ∞).

Dη,i(s log N ) =(3) subcritical regime:Dη,i(s log N ) =(2) critical regime:

2√Dη,i(s/ αN ) = e−s /2 + o(1),(1) supercritical regime:

With high probability, i.e., for a set of (η, i) with probability
tending to 1 as N → ∞, the following hold.

MAIN THEOREM

D(t)• subcritical regime:D(t)• critical regime:D(t)• supercritical regime:

111

√
αN

t/c log N

t/c log Nt• The proof is based on a stopping time argument: thefirst time the random walk moves along an edge thathas been relocated is close to a strong uniform time.

• In the critical regime and the subcritical regime themixing time is of order log N and depends on the degreesequence.

and does not depend on the degree sequence.

√1/ αN  log N,• In the supercritical regime the mixing time is of order

REMARKSB What happens when only edges touched by the random
walk can be rewired?

B What effect do hubs have on the mixing time?

§ FUTURE CHALLENGES