Simulation and Analysis

Network structure is intimately related to the processes that occur in networked systems. Different processes create different structures, and different structures influence networked processes. Simulations can be used to generate synthetic networks. These networks can be used to study how structure forms in real systems. Real or synthetic networks can also be used to simulate processes that occur on those networks, to understand the influence of structure on those processes. This chapter introduces several common synthetic network models, as well as an example of simulating networked processes using agent-based modeling.

In this chapter, we will cover the following topics:

• Watts-Strogatz networks: Simulating small worlds by adding random shortcuts to locally-clustered networks
• Preferential attachment: How the rich getting richer creates scale-free heavy...

Watts-Strogatz and small worlds

The small-world problem (discussed in Chapter 8, Social Networks and Going Viral) asks how it is possible for distant people to be connected by short paths, even when everyone's connections are local (Travers & Milgram, 1967). Duncan Watts and Steven Strogatz (1998) developed a class of networks to explain this behavior. The networks begin as k-rings: nodes placed around a circle, with each node connected to its nearest k neighbors. Then, with probability p, each node's edges are moved to a randomly selected other node. These rewirings create shortcuts across the network. Even a small number of shortcuts greatly reduces the distances between nodes in the network, resolving the small-world problem.

The following code uses the NetworkX function watts_strogatz_graph() to generate Watts-Strogatz small-world networks with p=0, p=0.1, and...

Preferential attachment and heavy-tailed networks

From the internet to airport trips, many networks are characterized by a few nodes with many connections, and many nodes with very few connections. These networks are called heavy-tailed because, when a histogram of the node degrees is drawn, the high-connectivity nodes form a tail.

There are many ways to generate heavy-tailed networks, but one of the most widely-used is the Barabási-Albert preferential attachment model (Albert & Barabási, 1999). The preferential attachment model mimics processes where the rich get richer. Every time a node is added, it is randomly connected to existing nodes, with high-degree nodes being more likely.

In NetworkX, the barabasi_albert_graph() function generates preferential attachment networks. The following code shows an example of such a network with 35 nodes:

G_preferential_35 ...

Configuration models

When you need a synthetic network to resemble an existing network, configuration models might be the way to go. Given an input network, they produce a new network with the same number of nodes, each with the same degree. The edges of the new network are created randomly, in a way that preserves node degree.

Configuration models and other methods for constructing synthetic networks based on real data can be used to protect privacy. For example, online social networks can release configuration models based on their true member network to allow researchers to study the properties of those networks without having access to members' private data.

As an example, we can use a configuration model to create a synthetic network based on the karate club network. The following code shows exactly how to do this, using the configuration_model() function in the degree_seq...

Agent-based models

Beyond just looking at how network structure is created, simulations can be used to explore the processes that take place on top of an existing network. Such simulations can be used to anticipate the effects of changing network structure on a complex system, or to predict problems, such as traffic jams and power outages.

This section introduces one type of simulation: agent-based modeling. Agent-based modeling is a common technique in complex systems that simulates multiple objects called agents. Each agent is described by its state. Depending on the application, a state might be a single number, or a complex data structure. As the simulation proceeds, each agent interacts with other agents, and their states are updated based on those interactions. Sometimes, all agents are allowed to interact with all other agents. But this is a book about networks, and in...

Summary

This chapter has shown us how simulations can be used to better understand both the processes that create network structure and the processes that are influenced by network structure. The Watts-Strogatz model creates small-world networks by adding random shortcuts to a highly-clustered ring network. Preferential attachment creates heavy-tailed, scale-free networks, where a few nodes have most of the connections. Configuration models are used to construct synthetic networks with properties similar to real networks. Finally, this chapter showed how agent-based modeling can be used to simulate a social learning process occurring on an existing network structure. In the next chapter, you'll learn about working with data that represents objects in space or time.

References

The following is a list of resources that you can consider to get further knowledge:

• Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439).
• DeGroot, M. H. (1974). Reaching a consensus. Journal of the American Statistical Association, 69(345).
• Golub, B., & Jackson, M. O. (2010). Naive learning in social networks and the wisdom of crowds. American Economic Journal: Microeconomics, 2(1).
• Travers, J., & Milgram, S. (1967). The small world problem. Psychology Today, 1(1).
• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684).