Controlling the dynamics of a network is an interesting task in many fields, especially social networks (where links represent some kind of interaction between two humans). For instance, influencing the transmission of opinions may lead to maximising the efficiency of a marketing campaign, restricting interactions between humans may avoid an epidemic outbreak, etc. An important factor in network controllability is the structure of such network that is determined by how nodes and links are added and deleted over time. If the controllability of a network is determined by how the network grew, controlling its growth can lead to a more controllable network.
Mathematical modelling can be used to approximate many scenarios, some more “interesting” than others. Using zombies to talk about the statistics of an infectious disease spread is sure to catch the reader’s attention. This is exactly what the paper You Can Run, You Can Hide: The Epidemiology and Statistical Mechanics of Zombies by Alexander A. Alemi et al. does. The authors state that Zombies are a fun framework to study concepts of modern epidemiology: “Zombism is just that – a (fictional) disease – and so should be amenable to the same kind of analysis and study that we use to combat more traditional diseases.”
The results of a full scale simulation of a zombie pandemic in the United States are in the paper as well as a discussion about the geography-dependent survival rates. For example, the disease is supposed to spread faster in the coasts due to the higher population density while the more remote areas in the centre of the country remained zombie free (even after four months). To model the simulation the following conditions are taken into account:
- In this simulation, zombies move but humans do not because the authors assume that in the chaos of the first days of the infection, the transportation networks shut down.
- How fast zombies bite humans and how effectively humans kill zombies is chosen based on the work of Witkowski and Blais, which, in turn, is based on the films Night of the Living Dead (1968) and Shawn of the Dead (2004).
This week I read about Game Theory in Morton D. Davis’ book Game Theory: A Nontechnical Introduction. I stumbled upon this book in the City Library while I was looking for a novel to read during the holidays.
What I found really interesting about Game Theory is the relationship between comprehensible strategy games and complex real-life dynamics: it has many applications in several fields including Economics, Political Science, Biology… not to mention Artificial Intelligence.
There are many cool examples in the book and no prior knowledge is really necessary to be able to (at least) grasp the basic concepts. In fact, many decisions in everyday life are taken using intuitive theoretical game models (also know as common sense).
This week I read two papers: Parallel Splash Belief Propagation by J. Gonzalez et al. and Understanding Belief Propagation and its Generalizations by J. S. Yedidia et al. The second was written eight years before the first one and I found that it is a very good introduction to the topic and a very well written paper (I appreciate a lot when a paper is easy to read).
Before starting with Belief Propagation, we need to understand the concept of inference and review graphical models (Bayesian Networks, Pairwise Markov Random Fields, Factor Graphs, etc.). I would recommend taking a look at Chapter 8 of Christopher M. Bishop’s book “Pattern Recognition and Machine Learning” (which can be downloaded for free from his website).
Back to the first paper, I highlight two basic concepts:
- The Belief Propagation (BP) algorithm is a way to approximately solve inference problems -whose goal is to calculate probability distributions- based on statistical models represented using graphs. Many scientific domains have separately addressed different real-world problems that can be solved using inference algorithms such as BP.
- Parallelisation is a programming technique consisting in performing more than one operation at the same time using the hardware resources available. As in everyday life, if independent tasks (operations) are divided among different people (processing units), the overall work is finished much quicker. Problems arise when tasks are not completely independent; some process may need to wait for another to finish or two operations may try modify the same object (data in memory) simultaneously. To deal with this, lots of scheduling algorithms exist.
As many other computationally heavy tasks, Belief Propagation can use parallelisation. This is useful to improve the overall performance of a machine learning system that uses an inference procedure. Parallel Splash Belief Propagation is an algorithm for approximate inference using high performance shared (multi-core) and distributed (cluster) memory systems. The proposed algorithm generalises the forward-backward scheduling to arbitrary cyclic graphical models and outperforms other techniques (in terms in running time before convergence and in total number of message computations).