# Spatial structure

March 21, 2012 16 Comments

In evolutionary game theory, the spatial structure of a game can be as important in determining the evolutionary success of a given strategy as is the strategy itself [1]. This is intuitive if we consider that strategies do not work in a vacuum: An agent’s payoff is a function of both its strategy *and* the context in which that strategy was executed. In light of this, a brief discussion concerning the role of spatial structure in simulations is warranted. Additionally, several common network types (random graphs, small-world and scale-free networks), as well as network properties (degree, clustering and path length) are considered. Readers are also encouraged to consult Albert and Barabási’s review, as it forms the basis for the latter summary [2].

To understand what is meant by spatial structure, something should first be said about what it means to lack one. It is interesting to note that the earliest applications of evolutionary game theory often favored a non-spatial approach [3], and that many continue to do so to this day. In such settings, populations are treated as inviscid (free-mixing), meaning that any agent can potentially pair with any other agent in an interaction; agents are, in other words, inherently *unconstrained *in their pairings. This extends to reproduction as well: Because new agents are not “placed” anywhere in particular (e.g., next to their parents), reproducing successfully has a more quantitative rather than qualitative effect on the population (e.g., there are more agents of your type, but you are not helping to generate a homogeneous neighborhood).

Reasons for preferring a non-spatial approach may be numerous, but one of the most apparent is the relative simplicity of analysis. Often, only the strategy proportions and the payoff matrix, which describes how fitness changes when these strategies interact, need be considered in order to predict population trends [4]. Nevertheless, spatial structure remains interesting both due to its potentially strong effect, as well as for theoretical reasons. Psychological research, for instance, has shown evidence for adaptive biases that lead to the formation of particular social networks, and it is often argued that such biases are a product of evolution [5]. Therefore, if we wish to use evolutionary game theory to reason about behavior, understanding spatial structure may, in certain cases, be a necessary first step.

At its simplest, spatial structure is a set of constraints on how agents interact. These constraints are typically described in terms of a graph, where agents form the vertices (i.e., nodes) of the graph, and potential interactions are represented by the edges connecting them. The lack of an edge indicates that the given agents cannot pair up for an interaction, and thus a simulation which does not impose a spatial structure may be described as a complete (i.e., fully-connected) graph. When spatial position matters, reproduction is also affected: The researcher must decide *where* an offspring is placed (e.g., next to the parent, far from the parent, at random?) – and even this decision may have a significant effect. Typically, the same spatial structure is applied to both interactions and reproduction.

To describe how graphs vary, several key terms must be defined. The first of these is *degree*, represented by *k*. The degree of a vertex is the number of connections it forms, and as such represents an agent’s connectivity. The higher the degree, the more potential partners the agent has for interaction, and the more spaces it has to potentially place an offspring. In most cases, it is not the degree of a given vertex, but the average degree or the degree distribution of the whole graph that is of interest. Next, *clustering*, as captured by a clustering coefficient,* *reflects the extent to which local, highly interconnected groups form. Another way to characterize this is as a measure of agent “cliquishness”. Finally, *path length* is the number of edges that must be traversed to move from one particular vertex to another. A low average path length suggests that long distance connections are common, whereas a high average path length implies that connections tend to be strongly localized.

Unfortunately, real-world networks often have sophisticated topologies that lack clear design principles. As a result, it is commonly thought that the simplest way to represent such networks is to treat them as *random graphs*. The most straightforward approach is described by the Erdõs-Rényi model: Here, we start with an empty graph, then consider every pair of points, connecting each with some probability *p*. The result is a graph of *n* vertices, degree *k* and approximately *pn(n – 1)/2* randomly distributed edges. Though the underlying principle is simple, in practice, such graphs are more complicated than they first appear. For instance, there are threshold phenomena whereby, as *p* varies, various properties (e.g., every pair of vertices being connected at least indirectly) emerge very suddenly, yet with remarkable consistency. Variations on this approach are abundant and frequently used [2].

