Transcript 幻灯片 1 - University of Southern California

Tipping Points, Statistics of
opinion dynamics
Chjan Lim, Mathematical Sciences,
RPI
Collaboration with B. Szymanski, W
Zhang, Y. Treitman, G. Korniss
Funding
Main: ARO grant 2009 – 2013 Prog Officer
C. Arney, R. Zachary; ARO grant 2012 –
2015 Prog Officer P. Iyer
Secondary: ARL grants 2009 – 2012, ONR
Applications
Predict Average Outcomes, Properties in
Networks of Semi-Autonomous sensorbots / drones.

Less direct and more qualitative
predictions of social-political-culturaleconomic networks
NG NG NG and more
Background of Naming Games (NG)
Other variants of signaling games
NG on Different networks
On Complete graphs – simple mean field
NG on ER graph
SDE model of NG
NG in detection community structure
Q. Lu, G. Korniss, and B.K. Szymanski, J. Economic Interaction and Coordination,4, 221-235 (2009).
Two Names NG are End-Games for 3 Names case
A
B
AB
ABC
A
B
C
C
Tipping Point of NG
 A minority of committed agents can persuade
the whole network to a global consensus.
 The critical value for phase transition is called
the “tipping point”.
J. Xie, S. Sreenivasan, G. Korniss, W.
Zhang, C. Lim and B. K. Szymanski
PHYSICAL REVIEW E (2011)
Saddle node bifurcation
Below Critical
Above Critical
Node
Saddle
unstable
Node
Node
Meanfield Assumption and Complete
Network
The network structure is ignored. Every
node is only affected by the meanfield.
The meanfield depends only on the
fractions(or numbers) of all types of nodes.
Describe the dynamics by an equation of
the meanfield (macrostate).
Scale of consensus time on complet
graph
2 word Naming Game on complete graph
38
36
numerical simulation
analytical result by linear solver
34
32
T/N
30
28
26
24
22
20
18
3.5
4
4.5
5
5.5
log(N)
6
6.5
7
Expected Time Spend on Each
Macrostate before Consensus (without
committed agents)
60
40
A
B
T(n , n )
50
30
20
10
0
100
100
80
80
60
60
40
40
20
20
nA
0
0
nB
NG with Committed Agents
q=0.06<qc
q=0.12>qc
q is the fraction of agents committed in A.
When q is below a critical value qc, the process
may stuck in a meta-stable state for a very
long time.
Higher stubbornness – same qualitative,
robust result
Two Names NG are End-Games for 3 Names case
A
B
AB
ABC
A
B
C
C
2 Word Naming Game as a
2D random walk
n_B
P(B+)
P(A-)
P(A+)
Transient State
P(B-)
Absorbing State
n_A
Linear Solver for 2-Name NG
Have equations:
Then we assign an order to the coordinates, make
,
into vectors, and finally write equations in the linear system form:
SDE models for NG, NG and NG
Higher stubbornness – same qualitative,
robust result
Diffusion vs Drift
Diffusion scales are clear from broadening
of trajectories bundles
Drift governed by mean field nonlinear
ODEs can be seen from the average /
midlines of bundles
Other NG variants – same 1D manifold
3D plot of trajectory bundles –
stubbornness K = 10 as example of
variant (Y. Treitman and C. Lim 2012)
Consensus time distribution
 Recursive relationship of P(X, T), the probability
for consensus at T starting from X, Q is the
transition matrix.
Take each column for the same T as a vector:
Calculate the whole table P(X,T) iteratively.
Take each row for the same X as a vector:
Consensus time distribution
-4
1.8
-7
p=0.1
x 10
4
numerical
analytical
1.6
p=0.06
x 10
numerical
analytical
3.5
1.4
3
1.2
P(T )
1
c
c
P(T )
2.5
0.8
2
1.5
0.6
1
0.4
0.5
0.2
0
0
0.5
1
1.5
2
Tc
2.5
3
3.5
4
4
x 10
0
0
0.5
1
1.5
Tc
2
2.5
7
x 10
Red lines are calculated through the recursive equation.
Blue lines are statistics of consensus times from numerical simulation(very expensive),
(done by Jerry Xie)
Consensus Time distribution
p=0.08
p=0.12
1
0.9
N=50
N=100
N=150
y=exp(x+1)
0.8
0.6
0.5
0.6
c
P(T ) * std(T )
0.5
c
P(T) * std(T)
0.7
st. normal
N=50
N=100
N=200
N=400
N=800
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
0
-1.5
-1
-0.5
0
0.5
1
T-E[T] / std(T)
1.5
2
2.5
0
-4
-2
0
2
( Tc -E[Tc ] ) / std(Tc )
Below critical, consensus time distribution tends to exponential.
Above critical, consensus time distribution tends to Gaussian.
For large enough system, only the mean and the variance of the
consensus time is needed.
4
6
Variance of Consensus time
Theorem: the variance of total consensus time
equals to the sum of variances introduced by
every macrostate:
is the expected total number of steps spend on the
given macrostate before consensus.
is the variance introduced by one step stay in the
given macrostate.
Naming Game on other networks
Mean field assumption
Local meanfield assumption
 Homogeneous Pairwise assumption
 Heterogeneous Pairwise assumption
Homogeneous Pairwis Assumption
The mean field is not uniform but varies for the nodes
with different opinion.
Mean field
P(·|A)
A
P(·|B)
B
P(·|A)
AB
Numerical comparison
1
0.9
0.8
0.7
pA
pB
0.6
pAB
Theoretical
0.5
0.4
Mean field
0.3
0.2
0.1
0
0
2
4
6
8
10
t
12
14
16
18
20
Trajectories mapped to 2D macrostate
space
1
0.9
mean field
<k>=3
<k>=4
<k>=5
<k>=10
<k>=50
0.8
0.7
p
B
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
pA
0.6
0.7
0.8
0.9
1
Concentration of the consensus time
11
10.5
10
ln(T
0.95
)
9.5
9
8.5
8
<k>=5 simulation
<k>=5 pair approx
<k>=10 simulation
<k>=10 pair appro
mean field
7.5
7
6.5
4.5
5
5.5
6
6.5
ln(N)
7
7.5
8
Analyze the dynamics
1.Choosing one type of links, say A-B, and A is the listener.
2.Direct change: A-B changes into AB-B.
3.Related changes: since A changes into AB, <k>-1 related
links C-A change into C-AB. The probability distribution of C
is the local mean field P(·|A).
C
Related×(<k>-1)
Direct
C
A
C
B
Merits of SDE model
Include all types of NG and other
communication models in one framework
and distinguish them by two parameters.
Present the effect of system size explicitly.
Collapse complicated dynamics into 1-d
SDE equation on the center manifold.
Thanks