Monday, May 13, 2013

An application of Cascading Behavior to Political Elections

An application of Cascading Behavior to Political Elections

Gino Tesei - April 24, 2013

This work was born as my peer assignment inside the course of Social Network Analysis by Prof. Lada Adamic, University of Michigan on Coursera. I would like to express my appreciation to Prof. Lada Adamic for the NetLogo model I extended and to the students who review this work for their precious point of view.

Abstract

Political elections are getting hotter and hotter on social networks when such an event occurs. In this work, I consider how new behaviors, practices and conventions can spread new political opinions from person to person through a social network in that case. I focused on two key characteristics of a given social network in case of political elections, i.e. the subjectivity of political issues and the level of resilience inside the network. Hence, two findings are showed. First, higher levels of resilience increases the predictability of political outcome no matter the initial allocation of political opinions. Second, higher levels of variability in payoffs to change opinion decreases the predictability of political outcome.

Part I. Constructing the model

1 Introduction

In [1] Easley and Kleinber considered how new behaviors, practices, opinions, conventions, and technologies spread from person to person through a social network, as people influence their friends to adopt new ideas. The first basic model considered is the so called Networked Coordination Game, where the situation where each node has a choice between two possible behaviors, labeled A and B, is studied. If nodes v and w are linked by an edge, then there is an incentive for them to have their behaviors match:
  • if v and w both adopt behavior A, they each get a payoff of a > 0;
  • if they both adopt B, they each get a payoff of b > 0; and
  • if they adopt opposite behaviors, they each get a payoff of 0.
Suppose that a p fraction of v’s neighbors have behavior A, and a (1 − p) fraction have behavior B, hence it is showed that A is the better choice if p ≥ b ⁄ (a + b). Moreover, it is used the following terminology:
Definition 1 Consider a set of initial adopters who start with a new behavior A, while every other node starts with behavior B. Nodes then repeatedly evaluate the decision to switch from B to A using a threshold of q. If the resulting cascade of adoptionsof A eventually causes every node to switch from B to A, then we say that the set of initial adopters causes a complete cascade at threshold q.
Definition 2 We say that a cluster of density p is a set of nodes such that each node in the set has at least a p fraction of its network neighbors in the set.
Hence the following Claim is proved.
Claim 1 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.
Hence, the heterogeneous thresholds model is introduced where each node v, we define a payoff av — labeled so that it is specific to v — that it receives when it coordinates with someone on behavior A, and we define a payoff bv that it receives when it coordinates with someone on behavior B.
Finally, the concept of cascade capacity of the network is introduced as the largest value of the threshold q for which some finite set of early adopters can cause a complete cascade. So it is proved that the cascade capacity of the infinite path is at least 1/2 while and there is no network in which the cascade capacity exceeds 1/2 .
Simulating side, the NetLogo model in [2] shows 2 examples from [1] and Lada Adamic Facebook network with the following parameters:
  • payoffs a, b, c > 0 fixed for any node;
  • bilingual option;
  • initial probability blue value.

1.1 Assumptions, parameters, how the model works

Here I will model to the case of political elections, an hot topic on social networks when such an event occurs. Specifically, I’ll build in [3] an extension of model [2] with
  1. heterogeneous thresholds in order to take into account that political issues are subjective and payoffs to change opinion are subjective as well; hence, for each node v, payoffs av = a±ra , with raϵ[-ka, ka] is random and where 0 ≤ ka ≤ a is a futher parameter of the model; on the same way, bv = b±rb with rbϵ[-kb, kb] is random and where 0 ≤ kb ≤ b is a futher parameter of the model;
  2. no bilingual option (= i.e. adopting both A and B), that is not applicable in case of political elections;
  3. % of “resilient” nodes (R) impossible to influence and that never change their initial opinion. This assumption is made to take into account people that, for instance, will vote ever a given party, no matter what their neighbors do.
