Simulating Collective Behaviour with Linear Threshold Model

Introduction

Your government has decided to ban Python. You cannot allow that to happen and therefore decide to riot. Of course, before actually rioting you want to know whether you will be successful and try to simulate the riot. Granovetter's Linear Threshold Model enables you to model the collective behaviour of people in cases such as riots, technology adoptions and other similar phenomena.

The Linear Threshold Model is a network-based approach. Each person is represented as a node and if two people interact with each other, such as friends or coworkers, an edge between those nodes exists. A person can now belong either to the rioting group or not. Initially every person is not part of the rioters.

How do we now figure out who riots and who does not? And how do we simulate a behaviour in which more and more people start rioting?
To solve these problems, we have to introduce an additional characteristic, which describes the behaviour of individuals. This the threshold.
The threshold is a abstraction over all different traits a person has and describes how likely it is for that person to engage in the riot, based on how many acquaintances (neighbors in the network) are rioting.

Lets go with our example:
You draw out your network of acquaintances. You have two friends Alice and Bob, who are also friends. Additionally, you have a coworker Eve, who neither Alice nor Bob know.
Enraged by the Python ban, you need no further motivation to riot. Your threshold is 0. You are the initiator of the riot. Therefore you start to riot at time step t=0.
At t=1, you can now start to influence other people. Bob has a very low threshold of 0.4. Because he has only two neighbors, Alice and you, his ratio of rioting to total neighbors of 0.5 exceeds his threshold and he also starts to riot. Alice however also programs in Javascript and is harder to convince with a threshold of 0.8. At time step t=1 she only has one rioting neighbor, since Bob only starts to actively participate in the next time step. Your coworker Eve cannot be convinced at all, since she doesn't like snakes. Her threshold is 1.1.
At t=2, both Bob and you are rioting. Therefore Alice's ratio of rioting to total neighbors is 1.0, which exceeds her threshold. Alice will also start to actively participate in your riot after the end of this turn.
Since no one else can be convinced to participate in the following time step, your simulation stops with 3 rioters and 1 non-rioter. Apparently that is enough to convince your government to repeal the Python ban. Congratulations!

You can find this example network and thresholds in Example Test Cases, under example_network and example_thresholds.

Task

Implement the function simulate_riot(network, thresholds), which simulates a riot using the linear threshold model, until no new people start rioting.

In each iteration of the model, a person is added to the rioters, if their ratio of rioting to total neighbors is greater or equal to their threshold. So formally a person i starts to riot, if the following condition is true: number_of_rioting_neighbors/total_number_of_neighbors >= threshold[i].

If a person starts rioting in iteration t, they are able to affect their neighbors in the following iteration t+1.

At iteration 0, people with threshold 0 start rioting.

The function records and returns the set of rioters at each iteration, in which new people get added to the set of rioters. If no changes in the number of rioters occur, the model stops and should return the recorded history.

Input

network is an adjacency matrix (list of lists) of dimensions N*N, representing an undirected, unweighted graph. If network[i][j] equals 1 an edge between person i and j exists, if it equals 0 no edge between i and j. Because the network is undirected, the matrix is symmetric. No person can be adjacent to themselves, therefore network[i][i] == 0 for all i in range(N).

thresholds is a list of floats with length N. thresholds[i] >= 0 applies for all i in range(N). thresholds[i] corresponds to the threshold of person i. This threshold is the minimum ratio of rioting to total neighbors, at which person i also starts to riot.

Output

Let history be the output of the function simulate_riot(network, thresholds). history is a list of sets of integers. It stores the set of rioting people after each iteration. history[0] contains the set of initial rioters, which are the people with threshold 0. If no person has a threshold of 0, no one can start rioting and therefore the empty list should be returned. history can have maximum length of N (number of people in network), since the model stops iterating after no changes occur and only N changes can occur.

Some links

• Original paper: Granovetter (1978). Threshold Models of Collective Behaviour
• Check out my kata about friend-foe networks: Detecting Factions in Friend-Foe Networks

Any comments are appreciated.

• Is the algorithm explanation understandable?
• Are the provided test cases sufficient?