Transcript Slide - people.bath.ac.uk

Condensation phenomena in stochastic systems
Bath 2016
Quantum Statistics and
Condensation Transitions
in Networks and Simplicial Complexes
Ginestra Bianconi
School of Mathematical Sciences, Queen Mary University of London, UK
Complex networks
Between randomness and order
LATTICES
Regular networks
Symmetric
COMPLEX NETWORKS
Scale free networks
Small world
With communities
ENCODING INFORMATION IN
THEIR STRUCTURE
RANDOM GRAPHS
Totally random
Poisson degree
distribution
Outlook
• Quantum statistics and condensation transition in
complex networks
– Bose-Einstein condensation in complex networks
– Fermi-Dirac statistics in growing trees
– Condensation transitions in weighted networks
• Quantum statistics and condensation transition in
network geometry (growing simplicial complexes)
– Network geometry with flavor
– Complex Quantum Network Manifolds
BA scale-free model
(1) GROWTH :
At every timestep we add a new node with m edges
(connected to the nodes already present in the system).
(2) PREFERENTIAL ATTACHMENT :
The probability Π(ki) that a new node will be connected
to node i depends on the connectivity ki of that node
ki
 ( ki ) 
 jk j
P(k) ~k-3
Barabási et al. Science (1999)
Growth with uniform attachment
(1) GROWTH :
At every timestep we add a new node with m links
connected to the nodes already present in the system).
(2) UNIFORM ATTACHMENT :
The probability Πi that a new node will be connected to
node i is uniform
1
i 
N
Exponential

Barabási & Albert, Physica A (1999)
Intrinsic properties
of the nodes
Not all the nodes are the
same!
6
1
Let assign to each node
an energy  from a
g()distribution and
a fitness h=e-b
3
2
5
4
The Bianconi-Barabasi
model
Growth:
G. Bianconi, A.-L. Barabási 2001
–At each time a new node and m links are added to the network.
–To each node i we assign a energy i from a g() distribution
Preferential attachment towards
high degree high fitness (low energy) nodes:
–Each node connects to the rest of the network by m links attached preferentially
to well connected, low energy nodes.
6
- b i
1
3
2
5
4
e ki
i 
- b j
e k j
j
Master-equation for the degree
distribution
• The master equation for the degree distribution can
be solved using a self-consistent argument
- b
- b
e
(k
1)
e
k t
N t 1 (k)  N t (k)  m
N t (k - 1) - m
N (k)  g( ) k, m
Z(t)
Z(t)
Z(t) 
t
- b
- b
d

e
k
N
(k)
mte
 

k
t
N (k) tP (k)
Self-consistent solution of the
Bianconi Barabasi Model
• The degree distribution is given by
P(k)   d g( )e
b ( -  )
b ( -  )
(m  e
(m)
)
(k)
(k  1 e b ( -  ) )
• As long as the self-consistent equation has a
solution for the chemical potential 
1
 d g( ) e b 
1
( -)
-1
Properties of
Bianconi-Barabasi model
Power-law degree distribution
P(k)  k
-
2   3
Fit-get-rich mechanism

e - b ( -  )
t 
k (t)  m 
t i 
Latecomers with high fitness
become hubs
Mapping to a Bose gas
We can map the fitness model to a Bose gas
with
– density of states g( );
– specific volume v=1;
– temperature T=1/b.
6
1
3
2
5
4
Network
In this mapping,
– each node of energy  corresponds to an
energy level of the Bose gas
– while each link pointing to a node of energy

, corresponds to an occupation of that
energy level.
G. Bianconi, A.-L. Barabási 2001
Energy diagram
Bose-Einstein condensation
in complex networks
Scale-Free
Fit-get-rich Phase
Phase

b
bC

