Suﬃcient conditions of endemic
threshold on metapopulation networks
Journal of Theoretical Biology 380, 134-143 (2015)
Taro Takaguchi
National Institute of Informatics, JapanJST, ERATO, Kawarabayashi Large Graph Project
Collaboration work withRenaud Lambiotte (University of Namur, Belgium)
ERATO 感謝祭 Season II, 2015年8月4日
1

At a glance
Metapopulation network+ Susceptible-infected-susceptible dynamics

city

Susceptible Infected(healthy) (sick)
Infection:+"→"person
Number of(a) numerical simulations(b) estimation of upper boundOur contribution

w. ratew. rate µ→"

Recovery:
Question: endemic threshold c ?

+"(t ! 1)

Odisease-freeendemicc

1. To prove that an upper bound (previous result)holds true for arbitrary networks.
2. To derive an improved upper bound relevant to a structural propertyof real-world networks.

2

Metapopulation SIS dynamics:
deterministic reaction-diﬀusion equation
Change in states of particles at node i (1  i, j  N )

DS

⇢I,i

DIiµ
⇢i@t ⇢S,i = µ⇢I,i⇢S,i@t ⇢I,i =⇢iµ⇢I,i +recoveryi ⌘i⇢S,i ⇢I,iDSX

Lij ⇢S,j ,ji⇢i⇢S,i ⇢I,iLij ⇢I,j .

