# Mimesis as random graph coloring

## Motivation:

After reading through the thought-provoking masterpiece by René Girard, Le Bouc Emissaire, it occurred to me that I could develop a useful conceptual model for mimetic behaviour. In particular, I propose a simple and tractable mechanism for mimetic desire.

When we change our beliefs, we do so not because of their intrinsic value. Our desire to switch from belief \(A\) to belief \(B\) is proportional to the number of adherents of belief \(B\) that we know. Technically, I modelled the problem of two conflicting beliefs that propagate through a network with \(N\) nodes in a decentralised manner. These beliefs are in some sense competing for adherents.

Using vertex notation, two individuals \(v_i\) and \(v_j\) with identical beliefs are connected with probability \(q\), and \(1-q\) otherwise. \(v_i\) changes its belief with a probability proportional to the number of nodes connected to \(v_i\) that have opposing views.

Two key motivating questions are:

- Under what circumstances does a belief get completely wiped out?
- Under what circumstances does a belief completely dominate(i.e. wipe out) all other beliefs?

In the scenario where there are only two possible beliefs these two questions are equivalent and I show that on average it’s sufficient that \(q > 1-q\) and that initially, one belief has a greater number of adherents than the other.

## Representation of the problem:

### Virtual weights as a representation of potential connections:

Nodes carrying the first belief were assigned to the set of red vertices, \(R\), and nodes carrying the second belief were assigned to the set of blue vertices, \(B\). However, I wasn’t satisfied with this representation.

After some reflection, I chose \(+1\) and \(-1\) as labels. The reason being that a change of belief using this representation would be equivalent to multiplication by \(-1\). As a result, the \(N\) vertices could be represented by an N-dimensional vector:

\begin{equation} \vec{v} \in \{-1,1\}^N \end{equation}

where \(N= \lvert v_i \in R \rvert + \lvert v_j \in B \rvert\).

Using this representation, between each pair of vertices we may define a virtual weight matrix \(W\):

\begin{equation} w_{ij} = v_i \cdot v_j \end{equation}

where \(w_{ij}=+1\) implies identical beliefs and we have \(w_{ij}=-1\) otherwise.

Now, we note that \(W\) may be conveniently decomposed as follows:

\begin{equation} W= W^+ + W^- \end{equation}

where \(W^-\) denotes potential connections between nodes of different color and \(W^+\) denotes potential connections between nodes of identical colors.

### Modelling the adjacency matrix as a combination of random matrices:

In order to simulate variations in connectivity we may assume that nodes of the same color are connected with probability:

\begin{equation} \frac{1}{2} < q < 1 \end{equation}

and nodes of different color are connected with probability \(1-q\).

Given \(W\) we may therefore construct the adjacency matrix \(A\) by sampling random matrices:

\begin{equation} M_1, M_2 \sim \mathcal{U}([0,1])^{N \times N} \end{equation}

\begin{equation} M^+ = 1_{[0,q)} \circ M_1 \end{equation}

\begin{equation} M^- = 1_{(1-q,1]} \circ M_2 \end{equation}

where \(1_{[0,q)}\) denotes the characteristic function over the set \([0,q)\) and then we compute the Hadamard products:

\begin{equation} A^+ = M^+ \cdot W^+ \end{equation}

\begin{equation} A^- = M^- \cdot W^- \end{equation}

so the adjacency matrix is given by \(A = A^+ + A^-\).

Now, in order to simulate stochastic dynamics we simply use majority vote:

\begin{equation} p(v_i^{n+1}=v_i^n) = \frac{\bar{N_i}}{N_i} \end{equation}

\begin{equation} p(v_i^{n+1}=-1 \cdot v_i^n) = 1- \frac{\bar{N_i}}{N_i} \end{equation}

\begin{equation} \bar{N_i} = \lvert A(i,-) > 0 \rvert -1 \end{equation}

\begin{equation} N_i = \bar{N_i} + \lvert A(i,-) < 0 \rvert \end{equation}

where \(\lvert A(i,-) > 0 \rvert -1\) denotes the number of connections between \(v_i\) and nodes sharing the same belief without counting a connection to itself.

## Simulation:

Putting everything together with Julia we may create the following mimesis function which takes as input the number of nodes in the random graph \(n\), the number of iterates of the system \(N\), the fraction of nodes that are red \(p\), and the probability that nodes of the same color form connections \(q\).

