Part IV. Games on networks
IV-3. Implementing network metrics
1. Goal
Our goal in this chapter is to include some network metrics in our model. These metrics will give us information about the structure of the generated network. In particular, we will compute:
- The network density, which is the number of links present in the network divided by the total number of links that could exist.
- The size of the largest component. A component is a maximal set of connected nodes, i.e. a maximal group of nodes such that there is a path from each node to every other node.
- The average local clustering coefficient. The local clustering coefficient of a node is the number of existing links between its neighbors divided by the total number of links that could possibly exist between them.[1] In a social network of friendships, this metric would measure the extent to which your friends are friends among themselves.
- The degree distribution, which shows the number of nodes that have degree k (with k = 0, 1, 2, 3…). As an example, figure 1 below shows the degree distribution of various networks with 100 nodes.[2]
Note that the degree of a node is the number of nodes that are at (geodesic) distance 1; in our model we will also compute the number of nodes that are within distances greater than 1.
2. Motivation. Reassessing the significance of network structure
Let us revisit the 2-player 2-strategy single-optimum coordination game of the previous chapter:
| Player 2 | |||
| Player 2 chooses A | Player 2 chooses B | ||
| Player 1 | Player 1 chooses A | 1 , 1 | 0 , 0 |
| Player 1 chooses B | 0 , 0 | 2 , 2 |
In the previous chapter we saw that, in this game, under certain conditions,[3] a population of 100 agents embedded on a network with average degree about 2, will most likely approach the state where all agents choose strategy B and spend most of the time close to it, regardless of the network structure. The star network was an exception, but the result seems to hold for most network structures. Network structure did not seem to play a significant role in networks with very high density either; in those networks, given our conditions, agents tend to approach the inefficient state and spend most of the time around there.
However, for moderately low densities (e.g. average degree about 10), network structure clearly plays a role, as you can see in the figures below. Figures 2 and 3 show two networks with average degree about 10, but completely different structure. Figure 2 shows a random network generated with the Erdős–Rényi model, and figure 3 shows a ring lattice. In the random network, most simulation runs approach the inefficient state and stay around it, while in the ring lattice, most simulations approach and stay around the efficient state.
For those cases where the average degree is certainly not enough to predict whether the population will approach the efficient state or not, we would like to explore whether there is any other property of the network th