G. Bianconi, A.-L. Barabási 2001
Bose-Einstein
condensate
b  bC
Properties of the condensate phase
• The self-consistent assumption does not work
anymore. The chemical potential  is no
longer well defined.The finite size estimation
of  becomes positive.
Properties of the condensate state
Change of scaling behavior of the maximum degree
Time-dependent Properties of the
condensate phase
• The sequence effective chemical potential is
not self-averaging (specifically it is above zero)
Time-dependent properties of the
condensate phase
• The sequence of records with lowest energy
dominate the dynamics.
The Complex Growing
Cayley tree model
Growth:
G. Bianconi, PRE 2002
–At each time attach a old node with ri=1 to m links are added to the network
and then we set ri=0.
–To each node i we assign a energy i from a g() distribution
Attachment towards high energy nodes:
–The node i growing at time t is chosen with probability
6
4
3
2
1
5
- b i
7
e ri
i 
- b j
e r j
j
Quantum statistics
in growing networks
Scale-free network
tree
Bianconi-Barabasi model (2001)
Bose Einstein statistics
Complex Cayley
Bianconi (2002)
Fermi statistics
MF Equations
for the growing scale-free network
and the complex growing Cayley tree
network
• Scale-free
Bianconi-Barabasi model
(ki here indicates the average degree of node i)
dki (t)
e - b i ki
m
- b j
dt
e
k

j
• Complex Growing
Cayley tree
(ri here indicates the average ri of node i)

dri (t)
e - b i ri
- b j
dt
e r
j
j
j
MF Solution of the
Bianconi-Barabasi model
The average degree of node increases in time as a
power-law with an exponent depending on its energy,
b and a self-consistent constant B
t f B ( )
ki (t)  m 
f B ( )  e - b ( -  B )
t i 
The self consistent constant B is determined by the
same equation fixing the chemical potential in a Bose
gas!

1
 d g( ) e b 
1
( - B )
-1
MF Solution of the
complex growing Cayley model
The average r of node (determining the probability that
a node is at the interface) decreases in time as a powerlaw with an exponent depending on its energy,
b and a self-consistent constant F
- f F ( )
t 
ri (t)  m 
t i 
f F ( )  e
- b ( -  F )
The self consistent constant F is determined by the
same equation fixing the chemical potential in a Fermi
gas!

1
1
  d g( ) b ( - F )
m
e
1
2
The energy of the nodes in the bulk of
the complex growing Cayley tree
follows the Fermi distribution
Fitness model with reinforcement of the
links
• A fitness xij is assigned
to each link
• At each time m’ links
chosen are reinforced. They
are chosen preferentially in
within high fitness and high
weights links with
probability
 i , j  x ijw ij
G. Bianconi, EPL 2005
h6
x12
h1
h3
h2
h5
h4
Fitness of links and fitness of nodes
The fitness of the links can be dependent on
the fitness of the nodes.
– In coauthorship networks more productive authors would
collaborate more with more productive authors
– In Airport networks connections between hub airports
would increase faster their traffic
The considered cases
x i , j  hi  h j
x i , j  hi h j
Mean field treatment
The ration m’/m fixes the constant C’ that determines the speed
at which links are reinforced
 t 
w ij  w 0  
 t ij 
 
f ( x ij )
f (x ij ) 
x ij
C'
The equation which fixes C’ is given by
m'

m
 dh r(h )  dx p(xh)
