Network formation is an aspect of network science that seeks to model how a network evolves by identifying which factors affect its

structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...

and how these mechanisms operate. Network formation

hypotheses A hypothesis (plural hypotheses) is a proposed explanation for a phenomenon. For a hypothesis to be a scientific hypothesis, the scientific method requires that one can test it. Scientists generally base scientific hypotheses on previous obser ...

are tested by using either a dynamic model with an increasing network size or by making an

agent-based model An agent-based model (ABM) is a computational model for simulating the actions and interactions of autonomous agents (both individual or collective entities such as organizations or groups) in order to understand the behavior of a system and wha ...

to determine which network structure is the equilibrium in a fixed-size network.

Dynamic models

A dynamic model, often used by

physicist A physicist is a scientist who specializes in the field of physics, which encompasses the interactions of matter and energy at all length and time scales in the physical universe. Physicists generally are interested in the root or ultimate caus ...

s and

biologist A biologist is a scientist who conducts research in biology. Biologists are interested in studying life on Earth, whether it is an individual Cell (biology), cell, a multicellular organism, or a Community (ecology), community of Biological inter ...

s, begins as a small network or even a single node. The modeler then uses a (usually randomized) rule on how newly arrived

nodes In general, a node is a localized swelling (a "knot") or a point of intersection (a Vertex (graph theory), vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two ...

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 A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a sm ...

property or the scale-free network property. These properties are common in almost every real network including the

World Wide Web The World Wide Web (WWW), commonly known as the Web, is an information system enabling documents and other web resources to be accessed over the Internet. Documents and downloadable media are made available to the network through web se ...

, 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 Watts is plural for ''watt'', the unit of power. Watts may also refer to: People *Watts (surname), list of people with the surname Watts Fictional characters *Watts, main character in the film '' Some Kind of Wonderful'' *Watts family, six chara ...

, 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 Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

-based modelling. In these models, a network with fixed number of nodes or agents is created. Every agent is given

utility function As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...

, 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.

Dynamic models

Agent-based models

Growing networks in agent-based setting

References

Further reading