Local World Evolving Network Models

Short description: Dynamic networks that change through time

Evolving networks are dynamic networks that change through time. In each period [math]\displaystyle{ t }[/math] 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 networks
• 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 and Rényi). Evolution of free scale networks is based on the preferential attachment – 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 (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 [math]\displaystyle{ m_{0} }[/math] and the small number of edges [math]\displaystyle{ e_{0} }[/math]. 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:

 [math]\displaystyle{ P_{local}'(k_{i})=P'(i\in Local-World)\frac{k_{i}}{\sum_{j\in Local}k_{i}^{}} }[/math]

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

 [math]\displaystyle{ P_{local}'(k_{i})=\frac{M_{}}{m_{0}+t}\frac{k_{i}}{\sum_{j\in Local}k_{i}^{}} }[/math]

while the dynamics are:

 [math]\displaystyle{ \frac{\partial k_{i}}{\partial t}=\frac{mM_{}}{m_{0}+t}\frac{k_{i}}{\sum_{j\in Local}k_{i}^{}} }[/math]

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

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 [math]\displaystyle{ M=m }[/math]

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:

 [math]\displaystyle{ \frac{\partial k_{i}}{\partial t}=\frac{m_{}}{m_{0}+t}\frac{k_{i}}{\sum_{j\in Local}k_{i}^{}} }[/math]

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

Case B Lower bounded limit [math]\displaystyle{ M=m_{0}+t }[/math]

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:

 [math]\displaystyle{ \frac{\partial k_{i}}{\partial t}=\frac{k_{i}}{2t} }[/math]

This equality indicates that in the upper bound solution, LW model follows the degree distribution of the power law: [math]\displaystyle{ P(k)\sim 2m^{2}/k^{3} }[/math] (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 [math]\displaystyle{ \delta }[/math] is introduced. Let [math]\displaystyle{ \delta }[/math] be the ratio of the number of nodes obtaining the information about the global network to the total number of nodes. Because [math]\displaystyle{ \delta }[/math] is a ratio, it must be that [math]\displaystyle{ \delta\in \left[0,1 \right] }[/math]. When [math]\displaystyle{ \delta=0 }[/math] there is no nodes that ow the global information and NLW model comes down to the local-world network model. In turn, [math]\displaystyle{ \delta=1 }[/math] 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 [math]\displaystyle{ e_{0} }[/math]. 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:

 [math]\displaystyle{ P_{global}(k_{i})=\frac{k_{i}}{\sum_{j}k_{j}} }[/math]

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:

 [math]\displaystyle{ P_{local}'(k_{i})=P'(i\in Local-World)\frac{k_{j}}{\sum_{j\in Local}k_{j}^{}} }[/math]

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

 [math]\displaystyle{ 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}} }[/math]

where [math]\displaystyle{ \delta }[/math] 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:

 [math]\displaystyle{ m = M }[/math]; [math]\displaystyle{ m\ll M \ll m_{0}+t }[/math] and [math]\displaystyle{ M=m_{0}+t }[/math]

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

Case A Lower bounded limit [math]\displaystyle{ M = m }[/math]

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:

 [math]\displaystyle{ \frac{\partial k_{i} }{\partial t}=\frac{\delta k_{i}+2(1-\delta)m}{2t} }[/math]

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

Case B. [math]\displaystyle{ m\ll M \ll m_{0}+t }[/math]

In time t there are [math]\displaystyle{ m_{0}+t }[/math] 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 [math]\displaystyle{ M=m_{0}+t }[/math]. Thus, the dynamics may be written as follows:

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

with the assumption that: [math]\displaystyle{ \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 }[/math]
As in previous case, the evolving network has a power-law degree distribution, however, with larger γ exponent, which equals : [math]\displaystyle{ \frac{4+\delta+\delta^{2}}{2-\delta-\delta^{2}} }[/math]
It may be noticed that the [math]\displaystyle{ \delta }[/math] 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 [math]\displaystyle{ \delta }[/math], 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