1
C
h
-1
1
C'
x
-1
In particular C’ is a
decreasing function
of m’/m
Condensation of the links
When the self-consistent equation of C’ does not admit a
solution we observe a condensation of the weights of a finite
fraction of the links
Networks
Pairwise interactions define networks
Simplicial complexes
Interactions between two or more nodes define
simplicial complexes
Simplicial complexes are not only formed by nodes and
links but also by triangles, tetrahedra etc.
Brain data as simplicial complexes
Giusti et al 2016
Protein complexes as simplicies
Wan et al. Nature 2015
Collaboration networks as
simplicial complexes
Actor collaboration networks
Nodes: Actors
Simplicies: Co-actors of a movie
Scientific collaboration networks
Nodes: Scientists
Simplicies: Co-authors of a paper
Network Geometry
aims at unveiling
the hidden metric space of networks
Boguna, Krioukov, Claffy Nature Physics (2008)
Hyperbolic geometry
Sum of the angles
of a triangle 
< p
Number of
nodes
N~
D
e
Hyperbolic networks
A large variety of networks display an
hyperbolic network geometry
strongly affecting their navigability
Boguna et al. Nature Communication (2010)
Emergent geometry
It is possible that
the hyperbolic geometry is an
emergent property
of the network evolution
which follows dynamical rules
that make no use of the hidden geometry?
Simplicial complexes and network geometry
Simplicial complexes are ideal to describe
network geometry
As such they have been widely used in quantum gravity
(spin foams, tensor networks, causal dynamical triangulations)
Growing networks describe the
emergence of complexity
Science 1999
Would growing simplicial complexes
describe
the emergence of geometry?
Emergent Network Geometry
The model describes the underlying
structure of a simplicial complex
constructed by gluing together
triangles by a non-equilibrium
dynamics.
Every link is incident to
at most m triangles with m>1.
Saturated and Unsaturated links
Unsaturated link
Saturated link
m=2
• if the link is unsaturated, i.e. less than m
triangles are incident on it
• if the link is saturated, i.e. the number of
incident triangles is given by m
Process (a)
We choose a unsaturated link and
we glue a new triangle the link
Growing
Simplicial
Complex
Growing
Geometrical
Network
Process (b)
We choose two adjacent unsaturated links and we add the link
between the nodes at distance 2 and all triangles that this link
closes as long that this is allowed.
Growing
Simplicial
Complex
Growing
Geometrical
Network
The model
Starting from an initial triangle,
At each time
• process (a) takes place and
• process (b) takes place with probability p<1
Z. Wu, G. Menichetti, C. Rahmede, G. Bianconi, Scientific Reports 5, 10073 (2015)
Discrete Manifolds
A discrete manifold of
dimension d=2 is a
simplicial complex
formed by triangles
such that every link is
incident to at most two
triangles.
Exponential degree
distribution
Scale-free networks
m
For
a scale-free,
small-world network with
high clustering coefficient
and significant community
structure is generated.
m


The d-dimensional
simplicial complexes
In dimension d the growing simplicial complex
built by gluing simplices of dimension d along their (d-1)-face
In d=1 the simplices are links
In d=2 the simplices are triangles
In d=3 they are tetrahedra.
Generalized degrees
The generalized degree kd,(a) of a -face a
in a d-dimensional simplicial complex is given by the number of
d-dimensional simplices incident to the -face a.
1
2
2
5
4
5
3
3
6
Number of triangles incident
• to the
6 nodes k2,0
• to the links k2,1

i
k 2,0 (i)
(i, j)
k 2,1 (i, j)
1
3
2
1
(1,2)
(1,3)
1
3
3
4
(1,4)
1
4
1
5
2
(1,5)
(2,3)
1
1
6
1
(3,4)
1
(3,5)
(3,6)
2
1
(5,6)
1
The incidence number
To each (d-1)-face awe associate the
incidence number
na  kd,d -1 (a ) -1
na
given by
the number of d-dimensional simplices incident to
the face minus one 

If na takes only values na=0,1 the simplicial complex is
a discrete manifold.
Network Geometry with Flavor
We start with a d-dimensional simplex,
At each time we choose a (d-1)-face
with probability
a[ s]  1 s na
and we glue to it a new d-dimensional simplex
The flavor s=-1,0,1

Growing
Simplicial
Complex
Network
Geometry
with Flavor
Flavor s=-1,0,1
and attachment probability
a[ s]
(1 - na )
s  -1
 [ -1]
Z

 1
(1 s na )

  [ 0 ]
