...

Dynamical Processes on ‘Coupled’ Complex Networks: Cascading Failures, Information

by user

on
Category:

football

2

views

Report

Comments

Transcript

Dynamical Processes on ‘Coupled’ Complex Networks: Cascading Failures, Information
1
Bell Labs, 16 November 2012
Dynamical Processes on ‘Coupled’ Complex
Networks: Cascading Failures, Information
Epidemics, and Complex Contagions
Osman Yağan
CyLab
Carnegie Mellon University
[email protected]
Joint work with
Dajun Qian, Junshan Zhang, Douglas Cochran, and
Virgil Gligor
2
Bell Labs, 16 November 2012
Network science
• An inter-disciplinary field bringing together researchers from
many areas.
⋄ engineering, mathematics, physics, biology, computer
science, sociology, epidemiology, etc.
• Tremendous activity over the past decade: special issues,
conferences, journals on network science.
⋄ DoD research initiatives, NSF grant programs
Main aim: Developing a deep understanding of the dynamics
and behaviors of social, biological and physical networks.
Bell Labs, 16 November 2012
Dynamical processes on complex networks
∗ Spreading of an initially localized effect throughout the whole (or,
a very large part of the) network.
• Diffusion of information, ideas, rumors, fads, etc.
• Disease contagion in human and animal populations.
• Cascade of failures, avalanches, sand piles.
• Spread of computer viruses or worms on the Web.
† Searching on networks (WWW, P2P)
† Flows of data, materials, biochemicals.
† Network traffic, congestion.
∗ Barrat et al. Dynamical Processes on Complex Networks, 2008
3
4
Bell Labs, 16 November 2012
Motivation
∗ Most research on complex networks focus on the limited case of a
single, non-interacting network.
∗ Yet, many real-world systems do interact with each other.
⋄ Major infrastructures depend on each other:
telecommunications, energy, banking and finance,
transportation, water supply, public health.
⋄ Social networks are coupled together:
Facebook, Twitter, Google+, YouTube, etc.
Q: Dynamical processes on interacting networks?
5
Bell Labs, 16 November 2012
My contributions
1. Cascading failures on interdependent cyber-physical systems
⋄ O. Yağan, D. Qian, J. Zhang and D. Cochran, IEEE Trans.
Parallel and Distrib. Syst. 23(9): 1708–1720, Sept. 2012
2. Complex contagions (influence propagation) in social networks
with multiple link types
⋄ O. Yağan and V. Gligor, Phys. Rev. E 86, 036103, Sept. 2012
3. Information propagation (simple contagions) in coupled
social-physical networks
⋄ O. Yağan, D. Qian, J. Zhang and D. Cochran, IEEE J. Sel.
Areas Commun., Issue on Network Science, to appear.
6
Bell Labs, 16 November 2012
Today
1. Cascading failures on interdependent cyber-physical systems
⋄ O. Yağan, D. Qian, J. Zhang and D. Cochran, IEEE Trans.
Parallel and Distrib. Syst. 23(9): 1708–1720, Sept. 2012
2. Complex contagions (influence propagation) in social networks
with multiple link types
⋄ O. Yağan and V. Gligor, Phys. Rev. E 86, 036103, Sept. 2012
Bell Labs, 16 November 2012
Cascading failures on
interdependent cyber-physical networks
7
Bell Labs, 16 November 2012
Interdependent networks?
• A collection of networks that depend on one another to provide
proper functionality.
• Interdependence is omnipresent in many modern systems.
• Major national infrastructures: telecommunications, energy,
banking and finance, water supply systems, emergency services.
• Interdependence exists even at smaller scales: e.g., smart-grid
⋄ Power stations depend on communication nodes for control
while communication nodes depend on power stations for
their electricity supply.
Large, smart and complex systems.
8
Bell Labs, 16 November 2012
But . . ., interdependent networks are fragile
Adversarial attacks, system failures, and natural hazards ⇒
• Node failures in one network may lead to failure of the
dependent nodes in other networks, and vice versa.
• Continuing recursively, this may lead to a cascade of failures.
• The failure of a very small number of nodes from a network
may lead to the collapse of the entire system.
9
10
Bell Labs, 16 November 2012
Real-world examples
Goal: Mitigate catastrophic impacts
Plan of action: Model and quantify cascading failures &
Develop design strategies that improve robustness
11
Bell Labs, 16 November 2012
A starting point: Buldyrev et al. (Nature, 2010)
Network A
Network B
1
1
2
2
3
3
N
N
Figure 1: Intra-topologies are not shown.
support-dependence relationships.
Inter-links determine
12
Bell Labs, 16 November 2012
Cascade dynamics
• Initially, a fraction 1 − p of nodes are randomly removed from
Network A ⇒ Models random attacks or failures.
• A node is said to be functional at Stage i if
1) it has at least one inter-edge with a node that was
functional at Stage i − 1, and
2) it belongs to the giant (i.e., the largest) component of the
subnetwork formed by the nodes (of its own network) that
satisfy condition 1.
• Cascade of failures propagates alternately between A and B,
eventually (i.e., in steady state) leading to either
i) residual functioning giant components in both networks, or
ii) complete failure of the entire system
13
Bell Labs, 16 November 2012
Robustness metrics
• SA∞ : Fractional size of the functional nodes of network A at
steady state.
• SB∞ : Fractional size of the functional nodes of network B at
steady state.
• 1 − pc : Critical attack size: Largest attack that can be
sustained. If more than 1 − pc fraction is attacked:
⇒ no functional giant component at Stage ∞; SA∞ = SB∞ = 0
Bell Labs, 16 November 2012
Main findings by Buldyrev et al.
• Let Networks A and B be Erdős-Rényi (ER) with mean degree
d. They established
⇒ e.g., if d = 3, the system is robust against
• 1 − pc ≃ 1 − 2.45
d
the removal of up to 18 % of the nodes.
• For a single ER network: 1 − pc = 1 − d1 ⇒ with d = 3, can
sustain the failure of up to 66 % of the nodes.
⇒ Interdependent networks are much more vulnerable!
• Broader degree dist.⇒More vulnerable to random failure
• Exact opposite of the case for single networks
• Intuition: High degree nodes may inter-connect low degree ones
14
15
Bell Labs, 16 November 2012
Rise of a new field
• The paper by Buldyrev et al. received 250 citations thus far
• Follow-up works concentrate on two main directions
⋄ Obtaining analogous results under more realistic models
∗ autonomous nodes, multiple networks, correlation
between inter- and intra-links, different network models,
multiple inter-links per node
⋄ Developing design strategies that improve robustness
∗ selection of autonomous nodes (nodes with high degree,
or betweenness), new metrics for robustness, optimum
inter-link allocation strategies
-Yağan et al., IEEE TPDS
16
Bell Labs, 16 November 2012
A new interdependent network model
Network A
Network B
1
1
2
2
k−1
k
N
N
∗ Each node has exactly
k inter-edges
∗ It suffices to have one
inter-connection with a
functioning node
Quantities of interest:
1) SA∞ , SB∞ ⇒ fraction of functioning nodes at steady-state
2) 1 − pc as a function of k (and intra-degree distributions)
17
Bell Labs, 16 November 2012
General solution
∗ Let Ai , Bi denote the functioning giant components in Net A and
Net B at stage i with corresponding fractional sizes SAi and SBi .
With p′A1 = p and SA1 = pFA (p), we have the recursive relations
k
′
′
pBi = 1 − 1 − pFA (pAi−1 ) ; SBi = p′Bi FB (p′Bi ), i = 2, 4, 6, . . . .
k p′Ai = p 1 − 1 − FB (p′Bi−1 )
; SAi = p′Ai FA (p′Ai ), i = 3, 5, . . .
pFA (p) : Fractional size of the giant component in A′ , where A′ is
the subgraph of A induced by the pN functl. nodes (after failures).
A −→failure of (1 − p)-fraction A′ −→largest component A′′
|A′′ |/N = pFA (p) ⇒ Depends on intra-degree distributions.
Bell Labs, 16 November 2012
∗ This recursive process stops at an “equilibrium point” where we
have p′B2m−2 = p′B2m and p′A2m−1 = p′A2m+1 so that neither network
A nor network B fragments further. Setting x = p′A2m+1 , y = p′B2m
k
x = p 1 − (1 − FB (y))
(1)
k
y = 1 − (1 − pFA (x))
Obtaining the quantities of interest: Assume FA , FB are known
1. Obtain the stable solution of Eqn (1) for a given p and k.
2. Compute SA∞ := limi→∞ SAi = xFA (x) and SB∞ = yFB (y).
3. Finding pc : repeat steps 1 and 2 for various p to find the
smallest p that gives SA∞ , SB∞ > 0.
pc = inf {0 ≤ p ≤ 1 : SA∞ , SB∞ > 0}
18
19
Bell Labs, 16 November 2012
Special case: ER networks
∗ Assume both networks are ER with mean intra-degrees a and b.
∗ It is known that: FA (x) = 1 − fA where fA is the unique solution
of fA = exp{ax(fA − 1)}. This leads to
SA∞ = p(1 − fBk )(1 − fA ),
k
SB∞ = 1 − (1 − p(1 − fA )) (1 − fB ).
where fA and fB are given by the pointwise smallest solution of
q
fA
fB = k 1 − (flog
if 0 ≤ fA < 1; ∀fB if fA = 1
A −1)ap
fA = 1 −
1−
q
k
log fB
B −1)b
1− (f
p
if 0 ≤ fB < 1; ∀fA if fB = 1.
(2)
(3)
20
Bell Labs, 16 November 2012
1
1
0
1
1
0
a) 1 − p = 0. 6
1
0
1
1
c ) 1 − p = 0. 5
b) 1 − p = 0. 55
1
1
fB
fA
0
1
d) 1 − p = 0. 44
0
1
e ) 1 − p = 0. 4
0
1
f ) 1 − p = 0. 3
Figure 2: Possible solutions of the system (3) when a = b = 3 and
k = 2. The critical 1 − pc corresponds to the case when the two curves
are tangential to each other.
∗ 1 − pc = 0.44 ⇒ With k = 2 system is robust against failures of
up to 44 % of the nodes. With k = 1, only against 18 %
∗ Phase transition is discontinuous, i.e., first order
21
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
0.8
0.7
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
0.2
0.3
0.4
≃ 0.66
0.5
0.6
0.7
0.8
0.9
1
Fraction of f ailed no des (1 − p )
Figure 3: Net A and Net B are ER with mean degrees a = b = 3
22
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
0.8
0.7
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
0.2
0.3
0.4
≃ 0.66
0.5
0.6
0.7
0.8
0.9
1
Fraction of f ailed no des (1 − p )
∗ With k = 2 system is robust against failures of up to 44 % of the
nodes. With k = 1, only against 18 %
23
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
0.8
0.7
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
0.2
0.3
0.4
≃ 0.66
0.5
0.6
0.7
0.8
0.9
1
Fraction of f ailed no des (1 − p )
∗ Phase transition is discontinuous in interdependent networks;
but, continuous in the single network case.
24
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
0.8
0.7
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
0.2
0.3
0.4
≃ 0.66
0.5
0.6
0.7
0.8
0.9
1
Fraction of f ailed no des (1 − p )
∗ For attacks of up to 30 % of the nodes, interdependent networks
with k = 2 are almost as robust as single networks.
25
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
0.8
0.7
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
k = 3
0.2
0.3
0.4
0.5
≃ 0.66
4
5
0.6
0.7
0.8
Fra c tion of f a iled no des (1 − p )
Figure 4: a = b = 3
0.9
1
26
Bell Labs, 16 November 2012
Fraction of functional nodes, S A ∞
1
0.9
p c vs. k
0.8
1 − pc ≃ 1 −
0.7
1 + 1 .4 5 ·k − 1. 2
d
0.6
k =2
0.5
0.4
k =1
Single E R networ k
0.3
0.2
0.1
0
0
≃ 0.18
0.1
critical f raction
1 − p c ≃ 0.44
k = 3
0.2
0.3
0.4
0.5
≃ 0.66
4
5
0.6
0.7
0.8
Fra c tion of f a iled no des (1 − p )
0.9
1
27
Bell Labs, 16 November 2012
A design question
• In our model, each node has exactly k undirected inter-edges;
i.e., k bi-directional inter-links per node.
• Suppose that we are given a fixed number of uni-directional
inter-network edges, say 2kN .
• How should these edges be allocated in order to maximize the
robustness, i.e., in order to achieve the largest SA∞ , SB∞ , 1 − pc
• Bi-directional vs Uni-directional,
Regular vs Random
∗ Yağan, Qian, Zhang, Cochran, NetSciCom, April 2011.
∗ Shao, Buldyrev, Havlin, and Stanley, Phys. Rev. E, March 2011.
Bell Labs, 16 November 2012
Random allocation vs. regular allocation
Implementing random allocation strategy:
∗ Consider a discrete probability distribution P : N → [0, 1], s.t.
P∞
P (j) = αj , j = 0, 1, . . ., with j=0 αj = 1.
∗ αj : fraction of nodes with j inter-links
∗ Randomly partition both networks into subgraphs with sizes
α0 N, α1 N, . . ., and assign j bi-directional inter-edges to each
node in the jth partition. ⇒ Intra topologies are unknown
∗ With α = (α0 , α1 , . . .), we want to compare
pc (α), SA∞ (α), SB∞ (α) vs. pc (k), SA∞ (k), SB∞ (k)
P∞
∗ Matching condition: k = j=0 αj j (with integer k)
28
29
Bell Labs, 16 November 2012
Theorem 1 Under the condition k =
∞
P
αj j, for all p, we have
j=0
SA∞ (k) ≥ SA∞ (α),
SB∞ (k) ≥ SB∞ (α).
(4)
Furthermore
1 − pc (k) ≥ 1 − pc (α).
(5)
Proof. (Outline) Obtain recursive relations concerning the
functional network sizes at each stage. Use induction and exploit
convexity in the obtained relations via the Jensen’s inequality.
∗ Random allocation yields highest robustness when αk = 1, αj = 0
∗ Regular allocation is better than ‘any’ random allocation
∗ Theorem 1 is valid for arbitrary intra-degree dist of Net A and B.
30
Bell Labs, 16 November 2012
Bi-directional vs. uni-directional inter-edges
∗ Consider an arbitrary probability distribution α = (α0 , α1 , . . .).
∗ Uni-directional strategy: Assign αj -fraction of nodes j inward
inter-edges; the supporting node is picked arbitrarily. We compare
pc,uni (α), SA∞ ,uni (α), SB∞ ,uni (α) vs. pc (α), SA∞ (α), SB∞ (α)
Theorem 2 For any p, we have that
SA∞ (α) ≥ SA∞ ,uni (α),
SB∞ (α) ≥ SB∞ ,uni (α),
(6)
and that
1 − pc (α) ≥ 1 − pc,uni (α).
∗ Bi-directional is better than uni-directional for any α
(7)
31
Bell Labs, 16 November 2012
Lessons learned
∗ Assume that intra-topologies of the networks are not known. For
a given average number of inter-edges per node (the number of
nodes it supports plus the number of nodes it depends upon),
i) it is better (in terms of robustness) to use bi-directional
inter-links rather than unidirectional links, and
ii) it is best to deterministically allot each node exactly the
same number of bi-directional inter-edges.
Broader inter-degree distribution ⇒ Lower robustness
Optimal inter-link allocation strategy:
Regular allocation of bi-directional links
32
Bell Labs, 16 November 2012
Intuitions
∗ Without knowing which nodes play a key role in preserving the
connectivity, it is best to treat all nodes “identically” and give
them equal priority in inter-edge allocation.
∗ Regular allocation of bi-directional links ensures that each node
supports (and is supported by) the same number of nodes.
⇒ Uniform support-dependence relationship
∗ Random allocation strategy disrupts this uniformity and leads
to a reduction in the system robustness.
∗ Uni-directional links is even worse because of the domino-effect.
33
Bell Labs, 16 November 2012
Summarizing . . .
• We proposed a new interdependent network model, where
nodes are allowed to have multiple inter-links.
• We analyzed the robustness of this new model against
cascading failures via the critical attack size and the
functional network sizes at steady-state.
• We characterized the trade-off between the number of
inter-links allocated and the robustness achieved.
• We showed that the optimal inter-link allocation strategy is to
give all nodes exactly the same number of bi-directional
inter-links (when intra-topologies are unknown).
Bell Labs, 16 November 2012
Some ideas for future work
• Optimal inter-link allocation with topology information
⋄ Assign more inter-edges to high intra-degree nodes?
⋄ Assign more inter-edges to nodes with high betweenness?
• More realistic rules for node failures
⋄ Based on fraction of failed neighbors rather than giant comp
• Multiple sources of failures
⋄ Net A is more vulnerable to one type of failures, while Net
B is more vulnerable to another type.
• Correlations between inter- and intra-edges due to nodes’
spatial locations.
34
35
Bell Labs, 16 November 2012
Influence propagation on
multiplex networks
Bell Labs, 16 November 2012
A dynamical process: Binary decisions with
externalities
• Each individual must decide between two actions, e.g.,
⋄ To buy or not to buy a smart phone
⋄ To vote for Democrats or Republicans
• There is an inherent incentive for individuals to coordinate
their decisions with those of their immediate acquaintances.
Linear Threshold Model (D. Watts, PNAS, 2002)
• Nodes can be in either one of the two states: active or inactive.
• Each node is initially given a threshold τ drawn from Pth (τ ).
• An inactive node with m active neighbors and k − m inactive
neighbors will turn active if m
k ≥ τ.
36
37
Bell Labs, 16 November 2012
Global cascades
• Start by activating a few nodes (give incentives, free samples)
• Assumption: Once active, a node can not be deactivated.
• Global Cascades: A linear fraction of nodes (in the
asymptotic limit) eventually becomes active
∗ Watts [PNAS 99, 5766]: Condition and Probability of global
cascades when an arbitrary node is made active
∗ Gleeson & Cahalane [Pyhs. Rev. E 77, 46117]: Expected size
38
Bell Labs, 16 November 2012
Our motivation
• Existing work considers simplex networks that have only a
single type of link.
• But, individuals engage in different types of relationships;
e.g., family, friends, office-mates, college-mates, etc.
• Existing work provides limited insight regarding the role of
“content” in the spreading process.
• Does a birth control pill have the same spreading
characteristics with a smart phone?
• What about joining a riot vs. deciding on vacation spot?
Bell Labs, 16 November 2012
Networks with multiple link types:
Multiplex networks
• Multiplex networks may provide better insight into the
cascade process by allowing link classification.
• May also allow capturing the effect of content
• Each link type may play a different role in different processes.
⋄ A video game would be more likely to be promoted among
high school classmates rather than family members;
exactly opposite in the case of a cleaning product.
⋄ Belief propagation: Links between distant Facebook
friends vs. links between close office-mates
39
Bell Labs, 16 November 2012
A Facebook snap shot – Classifying ‘friends’
Exploiting the role of ‘link types’ can pave the way for
developing better marketing strategies
40
41
Bell Labs, 16 November 2012
A content-dependent threshold model for
multiplex networks
• Consider a multiplex network where links can be of r types.
• For a given content (e.g., rumor, product, political view),
consider positive scalars c1 , . . . , cr , such that ci quantifies the
relative bias a type-i link has in spreading this content.
• Nodes switch state if their perceived proportion of active
neighbors exceeds a threshold τ . Namely, an inactive node
connected to mi active neighbors and ki − mi inactive
neighbors via type-i links will turn active if
c1 m1 + c2 m2 + . . . + cr mr
≥τ
c 1 k1 + c 2 k2 + . . . + c r kr
42
Bell Labs, 16 November 2012
Comparison of threshold rules
• Watts, PNAS 2002 :
m1 + m2 + . . . + mr
m
≥τ
=
k1 + k2 + . . . + kr
k
• Yağan & Gligor, PRE 2012 :
c1 m1 + c2 m2 + . . . + cr mr
≥τ
c 1 k1 + c 2 k2 + . . . + c r kr
Content-dependent coefficients c1 , . . . , cr will play a key role in the
dynamics of influence propagation
43
Bell Labs, 16 November 2012
Network model
∗ Let r = 2; i.e., assume that there are only two link types.
∗ F: Random network of type-1 links with degree distribution {pfk }.
∗ W: Random network of type-2 links with distribution {pw
k }.
∗ F, W : Independently generated with the configuration model
∗ H: System model F ∪ W with colored distribution {pk }
pk = pfk1 · pw
k2 ,
k = (k1 , k2 )
∗ With c := c1 /c2 an inactive node will become active if
cm1 + m2
≥τ
ck1 + k2
Q: Condition, probability, expected size of global cascades?
Bell Labs, 16 November 2012
44
Bell Labs, 16 November 2012
Condition and probability of global cascades
Simplex networks
• If the network is locally tree-like (i.e., no cycles), initially
influence can only diffuse through vulnerable nodes.
⋄ A node is deemed vulnerable if its state can be changed by
a single active neighbor; i.e., if k1 ≥ τ ⇔ k ≤ τ1
• Global cascade condition = Existence of a giant vulnerable
component (GVC); a component comprising a positive
fraction of nodes.
• Probability of global cascades = Fractional size of the
extended giant vulnerable component
⋄ Extended GVC = Nodes that have a link with at least one
node in GVC: activating any node in EGVC will activate GVC.
45
Bell Labs, 16 November 2012
Multiplex Networks with content-dependent threshold rule
• We need to define two notions of vulnerability:
⋄ A node is F-vulnerable if it becomes active by a single
active neighbor in F; i.e., if ck1c+k2 ≥ τ .
⋄ A node is W-vulnerable if it becomes active by a single
active neighbor in W; i.e., if ck11+k2 ≥ τ .
− We say that a node is simply vulnerable, if it is vulnerable
w.r.t. at least one type.
• If c 6= 1, a node can be F-vulnerable but not W-vulnerable, or
vice versa. ⇒ An active vulnerable node does not necessarily
activate all of its vulnerable neighbors.
Ordinary definition of a vulnerable component becomes
vague!
46
Bell Labs, 16 November 2012
A directed graph on vulnerable nodes
∗ In our formulation, subgraph of vulnerable nodes forms a
directed graph: i → j means that if active, i will activate j.
⋄ A potentially bi-directional F-link between nodes i and j will
have the direction from i to j (resp. j to i) only if j (resp. i) is
F-vulnerable (similarly for W-links).
47
Bell Labs, 16 November 2012
Components of a directed network
• Out-component of a vertex is the set of vertices that are
reachable from it.
• In-component of a vertex is the set of nodes that can reach it
• Giant out-component (GOUT): Set of nodes with infinite
in-component.
• Giant in-component (GIN): Set of nodes with infinite
out-component.
• Giant strongly-connected component (GSCC): Intersection of
GIN and GOUT.
∗ Any pair of nodes
in GSCC are connected via a
directed path.
48
49
Bell Labs, 16 November 2012
A subtle picture
• Condition for global cascades = Existence of GIN (Existence
of nodes with infinite out-component)
• Probability of global cascades = Fractional size of the
extended giant in-component (EGIN)
⋄ Extended GIN = Nodes in GIN plus nodes that, once can
activated, can activate a node in GIN
• Giant vulnerable component = GSCC
⋄ A set of vulnerable nodes s.t. activating any node (in this
set) leads to the activation of all nodes in the set.
Is Existence of GIN ⇔ Existence of GSCC?
Bell Labs, 16 November 2012
No, GIN may exist even if GSCC does not!
For n → ∞
• A positive fraction of nodes have infinite out-component. ⇒
GIN exists!
• The largest strongly connected component consists of two
nodes. ⇒ No GSCC!
Global cascades can take place even
without a giant vulnerable component!
⋄ Contradicts all previous models!
50
51
Bell Labs, 16 November 2012
Analytic results
Branching Process for Exploring Out-Components
• Start by activating an arbitrary node, and then recursively
reveal the largest number of vulnerable nodes reached and
activated by exploring its neighbors.
⋄ gi (x) : Generating function for the finite number of nodes
reached by following a type-i link. (i = 1, 2)
⋄ ρk,i : Probability that a node with colored degree k is
i-vulnerable. (i = 1, 2)
⋄ G(x) : Generating function for the finite number of nodes
reached and activated.
Generating function of a rv Z ⇒ G(x) =
P∞
ℓ
x
· P [Z = ℓ]
ℓ=0
52
Bell Labs, 16 November 2012
Recursive relations
G(x) = x
P
k=(k1 ,k2 )
pk · g1 (x)k1 g2 (x)k2
X k1 pk
X k1 pk
k1 −1
k2
g1 (x) = x
ρk,1 g1 (x)
g2 (x) +
(1 − ρk,1 ) (8)
< k1 >
< k1 >
k
k
X k2 pk
X k2 pk
k1
k2 −1
g2 (x) = x
ρk,2 g1 (x) g2 (x)
(1 − ρk,2 ) (9)
+
< k2 >
< k2 >
k
k
∗ We want to find the stable solution of (8)-(9) for x = 1.
∗ Trivial fixed point: g1 (1) = g2 (1) = 1 ⇒ G(1) = 1.
∗ G(1) = 1 ⇒ Conservation of probability implies that all
out-components are finite ⇒ no GIN ⇒ no global cascades
∗ But, the trivial solution g1 (1) = g2 (1) = 1 may not be stable.
∗ Shall check the Jacobian matrix of (8)-(9).
53
Bell Labs, 16 November 2012
The Jacobian


