Transcript Y. Kim

Conserved Mass Aggregation and Lamblion Problem on complex networks
Yup Kim
Kyung Hee University
References
S. Kwon, S. Lee and Y. Kim, PRE 73, 056102 (2006)
S. Lee, S. Yook and Y. Kim, Submitted to PRE, cond-mat/0603647
S. Lee, S. Yook and Y. Kim, Submitted to PRL
Collaborations
Soon-Hyung Yook, Sungchul Kwon, Sungmin Lee
The 2nd KIAS Conference on Statistical Physics (2006)
1
Outline
•
Condensation phase transition on complex networks
•
•
Lamb-lion problem on complex networks
Application
•
Conclusions
–
–
–
–
–
–
–
Symmetric Conserved mass aggregation (SCMA) model
SCMA model on complex networks
Mass distribution of a node with degree k, m(k)
Existence of infinite aggregation
Finite sized results for random walks (RWs) on scale-free
networks (SFNs)
Peer-to-Peer network
Propose an efficient algorithm
The 2nd KIAS Conference on Statistical Physics (2006)
2
Condensation phase transition
Examples :
clouds,
colloidal suspensions,
polymer gels,
aerosols,
river networks
fluid phase
Condensed phase
- Symmetric Conserved-mass aggregation (SCMA) model
Diffusion with unit rate :
mi  0 , m j  m j
Chipping with rate  :
 mi
Diffusion
(j is one of nns to i)
mi  mi  1 , m j  m j  1
Diffusion tends to aggregate masses.
Chipping tends to split masses.
Chipping
S. N. Majumdar et al, J. Stat. Phys. 99, 1 (2000)
The 2nd KIAS Conference on Statistical Physics (2006)
3
  0 ) : aggregation on a site
