In this episode a famous paint is stolen and the FBI team is involved in the case. The case complicates quickly, as they discover that the Nazis looted the house of the original paint's owner. Charlie uses mathematical models and discovers that the paint stolen was a fake. To complicate matters, there is a murder plot involved.

Network diffusion is a very active field nowadays, partially because of the popularity of social networks on the internet such as Facebook or MySpace. There are many questions that arise in this field: how do people make friends? How likely is that you will join a group or post a message if your friends have already done so. Mathematical models of several kinds are used to understand the behavior of these networks, such as the construction of random graphs with given constraints. Below we have a partial subgraph from Facebook, where people are vertices and are connected to other people if they are friends as defined by Facebook.

At some point, Charlie is trying to find out the possible places where the stolen paint can be sold. In order to do this, he uses a *network diffusion probability model*. Let us focus on the details of these models. First of all, the network is represented by a directed, weighted graph, where the weights represent the probability of diffusion. For instance, consider the graph below

Notice that from point there are two places to move from point A; that is, F and E. An object located at A moves to F with a probability of 0.1, whereas the same object moves to F with probability 0.9. Notice that the sum of all the weights of edges going *out* of any point is 1.

One can encode the a weighted graph in an *adjacency matrix*, which consists of a rectangular array, where entry (i, j) is the weight of the edge from i to j. For instance, the above graph is encoded as follows

- Let M be the above matrix, and N=[1 0 0 0 0 0] be the matrix representing point A. What does NxM represent? What about NxM
^{2}?, NxM^{k}for a positive integer k? - Use a calculator or a computer and find the value of NxM
^{k}for several k up to 4 digits. Do you notice anything unusual? - In the previous problem, at some point the product NxM
^{k}= NxM^{k+1}. In this case, we say that the product*stabilizes* - Consider the following statement: "For any matrix M, there exists a positive k so that the product NxM
^{k}stabilizes". Is this statement true? If so try to argue why. Otherwise provide a counterexample.

There are many applications where one is interested in network diffusion; for instance, the spread of diseases, evolution of species, spread of rumors, population dynamics, etc. We present a very simple model of the population dynamics, called the *Moran process*. The process is the following: A population is represented in a weighted graph, at each step one chooses a vertex v to reproduce, and pick one of its neighbors u to replace it with a copy of v. The picture below is represents this model: We pick the red vertex to reproduce, a neighbor to be replaced (the one connected with the red edge) and replace the blue vertex with a copy of the red one. In the picture below we have not included the weights, for simplicity. The model also puts weight on the vertices, representing the *fitness* of red or blue vertices

- We say that a moran process reaches
*fixation*if there is a step in the process where all the vertices are either red or blue (since at this point, any step will not change the color of any vertex). Give an example of a process that starts with all blue vertices, then a red vertex is introduces, and at some point all the vertices will become red. Give another example where the red vertices will eventually disappear. - For a graph G with all its vertices blue, define M
_{G}to be the minimal number of red vertices that need to be introduced (that is, the minimum number of blue vertices that need to be turned red) in order to guarantee a red fixation. Give examples of two graphs on n vertices (for any n) such that M_{G}= 1, and M_{G}= n - 1. Notice that M_{G}does not depend on the weights of the edges. - Let us look at the Moran process of the graph G be the directed 4-cycle A --> B --> C --> D --> A (where A, B, C, D are the vertices). Suppose that there are 3 blue vertices and one red vertex, and that the fitness of the red vertex is 10, while the fitness of the blue vertices is 1. If we select vertices with probability proportional to their fitness, what is the probability of choosing a red vertex for reproduction at the first step of the process? What about the probability of selecting a blue vertex?
- With the sam considerations as above, consider the Moran process at its fifth step. What is the probability of reaching red fixation at the fifths step? What about blue fixation?