Evolving network

Last updated
Animation of an evolving network according to the initial Barabasi-Albert model Barabasi Albert model.gif
Animation of an evolving network according to the initial Barabasi–Albert model

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.

Contents

Network theory background

The study of networks traces its foundations to the development of graph theory, which was first analyzed by Leonhard Euler in 1736 when he wrote the famous Seven Bridges of Königsberg paper. Probabilistic network theory then developed with the help of eight famous papers studying random graphs written by Paul Erdős and Alfréd Rényi. The Erdős–Rényi model (ER) supposes that a graph is composed of N labeled nodes where each pair of nodes is connected by a preset probability p.

Watts-Strogatz graph Watts strogatz.svg
Watts–Strogatz graph

While the ER model's simplicity has helped it find many applications, it does not accurately describe many real world networks. The ER model fails to generate local clustering and triadic closures as often as they are found in real world networks. Therefore, the Watts and Strogatz model was proposed, whereby a network is constructed as a regular ring lattice, and then nodes are rewired according to some probability β. [1] This produces a locally clustered network and dramatically reduces the average path length, creating networks which represent the small world phenomenon observed in many real world networks. [2]

Despite this achievement, both the ER and the Watts and Storgatz models fail to account for the formulation of hubs as observed in many real world networks. The degree distribution in the ER model follows a Poisson distribution, while the Watts and Strogatz model produces graphs that are homogeneous in degree. Many networks are instead scale free, meaning that their degree distribution follows a power law of the form:

This exponent turns out to be approximately 3 for many real world networks, however, it is not a universal constant and depends continuously on the network's parameters [3]

First evolving network model – scale-free networks

The Barabási–Albert (BA) model was the first widely accepted model to produce scale-free networks. This was accomplished by incorporating preferential attachment and growth, where nodes are added to the network over time and are more likely to link to other nodes with high degree distributions. The BA model was first applied to degree distributions on the web, where both of these effects can be clearly seen. New web pages are added over time, and each new page is more likely to link to highly visible hubs like Google which have high degree distributions than to nodes with only a few links. Formally this preferential attachment is:

Additions to BA model

The BA model was the first model to derive the network topology from the way the network was constructed with nodes and links being added over time. However, the model makes only the simplest assumptions necessary for a scale-free network to emerge, namely that there is linear growth and linear preferential attachment. This minimal model does not capture variations in the shape of the degree distribution, variations in the degree exponent, or the size independent clustering coefficient. Therefore, the original model has since been modified[ by whom? ] to more fully capture the properties of evolving networks by introducing a few new properties.

Fitness

One concern with the BA model is that the degree distributions of each nodes experience strong positive feedback whereby the earliest nodes with high degree distributions continue to dominate the network indefinitely. However, this can be alleviated by introducing a fitness for each node, which modifies the probability of new links being created with that node or even of links to that node being removed. [4]

In order to preserve the preferential attachment from the BA model, this fitness is then multiplied by the preferential attachment based on degree distribution to give the true probability that a link is created which connects to node i.

Where is the fitness, which may also depend on time. A decay of fitness with respect to time may occur and can be formalized by

where increases with

Further complications arise because nodes may be removed from the network with some probability. Additionally, existing links may be destroyed and new links between existing nodes may be created. The probability of these actions occurring may depend on time and may also be related to the node's fitness. Probabilities can be assigned to these events by studying the characteristics of the network in question in order to grow a model network with identical properties. This growth would take place with one of the following actions occurring at each time step:

Prob p: add an internal link.

Prob q: delete a link.

Prob r: delete a node.

Prob 1-p-q-r: add a node.

Other ways of characterizing evolving networks

In addition to growing network models as described above, there may be times when other methods are more useful or convenient for characterizing certain properties of evolving networks.

Convergence towards equilibria

In networked systems where competitive decision making takes place, game theory is often used to model system dynamics, and convergence towards equilibria can be considered as a driver of topological evolution. For example, Kasthurirathna and Piraveenan [5] have shown that when individuals in a system display varying levels of rationality, improving the overall system rationality might be an evolutionary reason for the emergence of scale-free networks. They demonstrated this by applying evolutionary pressure on an initially random network which simulates a range of classic games, so that the network converges towards Nash equilibria while being allowed to re-wire. The networks become increasingly scale-free during this process.

