Transcript r - kitpc

Link-adding percolations of networks with the
rules depending on geometric distance on a
two-dimensional plane
Chen-Ping Zhu1,2, Long Tao Jia1
1.Nanjing University of Aeronautics and Astronautics, Nanjing, China
2.Research Center of complex system sciences of Shanghai University of
Science and Technology, Shanghai, China
Outlines

Background
 Motivation
 Link-adding percolation of networks with the
rules depending on




Generalized gravitation
Topological links inside a transmission range
Generalized gravitation inside a transmission
range
Conclusions
2
Background：Product Rule
A: the rule yielding ER graph，link two disconnected nodes arbitrarily。
B：Achlioptas link-adding process，The product Rule. Randomly choose
two candidate links, and count the masses of components
M1,M2,M3,M4 ,respectively, the nodes belongs to. Link the e1 if
M1 (7) *M 2 (2)  M 3 (4) * M 4 (4)
C：phases in A, B processes. The ratio of size(mass) of giant component
increase with the number of added links.
Science, Achlioptas, 323, 1453-1455(2009)
3
Background：Product Rule
The background of explosive percolation
in real systems?

Achlioptas: k-sat problems
4
Background：Transmitting range
and decaying probability on geometric distance

Transmitting range of mobile ad hoc
networks(MANET)
Demanded by energy-saving in an
ad hoc network, every node has a limited
transmission range, could not
connect to all others directly.

Linking probability decays with geometric
distance--gravitation models
To link or not depending real distance in most of practical
networks. Generally speaking, connecting probability decays as
the distance.
Yanqing.Hu, Zengru.Di , arxiv. 2010.
G.Li, H.E.Stanley , PRL 104(018701). 2010.
5
Introduction to MANET
traditional communication network
mobile ad hoc network
6
Introduction to MANET

A mobile ad hoc network is a collection of
nodes. Wireless communication among nodes
works over possibly multi-hop paths without the
help of any infrastructure such as base stations.

Ad hoc network: infrastructureless, peer-to-peer
network, multi-hop, self-organized dynamically,
energy-limited
7
Effect of transmitting range
increases transmitting radius
Interference between
nodes: increases
 Energy consumption:
increases (Nodes can not be
recharged)
 Network output:
decreases
(MAC mechanism)

8
Effect of transmitting radius

Decrease transmitting
radius
network breaks into
pieces
9
Contradiction and equilibrium
A contradiction between global connectivity
and energy-saving (life-time)!
An equilibrium between both sides is demanded,
which asks transmission radius r and occupation
density  of nodes adapt to each other.
10
Scaling behavior of critical connectivity
r
1.0
0.8
r=2r0
c
2r0
0.21
3r0
0.13
4r0
0.09
5r0
0.065
6r0
0.037
r=3r0
r=4r0
0.6

r=5r0
r=6r0
0.4
analysis
0.2
0.0
0.01
0.1

11

Scaling behavior of critical connectivity
 ~ f (R )
1.1
1.2
1.0

0.9
R  (r  r0 ) r0
1.4
1.0
0.8
0.8
0.7
N=3600
N=10000
N=40000
0.6
r=2r0
0.4
r=3r0
0.2
0.6
0.5
r=4r0
0.0
-0.2

0.1
0.2
0.3
r=5r0
0.4
r=6r0
0.4
R=1
R=2
R=3
R=4
R=5
0.3
r0=1
0.2
N=40000
0.1
0.0
-0.1
-6.0
  0.49
-5.5
-5.0
-4.5
-4.0
-3.5
-3.0
-2.5
-2.0
-1.5
-1.0
-0.5
ln
12
Background：Transmitting range
and geometric distance

Transmitting range of mobile ad hoc
networks(MANET)
Demanded by energy-saving in an
ad hoc network, every node has a limited
transmission range, could not
connect all others directly.

