CS579: Lecture 09¶

Cascades II

Dr. Aron Culotta
Illinois Institute of Technology

With some figures from Networks and Markets: Reasoning about a highly connected world, David Easley and Jon Kleinberg

Last time...

We defined cascades as happening when others' decisions dominate personal evidence
Surprising cascades can occur even assuming rationality.
Cascades can lead to sub-optimal outcomes.
Cascades are fragile

This made several assumptions:

rationality
everyone can observe everyone else's actions
everyone's actions have equal influence
everyone has same utility function (e.g., we all win the same if we guess the number of marbles in the urn)
my utility is independent of yours

Today:

Assume people make decisions in a social network
- I can only view the actions of my neighbors
My utility is influenced by your decision

Game-theoretic Diffusion Model¶

Consider the following scenario:

Each node must choose between two possible behaviors $A$ and $B$
- E.g., $A$= join Facebook; $B$= join MySpace
If nodes $v$ and $w$ are linked by an edge, they are incentivized to have same behavior
Payoff matrix:

	$w$
$v$		$A$	$B$
	$A$	a,a	0,0
	$B$	0,0	b,b

Both do $A$: both get reward $a$.
Both do $B$: both get reward $b$.
Do opposite: both get reward $0$.

Each node plays this game with all neighbors.

Payoff for a node is sum over all neighbors.

Suppose some of $v$'s neighbors choose $A$ and some choose $B$
Which should $v$ choose?

E.g., if $a$ > $b$, then really I'd like to join Facebook
But, if most of my friends are on MySpace, then I should join MySpace instead.
This tradeoff is determined by difference in utility ($a-b$) and the proportion of my friends using MySpace

Suppose fraction $p$ of $v$'s neighbors choose $A$; $1-p$ choose $B$.
Let $d$ be the number of neighbors of $v$.
Then, $pd$ choose $A$ and $(1-p)d$ choose $B$
If $v$ chooses $A$, payoff=?
If $v$ chooses $B$, payoff=?

Suppose some of $v$'s neighbors choose $A$ and some choose $B$
Which should $v$ choose?

Suppose fraction $p$ of $v$'s neighbors choose $A$; $1-p$ choose $B$.
Let $d$ be the number of neighbors of $v$.
Then, $pd$ choose $A$ and $(1-p)d$ choose $B$
If $v$ chooses $A$, payoff=$\mathbf{pda}$
If $v$ chooses $B$, payoff=$\mathbf{(1-p)db}$
$A$ should be chosen iff

$$ pda \ge (1-p)db $$

equivalently

$$ p \ge \frac{b}{a+b} $$

Let $q=\frac{b}{a+b}$

Small $q \rightarrow$ $A$ much more appealing; only need a few neighbors choosing $A$ to choose $A$.
Large $q \rightarrow$ $B$ much more appealing; need many neighbors choosing $A$ to choose $A$.
We'll arbitrarily break ties by choosing $A$.

E.g.,

if utility of Facebook is 6 and utility of MySpace is 4
if 8 of my 10 friends are on MySpace, which should I join?

$q = \frac{b}{a+b} = \frac{4}{10}$

$p = \frac{2}{10}$

if $p \ge q$, choose Facebook

but, $\frac{2}{10} < \frac{4}{10}$, so stick with MySpace

How many of my friends have to switch to Facebook before I will switch?

These decisions are made in a network, which means that order matters.

What if half my friends switch to Facebook?

When does this stop?

What are states of equilibria?¶

All adopt $A$
All adopt $B$
Some adopt $A$ and some adopt $B$

Simulation¶

Assume all nodes select $B$ at time $0$
Select some nodes to adopt $A$ ("initial adopters")
What is resulting equilibria?
- All adopt $A$?
- Some adopt $A$?
- Assume we cannot switch back from $A$ to $B$.

In [1]:

import warnings
warnings.filterwarnings("ignore")
import networkx as nx
graph = nx.Graph()
graph.add_edges_from([('v', 'w'), ('v', 'r'), ('v', 't'),
                      ('w', 'r'), ('w', 's'), ('w', 'u'),
                      ('w', 't'), ('r', 's'), ('t', 'u'), ('s', 'u')])
# Initialize every node to choice 'B'
nx.set_node_attributes(graph, 'choice', 'B')

In [2]:

graph.node

Out[2]:

{'r': {'choice': 'B'},
 's': {'choice': 'B'},
 't': {'choice': 'B'},
 'u': {'choice': 'B'},
 'v': {'choice': 'B'},
 'w': {'choice': 'B'}}

In [3]:

import matplotlib.pyplot as plt
%matplotlib inline

