Introduction

Spreading information from human to human plays a significant role in daily human life. People spread information everyday. Sometimes we spread information to specific people in our life and sometimes we make an announcement to a broader audience. The spread of information can shape the public opinion (Galam, 2003) and therefore analyzing how information spreads within a community is an interesting and a present-day topic in research.

Goal of the project

In this project we will look at the speed of spreading information in different social network structures. Specifically, we will look at how quickly every person in the network knows about a rumour that is injected into a network. A more detailed and precise definition of the network will be given in the next section. In this study we will not only look at how fast knowledge spreads within a social network, we will also look at when nth order shared knowledge is achieved. Subsequently we will see if any interesting patterns arise and whether we can generalize our findings. Moreover, to better understand the workings of the network we will look at a stepwise example of a Kripke model that describes epochs in a simple social network.

Details of the social network

We define a social network to consist of N agents. The number of connections an agent has is randomly selected around a mean with the constraints, that every agent has a mininmum of one connection and a maximum of N-1 connections. Connections between agents are always bidirectional. The simulation starts with an injection of a rumour φ in a random agent (which we call agent 0). This happens at epoch 0. This means that after epoch 0, this agent knows φ. At epoch 1, agent 0 spreads the rumour to all its neighbors. Two agents are neighbors if they are connected. Not only does an agent spread φ, agents also spread the set of agents that know φ according to their belief. We call this set of agents M. This will be clarified in the example below.

Example

Consider a fully-connected social network with 4 agents. At epoch 0, a rumour φ is injected in the network at agent 1. At epoch 1, agent 1 spreads the rumour to agent 2, 3 and 4. Since agent 1 got the rumour injected, it does not know any other agents that know φ. Therefore M is empty. At epoch 2 all agents know φ. However, not all agents know that everyone knows φ. At epoch 2 three things happen:

• Agent 2 spreads to agent 1, 3 and 4 φ and M = {agent 1, agent 2}
• Agent 3 spreads to agent 1, 2 and 4 φ and M = {agent 1, agent 3}
• Agent 4 spreads to agent 1, 2 and 3 φ and M = {agent 1, agent 4}

After epoch 2 the knowledge of every agent is (duplications in the knowledge of agents are deleted):

• Agent 1: φ, M = {agent 1, agent 2, agent 3, agent 4}
• Agent 2: φ, M = {agent 1, agent 2, agent 3, agent 4}
• Agent 3: φ, M = {agent 1, agent 2, agent 3, agent 4}
• Agent 4: φ, M = {agent 1, agent 2, agent 3, agent 4}

This means that every agent knows φ and every agent knows that every agent knows φ. An example of a state of the network is given in Figure 1, here red nodes know the rumour while green nodes do not. Here agent 3 started with the rumour and has now spread this rumour to agents 9 and 8, in the following step the rumour will spread to agents 1, 2, 4, and, 6.

Kripke model of a social network simulation (step by step)

In this paragraph we will go through a simple simulation and we will create a Kripke model for every epoch. This walkthrough consists of 2 agents, A and B and rumour φ. The two agents are connected and the rumour φ is injected in agent A after epoch 0. This Kripke model assumes an S5 systems. This also means that an agent knows that it does not know φ (A5) which is an important assumption.

Epoch 0

At epoch 0 neither agent A nor agent B know φ. The Kripke model for epoch 0 is shown in Figure 2 This model shows that both agents consider worlds where they do or do not know φ. They also both consider worlds where the other agent does or does not know φ. The fact that the agents consider these worlds is a direct result of (A5). Informally, this means that the agents know that they do not know φ. However, this is not a realistic scenario because how can you know that you do not know something in the first place? This is one of the main arguments against the S5-system when dealing with a real-life scenario.

Epoch 1

At this point in time, agent A knows φ. However, agent B does not know φ yet. Agent A knows φ but it does not know whether agent B knows φ. Therefore agent A loses its relation between w₁ and w₂ and the Kripke model looks like Figure 3.

Epoch 2

Agent A has spread Agent A has spread φ to all its neighbours, which is agent B. Because agent A told φ to agent B, now all agents know φ. Since agent A told agent B φ, K_AK_Bφ. Since agent B heard φ from agent A, K_BK_Aφ. This can also be proven from the Kripke model shown in Figure 4.

Measurements