Linking probability decays with geometric
distance--gravitation models
To link or not depending real distance in most of practical
networks. Generally speaking, connecting probability decays as
the distance.
Yanqing.Hu, Zengru.Di , arxiv. 2010.
G.Li, H.E.Stanley , PRL 104(018701). 2010.
13
Background：linking probability decays as the
distance with the power d
a  d in the present work,
adjustable
G.Li, H.E.Stanley , PRL 104(018701). 2010.
Cost model
14
Background：gravitation models


A tool for analyzing bilateral trading, traffic flux
The scale of bilateral trading is proportional to gross
economic quantity of each side, inversely proportional
to the distance between them.
M ij  K
J.Tinbergen, 1962.
YiY j
Rij
P, Pöyhönen, Weltwirtschaftliches Archiv, 1963
J. E. Anderson, The American Economic Review, 1979
J.H. Bergstrand ., The review of economics and statistics.1985.
E Helpman, PR Krugman , MIT press Cambridge.1985.
Deardorff, A.V., NBER Working Paper 5377.1995.
15

Karbovski
16
Gravity model in MANET

Gravity model in MANET
Radhika Ranjan Roy, Gravity Mobility
Handbook of Mobile Ad Hoc Networks for Mobility Models
Part 2, 443-482 (2011)
17
motivation

What effect will be caused
when Product Rule is
combined with the
ingredient of distance?
1. Gravitation rule
2. Topological connection
within transmission range
3. Gravitation rule within
transmission range
Continuous percolation
transition/ “explosive
percolation”？
18
Denote quantities

N: number of nodes； N=L*L; L length of the lattice;

T: number of total links /N；
R : geometric distance between nodes;
M: mass of a component;
d: adjustable parameter；
r: transmission radius；
C: the ratio of the largest component, M/N;
Tc: transition point






19

Link-adding percolation of networks
with the rules depending on geometric
distance
20
Model 1：decaying on distance to the power of d
(generalized gravitation)

Produce 2 links just as
the PR, calculate the
masses of components
that 4 nodes belong to
Question:
Facilitate/prohibit percolation?
With maximum gravitation：
M3 * M 4
M1 *M 2

d
d
R12
R34
With minimum gravitation：
M3 * M 4
M1 *M 2

d
d
R12
R34
21
The rule with minimum gravitation
With minimum gravitation，percolation Probability decays as the d power of
distance. Inset: Tc vs. d N=128*128. d: 0-50. 100 realizations
percolation goes towards of ER when d ---> inf.
22
With maximum gravitation
C~d -α F [
T  T0
d ]
T0
=0.006,  =0.17
N=L*L， L=128， T0=0.826
a
Scaling relation of percolation probability C(T,d)
23
Model 2：topological linking within
transmission range (radius r)
Inside a given transmission range
M1 *M 2 M3 *M 4

d
R12
R34d
With max
Grav.：
Purple circle：
transmission range
With mim
Grav.：
Let d=0 for
gravitation rule.
M1 (1) *M 2 (3)  M3 (3) * M 4 (5)
M1 (1) *M 2 (3)  M3 (3) * M 4 (5)
24
Topological linking inside a transmission range
Mim. Grav.
Mam. Grav.
With the constraint of limited transmission ranges，no scaling relation
is found out for linking two node topologically without decaying with
distance. It constraint from r becomes weaker (r increases), mim. Grav.
Goes towards PR.
25
Model 3：gravitation rules inside transmission
ranges
Inside a transmission range r
Max. Grav.：
M3 * M 4
M1 *M 2

d
d
R12
R34
Min. Grav.：
M3 * M 4
M1 *M 2

d
d
R12
R34
Purple circle:
transmission circle
26
Gravitation rule inside a transmission range：
max. grav.
Given r，for diff. r，
select links with
the
rule of min. grav.,
scaling relation
exists,
for r=(3,8)
C~ r