In order to control the above assumptions, in addition to UI items of NetLogo model in [2], the user has (likewise, in order to get the second point, the bilingual slider has been removed and the related source code commented)
  • the reslience slider (0 to 100) to set up the % of nodes (drawn with the shape of a “cow”) resilient, i.e. that never change their initial opinion no matter what their neighbors think;
  • ka and kb sliders (0 to 100) to set up the maximum payoffs av and bv, so that av = a±ra , with raϵ[-ka, ka] is random and where 0 ≤ ka ≤ a; and bv = b±rb with rbϵ[-kb, kb] is random and where 0 ≤ kb ≤ b.
After such initial setting, the user can
  • choose a network topology among “setup-fb” (Lada Adamic Facebook network), “setup19_4” (a network topology from [1]), “setup19_3” (another network topology from [1]), “setup-line” (line network topology), and
  • allocate opinions,
  • update opinions untill getting an equilibrium.
In order to accomplish the latter step, the user can either use the “alloc-opinion” button after tuning up the initial probability of blue nodes or set up one by one each node as red or blue. It is pobbile to play with a partner with the first person picking one blue node and the second one picking onother red one, and so on. Moreover, the first person can choose a “cow” node (i.e. a resilient node) and, as soon as they are available, the second person can do the same.
Finally, it is possbile to update the color of nodes with the “update” button in order to get start the game. After some hundreds of ticks an equilibrium is typically reached as it can be shown by the following chart.
Hence, I inserted the stop command after 500 ticks. In order to monitor network evolution, the following monitors have been inserted:
  • init-blue: initial number of blue nodes;
  • init-red: initial number of red nodes;
  • resilient-red: number of red cows;
  • resilient-blue: number of blue cows;
  • num-red: number of red nodes;
  • num-blue: number of blue nodes;
  • delta-in / delta-out (ratio): ((num − blue) − (num − red))/((init − blue) − (init − red)).
In the following, I will refer to the ratio delta-in/delta-out just with ratio.
For instance, let suppose we choose se the “setup-fb” with
  • identical payoffs to change opinion, i.e. a = b = 3,
  • probability to have initally A opinion equal to have inially B opinion, i.e. init-blue-prob = 0.5,
  • 34% of persons impossible to influence, i.e. resilience level = 34,
  • no variability in payoffs to change opinion, i.e. ka= kb = 0.
These settings get the following results after simulating elections:
  • init-blue: 76;
  • init-red: 74;
  • resilient-red: 27;
  • resilient-blue: 25;
  • num-red: 106;
  • num-blue: 44;
  • delta-in / delta-out (ratio): -31.
Ceteris paribus (i.e. with the same input parameters), the output ratio can be different. The first question is how much it is different. In order to study statistically this problem, the “100 series” button has been created. By using it, for 100 times NetLogo will
  • setup the Facebook network (setup-fb) with the same input input parameters,
  • allocate and update opinions untill getting an equilibrium.
At the end of such 100 simulations,
  • the monitor “mean” will report the statistical mean of ratio,
  • the monitor “variance” will report the statistical mean of ratio.
  • the monitor “standard deviation” will report the standard deviation of ratio.
The second question is why the ratio can be different starting with the same input parameters. I will answer to this question in the following sections.

1.2 Source Code

Source code can be fully download from [3].

2 An interpretation of the model

The model in [3] is an extension of the one in [2]. Specifically, the model in [3] collapses in the one in [2] by setting
  • 0% of persons impossible to influence, i.e. resilience level = 0,
  • homogeneous payoffs to change political opinion, i.e. ka= kb = 0.
So, we can ask
  1. what kind of impacts we have in the model assuming that a part of nodes (“cows”) are politically resilient to external influence as it happens effectively during political elections?
  2. what kind of impacts we have in the model assuming that nodes have heterogeneous thresholds in order to take into account the subjectivity of political issues (= the payoffs to change opinion are subjective)?
I show an interesting finding. The more the percentage of persons politically resilient to external influence inside the network (“cows”) the less the importance of network topology in order to predict the final political outcome. This can be esily seen thinking at the extreme case, i.e. resilience = 100 corresponding to the case where any node is a “cow”. In that case we would easily predict ratio = 1, i.e. no one will change opinion. In section 3.1 I will show that such a correlation holds in the general case.

