Network formation

Network formation is an aspect of network science that seeks to model how a network evolves by identifying which factors affect its structure and how these mechanisms operate. Network formation hypotheses are tested by using either a dynamic model with an increasing network size or by making an agent-based model to determine which network structure is the equilibrium in a fixed-size network.

Dynamic models

A dynamic model, often used by physicists and biologists, begins as a small network or even a single node. The modeler then uses a (usually randomized) rule on how newly arrived nodes form links in order to increase the size of the network. The aim is to determine what the properties the network will be when it grows in size. In this way, researchers try to reproduce properties common in most real networks, such as the small world network property or the scale-free network property. These properties are common in almost every real network including the World Wide Web, the metabolic network or the network of international air routes.

The oldest model of this type is the Erdős-Rényi model, in which new nodes randomly choose other nodes to connect to. A second well-known model is the Watts and Strogatz model, which starts from a standard two-dimensional lattice and evolves by replacing links randomly. These models display some realistic network properties, but fail to account for others.

One of the most influential models of network formation is the Barabási-Albert model. Here, the network also starts from a small system, and incoming nodes choose their links randomly, but the randomization is not uniform. Instead, nodes which already possess a greater number of links will have a higher likelihood of becoming connected to incoming nodes. This mechanism is known as preferential attachment. In comparison to previous models, the Barabbas-Albert model seems to more accurately reflect phenomena observed in real-world networks.

Agent-based models

The second approach to model network formation is agent- or game theory-based modelling. In these models, a network with fixed number of nodes or agents is created. Every agent is given utility function, a representation of its linking preferences, and directed to form links with other nodes based upon it. Usually, forming or maintaining a link will have a cost, but having connections to other nodes will have benefits. The method tests the hypothesis that, given some initial setting and parameter values, a certain network structure will emerge as an equilibrium of this game. Since the number of nodes usually fixed, they can very rarely explain the properties of huge real-world networks; however, they are very useful to examine the network formation in smaller groups.

Jackson and Wolinsky pioneered these types of models in a 1996 paper, which has since inspired several game-theoretic models. These models were further developed by Jackson and Watts, who put this approach to a dynamic setting to see how the network structure evolve over time.

Usually, games with known network structure are widely applicable; however, there are various settings when players interact without fully knowing who their neighbors are and what the network structure is. These games can be modeled using incomplete information network games.

Growing networks in agent-based setting

There are very few models that try to combine the two approaches. However, in 2007, Jackson and Rogers modeled a growing network in which new nodes chose their connections partly based on random choices and partly based on maximizing their utility function. With this general framework, modelers can reproduce almost every stylized trait of real-life networks.

Further reading

• Barabási and Albert (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics 74 (1): 47–97. doi:10.1103/revmodphys.74.47. Bibcode: 2002RvMP...74...47A. Archived from the original on 2015-08-24. https://web.archive.org/web/20150824235818/http://www3.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf.