You're using an outdated browser. Please upgrade to a modern browser for the best experience.
Evolving Networks
Edit

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.

social networks network science network theory

1. 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. https://handwiki.org/wiki/index.php?curid=2084503

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(k)kγ

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]

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

pi=kijkj,

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

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

Π(ki)=ηikijηjkj,

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:

Π(ki)ki(tti)ν,

Where γ increases with ν

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

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

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

4.2. 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. 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.[6][7]

5. Applications

 
Route map of the world's scheduled commercial airline traffic, 2009. This network evolves continuously as new routes are scheduled or cancelled. https://handwiki.org/wiki/index.php?curid=1179563

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.[8] 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.

References

  1. Watts, D.J.; Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks". Nature 393 (6684): 409–10. doi:10.1038/30918. PMID 9623998. Bibcode: 1998Natur.393..440W. http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html. 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.  https://dx.doi.org/10.2307%2F2786545
  3. R. Albert; A.-L. Barabási (2000). "Topology of Evolving Networks: Local Events and Universality". Physical Review Letters 85: 5234–5237. doi:10.1103/PhysRevLett.85.5234. PMID 11102229. Bibcode: 2000PhRvL..85.5234A. http://nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/Universality_Physical%20Rev%20Ltrs%2085,%205234%20(2000).pdf. 
  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. 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. doi:10.1038/nature05670. Bibcode: 2007Natur.446..664P. http://www.nature.com/nature/journal/v446/n7136/pdf/nature05670.pdf. ;
  7. 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. http://portal.acm.org/ft_gateway.cfm?id=1281213&;type=pdf. 
  8. I. Farkas et al. (2002). "Networks in life: scaling properties and eigenvalue spectra". Physica 314: 25–34. doi:10.1016/S0378-4371(02)01181-0. Bibcode: 2002PhyA..314...25F. http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200211-01_PhysA-NetworksInLife/200211-01_PhysA-NetworksInLife.pdf. ;
More
Related Content
The logarithmic derivative has been shown to be a useful tool for data analysis in applied sciences because of either simplifying mathematical procedures or enabling an improved understanding and visualization of structural relationships and dynamic processes. In particular, spatial and temporal variations in signal amplitudes can be described independently of their sign by one and the same compact quantity, the inverse logarithmic derivative. In the special case of a single exponential decay function, this quantity becomes directly identical to the decay time constant. When generalized, the logarithmic derivative enables local gradients of system parameters to be flexibly described by using exponential behavior as a meaningful reference. It can be applied to complex maps of data containing multiple superimposed and alternating ramping or decay functions. Selected examples of experimental and simulated data from time-resolved plasma spectroscopy, multiphoton excitation, and spectroscopy are analyzed in detail, together with reminiscences of early activities in the field. The results demonstrate the capability of the approach to extract specific information on physical processes. Further emerging applications are addressed.
Keywords: spectroscopy; data analysis; logarithmic derivative; temporal decay; nonlinear optics; nonlinear order; multiphoton processes; pulsed lasers; signal processing; overlapping spectral lines
Assembly theory is a framework for quantifying selection, evolution, and complexity. It, therefore, spans various scientific disciplines, including physics, chemistry, biology, and information theory. Assembly theory is rooted in the assembly of an object from a set of basic building units, forming an initial assembly pool and from subunits that entered the assembly pool in previous assembly steps. Hence, the object is defined not as a set of point particles but by the history of its assembly, where the assembly index is the smallest number of steps required to assemble the object.
Keywords: assembly theory; complexity; origin of life; emergent dimensionality; mathematical physics
An article about the term "synchronicity" defined as the occurrence of meaningful coincidences that seem to have no cause.
Keywords: synchronicity; coincidences; Carl Jung
Historical sociology is a subfield of sociology that examines how social structures, institutions, and processes evolve over time. It integrates historical analysis and sociological theory to understand long-term social transformations, including changes in power, economy, culture, and social relations. Historical sociology draws from classical sociological traditions, including the works of Karl Marx, Max Weber, and Émile Durkheim, and is used to analyze phenomena such as state formation, revolutions, capitalism, colonialism, and social movements.
Keywords: Historical Sociology; Social Change and Continuity; Comparative-Historical Analysis; Sociology of Modernity
Economic sociology is a subfield of sociology that examines the social foundations of economic behavior, institutions, and systems. Unlike mainstream economics, which primarily relies on mathematical models and rational-choice theories, economic sociology explores how social structures, cultural norms, power relations, and historical contexts shape economic life. This field integrates insights from classical sociology (Karl Marx, Max Weber, Émile Durkheim) and has evolved to include contemporary debates on markets, globalization, capitalism, economic networks, and financial crises. Economic sociology is concerned with topics such as labor markets, economic inequality, social capital, consumer behavior, and the role of institutions in economic development.
Keywords: Economic Sociology; Cultural Economy; Labor and Work; Class and Economic Inequality
Upload a video for this entry
Information
Subjects: Others
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 1.3K
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 21 Nov 2022
Academic Video Service