```
function mimesis(n::Int64,N::Int64,p::Float64,q::Float64)
```
n: number of nodes in the random graph
N: number of iterations of the random graph coloring process
p: the fraction of nodes that are red
q: the probability that nodes of the same color form connections
```
## initialisation:
v = zeros(N,n)
color_ratio = zeros(N)
## generate positive terms:
v1 = (rand(n) .< p)*1.0
## generate negative terms:
v2 = ones(n) - v1 ## negative terms
v[1,:] = v1 - v2
color_ratio[1] = sum((v[1,:] .> 0)*1.0)/n
for i = 1:N-1
W = zeros(n,n)
for j =1:n
for k =1:n
## ignore self-connections
W[j,k] = v[i,j]*v[i,k]*(j != k)*1.0
end
end
if abs(sum(v[i,:])) < n
## split W into positive and negative parts...
Z1 = (W .< 0)*1.0 ## vertices with different colors
Z2 = W + Z1 ## vertices with the same color
## sample random zero-one matrices for new connections:
M1 = (rand(n,n) .< q)*1.0
M2 = (rand(n,n) .< 1-q)*1.0
## use Hadamard products to construct new adjacency matrices:
A1 = M1 .* Z2
A2 = M2 .* Z1
A = A1 - A2
## generate probabilities for color transformations:
M_hat = [sum(A[i,:] .> 0) for i = 1:n]
M = M_hat + [sum(A[i,:] .< 0) for i = 1:n]
P = [M_hat[i]/(M[i]+1.0) for i =1:n]
## zero-one vectors based on P:
p_q = (rand(n) .< P)*1.0
Q1 = p_q .* v[i,:]
Q2 = -1.0*(ones(n) .- p_q) .* v[i,:]
v[i+1,:] = Q1 + Q2
color_ratio[i+1] = sum((v[i+1,:] .> 0)*1.0)/n
else
v[i+1,:] = v[i,1]*ones(n)
color_ratio[i+1] = v[i+1,1]
end
end
return color_ratio
end
```

The above function may be called as follows for example:

```
c_ratio = mimesis(10, 100, 0.1,0.6);
```

## Analysis:

### The expected number of neighbors:

If we denote the number of red vertices at instant \(n\) by \(\alpha_n\) and the number of blue vertices by \(\beta_n\) we may observe that the expected number of neighbors is given by:

\begin{equation} \langle N(v_i \in R) \rangle = q \cdot (\alpha_n -1) + (1-q) \cdot \beta_n \end{equation}

\begin{equation} \langle N(v_i \in B) \rangle = q \cdot (\beta_n -1) + (1-q) \cdot \alpha_n \end{equation}

Using the above equations we may define:

\begin{equation} \langle \alpha_{n+1} \rangle = \alpha_n \left( \frac{q \cdot (\alpha_n -1)}{q \cdot (\alpha_n -1) + (1-q) \cdot \beta_n} \right) + \beta_n \left(\frac{(1-q) \cdot \alpha_n}{q \cdot (\beta_n -1) + (1-q) \cdot \alpha_n} \right) \end{equation}

and we may deduce that \(\langle \beta_{n+1} \rangle = N - \langle \alpha_{n+1} \rangle\). It must be noted that this is an approximation that works particularly well when \(0< q < 0.2\) or when \(0.8 \leq q < 1.0\).

### \(\alpha_n > \beta_n\) implies that \(\lim\limits_{n \to \infty} \langle \alpha_n \rangle = N\):

Assuming that \(q > 1-q\), a simple calculation shows that:

\begin{equation} \langle \alpha_{n+1} \rangle - \alpha_n \geq 0 \iff \alpha_n \geq \beta_n \end{equation}

and since:

\begin{equation} \langle \alpha_{n+1} \rangle - \alpha_n= 0 \iff \alpha_n = \beta_n \end{equation}

we may deduce that:

\begin{equation} \lim\limits_{n \to \infty} \langle \alpha_{n} \rangle = N \end{equation}

### Analysis of \(\Delta \alpha\):

Using the fact that \(\beta_n = N - \alpha_n\) we may derive the following continuous-space variant of \(\Delta \alpha_n = \langle \alpha_{n+1} \rangle - \alpha_n\):

\begin{equation} \Delta \alpha(\alpha,\gamma) = \frac{\alpha \cdot (N-\alpha)}{\gamma \cdot (\alpha -1) + (N-\alpha)} - \frac{\alpha \cdot (N-\alpha)}{\gamma \cdot (N - \alpha -1) + \alpha} \end{equation}

where \(\gamma = \frac{q}{1-q}\).

Assuming that \(N\) is a constant(ex. \(N=100\)) I obtained the following graph for various values of \(q\):

It’s interesting to note that the curve doesn’t exactly behave in a symmetric manner, which is a little bit surprising. Specifically, the behavior of \(\Delta \alpha\) when \(q=0.2\) doesn’t resemble the behavior of \(\Delta \alpha\) when \(q=0.8\).

## References:

- Réka Albert & Albert-László Barabási. Statistical mechanics of complex networks. 2002.
- René Girard. Le Bouc émissaire. 1986.
- P. Erdös and A. Rényi. On the evolution of random graphs. 1960.
- G. Grimmett and C. McDiarmid. On colouring random graphs. 1975.