As previously mentioned we want to measure how quickly rumour φ spreads and when second order shared knowledge is achieved. For the final project we want to compare different social network initializations with each other. More specifically, we want to look at the number of epochs needed for nth order shared knowledge for different social network initializations. To get more insight into the behaviour of different network structures we will now discuss and compare the results of four different experimental runs. Two of these experiments will focus on sparsely connected graph structures, which will resemble a situation in which agents only have direct contact with to a small subset of all agents M. The other two experiments will focus on densely connected graph structures in which every agent is connected to all other agents, or in other words a complete graph.

Experiment 1: 10 agents, 5 connections per agent

Experiment one concerns a graph structure consisting 10 agents in which every agent is connected to 5 other randomly selected agents. We ran the simulation until 8th order shared knowledge was achieved. The results of the simulation can be seen in figure 5. The dotted line shows how many agents (%) know the original rumor at a given time-step, the solid lines represent the orders or shared knowledge. As can be seen from the figure it took exactly 11 time steps for the system to reach 8th order shared knowledge. Furthermore we can see a repeating shape in the solid lines. 1st order shared knowledge goes from 0 percent to 80 percent in one time-step, between t=2 and t=3 after which it reaches 100 percent at t=4. After 1st order shared knowledge has been reached at t=4, the line for 2nd order shared knowledge moves from 0 percent to 10 percent between t=4 and t=5, reaching 100 percent at t=6. This exact movement repeats itself up until 8th order shared knowledge.

Experiment 2: 50 agents, 5 connections per agent

Experiment two concerns a complete graph consisting of 10 agents, meaning that every agent has exactly one direct connection with every other agent. The results of experiment two can be found in figure 6. If we look at figure 6 we can see that it takes exactly 9 time-steps to reach 8th order shared knowledge, which is 2 steps less compared to experiment one. Furthermore, we can also see that the lines are very structured and predictable. It takes exactly one time step to go from nth order shared knowledge to (n+1)th order shared knowledge.

Experiment 3: 10 agents, 10 connections per agent (complete graph)

Experiment three concerns a sparsely connected graph structure consisting of 50 agents in which every agent is connected to 5 other randomly selected agents. The results of the simulation can be seen in figure 7. If we look at figure 7 we can see that it takes exactly 15 time-steps to reach 8th order shared knowledge. Furthermore, we can see that the lines are more chaotic and less predictable compared to experiments one and two. There seems to be no obvious pattern in the lines.

Experiment 4: 50 agents, 50 connections per agent (complete graph)

Experiment four concerns another complete graph consisting of 50 agents. The results of the simulation can be found in figure 8. If we look at figure 8 we again see the same behaviour as we saw in experiment 2. 8th order shared knowledge is reached at time-step 9.

Discussion Experiments

We will now discuss the observations made in experiments one to four. We saw that both experiment two and four show very structured and predictable behaviour. This can of course be explained by the fact that these are complete graphs, i.e. every agent has a direct connection to every other agent. This means that they can spread their knowledge to the whole network in one time-step. This graph structure shows behaviour reminiscent of the public announcements discussed during the lectures. In experiment one we also saw fairly predictable behaviour, which can be explained by the small amount of agent which leads to a relative densely connected graph, since every agent is connected to 5 other agents, which is 50 percent of the entire network. This leads to a network structure in which information propagates quickly and does not have to travel far, resulting in predictable behaviour. In experiment four we saw more unpredictable lines, which can be explained by the fact that the networks consisted of 50 agents in which every agent is connected to 5 other agents, which is just 10 percent of the entire network. This leads to a more complex flow of information, i.e. less predictable lines.

Diving Deeper

Understanding the Network Dynamics

The results of the experiment show that the first orders of shared knowledge take longer to spread than higher orders of shared knowledge with respect to the first inception of Kφ or E_iφ. For all levels of connectivity and all network sizes the same pattern seems to arise, although spreading is slower in when networks are more sparsely connected. In order to explain how this is happening we will look at a simple network shown in Figure 10. The graph in Figure 9 shows the corresponding results. In this particular run the rumor φ was injected at node 1. The following steps show how the knowledge of all 5 nodes updates while running. We will remove lists of K_iφ or K_iEKφ as soon as an agent can conlude a higher order shared knowledge in order to prevent an exponential growing mess. But that knowledge is there will be there implicitly through EK. For simplicity we will leave out any possible inferences that are not relevant for shared knowledge.

Step 1

• K₁φ

Step 2

• K₁φ ∧ K₂φ
• K₂φ ∧ K₁φ

Step 3

• K₁φ ∧ K₂φ
• K₂φ ∧ K₁φ ∧ K₃φ ∧ K₄φ
• K₃φ ∧ K₁φ ∧ K₂φ
• K₄φ ∧ K₁φ ∧ K₂φ

