Evolving networks

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.

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

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:

$P\left(k\right)\sim k^{{-\gamma }}$

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:

$p_{i}={\frac {k_{i}}{\displaystyle \sum _{j}k_{j}}},$

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

$\Pi (k_{i})={\frac {\eta _{i}k_{i}}{\displaystyle \sum _{j}\eta _{j}k_{j}}},$

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

$\Pi (k_{i})\propto k_{i}(t-t_{i})^{{-\nu }},$

Where $\gamma$ increases with $\nu$

Removing nodes and rewiring links

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.

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

• "Understanding Network Science," http://www.zangani.com/blog/2007-1030-networkingscience
• "Linked: The New Science of Networks", A.-L. Barabási Perseus Publishing, Cambridge.

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. Retrieved 2014-01-31.
2. Travers Jeffrey; Milgram Stanley (1969). "An Experimental Study of the Small World Problem". Sociometry. 32 (4): 425–443. doi:10.2307/2786545.
3. R. Albert; A.-L. Barabási (2000). "Topology of Evolving Networks: Local Events and Universality" (PDF). Physical Review Letters. 85: 5234–5237. arXiv:cond-mat/0005085. Bibcode:2000PhRvL..85.5234A. doi:10.1103/PhysRevLett.85.5234. PMID 11102229.
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).
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" (PDF). Nature. 446 (7136): 664–667. arXiv:0704.0744. Bibcode:2007Natur.446..664P. doi:10.1038/nature05670.
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: 163–172.
10. I. Farkas; I. Derenyi; H. Heong; et al. (2002). "Networks in life: scaling properties and eigenvalue spectra" (PDF). Physica. 314: 25–34. arXiv:cond-mat/0303106. Bibcode:2002PhyA..314...25F. doi:10.1016/S0378-4371(02)01181-0.