Though the random graph paradigm remains common, others have emerged as well, such as a cross between random graphs and highly clustered regular lattices: the *small-world network*. These networks are defined by a low average path length between any pair of vertices, a concept that was famously captured by Stanley Milgram’s “six degrees of separation” experiment, where he argued that, on average, any two individuals in the United States are only separated by approximately six social relationships. The implications of this property are that, while local, highly connected groupings are possible, long distance connections make it easy to move anywhere on the graph. This is worth noting, since virtually all real-world networks have a higher clustering coefficient than random graphs do, yet small-world properties abound; examples include various social networks and the Internet. Nevertheless, these properties in and of themselves are not sufficient to specify any particular organizational structure, and, in fact, even random graphs may be regarded as a type of small-world network [2].

The third and final paradigm is the *scale-free network*. Whereas the degree distribution of a random network is a Poisson distribution, scale-free networks are defined by the fact that their degree distribution has a power-law tail. In other words, vertices with very high numbers of edges are uncommon, and such vertices tend to form “hubs” around which less-connected vertices then gather. Unsurprisingly, scale-free networks have small-world properties, since traversing from any vertex to another is often as simple as connecting to the nearest hub and then using this to access a hub near the target vertex. Like small-world networks, scale-free networks are also quite prevalent across a variety of contexts, ranging from the Internet to metabolic networks [2].

One spatial structure that has proven particularly useful from the point of view of evolutionary game theory is a variation on the random graph: the *random k-regular graph*. Although random, in that the vertices are randomly connected, these are also regular, in that each vertex has the same degree *k*. This offers several advantages: First, the random nature of the graph means that no deliberate assumptions about properties such as clustering or average path length are made, which makes them easier to justify at a theoretical level (e.g., if we don’t know what a particular network should look like, this is a *relatively* neutral place to start). Second, the graph’s regularity means that agents always have an equal number of neighbors, and thus an equal number of interactions and consistent structural constraints on reproductive potential. This precludes scenarios where a more highly connected agent receives higher or lower fitness payoffs, or reproduces more or less, simply as a result of its level of connectivity, rather than the effectiveness of its strategy. One final advantage is that Ohtsuki and Nowak have proposed a means by which more traditional ways of reasoning about non-spatial models may be applied to random *k*-regular graphs [6]. This has the potential to make games on such graphs more mathematically tractable than other models.

Creating a random *k*-regular graph is theoretically quite straightforward: We simply consider the entire possible set of graphs with *n* vertices and *k* degree, and then pick a graph at random. The question of how this is done in practice is more difficult however, since computational constraints almost always necessitate the use of a faster algorithm. The practical considerations of generating such graphs will be discussed in a future entry.

**References**

- Killingback, T., & Doebeli, M. (1996). Spatial Evolutionary Game Theory: Hawks and Doves Revisited.
*Proceedings of the Royal Society of London. Series B: Biological Sciences*,*263*(1374), 1135–1144. - Reka Albert, & Albert-Laszlo Barabasi (2002). Statistical mechanics of complex networks Reviews of Modern Physics, 74 (1), 47-97 arXiv: cond-mat/0106096v1
- Smith, J. M. (1982).
*Evolution and the theory of games*. Cambridge University Press. - Nowak, M. A. (2006).
*Evolutionary dynamics: exploring the equations of life*. Harvard University Press. - Henrich, J., & Broesch, J. (2011). On the nature of cultural transmission networks: evidence from Fijian villages for adaptive learning biases.
*Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences*,*366*(1567), 1139–1148. - Ohtsuki, H., & Nowak, M. A. (2006). The replicator equation on graphs.
*Journal of Theoretical Biology*,*243*(1), 86–97.

Pingback: Generating random k-regular graphs « Theory, Evolution, and Games Group

If small world and scale free are the empirical characteristics of the network we usually observe, then why random k graph should be of particular interest. Is it because it’s easier to implement. And under what condition would the random k graph have the desired small world and scale free feature?