Step 4

• K₁φ ∧ K₂φ ∧ K₃φ ∧ K₄φ
• K₂φ ∧ K₁φ ∧ K₃φ ∧ K₄φ
• K₃EKφ ∧ K₃φ ∧ K₁φ ∧ K₂φ ∧ K₄φ ∧ K₅φ
• K₄EKφ ∧ K₄φ ∧ K₁φ ∧ K₂φ ∧ K₃φ ∧ K₅φ
• K₅EKφ ∧ K₅φ ∧ K₁φ ∧ K₂φ ∧ K₃φ ∧ K₄φ

Step 5

• K₁φ ∧ K₂φ ∧ K₃φ ∧ K₄φ
• K₂EKφ ∧ K₃EKφ ∧ K₂φ ∧ K₁φ ∧ K₃φ ∧ K₄φ ∧ K₅φ
• K₃EKφ ∧ K₄EKφ ∧ K₅EKφ -- Conclude EKφ
• K₄EKφ ∧ K₃EKφ ∧ K₅EKφ -- Conclude EKφ
• K₅EKφ ∧ K₃EKφ ∧ K₄EKφ -- Conclude EKφ

Step 5

• K₁EKφ ∧ K₂EKφ ∧ K₃EKφ ∧ K₁φ ∧ K₂φ ∧ K₃φ ∧ K₄φ ∧ K₅φ
• K₂EKφ ∧ K₃EKφ ∧ K₄EKφ ∧ K₅EKφ -- Conclude EKφ
• K₃EKφ ∧ K₂EKφ ∧ K₄EKφ ∧ K₅EKφ
• K₄EKφ ∧ K₂EKφ ∧ K₅EKφ ∧ K₅EKφ
• K₅EKφ ∧ K₃EKφ ∧ K₄EKφ

Step 6

• K₁EKφ ∧ K₂EKφ ∧ K₃EKφ ∧ K₄EKφ ∧ K₅EKφ -- Conclude EKφ
• K₂EKφ ∧ K₁EKφ ∧ K₃EKφ ∧ K₄EKφ ∧ K₅EKφ
• K₃EKφ ∧ K₂EKφ ∧ K₄EKφ ∧ K₅EKφ
• K₄EKφ ∧ K₂EKφ ∧ K₅EKφ ∧ K₅EKφ
• K₅EKφ ∧ K₃EKφ ∧ K₄EKφ ∧ K₂EKφ

Step 7

• K₁EEKφ -- Conclude EEKφ
• K₂EEKφ -- Conclude EEKφ
• K₃EKφ ∧ K₁EKφ ∧ K₂EKφ ∧ K₄EKφ ∧ K₅EKφ
• K₄EKφ ∧ K₁EKφ ∧ K₂EKφ ∧ K₅EKφ ∧ K₅EKφ
• K₅EKφ ∧ K₃EKφ ∧ K₄EKφ ∧ K₂EKφ

These first 7 steps of this simple network with 5 nodes show what explains the behaviour (i.e. the accelarated spread of higher orders of shared knowledge). The spread of the original rumor φ looks almost linear, it goes from node to node, and sometimes two nodes at the same time. But the meta knowledge about who knows φ already starts spreading back into the network before everybody knows φ. Which results in first order knowledge already being concluded at three different nodes in the same time step. Now the knowledge about EKφ spreads from three points at once. Spreading from three points at the same time results in EKφ conclusions spreading faster through the network once the first EKφ is concluded. An analogy for this is dropping a pebble in a bucket (rumor injection), the ripples spread evenly through the bucket (spreading Kφ) but once they bounce against the walls they start coming back and meeting one another (combining K_iφ lists into conclusions).

Patterns

As is clear by now our main observations was the rapid spread of higher order knowledge. When we started the porject we thought it might be possible to determine the time it would take to reach ith order shared knowledge given the network size and diameter. However, we quickly determined that this is highly dependent on the specific network. Nonetheless we are able to deduce some key boundaries for the time it takes to reach ith order shared knowledge.

• The time it takes for every agent to know φ is given by the diameter (D) of the network
• The the lower bound of time it takes for a network of size n to achieve ith order shared knowledge of φ is:
  E(i) = E(i - 1) + 2log(n/E(i - 1)). With E(0) = D, which represents the spread of initial knowledge.
• The upper bound of time it takes for a network of size n to achieve ith order shared knowledge of φ is i*n.

Code for the simulations

The code for this project can be found here. One can run the simulations by typing python Graph.py.