Evolving
networks
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
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:
*Random networks
*Free- scale networks
*
Small-world network
A small-world network is a graph characterized by a high clustering coefficient and low distances. In an example of the social network, high clustering implies the high probability that two friends of one person are friends themselves. The l ...
s
*Local-world networks
One of the main feature which allows to differentiate networks is their evolution process. In random networks points are added and removed from the network in a totally random way (model of
Erdős
Erdős, Erdos, or Erdoes is a Hungarian surname.
Paul Erdős (1913–1996), Hungarian mathematician
Other people with the surname
* Ágnes Erdős (1950–2021), Hungarian politician
* Brad Erdos (born 1990), Canadian football player
* Éva Erd� ...
and
Rényi). Evolution of free scale networks is based on the
preferential attachment
A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who ...
– nodes connect to nodes that have already possessed a large number of links. In result hubs (nodes that have the largest number of edges) are created and networks follow power law of distribution (
model of Barabási and Albert's). In opposite, in
small world networks there are no hubs, and nodes are rather egalitarian and locally grouped in smaller clusters. These kind of networks are described by
Watts and Strogatz (WS) model. All aforementioned models assume that newly added points have a global information about the whole network. However, in case of large systems, such knowledge is rather rare. This strongly limits nodes’ possibilities of connection choice. As a result, decisions about links are made rather in a local world than in the whole network. Networks which consider this locality are called local-world networks and were first described by the Li and
Chen model
In finance, the Chen model is a mathematical model describing the evolution of interest rates. It is a type of "three-factor model" (short-rate model) as it describes interest rate movements as driven by three sources of market risk. It was the f ...
(2003). The local world model was extended inter alia by Gardeñes and Moreno (2004), Sen and Zhong, Wen et al. or Xuan et al.
[Xuan, Q., Y.Li and T.Wu (2007). Physica A, Vol.378, p.561]
World Evolving Network Model of Li and Chen (2003)
The model starts with the set of small number of nodes
and the small number of edges
. There are M nodes that were selected randomly from the whole global network, so that they constitute a so-called “local world” for new coming nodes. Thus, every new node with m edges connects only to m existing nodes from its local world and does not link with nodes which are in the global system (the main difference from the BA model). In such case, the probability of connection may be defined as:
:
Where
and the term "Local-World" refers to all nodes, which are in interest of newly added node at time t. Thus, it may be rewritten:
:
while the dynamics are:
:
In every time ''t'', it is true that
, so that two corner solutions are possible:
and
.
Case A. Lower bounded limit
A new node connects only to nodes from the initially chosen local world M. This identifies that in network growing process, preferential attachment (PA) selection is not efficient. The case is identical with BA scale free model, in which network grows without PA. The rate of change of the i th node’s degree may be written in the following way:
:
Thus, above proves that in the lower bound solution, network has an exponentially decayed degree distribution :
(Fig.1)
Case B Lower bounded limit
In this case local world behaves in the same way as the global network. It evolves in time. Therefore, LW model may be compared to Barabasi–Albert scale-free model, and the rate of change of the 'i th' node’s degree may be expressed as:
:
This equality indicates that in the upper bound solution, LW model follows the degree distribution of the power law:
(Fig. 2)
Hence, from A and B, it may be found that among corner solutions, Li and Chen’s model represents a transition for the degree distribution between the exponential and the power-law (Fig.3).
New Local World Evolving Network Model of Sen and Zhong (2009)
The model is the extension of LM model in a sense that it divides nodes on these which have the information about the global network and on these which does not.
To control for this diversification, parameter
is introduced. Let
be the ratio of the number of nodes obtaining the information about the global network to the total number of nodes. Because
is a ratio, it must be that