Treat evolving networks as successive snapshots of a static network

The most common way to view evolving networks is by considering them as successive static networks. This could be conceptualized as the individual still images which compose a motion picture. Many simple parameters exist to describe a static network (number of nodes, edges, path length, connected components), or to describe specific nodes in the graph such as the number of links or the clustering coefficient. These properties can then individually be studied as a time series using signal processing notions. [6] For example, we can track the number of links established to a server per minute by looking at the successive snapshots of the network and counting these links in each snapshot.

Unfortunately, the analogy of snapshots to a motion picture also reveals the main difficulty with this approach: the time steps employed are very rarely suggested by the network and are instead arbitrary. Using extremely small time steps between each snapshot preserves resolution, but may actually obscure wider trends which only become visible over longer timescales. Conversely, using larger timescales loses the temporal order of events within each snapshot. Therefore, it may be difficult to find the appropriate timescale for dividing the evolution of a network into static snapshots.

Define dynamic properties

It may be important to look at properties which cannot be directly observed by treating evolving networks as a sequence of snapshots, such as the duration of contacts between nodes [7] Other similar properties can be defined and then it is possible to instead track these properties through the evolution of a network and visualize them directly.

Another issue with using successive snapshots is that only slight changes in network topology can have large effects on the outcome of algorithms designed to find communities. Therefore, it is necessary to use a non classical definition of communities which permits following the evolution of the community through a set of rules such as birth, death, merge, split, growth, and contraction. [8] [9]

Applications

Route map of the world's scheduled commercial airline traffic, 2009. This network evolves continuously as new routes are scheduled or cancelled. World-airline-routemap-2009.png
Route map of the world's scheduled commercial airline traffic, 2009. This network evolves continuously as new routes are scheduled or cancelled.

Almost all real world networks are evolving networks since they are constructed over time. By varying the respective probabilities described above, it is possible to use the expanded BA model to construct a network with nearly identical properties as many observed networks. [10] Moreover, the concept of scale free networks shows us that time evolution is a necessary part of understanding the network's properties, and that it is difficult to model an existing network as having been created instantaneously. Real evolving networks which are currently being studied include social networks, communications networks, the internet, the movie actor network, the World Wide Web, and transportation networks.

Further reading

Related Research Articles

<span class="mw-page-title-main">Scale-free network</span> Network whose degree distribution follows a power law

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">Complex network</span> Network with non-trivial topological features

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.

<span class="mw-page-title-main">Degree distribution</span>

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.

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

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.

<span class="mw-page-title-main">Watts–Strogatz model</span> Method of generating random small-world graphs

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 applied probability theory, the Simon model is a class of stochastic models that results in a power-law distribution function. It was proposed by Herbert A. Simon to account for the wide range of empirical distributions following a power-law. It models the dynamics of a system of elements with associated counters. In this model the dynamics of the system is based on constant growth via addition of new elements as well as incrementing the counters at a rate proportional to their current values.

In the study of scale-free networks, a copying mechanism is a process by which such a network can form and grow, by means of repeated steps in which nodes are duplicated with mutations from existing nodes. Several variations have been studied. In the general copying model, a growing network starts as a small initial graph and, at each time step, a new vertex is added with a given number k of new outgoing edges. As a result of a stochastic selection, the neighbors of the new vertex are either chosen randomly among the existing vertices, or one existing vertex is randomly selected and k of its neighbors are "copied" as heads of the new edges.

<span class="mw-page-title-main">Assortativity</span> Tendency for similar nodes to be connected

Assortativity, or assortative mixing is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree. The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

<span class="mw-page-title-main">Network science</span> Academic field

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

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.

<span class="mw-page-title-main">Hierarchical network model</span>

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.

Evolving networks are dynamic networks that change through time. In each period there are new nodes and edges that join the network while the old ones disappear. Such dynamic behaviour is characteristic for most real-world networks, regardless of their range - global or local. However, networks differ not only in their range but also in their topological structure. It is possible to distinguish:

<span class="mw-page-title-main">Deterministic scale-free network</span>

