Local World Evolving Network Models

An evolving network is a network that changes over time. In this type of network, components (called nodes) and the connections between them (called edges) can be added or removed. This dynamic behavior is a key feature of many real-world systems. For example:

• A social network evolves as people make new friends, join new communities, or lose touch with old acquaintances.

• The Internet evolves as new websites are created and linked to, while old ones are taken down.
• Transportation networks evolve as new roads or airline routes are added.

Studying how networks evolve helps researchers understand the growth and structure of complex systems. Different mathematical models have been developed to describe these changes, each capturing different rules for how nodes and edges are added or removed.

Common evolution models

The structure of a network is determined by the process of its evolution. The main models that describe these processes differ in how new nodes choose which existing nodes to connect with. All the following models assume that newly added points have global information about the whole network, except for the local-world model

• Random networks follow the Erdős–Rényi model, where new nodes and edges are added to the network in a completely random way. This was one of the earliest models for network evolution.
• Scale-free networks evolve through a process called preferential attachment. In this model, new nodes are more likely to connect to existing nodes that already have many connections—a "rich-get-richer" effect. This creates highly connected "hubs" and is described by the Barabási–Albert model.
• Small-world networks are characterized by nodes that are highly clustered into local groups, yet are connected by short paths to any other node in the network. The Watts–Strogatz model describes networks that are neither completely regular nor completely random, but have this "small-world" property.
• Local-world networks account for the fact that in many large systems, a new node only has knowledge of a small, local portion of the entire network. Therefore, it makes connections based on this limited local information rather than global knowledge. This concept was first described by Li and Chen (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.

World Evolving Network Model of Li and Chen (2003)

The model starts with the set of small number of nodes $m_{0}$ and the small number of edges $e_{0}$. 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:

 $P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

Where  $P'(i\in Local-World)={\frac {M}{m_{0}+t^{}}}$ 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:

 $P_{local}'(k_{i})={\frac {M_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

while the dynamics are:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {mM_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

In every time t, it is true that  $m\leqslant M\leqslant m_{0}+t$, so that two corner solutions are possible:  $M=m$ and  $M=m_{0}+t$.

Fig.1.Degree distribution comparison in log–log scale of lower bound case with M = m = 3, and a local-world evolving network with M = 4 and m = 3. Networks have N = 10 000. The inset is in the log-linear scale of the same curves

Case A. Lower bounded limit $M=m$

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:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {m_{}}{m_{0}+t}}{\frac {k_{i}}{\sum _{j\in Local}k_{i}^{}}}$

Thus, above proves that in the lower bound solution, network has an exponentially decayed degree distribution : $P(k)\sim e^{-k/m}$(Fig.1)

Case B Lower bounded limit $M=m_{0}+t$

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:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {k_{i}}{2t}}$

This equality indicates that in the upper bound solution, LW model follows the degree distribution of the power law: $P(k)\sim 2m^{2}/k^{3}$ (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 $\delta$ is introduced. Let $\delta$ be the ratio of the number of nodes obtaining the information about the global network to the total number of nodes. Because $\delta$ is a ratio, it must be that $\delta \in \left[0,1\right]$. When $\delta =0$ there is no nodes that ow the global information and NLW model comes down to the local-world network model. In turn, $\delta =1$ means that each node possesses the global information about the network, which makes NLW model identical with BA model.
The NWL model starts in the same way as LW – there is a set of small number of nodes m_0 and the small number of edges $e_{0}$. There are M nodes that were selected randomly from the whole global network and established a “local world” for new coming nodes. However, in NLW model every new node with m edges can connect to global or local system. The decision depends on received information. If a new node gets information about the whole network, the probability that it will be connected with node i depends on the degree ki of that node, such that:

 $P_{global}(k_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}$

In turn, if the node was not provided in the global information and knows only its local world, it will link only with nodes from this system with the probability:

 $P_{local}'(k_{i})=P'(i\in Local-World){\frac {k_{j}}{\sum _{j\in Local}k_{j}^{}}}$

Thus, the general probability in the new local world model may be written as:

 $P_{all}'(k_{i})==\delta {\frac {k_{i}}{\sum _{j}k_{j}}}+(1-\delta )P'(i\in Local-World){\frac {k_{i}}{\sum _{j}k_{j}}}$

where $\delta$ is the probability that a new node possesses a knowledge about the global network. Similarly to the LW model, the NLW model distinguish three cases of local-world selection:

 $m=M$; $m\ll M\ll m_{0}+t$ and $M=m_{0}+t$

The upper bound case (Case C) is the same as in the local world model.

Case A Lower bounded limit $M=m$

In the lower limit there are only few nodes that meet holistic preferential attachment requirement, while most of them connect a new edge randomly. Moreover, the cumulative degree of the local world depends on the random selection. In such case, the dynamics of the system are described by:

 ${\frac {\partial k_{i}}{\partial t}}={\frac {\delta k_{i}+2(1-\delta )m}{2t}}$

with the assumption that: $\sum _{j\in local}k_{j}=M\left\langle k_{i}\right\rangle =m\left\langle k_{i}\right\rangle \approx mk_{i}$
In this case, the degree distribution of the networks follows a power-low distribution, and the exponent of the scale-free network $(\sigma )$ equals $1+{\frac {\delta }{2}}$ so that the initial assumption about small $\delta$indicates that the power-low exponent of the network reaches a high value.

Case B. $m\ll M\ll m_{0}+t$

In time t there are $m_{0}+t$ nodes If the new coming node does not have the information about the global network, it will link to i node in the local system with the probability $M=m_{0}+t$. Thus, the dynamics may be written as follows:

 ${\frac {\partial k_{i}}{\partial t}}=\left[{\frac {\delta }{2}}-{\frac {1+\delta }{1-\delta }}\right]{\frac {k_{i}}{t}}$

with the assumption that: $\sum _{j\in local}k{j}=\sum _{j\in local}k_{j}=\left[\delta \left\langle k_{i}\right\rangle +(1-\delta )m\right]M$
As in previous case, the evolving network has a power-law degree distribution, however, with larger γ exponent, which equals : ${\frac {4+\delta +\delta ^{2}}{2-\delta -\delta ^{2}}}$
It may be noticed that the $\delta$ ratio is the only parameter of the scale-free exponent of the new model. Thus, the significant improvement of the model comes from the introduction of $\delta$, which by adding or removing nodes that possess the information about the global network, allows to control a topological structure of a network.

Sources

• Bao, Z. and Y.Cao (2008). Journal of Zhejiang University Science A, Vol.9, No.10, p. 1336
• Lu, J., H.Leung and G.Chen (2004). Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications & Algorithms, Vol.11a, p. 70