Part II. Model testing

3 Misuring two key characteristics of the model

In this section two key characteristics of the model will be measured
  • higher levels of resilience increases the predictability of political outcome no matter the network topology and the initial allocation of red and blue nodes;
  • higher levels of variability in payoffs to change opinion decreases the predictability of political outcome.

3.1 Higher levels of resilience increases the predictability of political outcome no matter the initial allocation of red and blue nodes

In order to study such a problem, I performed the following simulations.
resilience ka kb init-blue-prob. ^mean(ratio) ^variance(ratio) ^std − dev(ratio)
0 0 0 0.5 3.83 899.18 29.98
10 0 0 0.5 3.35 520.49 22.81
20 0 0 0.5 3.60 218.32 14.77
50 0 0 0.5 3.21 111.95 10.58
60 0 0 0.5 2.01 82.29 9.34
70 0 0 0.5 1.42 81.96 9.05
90 0 0 0.5 1.32 13.78 1.94
100 0 0 0.5 0.92 0.07 0.27
A regression of observed mean of ratio has been performed. The value of R2tells us the proportion of the variance in the forecast variable (i.e. the mean of ratio) that can be accounted by the predictor variable (i.e. resilience). Hence, if we know the resilience we can predict 89% of the variability we will see in the mean of ratio. It is a pretty good result (a typical threshold value for R2 is 0.37).
In the same way, if we know the resilience we can predict 72% of the variability we will see in the variance of ratio. It is a pretty good result (a typical threshold value for R2 is 0.37).

3.2 Higher levels of variability in payoffs to change opinion decreases the predictability of political outcome

In order to study such a problem, I performed the following simulations.
resilience ka kb init-blue-prob. ^mean(ratio) ^variance(ratio) ^std − dev(ratio)
0 0 0 0.5 4.46 705.60 26.56
0 10 10 0.5 4.54 731.32 27.04
0 20 20 0.5 2.99 583.03 24.14
0 30 30 0.5 2.27 407.61 20.18
0 40 40 0.5 6.34 429.23 20.71
0 50 50 0.5 6.19 617.39 24.84
0 60 60 0.5 6.64 447.33 21.15
0 80 80 0.5 8.69 424.75 20.61
0 100 100 0.5 5.00 827.24 28.76
Here a regression of observed mean of ratio has been performed. The value of R2tells us the proportion of the variance in the forecast variable (i.e. the mean of ratio) that can be accounted by the predictor variable (i.e. threshold variability ka = kb). Hence, if we know threshold variability we can predict 31% of the variability we will see in the mean of ratio. It is not a good result (a typical threshold value for R2 is 0.37).
In the same way, if we know threshold variability we can predict 0.12% of the variability we will see in the variance of ratio. It is not a good result (a typical threshold value for R2 is 0.37).

4 A comparable existing model chosen and simulated

The comparable existing model chosen is the one in [2], as the model in [3] is an extension of the one in [2]. Specifically, the model in [3] simulates in the one in [2] by setting
  • 0% of persons impossible to influence, i.e. resilience level = 0,
  • homogeneous payoffs to change political opinion, i.e. ka= kb = 0.
I simulated the model in [2] with the one in [3] both in sub-section 3.1 and in sub-section 3.2. For instance, in the former case the following results are produced.
resilience ka kb init-blue-prob. ^mean(ratio) ^variance(ratio) ^std − dev(ratio)
0 0 0 0.5 3.83 899.18 29.98

5 A comparison between two models

The questions that the model in [3] can answer and that the model in [2] can not are
  1. what kind of impacts we have in the model assuming that a part of nodes (“cows”) are politically resilient to external influence as it happens effectively during political elections?
  2. what kind of impacts we have in the model assuming that nodes have heterogeneous thresholds in order to take into account the subjectivity of political issues (= the payoffs to change opinion are subjective)?