A scale-free network is a type of networks that is of particular interest of network science. It is characterized by its degree distribution following a power law. While the most widely known generative models for scale-free networks are stochastic, such as the Barabási–Albert model or the Fitness model can reproduce many properties of real-life networks by assuming preferential attachment and incremental growth, the understanding of deterministic scale-free networks leads to valuable, analytical results.

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

<span class="mw-page-title-main">Hub (network science)</span> Node with a number of links that greatly exceeds the average

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.

In a scale-free network the degree distribution follows a power law function. In some empirical examples this power-law fits the degree distribution well only in the high degree region, however for small degree nodes the empirical degree-distribution deviates from it. See for example the network of scientific citations. This deviation of the observed degree-distribution from the theoretical prediction at the low-degree region is often referred as low-degree saturation.

The initial attractiveness is a possible extension of the Barabási–Albert model. The Barabási–Albert model generates scale-free networks where the degree distribution can be described by a pure power law. However, the degree distribution of most real life networks cannot be described by a power law solely. The most common discrepancies regarding the degree distribution found in real networks are the high degree cut-off and the low degree cut-off. The inclusion of initial attractiveness in the Barabási–Albert model addresses the low-degree cut-off phenomenon.

<span class="mw-page-title-main">Mediation-driven attachment model</span>

In the scale-free network theory, a mediation-driven attachment (MDA) model appears to embody a preferential attachment rule tacitly rather than explicitly. According to MDA rule, a new node first picks a node from the existing network at random and connect itself not with that but with one of the neighbors also picked at random.

In the analysis of social networks, the uniform-preferential-attachment model, or UPA model is a variation of the Barabási–Albert model in which the preferential attachment is perceived as having a double nature. New nodes joining the network may either attach themselves with high-degree nodes or with most recently added nodes. This behaviour can be noticed in some examples of social networks, such as the citation network of scientific publications.

References

  1. Watts, D.J.; Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 409–10. Bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID   9623998. S2CID   4429113.
  2. Travers Jeffrey; Milgram Stanley (1969). "An Experimental Study of the Small World Problem". Sociometry. 32 (4): 425–443. doi:10.2307/2786545. JSTOR   2786545.
  3. R. Albert; A.-L. Barabási (2000). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters . 85 (24): 5234–5237. arXiv: cond-mat/0005085 . Bibcode:2000PhRvL..85.5234A. doi:10.1103/PhysRevLett.85.5234. hdl:2047/d20000695. PMID   11102229. S2CID   81784. Archived (PDF) from the original on 2010-12-24. Retrieved 2011-10-26.
  4. Albert R. and Barabási A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, 47 (2002)
  5. Kasthurirathna, Dharshana; Piraveenan, Mahendra. (2015). "Emergence of scale-free characteristics in socioecological systems with bounded rationality". Scientific Reports . In Press.
  6. Pierre Borgnat; Eric Fleury; et al. "Evolving Networks" (PDF). Archived (PDF) from the original on 2011-08-12. Retrieved 2011-10-26.{{cite journal}}: Cite journal requires |journal= (help)
  7. A. Chaintreau; P. Hui; J. Crowcroft; C. Diot; R. Gass; J. Scott (2006). "Impact of human mobility on the design of opportunistic forwarding algorithms" (PDF). Infocom.
  8. G. Palla; A. Barabasi; T. Vicsek; Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng (2007). "Quantifying social group evolution". Nature. 446 (7136): 664–667. arXiv: 0704.0744 . Bibcode:2007Natur.446..664P. doi:10.1038/nature05670. PMID   17410175. S2CID   4420074.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. Y. Chi, S. Zhu; X. Song; J. Tatemura; B.L. Tseng (2007). Structural and temporal analysis of the blogosphere through community factorization. KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 163–172. CiteSeerX   10.1.1.69.6959 . doi:10.1145/1281192.1281213. ISBN   9781595936097. S2CID   15435799.
  10. I. Farkas; I. Derenyi; H. Heong; et al. (2002). "Networks in life: scaling properties and eigenvalue spectra" (PDF). Physica . 314 (1–4): 25–34. arXiv: cond-mat/0303106 . Bibcode:2002PhyA..314...25F. doi:10.1016/S0378-4371(02)01181-0. S2CID   1803706. Archived from the original (PDF) on 2011-10-04. Retrieved 2011-04-21.