As Marcel points out, random k-regular graphs are one of the simplest approaches (the first thing to try after an inviscid population), thus they are used for simplicity. In particular, locally a regular random graph looks like a Cayley tree, thus pairwise approximation works well as an analytic technique. This is especially useful in evolutionary game theory where it was formalized as the Ohtsuki-Nowak transform (I will have a blog post up about that soon; I hope), which makes it really easy to handle games analytically on these sort of graphs.

Obviously a k-regular graph NEVER has the scale-free property. A graph is scale-free if its degree distribution is a power law. In a k-regular graph, every vertex has the same degree k; thus its degree distribution is a delta function at k; obviously not power law. If you relax the graph slightly, from a random k-regular graph to an Erdős–Rényi random graph with edge density k/n (every edge in a n-vertex graph has independent probability k/n of existing) then your degree distribution will be a Binomial distribution B(n,k/n). This is also obviously not a power-law since it is highly peaked around the mean of k.

For all effective purposes, the Erdős–Rényi model behaves like the random k-regular graphs. Unfortunately, when worrying about games, it becomes a hastle to consider agents with different numbers of neighbours (a key-question: should you renormalize their payoff by number of neighbours or not?). So when you are using an empirically unrealistic degree distribution (either the delta at k or sharp Binomial around k) then it is easier to just assume the delta, since you have less choices to make.

As for small-world-ness, this is a different issue, and it depends if you are mathematician or not. To mathematicians, small-world means something general: a family of graphs is small world if for an n vertex graph the diameter (or more often the use the weaker: average shortest path) is proportional to (log n). Of course, for a random graph there is some probability that we have disconnected components (giving you an infinite diameter but in a trivial way; although we are still fine in the average shortest path definition). What is usually done (and what is the case with high probability for a k-regular graph) is that the vertexes form one giant component, and we just throw away the vertexes that are not connected to this component. It is not hard to show, that the diameter of this component will scale like (log n); thus being small-world in the math sense.

However, when social scientists work on networks, they usually don’t understand asymptotic statements like “for an n vertex graph the diameter is proportional to (log n)” and for them small-world means a specific type of graphs proposed by Watts and Strogatz (1998). The Watts-Strogatz model has a very high clustering coefficient (which is common in certain empirical networks) and thus does not resemble Cayley trees at all on a local scale (since a tree by definition has 0 clustering). This makes the Watts-Strogatz model very different from Erdős–Rényi or k-regular random graphs. It also makes the network much harder to work with analytically since pairwise approximation is only perfect on Cayley trees or things that resemble them locally.

Thanks for the clarification. I realized that random k graph would never have the small world feature when reading one of the reference.And random graph only looks like Cayley tree locally. They are still connected, most of the time. I am not familiar with the pairwise approximation technique and the Ohtsuki-Nowak transform. Looking forward to your post. And thanks a lot to Marcel this posts and the one explaining how to generate random k graph

Pingback: Slides for Szabo & Fath’s Evolutionary Games on Graphs « Theory, Evolution, and Games Group

Pingback: Slides for Roca, Cuesta & Sanchez’s EGT: Temporal and spatial effects beyond replicator dynamics « Theory, Evolution, and Games Group

Pingback: Ohtsuki-Nowak transform for replicator dynamics on random graphs « Theory, Evolution, and Games Group

Pingback: Asking Amanda Palmer about cooperation in the public goods game | Theory, Evolution, and Games Group

Pingback: Finance and ecology | Theory, Evolution, and Games Group

Pingback: Evolutionary games in set structured populations | Theory, Evolution, and Games Group

Pingback: Game theoretic analysis of motility in cancer metastasis | Theory, Evolution, and Games Group

Pingback: Warburg effect and evolutionary dynamics of metastasis | Theory, Evolution, and Games Group

Pingback: Black swans and Orr-Gillespie theory of evolutionary adaptation | Theory, Evolution, and Games Group

Pingback: Cooperation through useful delusions: quasi-magical thinking and subjective utility | Theory, Evolution, and Games Group

Pingback: Simplifying models of stem-cell dynamics in chronic myeloid leukemia | Theory, Evolution, and Games Group

Pingback: Approximating spatial structure with the Ohtsuki-Nowak transform | Theory, Evolution, and Games Group