Network formation

Last updated August 12, 2023

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.^[1] 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.^[2]

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.^[3] With this general framework, modelers can reproduce almost every stylized trait of real-life networks.

Related Research Articles

A complex system is a system composed of many components which may interact with each other. Examples of complex systems are Earth's global climate, organisms, the human brain, infrastructure such as power grid, transportation or communication systems, complex software and electronic systems, social and economic organizations, an ecosystem, a living cell, and ultimately the entire universe.

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

<span class="mw-page-title-main">Small-world network</span> Graph where most nodes are reachable in a small number of steps

A small-world network is a 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. Due to this, most neighboring nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes grows proportionally to the logarithm of the number of nodes N in the network, that is:

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

Dynamic network analysis (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA), social simulation and multi-agent systems (MAS) within network science and network theory. Dynamic networks are a function of time to a set of graphs; for each time point there is a graph. This is akin to the definition of dynamical systems, in which the function is from time to an ambient space, where instead of ambient space time is translated to relationships between pairs of vertices.

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert.

The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used $to formulate it in his popular science book Six Degrees .$

In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

Social network analysis (SNA) software is software which facilitates quantitative or qualitative analysis of social networks, by describing features of a network either through numerical or visual representation.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.

In social network analysis, the co-stardom network represents the collaboration graph of film actors i.e. movie stars. The co-stardom network can be represented by an undirected graph of nodes and links. Nodes correspond to the movie star actors and two nodes are linked if they co-starred (performed) in the same movie. The links are un-directed, and can be weighted or not depending on the goals of study. If the number of times two actors appeared in a movie is needed, links are assigned weights. The co-stardom network can also be represented by a bipartite graph where nodes are of two types: actors and movies. And edges connect different types of nodes if they have a relationship. Initially the network was found to have a small-world property. Afterwards, it was discovered that it exhibits a scale-free (power-law) behavior.

Networks are crucial parts of any action taken in a marketplace. Peter Drucker even described the future economy as one of a society of networks. Companies embedded in such networks stand to gain a lot. There are a number of different network models, which have distinct relevance to customers, and marketing initiatives. A network in marketing can be formed either strategically or completely randomly. Marketing channels and business networks have been referred to, by Achrol & Kotler as:

“Interdependent systems of organizations and relations that are involved in carrying out all of the production and marketing activities involved in creating and delivering value in the form of products and services to intermediate and final customers.”

Hierarchical network models are iterative algorithms for creating networks which are able to reproduce the unique properties of the scale-free topology and the high clustering of the nodes at the same time. These characteristics are widely observed in nature, from biology to language to some social networks.

<span class="mw-page-title-main">Bianconi–Barabási model</span>

The Bianconi–Barabási model is a model in network science that explains the growth of complex evolving networks. This model can explain that nodes with different characteristics acquire links at different rates. It predicts that a node's growth depends on its fitness and can calculate the degree distribution. The Bianconi–Barabási model is named after its inventors Ginestra Bianconi and Albert-László Barabási. This model is a variant of the Barabási–Albert model. The model can be mapped to a Bose gas and this mapping can predict a topological phase transition between a "rich-get-richer" phase and a "winner-takes-all" phase.

Network homophily refers to the theory in network science which states that, based on node attributes, similar nodes may be more likely to attach to each other than dissimilar ones. The hypothesis is linked to the model of preferential attachment and it draws from the phenomenon of homophily in social sciences and much of the scientific analysis of the creation of social ties based on similarity comes from network science. In fact, empirical research seems to indicate the frequent occurrence of homophily in real networks. Homophily in social relations may lead to a commensurate distance in networks leading to the creation of clusters that have been observed in social networking services. Homophily is a key topic in network science as it can determine the speed of the diffusion of information and ideas.

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as the brain or the Internet.

Evolution of a random network is a dynamical process, usually leading to emergence of giant component accompanied with striking consequences on the network topology. To quantify this process, there is a need of inspection on how the size of the largest connected cluster within the network, $, varies with the average degree . Networks change their topology as they evolve, undergoing phase transitions. Phase transitions are generally known from physics, where it occurs as matter changes state according to its thermal energy level, or when ferromagnetic properties emerge in some materials as they are cooling down. Such phase transitions take place in matter because it is a network of particles, and as such, rules of network phase transition directly apply to it. Phase transitions in networks happen as links are added to a network, meaning that having N nodes, in each time increment, a link is placed between a randomly chosen pair of them. The transformation from a set of disconnected nodes to a fully connected network is called the evolution of a network.$

References

↑ Jackson and Wolinsky (1996). "A Strategic Model of Social and Economic Networks" (PDF). Journal of Economic Theory. 71: 44–74. doi:10.1006/jeth.1996.0108. hdl: 10419/221454 .
↑ Jackson and Watts (2002). "The Evolution of Social and Economic Networks" (PDF). Journal of Economic Theory. 106 (2): 265–295. doi:10.1006/jeth.2001.2903. Archived from the original (PDF) on 2012-07-11.
↑ Jackson and Rogers (2007). "Meeting Strangers and Friends of Friends: How Random are Social Networks" (PDF). American Economic Review. 97 (3): 890–915. doi:10.1257/aer.97.3.890.