Jp = 

<(k12 −k1 )ρk,1 >
<k1 >
<k1 k2 ρk,2 >
<k2 >
<k1 k2 ρk,1 >
<k1 >
<(k22 −k2 )ρk,2 >
<k2 >




∗ Let σ(J p ) = max{|λi | : λi is an eigenvalue of J p } : spectral radius
∗ If σ(J p ) ≤ 1, then the solution g1 (1) = g2 (1) is stable; i.e., GIN
does not exist whp.
∗ If σ(J p ) > 1, another solution with g1 (1), g2 (1) < 1 exists and
becomes the stable solution of (8)-(9) ⇒ G(1) < 1
∗ 1 − G(1) = prob. of activating infinite nodes = size of EGIN
Global Cascade Condition: σ(J p ) > 1
Probability of Global Cascades, Ptrig : 1 − G(1)
54
Bell Labs, 16 November 2012
Expected size of global cascades
• Analysis is based on the approach by Gleeson & Cahalane
[Pyhs. Rev. E 77, 46117]: via the tools developed for analyzing
zero-temperature random field Ising model on Bethe lattices.
• Construct a tree with a single node at the top level ℓ = ∞.
⋄ qi,ℓ : Probability that a node at level ℓ, connected to its
unique parent by a type-i link, is active given that its parent is
not. (i = 1, 2)
• Recursive relations for each ℓ = 0, 1, . . ..
qi,ℓ+1
=
−δi1
X ki pk k1X
< ki >
k2X
−δi2
k1 − δi1 l
F ((l, j), k)
q1,ℓ
l
j=0
k
l=0
k
−
δ
2
i2
j
× (1 − q1,ℓ )k1 −l−δi1
q2,ℓ
(1 − q2,ℓ )k2 −j−δi2
j
55
Bell Labs, 16 November 2012
• Under the assumption that nodes do not become inactive once
they turn active, the quantities q1,ℓ and q2,ℓ are non-decreasing
in ℓ.
• They converge to a limit q1,∞ and q2,∞ .
• The expected cascade size is given by
S
=
X
k
pk
k2
k1 X
X
l=0
k1 l
F ((l, j), k)
q1,∞ (1 − q1,∞ )k1 −l
l
j=0
k2 j
×
q2,∞ (1 − q2,∞ )k2 −j .
j
where q1,∞ and q2,∞ correspond to the stable fixed point.
Expected Size of Global Cascades: S
56
Bell Labs, 16 November 2012
Simulation results
57
Bell Labs, 16 November 2012
1
Content C 1 with c = 0.25
Content C 2 with c = 1.0
1
P t r ig -Anlys
P t r i g – Analysis
0.8
P t r i g – Expt.
S -Anlys
Fractional Size
Fractional Size
P t r ig -Expt.
S -Expt.
0.6
0.4
0.4
0.3
0.2
0.2
0.8
S – Expt.
0.6
0.4
0.2
0.15
0.2
0.1
1
0.1
0.05
0
0.85
0
0
S – Analysis
2
0.9
0.95
3
1
1.05
0
0.55
4
5
6
Average Degree (z 1 = z 2 )
0
0
1
0.6
0.65
2
0.7
3
4
5
6
Average Degree (z 1 = z 2 )
Figure 5: n = 5 × 105 , τ is fixed at τ ⋆ = 0.18, and F and W are ER with
mean degrees z1 and z2 , respectively.
• Excellent agreement between analysis and simulations!
• Content parameter c affects the range, probability, and size of
cascades ⇒ Distinguish between link types!
58
Bell Labs, 16 November 2012
z 1 = 1.5, z 2 = 5.5
0.25
S – Expt.
S – Analysis
S – Analysis
P trig – Analysis
0.6
0.4
0.2
0.2
S – Expt.
0.8
Fractional Size
0.8
0.9
S – Expt.
Fractional Size
Fractional Size
z 1 = 6.0, z 2 = 1.5
z 1 = z 2 = 0.7
1
P trig – Analysis
0.15
0.1
S – Analysis
0.7
P trig – Analysis
0.6
0.5
0.4
0.3
0.2
0.05
0.1
0
0
1
2
3
Content Parameter (c)
(a)
4
0
0
1
2
3
4
0
0
1
2
3
Content Parameter (c)
Content Parameter (c)
(b)
(c)
4
• All parameters except c are fixed, and the variation of Ptrig
and S are observed.
• Content parameter c can dramatically change the dynamics
of complex contagions over the same network.
• Depending on z1 , z2 , the range of c that favors global cascades
changes significantly.
59
Bell Labs, 16 November 2012
Summarizing . . .
• We proposed a new social contagion model that allows
⋄ capturing the effect of content on the influence
propagation process
⋄ distinguishing between different link types in the social
network
• Under this new model, we obtained the condition,
probability and expected size of global spreading events.
• We showed how different content may have completely
different spreading characteristics over the same network.
• We showed that link classification and content-dependence
of links’ roles are essential for an accurate marketing analysis.
60
Bell Labs, 16 November 2012
Ideas for future work
• Checking the validity of the content-dependent threshold model
in real-world networks.
• Estimating content parameter c in real cascade processes.
• Expanding the analysis results to networks that have
clustering, assortativity, etc.
• Revisiting the influence maximization∗ problem for
multiplex networks under the content-dependent threshold rule.
⋄ Deriving different marketing strategies for different
products.
∗ Kempe, Kleinberg, Tardos, KDD 2003.
61
Bell Labs, 16 November 2012
Thanks!
Visit www.andrew.cmu.edu/~ oyagan for more ...
62
Bell Labs, 16 November 2012
A few quotations
∗ The notion of perceived proportion of active neighbors is
used first by Mark Granovetter in his seminal paper “Threshold
Models of Collective Behavior,” Am. J. Sociol. 83, 1978, pp. 1429.
“By ‘social structure’ I mean here only that the influence of any
given person has on one’s behavior may depend upon the
relationship. Take a simple case, where the influence of friends is
twice that of strangers. . . . What we may then call the
‘perceived proportion of rioters’ . . .”
∗ Jon Kleinberg, “Cascading Behavior in Networks,” 2007.
“It would be nice to express the notion that an individual will
adopt a behavior when, for example, two of her relatives and
three of her co-workers do so.”
63
Bell Labs, 16 November 2012
An illustration of cascading failures
v1
v'1
v'1
v2
v '2
v '2
v3
v'3
v3
v'3
v4
v '4
v4
v '4
v4
v '4
v4
v '4
v4
v '4
v5
v'5
v5
v'5
v5
v'5
v5
v'5
v5
v'5
v6
v'6
v6
v'6
v6
v'6
v6
Initial set-up
Stage 1
v'1
Stage 2
Stage 3
Steady state
Fly UP