chipping-dominant (    ) : masses scattered over entire lattice.
diffusion-dominant (
(zero-range process : ZRP)
For 0     , competition between diffusion and chipping
→ phase transitions from condensed phase into fluid phase.
Zero Range Process (ZRP)
Braz. J. Phys. 30, 42 (2000)
Hopping
Jumping
A particle jumps out of the site at the rate
and hops to a site
with the Probability
.
A condensed phase, which a finite fraction of
total particles condenses on a single site,
arises or not according to
,
.
The 2nd KIAS Conference on Statistical Physics (2006)
4
Phase diagram
Order parameter : P(m) = mass distribution of a single site
= Probability that a site has mass m in the steady state.

P(m)
Condensed
phase
Fluid phase
m
P(m) ~ e
 m / m*
~ m 
in fluid phase
at criticalit y
~ m   condensate

Mean field theory
c    1  1
  5/ 2
The 2nd KIAS Conference on Statistical Physics (2006)
5
- SCMA model on complex networks
scale-free networks (SFNs)
Degree distribution
Diffusion with unit rate :
Chipping with rate ω :
m i  0 , m j  m j  mi
mi  mi  1 , m j  m j  1
ω= 0 : complete condensation on a node
ω = ∞ : Zero-range process with constant chipping rate
→ Condensation always exists on scale free networks with   2
; J. D. Noh et al, Phys. Rev. Lett. 94, 198701 (2005).
What about 0 < ω < ∞ case on SFNs ?
What is the effect of underlying topology like SFNs on condensation transitions ?
The 2nd KIAS Conference on Statistical Physics (2006)
6
(1) Random and scale free networks of   3
N = # of nodes = 10000, K = # of links = <k>N/2 = 20000
<k> = average degree = 4 in our simulations
(a) = Random net. (RN) (b) = SFN of   4.3
The 2nd KIAS Conference on Statistical Physics (2006)
7
Phase diagram : RNs (a) and SFN of   4.3 (b)
  2.38( 3 ) : RN
  2.33( 2 ) :   4.3
The same type of
condensation transition as
those on regular lattices.
(SFN with   3 )
But the critical line
depends on network
structures.
The 2nd KIAS Conference on Statistical Physics (2006)
8
(2) SFNs of   3
(a)   3.0 (b) 
 2.4
(c) expected phase diagram
In   0 limit, it is practically impossible to show the existence of the condensation.
(Consideration of Diffusive Capture Process or Lamb-Lion Problem on the networks).
The 2nd KIAS Conference on Statistical Physics (2006)
9
Total mass of nodes with degree k = M k
In a certain run of simulation,
 1
  3 (  2.4)
By diffusion, the aggregate diffuses around networks and the
dominant hub is not the node at which the condensate is located
unlike ZRP.
The 2nd KIAS Conference on Statistical Physics (2006)
10
- Average mass of a node with degree k ,
mk
At    , it was shown that complete condensation always
takes place on SFNs. What about on RNs ?
ZRP on SFN
PRL 94,
198701 (2005)
For
0  
, the behavior in the condensed phase ?
 1
 3
The 2nd KIAS Conference on Statistical Physics (2006)
11

M k   m P ( m, k )
m 0
P (m, k )  P (m) Pk
Pk
= the probability of finding a random walker on
degree k in k-space
The 2nd KIAS Conference on Statistical Physics (2006)
12

- Existence of infinite aggregation
Condensed
phase
Condensed
phase
Fluid phase

Fluid
phase
Or

Condensed phase
(no Fluid phase)

Lamb-lion problem
- For the existence of an infinite condensate, the two
masses should aggregate again in finite time interval.
- If not, unit mass continuously chips off from the infinite
aggregation, which will finally disappear.
S (t ) : survival probability
T
: average life time
finite
The 2nd KIAS Conference on Statistical Physics (2006)
13
- Finite sized results for RWs on SFNs
1
1
10
10
0
0
=4.3
10
10
-1
10
Nv(t)/N
Nv(t)/N
10
-2
10
-3
10
-4
10
N=1000
N=10000
N=100000
N=1000000
-5
10
-6
10
-2
10
-3
10
-4
10
N=1000
N=10000
N=100000
N=1000000
-5
10
-6
10
-7
-7
10
=3.0
-1
-7
-6
-5
-4
-3
-2
-1
10 10 10 10 10 10 10
0
1
2
3
4
10
5
-7
-6
-5
-4
-3
-2
-1
10 10 10 10 10 10 10
10 10 10 10 10 10
0
1
2
3
4
5
10 10 10 10 10 10
t/N
t/N
1
10
0
=2.4
10
Nv
: The number of visited distinct
sites of a random walker
Tsat
: The saturation time
-1
Nv(t)/N
10
-2
10
-3
10
T
-4
10
N=1000
N=10000
N=100000
N=1000000
-5
10
-6
10
For any
-7
10
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
10 10 10 10 10 10 10 10 10 10 10 10 10 10
t/N
: The average life time

Tsat ~ Nv ~ t ~ N
The 2nd KIAS Conference on Statistical Physics (2006)
14
=3.0
0.65
0
10
R / (log(N))
R/ (log(N))
0.97
=4.3
N=1000
N=10000
N=100000
N=1000000
1
N=1000
N=10000
N=100000
N=1000000
-1
10
-1
10
0
1
10
2
10
3
10
t / (log(N))
10
-1
10
0.97
0
10
1
10
2
3
10
t / (log(N))
10
4
10
0.65
R / (log(log(N)))
0.45
6
=2.4
5
4
3
R
: the distance between
two random walkers
(the shortest path)
N
: the number of nodes
2
N=1000
N=10000
N=100000
N=1000000
1
0
10
1
10
2
10
3
10
4
10
t / (log(log(N)))
5
10
0.45
The 2nd KIAS Conference on Statistical Physics (2006)
15
Diffusive capture process = lamb-lion problem
Static trap
On regular
lattice
Yes
random walker to random walker
?

random walker
On networks
No!!
Hub effect
The 2nd KIAS Conference on Statistical Physics (2006)
16
Lamb-lion problem
The diffusion-controlled reactions, in which diffusing particles
are immediately converted to a product if a pair of them meets
together, have many physical applications.
Examples : electron trapping and recombination, wetting, melting,
exciton fusion, and commensurate-incommensurate transitions
PRB 39, 889 (1989), JSP 34, 667 (1984), PRB 29, 239 (1984), JPA 21, L89 (1988)
Among these examples, dynamic properties of wetting, melting, and commensurateincommensurate transition are known to be related to the diffusive capture process,
whose kinetics can be simplified by lamb-lion problem (diffusing preys-predators model).
Diffusion-controlled
reaction
First passage
phenomena of RWs
Survival probability
of a diffusing lamb
What is the survival probability
of a diffusing
lamb which is hunted by
hungry lions?
On regular lattice
P.L.Krapivsky and S.Redner J.Phys.A 29, 5347 (1996)
The 2nd KIAS Conference on Statistical Physics (2006)
17
One of interesting applications can be found in searching information over the Internet.
The major searching engines, such as Google, use general
random walking robots along the links between hyper-texts
to collect information of each web page.
The searching algorithm can be mapped to the system of
a diffusing particle to find an immobile absorbing particle.
Our model
Initially a lamb and
lions are randomly
distributed to the nodes on the networks.
Korean Phys. Soc. 48, S202 (2006)
At each time step, a lamb and
lions
take random walks simultaneously.
If the lamb meets the lion, the lamb is
captured.
Degree distribution
The 2nd KIAS Conference on Statistical Physics (2006)
18
We measure
and
on LSFNs with various
and network size
.
The 2nd KIAS Conference on Statistical Physics (2006)
19
We measure the average life time
and the survival probability
on TSFNs.
The 2nd KIAS Conference on Statistical Physics (2006)
20
Origin of long-living tail of
for
The data explicitly shows that lamb-lion
with
corresponds to the long
surviving tail. In the used networks, the
explicitly demonstrates that the
lamb and the lion are in different
branches.
The 2nd KIAS Conference on Statistical Physics (2006)
21
Relation between degrees and capture events
PRL 92, 118701 (2004).
We measure the number of captures
occurring at a node with degree .
Assume
(
: the model dependent parameter satisfying
)
increases as
for
.
Determined 's from the data in (a) and (b) are
for LSFN and
for TSFN.
The 2nd KIAS Conference on Statistical Physics (2006)
22
Relation between degrees and capture events
Assume
(
: the model dependent parameter satisfying
)
increases as
for
.
Determined 's from the data in (a) and (b) are
for LSFN and
for TSFN.
provides the topological origin of the gathering behavior of random
walks at hubs. This implies that the lamb and the lion have a strong tendency to move into
big hubs.
The 2nd KIAS Conference on Statistical Physics (2006)
23
Application
Complex Network
Lamb
Information packet
Lion
Query packet
We apply results of our study on diffusive capture process
to the searching algorithm to find file in the Peer-to-Peer
(P2P) file-sharing networks.
P2P systems are distributed systems in which nodes
exchange files directly with each other.
Implementing an efficient searching algorithm is the key
to a better performance of P2P protocol design.
The 2nd KIAS Conference on Statistical Physics (2006)
24
Flooding based algorithm (FB)
n-random walker algorithm (n-RW)
query packet
s
s
T
Each node forwards the received query
packets to all of its nearest neighbors until
the pre-assigned time-to-live (TTL)
becomes 0.
FB causes significant traffic congestion. For
example, the P2P traffic consumes 60-70%
of European Operators’ bandwidth.
(http://www.theregister.co.uk/2003/10/14
/edonkey_rides_like_the_wind/)
T
The node who want to search a file
produces n query packets. Each
querying packet takes random walks
along the P2P connections until the
pre-assigned TTL becomes 0.
n-RW algorithm can cause long waiting
time if there are a few requested files in
the network and they are located at the
node with small number of connections.
The 2nd KIAS Conference on Statistical Physics (2006)
25
Degree distribution of P2P network
In general, the degree distribution of P2P networks follows the power law,
with
, or highly skewed fat-tailed distributions.
(=> Expect attracting hubs)
L.A.Adam, R.M.Lukose, B.Huberman, & A.R.Puniyani, PRE 64, 46135 (2001)
M.Ripeanu, I.Foster & A.Iamnitchi, IEEE Internet Computing Journal 6, 50 (2002)
Stutzbach, D. & Rejaie, R. In Global Internet Symposium, 127 Mar. (2005)
=> exists effective attractor (Hubs)
We expect two main benefits by using new algorithm.
1) the amount of traffic is constant and much less than FB algorithm
2) provide more scalable searching time than n-RW algorithm
The 2nd KIAS Conference on Statistical Physics (2006)
26
Propose an efficient algorithm
information packet
query packet
s
n-lion and lamb algorithm (NLL)
i) Each node sends out an information packet (names of files + IP address).
(Each of these packets takes random walks along the P2P connections.)
ii) Independently, a randomly chosen node sends out one query packet to find
a specific file. (The query packet also takes random walks.)
iii) If the query packet meets an information packet which has the requested file
name in its list, then the IP information in the information packet is sent back
to the requesting node.
iv) And then the query packet is discarded but the information packets continue
random walks for the next query.
One query event
The 2nd KIAS Conference on Statistical Physics (2006)
27
The average traffic
of each algorithm.
FB generates around 50 times more traffic than NLL on the average.
The inset shows the time evolution of
obtained from a single run of simulation of FB.
The local maximum exceeds
which is 2,000 times larger than the traffic generated
by NLL.
At the moment of occurring such large amount of traffic, FB would consume
the most of the bandwidth of the Internet and cause severe traffic congestion
over the network. However, NLL always guarantees a constant level of traffic,
which is much less than that of FB and comparable to that of n-RW.
The 2nd KIAS Conference on Statistical Physics (2006)
28
: the number of available files on a network
The average searching time of NLL on SFNs is,
at least, 10 times faster than n-RW on SFNs.
: the average searching time
increases almost linearly for n-RW
. However, NLL
for small
, but
grows as
The average searching times satisfy
seems to be less than 0.5 or
The difference between NLL and 2-RW,
, increases as
becomes saturated to a fixed finite value
.
for large
.
Since the probability that two random walks visits a node with degree
is proportional to
, the hub can collect all information packets.
(More scalable searching time than n-RW)
hub
The 2nd KIAS Conference on Statistical Physics (2006)
29
Conclusion
On RN and SFNs with
, CMA model undergoes the same type
of condensation transitions as one dimensional lattice.
(The critical line depends on the underlying network structures.)
On SFNs with
, an infinite aggregation with exponentially
decaying background mass distribution always takes place for any
nonzero density. (no phase transitions)
On TSFNs,
On LSFNs,
The 2nd KIAS Conference on Statistical Physics (2006)
30
The lamb and the lion have a strong tendency to move into big hubs.
By numerical simulations, we verify that our new searching algorithm can
drastically decrease the traffic congestion compared to FB algorithm and
can provide more scalable average searching time than n-RW algorithm
and comparable with FB algorithm.
The hubs spontaneously play a very similar role of the directory servers
in structured P2P networks. However, we expect the one of the advantages
of using NLL algorithm can be in reducing large amount of system
resources for the directory server to store and handle the huge centralized
information packet, because most of information packets stay on the
dominant hubs and their nearest neighbors for a considerable amount of
time. Therefore, the information on the nearest neighbors of the hubs at a
given time is easily accessed through the hubs by random walks without
storing all information at the hubs.
The 2nd KIAS Conference on Statistical Physics (2006)
31
  3 SFNs
S (t ) : survival probability
Tsat ~ Nv ~ T ~ N

(  1)
If T ~ N
Then S (t ) is finite.
T
Tsat
N
 0

Static trap
On regular
lattice
Yes
random walker to random walker
?

random walker
On networks
No!!
Hub effect
The 2nd KIAS Conference on Statistical Physics (2006)
32