layout = nx.spring_layout(graph)
def draw_graph(graph):
    plt.figure()
    nodes = graph.nodes()
    colors = ['r' if graph.node[n]['choice'] == 'A' else 'b'
              for n in graph]
    plt.axis('off')
    nx.draw_networkx(graph, nodelist=nodes, with_labels=True,
                     width=1, node_color=colors,alpha=.5,
                     pos=layout)    
draw_graph(graph)

In [4]:

# Make v, w "early adopters"
graph.node['w']['choice'] = 'A'
graph.node['v']['choice'] = 'A'
draw_graph(graph)

In [5]:

[v for v in graph]

Out[5]:

['v', 'w', 'r', 't', 's', 'u']

In [6]:

def simulate(graph, a, b, verbose=False):
    """ For each node, set new choice based on payoffs a/b and
    choices of neighbors. """
    for v in graph:
        if graph.node[v]['choice'] == 'B':  # see if v wants to switch to action 'A'
            a_neighbors = [w for w in graph.neighbors(v)
                           if graph.node[w]['choice'] == 'A']
            b_neighbors = [w  for w in graph.neighbors(v)
                           if graph.node[w]['choice'] == 'B']
            p = len(a_neighbors) / (len(a_neighbors) + len(b_neighbors))
            q = b / (a + b)
            if verbose:
                print('node %s p=%.3f q=%.3f' % (v, p, q))
            if p >= q:
                graph.node[v]['choice'] = 'A'
            else:
                graph.node[v]['choice'] = 'B'

In [7]:

# Make first step of simulation.
simulate(graph, 3, 2, verbose=True)
draw_graph(graph)

node r p=0.667 q=0.400
node t p=0.667 q=0.400
node s p=0.667 q=0.400
node u p=1.000 q=0.400

In [8]:

# Make second step of simulation.
simulate(graph, 3, 2, verbose=True)
draw_graph(graph)

So, all adopt $A$ after 2 steps.

In [12]:

# Consider a larger network. (Fig 19.4 in book)
def create_large_graph():
    graph = nx.Graph()
    graph.add_edges_from([(1,2), (1,3), (2,3), (2,6),
                          (6,4), (6,9), (4,7), (4,5),
                          (9,7), (5,7), (9,11), (5,8),
                          (7,8), (7,10), (9,10), (8,10),
                          (11,12), (11,15), (10,12), (8,14),
                          (15,16), (12,16), (14,13), (12,13),
                          (14,17), (13,16), (15,16), (17,16)])
    nx.set_node_attributes(graph, 'choice', 'B')
    return graph

graph = create_large_graph()
# Initialize every node to choice 'B'
layout = nx.spring_layout(graph)
draw_graph(graph)

In [13]:

# Make 7, 8 "early adopters"
graph.node[7]['choice'] = 'A'
graph.node[8]['choice'] = 'A'
draw_graph(graph)

In [14]:

[n for n in graph]

Out[14]:

[1, 2, 3, 6, 4, 9, 7, 5, 11, 8, 10, 12, 15, 14, 16, 13, 17]

In [15]:

# Simulation, step 1
simulate(graph, 3, 2)
draw_graph(graph)

In [16]:

# Simulation, step 2
simulate(graph, 3, 2)
draw_graph(graph)

In [17]:

# Simulation, step 3
simulate(graph, 3, 2)
draw_graph(graph)
# No changes after 3 steps.

Cascade: a sequence of adoptions of a behavior

Two possible outcomes of a cascade:

incomplete cascade: converges to partial adoption
complete cascade: converges to total adoption

The choice of initial adopters can cause a complete cascade or an incomplete cascade.

How can we increase likelihood of a cascade?¶

Increase payoff $a$ (e.g., make a better product)
Better selection of initial adopters (e.g., market to certain people more)

In [19]:

# Let's increase payoff a from 3->4

graph = create_large_graph()
# Make 7, 8 "early adopters"
graph.node[7]['choice'] = 'A'
graph.node[8]['choice'] = 'A'
draw_graph(graph)

In [20]:

# Simulation, step 1
simulate(graph, 4, 2)
draw_graph(graph)

In [21]:

# Simulation, step 2
simulate(graph, 4, 2)
draw_graph(graph)

In [23]:

# Simulation, step 3
simulate(graph, 4, 2)
draw_graph(graph)
# All adopt A after 4 steps.

In [24]:

# Next, let's go back to 3/2 payoffs,
# but convince 12 to adopt.
graph = create_large_graph()
# Make 7, 8 "early adopters"
graph.node[7]['choice'] = 'A'
graph.node[8]['choice'] = 'A'
draw_graph(graph)
simulate(graph, 3, 2)
draw_graph(graph)
simulate(graph, 3, 2)
draw_graph(graph)
simulate(graph, 3, 2)
draw_graph(graph)

In [25]:

# Convince 12 to adopt 'A'
graph.node[12]['choice'] = 'A'
simulate(graph, 3, 2)
draw_graph(graph)

In [26]:

# Cascade continues...
simulate(graph, 3, 2)
draw_graph(graph)

In [27]:

# Cascade stops.
simulate(graph, 3, 2)
draw_graph(graph)

** What prevents cascade from affecting nodes 1,2,3?**

Cascades and Clusters¶

A cluster of density $p$ is a set of nodes such that each node has at least a $p$ fraction of its neighbors in the set.

density

What cluster has density 1?

Conjectures:
(i) A cascade halts at dense clusters;
(ii) This is the only thing that halts a cascade.

More formally:

Consider a set of initial adopters of behavior $A$, with a threshold of $q$ for nodes in the remaining network to adopt behavior $A$.

(i) If the remaining network contains a cluster of density greater than $(1 − q)$, then the set of initial adopters will not cause a complete cascade.

(ii) Moreover, whenever a set of initial adopters does not cause a complete cascade with threshold $q$, the remaining network must contain a cluster of density greater than $(1 − q)$.

Proof of Claim 1: A cascade halts at dense clusters

cluster

By contradiction:

Assume node $v$ is in a cluster with density greater than $1-q$
Assume that $v$ is the first to adopt $A$ in that cluster (contradiction)
For this to happen, fraction $q$ of $v$'s neighbors must have adopted $A$
Since $v$ is first to adopt in this cluster, all neighbors that adopted $A$ must be outside of cluster.
But, by definition, more than $1-q$ neighbors are in cluster, thus less than $q$ neighbors are outside of cluster.

contradition $\Box$

In [28]:

draw_graph(graph)

density$(\{1,2,3\}) = \frac{2}{3}$ (For node 2, edges (2,1) and (2,3) are in the cluster, edge to 6 is out of the cluster.)
For payoff, $a=3$ and $b=2$, so node adopts if

$$ p \ge \frac{b}{a+b} \ge \frac{2}{5} $$

so $$ q = \frac{2}{5} $$

Node 2 does not adopt because $p_2 = \frac{1}{3} < \frac{2}{5} $ (only 6 has adopted; 1 and 3 have not)
Is density$(\{1,2,3\}) \ge 1-q$ ?
- $\frac{2}{3} \ge \frac{3}{5}$

Proof of Claim 2: Dense clusters are the only things that halt cascades.

obstacles

Show that whenever a cascade halts, there exists a cluster with density greater than $(1-q)$.
Let $S$ be the set of nodes that have not yet adopted $A$
Show that $S$ has density greater than $1-q$.
Consider any $w \in S$
- Since $w$ has not adopted $A$, the fraction of its neighbors adopting $A$ is less than $q$ (by definition)
- Hence, fraction of its neighbors adopting $B$ is greater than $1-q$.
- Since $S$ contains all nodes adopting $B$, the fraction of $w$'s neighbors in $S$ is greater than $1-q$.
- Since this is true for all $w \in S$, $S$ is a cluster with density greater than $(1-q)$. $\Box$

A set of initial adopters can cause a complete cascade at threshold $q$ if and only if the remaining network contains no cluster of density greater than $(1 − q)$.

Weak ties and diffusion¶

weak

Will $u$ or $v$ adopt from $w,x$?

"Although a world-spanning system of weak ties in the global friendship network is able to spread awareness of a joke or an on-line video with remarkable speed, political mobilization moves more sluggishly, needing to gain momentum within neighborhoods and small communities."

Extension 1: Each node has a different payoff¶

	$w$
$v$		$A$	$B$
	$A$	$a_v$,$a_w$	0,0
	$B$	0,0	$b_v$,$b_w$

If $v$ chooses $A$, payoff=$pda_v$
If $v$ chooses $B$, payoff=$(1-p)db_v$
$A$ should be chosen iff

$$ pda_v \ge (1-p)db_v $$

equivalently

$$ p \ge \frac{b_v}{a_v+b_v} $$

Let $$q_v = \frac{b_v}{a_v+b_v}$$

$q_v$ is a personal threshold. $v$ chooses $A$ iff a $q_v$ fraction of neighbors do.

How does diversity of $q_v$ affect cascade?

personal

Influenceable people? (susceptibility)

Extension 2: Add edge weights¶

Edge $e_{u,v} \in [0,1]$ specify the influence $u$ has on $v$
- e.g., $e_{\hbox{teacher, student}} > e_{\hbox{student, teacher}}$ (maybe?)
Let $A_v$ be the neighbors of $v$ that adopt $A$
$v$ adopts $A$ if:

$$\sum_{u \in A_v} e_{u,v} \ge q_v$$

Linear Threshold Model (See Watts 2002)