r  r0
H [T *
r0

]
=0.1，0.1， d=2，
N=L*L， L=128，r0=2
27
Gravitation rule inside a transmission range：min. grav.
Given r，for diff. d，
select links with the
rule of min.grav.,
scaling relation exists

T  T0
d 
C ~   G[
T0
2

d]
0.23，0.01，r=5r0，L=128，
N=L*L，T0=3
28
Finite size scaling transformation：
scaling law for continuous phase transition (min.grav.)
With a given transmission radius r and distance-decaying power d
C ~ N   / Q[(T - TC ) * N1/ ]
Scaling law for continuous phase transition
1/0.2,/0.005,/0.995
 N
C2  C
2
χ ~ N / Z [(T - TC ) * N1/ ]
/1/.
F.Radicchi, PRL, 103,168701,(2009)
29
Scaling law for continuous phase transition
/1/.
30
Conclusions

Based on real backgrounds：gravitation rules, cost models,
MANET，we extend the Product Rule. We realized the
crossover from continuous percolation of ER graphs to the
explosive percolation with minimum gravitation rule.

Extend PR，set up 3 types of models----gravitation rules,
topological linking inside limited transmission ranges, and the
combination of both, test the effects with selective preferences
of maximum gravitation and minimum gravitation, respectively.
31
Conclusions

5 scaling relations are found with numerical
simulations
r  r0
C ~ r  H [T *
r0

T  T0
d 
C ~   G[
T0
2

T  T0 
d ]
T0
]
C~d -α F [
]
C ~ N   / Q[(T - TC ) * N1/ ]

χ ~ N / Z [(T - TC ) * N1/ ]

A scaling law for link-adding process with min. grav. rule is
found with varying r and d, which suggests a continuous phase
transition.

/1/.
We can shift thresholds of percolation in (0.36, 1.5) taking
geometric distance into account.
32
参考文献
[1] D. Achlioptas. R. M. D’Souza. and J. Spencer, “Explosive Percolation in Random
Networks”, Science, vol. 323, pp. 1453-1455, Mar. 2009.
[2] R. M. Ziff, “Explosive Growth in Biased Dynamic Percolation on Two-Dimensional
Regular Lattice Networks”, Phys. Rev. Lett, vol. 103, pp. 045701(1)-(4), Jul. 2009.
[3] Y. S. Cho. et al, “Percolation Transitions in Scale-Free Networks under the
Achlioptas Process”, Phys. Rev. Lett, vol. 103, pp. 135702(1)-(4), Sep. 2009.
[4] F. Radicchi and S. Fortunato, “Explosive Percolation in Scale-Free Networks”,
Phys. Rev Lett, vol. 103, pp. 168701(1)-168701(4), Oct. 2009.
[5] Friedman EJ, Landsberg AS, “Construction and Analysis of Random Networks with
Explosive Percolation”, Phys. Rev Lett, vol. 103, 255701, Dec. 2009.
[6] D'Souza RM, Mitzenmacher M, “Local Cluster Aggregation Models of Explosive
Percolation”, Phys. Rev Lett, vol. 104, 195702, May. 2010.
[7] Moreira AA, Oliveira EA, et al. “Hamiltonian approach for explosive percolation”,
Physical Review E, vol. 81, 040101, Apr. 2010.
[8] Araujo NAM, Herrmann HJ, “Explosive Percolation via Control of the Largest
Cluster”, Phys. Rev. Lett, vol. 105, 035701, Jul. 2010.
33
Thank you!
34
We can shift thresholds of percolation in
(0.36, 1.5) taking geometric distance into account.

35
Tc( N )  Tc  bN 1/
1.48
Tc
Fit of Tc
1.46
1.44
Equation
y = a + b*x^c
Tc
Adj. R-Squar
0.98485
Value
1.42
Standard Err
Tc
a
1.54044
0.00819
Tc
b
-0.6337
0.04526
Tc
c
-0.2
0
1.40
1.38
0
10000
20000
30000
40000
50000
60000
70000
N
36
37