At this regard, sub-section 3.1 and 3.2 claim that
  • higher levels of resilience increases the predictability of political outcome no matter the initial allocation of red and blue nodes;
  • higher levels of variability in payoffs to change opinion decreases the predictability of political outcome.

6 Step by step instructions and key points in source code

In this section I will provide
  • step by step instructions for replicating the evaluation; and
  • the related key points in source code.

6.1 Step by step instructions

Download NetLogo model from [3]. Open and set up
  • Facebook network (“setup-fb” button),
  • identical payoffs to change opinion, i.e. a = b = 3,
  • probability to have initally A opinion equal to have inially B opinion, i.e. init-blue-prob = 0.5,
  • 0% of persons impossible to influence, i.e. resilience level = 0,
  • homogeneous payoffs to change political opinion, i.e. ka= kb = 0.
Hence,
  • allocate opinions (“alloc-opinion” button),
  • update opinions (“alloc-opinion” button) untill getting an equilibrium.
On the other side, download NetLogo model from [2]. Open and set up
  • Facebook network (“setup-fb” button),
  • identical payoffs to change opinion, i.e. a = b = 3,
  • probability to have initally A opinion equal to have inially B opinion, i.e. init-blue-prob = 0.5.
Hence,
  • allocate opinions (“alloc-opinion” button),
  • update opinions (“alloc-opinion” button) untill getting an equilibrium.

6.2 Key points in source code

In order to implement resilient nodes (“cows”) and heterogeneous thresholds, the following turtles-own variables must be declared.
turtles-own [   
  resilient   
  a-node ;; heterogeneous payoff    
  b-node ;; heterogeneous payoff  
]
Hence, the update procedure must be properly modified.
...
ask turtles [       
  if resilient = 0 [        
    if any? link-neighbors with [color = blue or color = red] [  
      let payoff-a a-node * count link-neighbors with [color = blue]
      let payoff-b b-node * count link-neighbors with [color = red] 
      set color blue       
      if (payoff-a < payoff-b) [            
        set color red          
      ]          
      if ((payoff-a = payoff-b) and (random 100 < 50)) [
        set color red    
      ]        
    ]     
]     ]    
​
...
​
tick
...
For other minor modifications, please refer to source code from [3].

Part III. Interpretation

7 Limitations of data

The main limitation is that conclusions of sub-section 3.1 and 3.2 are derived from a single network topology (Lada Adamic Facebook network). In order to extend such conclusions to the general case, simulations and related regressions of sub-section 3.1 and 3.2 should be performed in a wider range of network topologies.
Another limitations is that conclusions of sub-section 3.1 and 3.2 are derived starting from a statistically initial equal situation (i.e. initial number of red nodes statistically equal to the number of initial blue nodes). In order to extend such conclusions to the general case, simulations and related regressions of sub-section 3.1 and 3.2 should be performed in a wider range of inital political allocation patterns.

8 Insights from the analysis

Conclusions of sub-section 3.1 and 3.2 claim that
  • higher levels of resilience increases the predictability of political outcome no matter the network topology and the initial allocation of red and blue nodes;
  • higher levels of variability in payoffs to change opinion decreases the predictability of political outcome.
Hence,
  • samples of social network comminities could be studied in order to asses the level of political resilience (e.g. members can answer to some questionaries). If such a level is high (e.g. forums where people have same political opinions), then the model could be used in order to predict and influence political outcome inside that community (e.g. putting strategically some “cows” inside the network).
  • samples of social network comminities could be studied in order to asses the level of variability in payoffs to change political opinion (e.g. members can answer to some questionaries). If such a level is high, we know is very hard to influence and predict political outcome inside the whole community. A strategy could be trying to cut the community (e.g. putting strategically some “cows” around weak ties of community) and repeat the process on the two seprate communities.

References

[1] Easley and Kleinberg, Networks, Crowds and Markets, Ch19.Cascading Behavior in Networks
[3] Gino Tesei, NetLogo Model for political elections (https://docs.google.com/file/d/0B1zSgDfZgjLTY1REdjZlR3JCcU0/edit?usp=sharing)