s0
(1 s na' )  Z
a'Qd,d-1
 k d , d -1 (a ) s  1

 Z [ 1]
s=-1 Manifold
s=0 Uniform attachment
s=1 Preferential attachment
na=0,1
na=0,1,2,3,4…
na=0,1,2,3,4…
Dimension d=1
Manifold
Chain
s=-1
Chain
Uniform
attachment
s=0
Exponential
Preferential
attachment
s=1
BA model
Scale-free
Dimension d=2
Manifold
Chain
s=-1
Exponential
Uniform
attachment
s=0
Scale-free
Preferential
attachment
s=1
Scale-free
Dimension d=3
Manifold
Chain
s=-1
Scale-free
Uniform
attachment
s=0
Scale-free
Preferential
attachment
s=1
Scale-free
Effective preferential attachment
emerging in d=3 dimensions
t=3
t=4
i
i
Node i has generalized degree 3
Node i has generalized degree 4
Node i is incident to 5 unsaturated faces
Node i is incident to 6 unsaturated faces
Random Apollonian networks are the
planar projections of NGF manifold in
d=3
NGF Manifold d=3 s=-1
i
Apollonian random network
Planar projection of the NGF
Degree distribution of NGF
• The NGF with s+d=0, i.e. with (s,d)=(-1,1) are
chains
• For s+d=1, i.e. (s,d)=(-1,2) and (0,1) we have
Pd[ s]
 d k -d 1
 

d  1 d  1
• For s+d>1 we have

Pd[ s]
d  s  [1 (2d  s) /(d  s - 1)]
 [k - d  d /(d  s - 1)]

2s  s
 [d / d  s - 1]
 [k - d  1 (2d  s) /(d  s - 1)]
Generalized degree distribution for
Network Geometry with Flavor (NGF)
• For s=1 the NGF are always scale-free
• For s=0 the NGF are scale-free for d>1
• For s=-1 the NGF are scale-free for d>2
G. Bianconi, C. Rahmede, Scientific Reports (2015);PRE (2016).
Generalized degree distribution
case b=0, and s=-1
• If =d-1 the generalized degrees follow a binomial distribution
d -1
 d for k 1,
Pd ,d -1 (k)  
 1 for k  2.
 d
• If =d-2 the generalized degree follow a exponential distribution
 2 k d -1
Pd ,d -2 (k)   
for k 1
d 1 2
• If <d-2 the generalized degree follow a power-law distribution
d -1 [1 (d 1) /(d -  - 2)]
[k  2 /(d -  - 2)]
Pd , (k) 
for k 1
d -  - 2 [1 2 /(d -  - 2)] [k 1 (d 1) /(d -  - 2)]
Generalized degree distributions
of NGF
Theory versus simulation in NGF s=-1,0,1 and d=3
Emergent hyperbolic geometry
The emergent hidden geometry is the hyperbolic Hd space
Here all the links have equal length
d=2
Emergent hyperbolic geometry
d=3
The pseudo-fractal geometry of
the surface of the
3d manifold
(random Apollonian network)
Energies
of the nodes
Not all the nodes are the
same!
6
Let assign to each node i
1
an energy  from a
g()distribution
5
3
4
25
Energy of the -faces
Every -face a is associated to an energy
which is the sum of the energy of the nodes
belonging to a
a   i
ia
For example, in d=3
the energy of a link
2

1
is
12
is
123
3
the energy of a face
1
2
Fitness of the -faces
The fitness of a -face a is given by
ha  e
-b  a
where b=1/T is the inverse temperature
If b=0 all the nodes have same fitness
If b>>1 small differences in energy have large impact on
the fitness of the faces

Network Geometry with Flavor
Starting from a d-dimensional simplex
We choose a (d-1)-dimensional face a,
with probability
- b a
(1 - s na )
a 
- b a '
e
 (1 - s na' )
e
a'Qd,d-1
and glue a new d-dimensional simplex to it.
The parameter b=1/T is the inverse temperature.
 If b=0 we are recast into the previous model
The flavor s=-1,0,1
Bianconi-Barabasi model or the fitness model
Is the NGF d=1 s=1
- b i
e
kni )
[ -1]
e
(1
s
a 
 i  - b - b j a
e a ' e(1 - sknja' )
- b a
a'Qd,d-1
j 1, N
b The
 baverage
bC 
C
degree of the nodesb
withenergy


follows the Bose-Einstein statistics
[k i -1] 

1
e b ( -  ) -1
G. Bianconi A.L. Barabasi PRL (2001)
Quantum statistics
and
Network Geometry with Flavor
What is the combined effect
of flavor and dimensionality
on the emergence of
quantum statistics?
The average of the generalized degree
of the NGF over -faces of energy 
k
-1
follows
d ,

G. Bianconi, C. Rahmede, Scientific Reports (2015);PRE (2016).
Manifolds in d=3
In NGF with s=-1 and d=3
also called
Complex Quantum Network Manifolds
the average of the generalized degree follow
the Fermi-Dirac, Boltzmann and Bose-Einstein
distribution
respectively for
triangular faces, links and nodes
Emergence of quantum statistics in
CQNM
The average of the generalized degrees follows either
Fermi-Dirac, Boltzmann or Bose-Einstein distributions
depending on the dimensionality of the -face
k
d ,d -1
k
- b ( -  d,d-2 )
-1


n
(

,

)

e

d ,d -2
Z
d ,d -2
k
d ,
-1  n   n F (, d ,d -1 ) 
1
e b ( -  d ,d-1 ) 1
d -
1
-1  An B (, d , ) 
d -  - 2 e b ( -  d, ) -1
for   d - 2
In d=3 the average of the generalized degree follow
the Fermi-Dirac, Boltzmann and Bose-Einstein distribution
respectively for triangular faces, links and nodes
Theory and simulations for NGF in
d=3
Emergent geometry
at high temperature
d=2
b=0.01
Emergent geometry at
low temperature
d2
b=5
Emergent geometry
at high temperature
d=3
b=0.01
Emergent geometry at
low temperature
d=3
b=5
Conclusions
Growing simplicial complexes called Network Geometry with Flavor (NGF)
display:
•
•
•
small world behavior, finite clustering coefficient, high modularity
strong dependence on the dimensionality
– NGF with s=-1 are manifolds and are scale-free for d>2
– NGF with s=0 ( uniform attachment) are scale-free for d>1
emergent hyperbolic geometry
NGF at finite temperature (with fitness and energy)
•
•
have generalized degrees following the Fermi-Dirac, Boltzmann or Bose-Einstein
distribution depending on the dimensionality of the -face and the flavor s.
NGF can undergo phase transition strongly affecting their hidden hyperbolic
geometry.
Collaboration
Zhihao Wui
Ginestra Bianconii
Christoph Rahmedei
Giulia Menichettii
References
EMERGENT COMPLEX NETWORK GEOMETRIES
• Z. Wu, G. Menichetti, C. Rahmede, G. Bianconi, Emergent Complex Network Geometry
Scientific Reports 5, 10073 (2015)
NETWORK GEOMETRY WITH FLAVOR
• G. Bianconi, C. Rahmede Network geometry with flavor: from complexity to quantum geometry
Phys. Rev. E 93, 032315 (2016).
MANIFOLDS
•
G. Bianconi, C. Rahmede, Quantum Complex Network Manifolds in d>2 are scale-free
Scientific Reports 5, 13979 (2015)
PERSPECTIVE
•
G. Bianconi, Interdisciplinary and physics challenges in network theory EPL 111, 56001 (2015).
Quantum Complex Network Geometries
•
G. Bianconi, C. Rahmede, Z. Wu, Quantum Complex Network Geometries: Evolution and Phase
Transition Phys. Rev. E 92, 022815 (2015)
Equilibrium and configuration model
O.T. Courtney and G. Bianconi, Generalized network structures: the configuration model and the
canonical ensemble of simplicial complexes arXiv: 1602.04110 (2016).