jinfectiondiffusion⇢i : infection rate at node i (Laplacian
L : random-walk(1(i = j),Lij =Aij /kj (i 6= j).

DIX0)( A :adjacency matrix)3Motivation of i =⇢i

Schläpfer et al., J. R. Soc. Interface 11, 20130789 (2014)- Mobile-phone call data in Portugal- Number of links superlinearly increases with population size.
ln K
K / N ↵ , ↵ = 1.12(# linksin city)

ln N (city population)
Infection ratei =⇢i ,i increases with population size at each node.

=↵Most of previous studies:1 (0 
2 {0, 1}

 1)

(cf: Colizza et al., Nat. Phys. (2006); Saldaña, Phys. Rev. E (2008);
Masuda, New J. Phys. (2010))

4

Procedure of analysis
GoalDerive the endemic thresholdc (or its upper bound)

MethodDisease-free equilibrium: the fixed point of the reaction-diffusion equations⇢⇤S,i ,⇢⇤I,i=✓ki⇢, 0hkiThis fixed point is (linearly) unstable
Number of(t ! 1)

Odisease-free◆(1  8 i  N )endemic equilibrium arises

endemicc5Linear stability of a fixed point
Original equationdx = f (x) x 2 RN f : RN 7! RN
dtdx
dt

Linearized equation at x = x0@fi
dx = J(x0 ) x (J(x0 ))ij =@xj x=x0
dt

Formal solution

x(t) = exp (tJ(x0 )) x0 =X0f (x)x0
unstablex
stablec i e i t uii

Fixed point x = x0 is linearly unstable

max Re1iNi (J(x0 )) > 06

Procedure of analysis
GoalDerive the endemic thresholdc (or its upper bound)

MethodDisease-free equilibrium: the fixed point of the reaction-diffusion equations⇢⇤S,i ,⇢⇤I,i=✓ki⇢, 0hki

This fixed point is (linearly) unstablemax (◆(1  8 i  N )endemic equilibrium arises, µ, . . .) > 0→ c = · · · (exact threshold)
Otherwise → c < · · · (upper bound)max = 0 is solvable in terms of7

Previous study:
heterogeneous mean-field approximation
Saldaña, Phys. Rev. E (2008); Math. Model. Nat. Phenom. (2010)

Assumption
0- Nodes with the same k are identicalkkP (k)P (k 0 )- Links are drawn according to config model: P (k, k0 ) =hki

(uncorrelated case)

Reduced reaction-diffusion equations:@t ⇢S,k = µ⇢I,k@t ⇢I,k =⇢k 1 ⇢S,k ⇢I,kDS ⇢S,k✓µ⇢I,k + ⇢k 1 ⇢S,k ⇢I,k DI ⇢I,kDisease-free equilibrium:✓⇢⇤S,k ,⇢⇤I,k✓=k⇢, 0hki◆◆ X
P (k 0 )⇢S,k0k⇢S , k 0hki
◆ X
P (k 0 )⇢I,k0k⇢I . k0hki

8✓k⇢, 0hki

hdiagonali(2)
JHMF = . . .

DI (I+Jacobian matrix at⇢⇤S,k ,⇢⇤I,k=Saldaña, Phys. Rev. E (2008); Math. Model. Nat. Phenom. (2010)

(1)
JHMF

JHMF =(1)
JHMF =O

⇤

(2)

JHMF

DS (I+)

rank-1 matrix
with = 0, 1

Lower bound of!

[·]kk =

max of Jaccobian matrix

max (JHMF ) =(2)(Jmax HMF )◆maxc < (µ + DI )

k✓

✓

k⇢
hki

kmaxhki◆◆✓k⇢hki◆)µ(µ + DI )9

Present study: arbitrary networks
Non-reduced reaction-diffusion equations:@t ⇢S,i = µ⇢I,i1⇢i⇢S,i ⇢I,iDSXLij ⇢S,j ,j@t ⇢I,i =1µ⇢I,i + ⇢i

⇢S,i ⇢I,i

Jacobian matrix at ⇢⇤S,i , ⇢⇤I,i =J=✓J (1) =(1)JODS L⇤J (2)◆✓0 →max (J) =Lij ⇢I,j .

jki⇢, 0hkihdiagonali
J (2) = . . .

From the spectral property of L ,(L)DIX[·]ii =◆DI L
✓ki⇢hki(2)
(J)
max

◆µ10

Special cases in whichhdiagonali
J (2) = . . .
[·]ii =(a)(2)(J) is tractablemaxDI L✓ki⇢hki◆µ= 0 : population-independent infection rate(2)(J)=µc = µmax(b) the network is regular: ki = k (1  8 i  N )(2)(J)= ⇢maxµc = µ⇢Diffusion rate DI is irrelevant
114-regular random graph and square lattice
N = 1024

4-regular randomgraph= 0.5

DI = 1

DI= µ⇢

Square lattice(µ, DS , ⇢) = (1, 1, 100)

DI

12

The upper bound holds for arbitrary networks
Symmetrize J (2) via similarity transformation: Jˆ(2) ⌘ D 1/2 J (2) D 1/2> ˆ(2)xJ x(2)(2)ˆ) = max (J ) = max
max (Jxx> x
i>Let x = (0, . . . , 0, 1, 0, . . . , 0)✓◆ki(2)) max⇢(µ + DI )max (Jihki✓◆kmax
c < (µ + DI )
hki

Fact
Heterogeneous mean-field approximation:
to replace the principal eigenvector with this unit vector13

An improved upper boundLet xi =max (J((2)0p)

c < minkc

ki /Kc(ki < kc ),(ki kc ).

Kc ⌘X

j:kjkjkc

total number of links between nodes with kimaxkc( ✓✓kc⇢
hki

µ+ 1◆

kc

2Ec+ DI(µ + DI )Kc◆✓◆ )
2Eckc
DI⇢Kc
hki

Implication
More links between large-degree nodes → smaller upper bound of c14

Rich-club phenomenon
Zhou & Mondoragón, IEEE Comm. Lett (2004); Colizza et al. Nat. Phys. (2006)

Rich-club coefficient:

2E>k(k) =N>k (N>kIf

orig (k) >

1)

9(k)
fork>
kc
rand

Large-degree nodes are more likely to be adjacent to each other.
Real examples:
Airport network, coauthorship, neuronal network, etc.

15

Improved upper bound of cfor an empirical rich-club network
US airports network (data from the Koblenz network collection)

N = 1572
0.5
fraction ofinfected 0.4
particlesP

Results of numerical simulations

lI / np

0.3⇢
I,ii⇢N 0.2

minkc

0.1

(✓

µ+ 12EcKc(µ + DI )

00

0.2

0.4

0.6

0.8

✓

◆

DI

kmaxhki◆

✓kc
⇢hki)

◆1

`

(µ, DS , DI , ⇢, ) = (1, 1, 1, 100, 0.1)
16

Impacts of rich-club structure andUpper bounds as a function of kc

Upper bounds as a function of(a)

(c)

121
HMF

1.50.9``0.5

100.50.8`

0.50.7050

100 150 200 250 300
kc(µ, DS , DI , ⇢, ) = (1, 1, 1, 100, 0.1)

01

`HMF
simulations
00.2

0.4

0.6

0.8

1

a

Recall that we saw
in the phone-call data

= 0.1217

Summary- Metapopulation network + SIS epidemic dynamics✓◆- Target: endemic threshold c for arbitrary networks
kmax<(µ+D)
Upper
boundofbasedonHMF
approximation:cIchki(→ valid for arbitrary networks✓◆✓◆2Eckcµ+ 1DI⇢- An improvement of upper bound: c < minkKchki→ rich-club networks: smaller upper bound of c- Considerable improvement with realistic population-dependencyc)

Journal reference:
Taro Takaguchi and Renaud Lambiotte,“Sufficient conditions of endemic threshold on metapopulation networks”
Journal of Theoretical Biology 380, 134-143 (2015).
18