Prepared by Jing Zhang, Bikram Kashyap and Buddhika Laknath Semage

This lecture talks about diffusion in social networks. The type of tools that we’re using is simulation and some mathematics. Those are the related literature, the most impactful literature that clipped on diffusion.

### Models and Tools

-Claudio Castellano. Santo Fortunato and Vittorio Loreto (2009), Statistical Physics of Social Dynamics, Reviews of Modern Physics 81, 591-646.

-Thomas Liggett. [Interacting particle systems](http://catalog.lib.buffalo.edu/vufind/Record/000681209). Vol. 276. Springer Science & Business Media, 2012.

-Seth Tisue, and Uri Wilensky. “[Netlogo](https://ccl.northwestern.edu/netlogo/): A simple environment for modeling complexity.” International conference on complex systems. 2004.

– N. A. Christakis, & J. H. Fowler (2007). The spread of obesity in a large social network over

Centola, D. 2010. The Spread of Behavior in an Online Social Network Experiment. science 329(5996):1194

-Stephen Eubank, et al. “Modeling disease outbreaks in realistic urban social networks.” Nature 429.6988 (2004): 180-184.

The first one is a summary of all kinds of models about diffusion. Models about diffusion can explain the formation of language, for example, culture and other type of things.

The second one is about the interacting particle systems and the idea is that if we have just one particle and if each particle can take two states, and if we have a large system of many of those not interacting particles, then the system is pretty easy to understand, because it’s just the product dynamics of the individual particles, but if we impose some interaction among those particles, then, the system becomes harder to understand,.

Also, because this type of problem maybe very hard, especially if we cope with a smaller system. If we cope up with a larger system, then we could think of what would be the equilibrium behavior and how many equilibrium states there will be. If we let the system evolve from arbitrary initial state, then how many final states there will be and how many attracting states? Those are the attracting states, so given initial state, how can we know what will be the final state of the system up to the evolution?

The third one is a simulator. NetLogo is agent-based stimulator. The configuration of NetLogo is a space, a two-world space with grid, so we have cells in our matrix and the cells in the matrix can interact with the neighbors. We can define the neighbors in different ways. They can interact with the neighbors in various ways that can be defined with a program language.

Also, we have many practical work on real-world data set and this one, the first one by Christakis and Fowler is perhaps the work that makes people begin to realize that this kind of diffusion behavior actually exists in our real-world network. It is on data set collected about the medical records collected in the New England area in Massachusetts, and it is about more than 30 years of data sets. It’s a data set about patients. Each time a patient visited the clinics, we have a recording about the height, weight, and on the behavior of the patients. Since the patients recommend their relatives and their friends to join the medical network, so we’d have a network, and as we get a huge amount of data then, this is the situation we can talk about science because we have a huge amount of data then. This means that we have either central limit theorem or theorem of mass deviation, so the patterns that we can find may be some pattern that can be generalizable. This is a first, a practical study about the social diffusion.

The last study about social diffusion is about the behavior. From the previous studies, we know that the behaviors and opinions will diffuse in real-world networks. One opinion is that the more of my neighbors, the more of my friends take certain opinions, then I will have higher probability of take this opinion. Another competitive idea is that the probability for me to take opinion does not depend on the number of friends that take opinion. It is only based on whether or not I am in the influence of opinions.

### Voter Model

– $N=\{1,\dots,n\}$ are nodes

– $E\subseteq 2^N$ are edges

– $X_i(0)=\pm 1$ for $i\in N$

Interate over $t$:

Choose j randomly from $\{j: (i,j)\in E\}$ with probability $1 \big / \sum_{(i,j)\in E} 1$, and

$X_i(t+1)\leftarrow X_j(t)$

The first model that we want to talk about is what people call a voter model. A voter model works in the following way. We have a node and we have an edges on those nodes. We could have N times N directed edges, and each edge could exist or not exist. This is why we have 2 to the N number of potential edges.

Each node could take one of two states, either +1 or -1, so they are voting. They are either voting for +1 or voting for -1. This is the set-up of our work. We have nodes and we have edges, and the nodes could take either +1 or -1, and the dynamics of this voter model works in the following way: we iterate through time, at any time, we randomly pick a node and after we random pick a note, we randomly pick one of his neighbor, it could be any neighbor, uniformly, and then, we change our opinion to the opinion of our neighbor. These kind of model captures the behavior that a person, the opinions, the randomness spread from one person to another person.

#### Modifications:

– Adding “zealots” who do not change opinions

– 3 States per agent, leftists, centrists and rightists

interactions involve only centrists

leftists and rightists do not talk to each other.

– Introducing memory — Changing opinion only after encouraging opposite opinion $\ge r$ times

Modifications of these models could be done to capture a more advanced behavior include, for example, we have a certain amount of zealots in a system and those zealots do not change opinions. This could be true, right? The idea is how does the zealot affect the behavior of this network?

Another modification could be that we have, instead of two states for each node, we have three states. We could have each agent, each node could be a leftist or a rightist, or a centrist. The leftist could bring a centrist to the left side and the rightist could bring the centrist to the right side, but the leftist never interact with the rightist, and the rightist never act with the leftist. Again, the idea is what will be the dynamics of this model. Those are the ways that have some impact. This means that those ways have been adopted by many persons in their studies.

Another way is for us to introduce our memory. This means that we only change, a person in the network only changes his or her opinion after he or she has already heard of this opinion for many times, heard of either +1 or -1. In the example that we mention, it could be that a certain amount of people have already told him about the new opinion.

The questions that we want to ask in such kind of models as, for example, whether or not all people in this system will agree on on a certain stand meaning, whether the system will cover still either all +1 or all -1, or something. This is **one** thing that we could ask.

If it does not happen, the next question is whether or not this system will ultimately get to some stationary state after some time, or this system will be evolving randomly or purely adequate. This is the **second** question that we could ask.

The **third** question that we could ask is that whether this system will become more, will evolve, will form more order or less order will be more chaotic or less chaotic. Those are all very good questions that we could ask. If we think about the book on interacting particle systems, the hardest thing is first, how can we formulate this problem mathematically? After we formulate this program mathematically, how can we solve those problems? Those problems, although they sound pretty easy and intuitive, but they are actually pretty hard.

Constantly, the voter model, what we found is that starting from a chaotic state. The system will evolve and it ultimately reaches some state with some stationary, with some order there. This is a voting model written by NetLogo [http://ccl.northwestern.edu/netlogo/models/Voting], and so we can actually conduct some experiments. If we evolve this voter model, will ultimately gets to some stationary state and in different scenarios we’ll get different conclusions, and in some scenarios, we will be able to get a consensus in this system.

Another model that we want to talk about is called this bounded confidence model. Again, we have a system, a network of nodes or people. In this network, each people could have opinion, and this opinion is a number randomly distributed between zero and 1.

**Bounded Confidence Models
**(http://ccl.northwestern.edu/netlogo/models/community/bc)

People only talk to those with similar opinions

– $N=\{1,\dots,n\}$ are nodes

– $E\subseteq 2^N$ are edges

– $X_i(0) = x_i(0) \in [0,1]$

Interate over $t$:

Choose j randomly from $\{j: (i,j)\in E\}$

if $|x_i(t)-x_j(t)|\ge\epsilon$ nothing happens at time $t+1$, otherwise

– $X_i(t+1) = X_i(t)+\mu\cdot \left(x_j(t)-x_i(t)\right)$

– $X_j(t+1) = X_j(t)+\mu\cdot \left(x_i(t)-x_j(t)\right)$

**Properties of Bounded Confidence Models**

Number of clusters is approximately $1 / (2\epsilon)$,

because at stationarity, people in different clusters cannot talk to each other

This model evolves in the following way. At each time we iterate over time $T$, at each time $T,$ we randomly choose a pair of nodes, $I $and$ J,$ and if the opinions of $ I$ and $J$ is greater than some threshold then, it will not influence one another. However, if the opinions of those two people are within some SigmaXL, then they will change their opinion, convert their opinion according to the opinion of other people. This is the bounded confidence model.

Again, the question that we want to ask about this bounded confidence model is that what will be the distribution of the opinions ultimately in this system? Those are mathematical problems, but the first is, to start thinking about this model is to first proceed with some stimulation and find out what will be the result.

NetLogo User Community Models

[http://ccl.northwestern.edu/netlogo/models/community/bc]. At each time step, we randomly select two people among all peoples, and if the opinions of those two people are too far away, then, those people do not change opinions, but if the opinions of those people are close enough, then their opinions will move closer to each other.

Then, this means that if the opinions of any two persons are close enough, then, their opinions will converge. So, as time goes on, there will be certain attractors in the system, and those attractors will collect together the nearby opinions. That is why we ultimately get some polarized opinions in this system.

**Majority Rule Models**

A group of $r$ agents is selected at random,

and all agents in the group take the majority opinion.

$\Rightarrow$ System could have concensus $E(X)=\pm 1$, unstable state and metastable state.

[Models based on Social Impact Theory]

(http://ccl.northwestern.edu/netlogo/models/community/Sitsim)

– $N=\{1,\dots,n\}$ are nodes

– $E\subseteq 2^N$ are edges

– $X_i(0)=\pm 1$ for $i\in N$

Agents change opinions according to the

opinions of distance, persuasiveness, and supportiveness of other agents.

The other kind of model about the opinions is that, again, here, we have the agents. They are in a network, so they have distances, and the distances could be defined in various ways such as the number of hops, one node to another node, or if the network, the distance is defined in terms of distance, then we can find out a circle and find out the groups within the circle.

What we do in this majority role model is that we have a system of people and each people could take one of two opinions, either plus or minus. Each two people have a distance. At each time step, we will random pick a person, and then, randomly pick a radius among this person. This is the group that we want to consider. Then, we change the opinions of all of those persons into the majority of their opinions. This is how this model works.

Of course, we can also work with a more complicated model, and the beauty of a simple model is that a simple model will be more generalizable to other situations, and if we have a lot of constraints about a model, then the generalizability of the model is limited.

Based on the social impact theory, an agent change opinions according to opinions of the distance such as in the majority role or could also be based on the persuasiveness of the other people, or based on the supportiveness of the other agents. The agent could persuade another agent. An agent could pursue another agent to change opinion or could support the same opinion of another agent. This is the idea.

In a social network, we normally have. It’s normally a small world, cluster network. We have clusters and in the clusters, people are cohesively, tightly connected, and between the clusters, we have wear ties. There are also gateway people and the gateway people tends to propagate the ideas from one cluster to another cluster. As social impact theory actually captures this type of dynamics. Another book which I haven’t listed here because it’s just a pop science book. I think it’s called Structural Hole. It’s also a pretty interesting book about the dynamics of social networks and the diffusion of information and ideas within a social network.

We have talked about the opinion dynamics. The next topic that I want to talk about is culture dynamics. Culture dynamics is actually not very different from opinion dynamics. The only difference is that in opinion dynamics, each person can have one dimension which is opinion about something. It could be the + or 1, it could be a range, but in culture dynamics, we have a culture is composed of multiple opinions. We could have opinion one to opinion N, and each opinion could take values from a range. It could be the +1, -1 could be within a range.

### Cultural Dynamics

– What are the microscopic mechanisms that drive the formation of cultural domains?

– What is the ultimate fate of diversity?

Is it bound to persist, or all differences will eventually disappear?

– What is the role of social network structure?

In cultural dynamics models, we examine the evolution interaction of different cultural domains and groups and try to reason their eventual fate. Whether the cultures will combine, or if they will consolidate. What factors are responsible. What are the roles of social network structure?

Axelrod Model [http://ccl.northwestern.edu/netlogo/models/community/Dissemination%20of%20Culture]

Individuals in a network have

– $F$ **features** $\left(\sigma_1,\sigma_2,\dots,\sigma_F\right)$,

– $q$ **traits** per feature $\sigma_f=0,1,\dots,q$ for $f=1,\dots,F$

At each step

#. an individual $i$ and its neighbour $j$ are selected,

#. their similarity is estimated $w_{i,j}={1\over F}\sum_{f=1}^F 1_{\sigma_f(i),\sigma_f(j)}$

**social influence**: tendency for individuals to become more similar when they interact

#. with probability $w_{i,j}$, $\sigma_f(j)\leftarrow\sigma_f(i)$ for $f$ s.t. ($\sigma_f(i)\ne\sigma_f(j)$)

**homophily**: tendency for the likes to interact more

Axelrod, R., 1997, J. Conflict Resolut. 41(2), 203.

** Properties of Axelrod Model **

starting from disordered initial condition, the system will evolved into

– the ordered state, in which all individuals share the same traits for all features, or

– one of frozen states, with coexistence of different cultural regions.

– System will more likely to evolve into many cultural regions if each feature has more traits.

At each step, an individual i and its neighbor j are selected, and their similarity is calculated using $w_{i,j}={1\over F}\sum_{f=1}^F 1_{\sigma_f(i),\sigma_f(j)}$. That is we are calculating the similarities based on agreement of the features. If feature f of individuals i and j agrees, then their similarity weight increases, and if the feature f is different, then it has no contribution.

Now, with probability wi,j, we change the features of individual j by the features of individual i.

Set $\sigma_f(i)=\sigma_f(j)$, with probability $w_{i,j}$ for all f such that $\sigma_f(i)\ne\sigma_f(j)$.

Repeated application of this algorithm can be used to simulate the evolution of culture groups. Starting with a random distribution of features and the traits, we can run the algorithm and end up with three different kind of evolution:

● All converge into one culture, with same features.

● There will different cultural regions coexisting, in a frozen state. There will be clusters of features for the different cultural regions.

● If each feature has a lot of traits, convergence becomes hard. So we will end up with lot of small clusters, that is, cultural regions.

If we try to use tweets to simulate the system, with a small number of tweets per culture, the system will consolidate the people in the culture. With a high number of tweets, this becomes much harder. In a system of people, we have many features, and many tweets for each features, that is, the tweets can be considered traits. With high count of tweets, we end up in the third situation as described above.

It is easy to simulate the system programmatically. But getting an mathematical solution is hard. There are entire groups of people working on finding mathematical answers.

### Flock Dynamics

Each particle $i$ is characterized by its

– position $x_i$,

– direction $\theta$, and

– constant modulus of speed $v_0$

At each time step,

$\theta_i(t+\Delta t)=\theta(t) _{S(i)}+\xi$, where $\xi\sim U(-\eta,\eta)$

particle $i$ assumes average direction of particles nearby, with some random perturbation

A. Czirok, A.-L. Barabasi, and T. Vicsek, 1999, Phys. Rev. Lett. 82(1), 209

This kind on dynamics model is based on movement of birds and other animals like fish that moves in large groups. What we observe is birds moving in flocks, where a huge group moves together.

Each particle/member has 3 properties:

● Position $x_i$

● DIrection $\theta$

● Constant speed modulus $v_0$

At each time step, each particle assumes average direction of nearby particles, with some random deviation. With the passage of time, it is quite obvious that we will end up with clusters of particles moving in the same direction. Also if the particles are too fast, and the neighbourhood radius is small, then the interaction between particles will be very weak, and clusters will not form. If the particles are fast, and the neighbourhood is not to small, we can end up with just a single large cluster. NetLogo has a simulator where we can play with different parameters and simulate the system. The flock model might be too complex to be analytically analyzed, and there may not be any solid work on the analytical solution of the ultimate behaviour of the flock.

http://ccl.northwestern.edu/netlogo/models/Flocking

**Properties of Flock Dynamics **

Order parameter $\Phi={1\over N}\left|\sum_{j=1}^N \vec v_j\right|$ varies with noise level $\eta$:

$\Phi(\eta)=\begin{cases}

\left[\frac{\eta_{c}(\rho)-\eta}{\eta_{c}(\rho)}\right]^{\beta} & \eta\eta_{c}(\rho)

\end{cases}$

where

– $\rho$ is the density of particles

– $\eta_c$ is threshold noise for system to evolve into an ordered state

The order parameter $\Phi$ varies with the noise $\eta$. If the noise level is over a threshold noise level $\eta_c$, then we will have chaotic behaviour, and the flocks will not form. If the noise is less than the critical noise level, then we will end up with consolidated behaviour. The lower the noise, the more coordinated the members in the flock will be.

### Language Dynamics

– Processes explaining the emergence, change, evolution, interactions and extinction of languages

– **Sociobiological approach**: Successful communicators, enjoying a selective advantage, are more likely to reproduce than worse communicators.

– **Sociocultural approach**: Agents can select better strategies exploiting cultural choice and direct feedback from the system.

Language Dynamics model is an attempt at exploring behaviors of human languages. With this model it’s possible to simulate events such as formation of languages, evolution and the outcome.

There are two schools of thoughts when it comes to language dynamics.

1. Sociobiological approach

This approach takes the position that successful communicators enjoy a selective advantage because they can better communicate with each other and they can better coordinate their behavior. It’s based on the hypothesis that social behavior has resulted from evolution and attempts to explain and examine social behavior within that context [1][3]. Applying the phenomena of natural selection in evolution theory, successful communicators are more likely to reproduce than their less successful communicators and become the more prominent trait.

2. Sociocultural approach

This approach is based on the concept that human activities take place in cultural contexts, are mediated by language and other symbol systems, and can be best understood when investigated in their historical development [2]. Because of the interdependence of social and individual processes, individual agents can set up better strategies by exploiting culture choice and feedback from the system.

#### Naming Game

There is a vocabulary of words.

Initially all agents in a network have empty memory.

Iterate over the following steps until convergence.

1. A pair of neighbor agents are chosen, one as speaker and the other as listener.

2. If the speaker has empty memory, he will generate a new word from the vocabulary.

Speaker randomly selects a word from his memory and tell it to the listener.

3. If the listener has the word, he will remove all other words and keep only this one.

Otherwise, the listener will remember this word.

Baronchelli, A., Felici, M., Loreto, V., Caglioti, E. & Steels, L. Sharp transition towards shared vocabularies in multi-agent systems. J. Stat. Mech. 2006, P06014 (2006).

Naming game is a quite well-known interpretation of the language dynamics. It’s a model able to account for the emergence of a shared vocabulary of form-meaning associations through social/cultural learning [4].

It works in the following way.

There’s a vocabulary of words, a network and nodes, which are the agents. Initially, the agents have an empty memory. Whenever they encounter something, they will name them and will communicate the name with other agents.

At each time, we will randomly choose a pair of neighboring agents as the pair of agents who needs to communicate with each other. We specify one agent as a speaker and another agent as a listener. If the speaker has an empty memory, he would generate a new word from the vocabulary. And if the listener has the word in his vocabulary, then the speaker and the listener have both consolidated the word. The interaction is considered a success, and both agents delete from their inventories all their names except for the agreed name.

But if the name chosen by the speaker is not in the memory of the listener, he will think of the word as a new word, and will add the word to his memory (ie: remember the word).

**Properties of Naming Game**

Starting from random choice of words by networked individuals,

global consensus will eventually emerge.

– $N_w(t)$, total number of words in the population

– $N_d(t)$, total number of different words in the population

– $S(t)$, success rate

Now that we have established the rules of the game, let’s look at the dynamics.

What has been observed in this model is that during the exploitation stage, the total number of active words in the system will first increase. Then it will decrease and the total number of different words will also decrease. But the successful rate of this system will gradually increase.

**Evolution Language Game**

– $n$ objects

– $m$ words

– **production matrix** $p_{i,j}$ probability for speaker to use word $j$ when seeing object $i$

– **comprehension matrix **$q_{i,j}$ probability for lisener to associate word $j$ to object $i$

–** language** $L=(P,Q)$

– **fitness** $F(L_1,L_2)={1\over 2}\sum_{i,j} p_{i,j}^{(1)}q_{j,i}^{(2)}+p_{i,j}^{(2)}q_{j,i}^{(1)}$

– **associate matrix **$a_{i,j}$ number of times parent associate object $i$ with word $j$

– $p_{i,j}=a_{i,j}/\sum_l a_{i,l}$

– $q_{i,j}=a_{i,j}/\sum_l a_{l,j}$

In order for a set of agents in a network to form a language, the set of agents should choose some strategy to be able to think in an understandable way through the above naming game. This is the idea behind evolution of language game.

There are N objects and M words. We want to use the M words to represent the N objects. There are two matrices.

1. Production matrix – This is at the speaker’s side. Each row represents an object and each column represent a word. Whenever we see an object, we have a distribution of the words, which represents the likelihood of the speaker to choose certain words. An entry in this matrix – $p_{i,j}$ ¬ represents the probability for speaker to use word j when explaining the object i.

2. Comprehension matrix – This is at the listener’s side. Whenever a listener gets a word, he will map the word to a set of objects in the system. An entry in the matrix – $q_{i,j}$ represents the probability for the listener to associate word j to object i.

The fitness of this system will be represented as the probability for a pair of listener and the speaker to understand one another in both ways.

$F(L_1,L_2) = \frac{1}{2}\Sigma_{i,j} p_{i,q}^{(1)}q_{j,i}^{(2)} + p_{i,q}^{(2)}q_{j,i}^{(1)}$

The first term is the average success rate for person J to understand person I. The second term is the average success rate for person I to understand person J. The combination of two terms gives the fitness of this system.

This system evolves in a way that the parents will have kids in a genetic model and the kids will take the production matrix or the comprehension matrix from the parents with some random permutation. In the end, our goal is to evolve this language so that the rate — the fitness of this system increases.

### References

[1] https://en.wikipedia.org/wiki/Sociobiology

[2] http://webpages.charter.net/schmolze1/vygotsky/johnsteiner.html

[3] http://plato.stanford.edu/entries/sociobiology/

[4] http://openaccess.city.ac.uk/2659/1/In-depth%20analysis%20of%20the%20Naming%20Game%20dynamics.pdf