ABSTRACT

A large number of research results show that the synchronizability of complex networks is closely related to the topological structure. Some typical complex network models, such as random networks, small-world networks, BA scale-free network, etc, have totally different synchronizability. In this paper, a kind of hierarchical network synchronizability of self-similar module structures was studied, with more focus on the effect of the initial size of the module and network layer to the synchronizability and further research on the problem of network synchronous optimization. The Law of Segmentation Method was employed to reduce the maximum node betweenness and the Law of Parallel Reconnection employed to improve the ability of synchronizability of complex network by reducing the average path length of networks. Meanwhile, the effectiveness of proposed methods was verified through a lot of numerically simulative experiments.

Keywords:

Complex Networks, Hierarchical Network, Synchronizability, Optimization

1. Introduction

A large number of empirical studies show that many complex networks in reality, such as the Internet, gene regulatory networks. Internet interpersonal relationship networks have two common features, that is small world effect and scale-free property. In addition, many networks also have the Hierarchical modularity [1] [2] . These kinds of networks are composed of some internally intensive modules. The connections between modules are relatively loose, organized according to some hierarchical relationship. The network with this kinds of organizational structures is called Hierarchical network which is a relatively common network model, such as administrative management network model, the semantic memory network model, electronic commerce network, database management, etc. Therefore, the study of complex networks is of great significance for design and management of many real networks.

Synchronization is a common collective sports phenomenon in nature, such as synchronous flash of fireflies, applauding at the same time and so on. Since the 21st century, the Synchronous Dynamics of complex networks has become a heated research topic for scholars in many fields as the foundation of WS small-world network and BA scale-free network model. Some typical networks, such as synchronous and controlled problems of random networks, regular networks, small-world networks and scale-free networks have gained abundant research results [3] - [10] .

In 2004, Hong and other people found in the process of studying the WS small-world network that the network degree distribution heterogeneity and the network synchronizability had positive correlation, and then pointed out that the biggest node betweenness was the most appropriate influence factor for network topology characteristics. Besides, they pointed out the smaller the maximum node betweenness was, the stronger the network synchronous ability would be [9] .

Zhou Tao et al. put forward an effective method to improve the synchronizability of the network upon the Law of “Random Crossing Edge” [3] and found out that with the increase of the crossing edge distance, the average distance of the network decreases and the capacity of the network synchronization improves obviously. It proves that the smaller the average distance of the network is, the more advantageous it is for the synchronization of the dynamic system on the network [11] .

However, the above mentioned typical network models do not have a Hierarchical module topology. Due to the more complex modular structure of hierarchical networks, it is difficult to do research on the theory of the synchronized dynamics so that there are less relative research outcomes. The synchronizability of a kind of self-similar hierarchy network of network synchronization capability will be examined in this paper. We mainly focus on the effects of initial module sizes of hierarchy network and layers on network synchronizability, and further improve the ability of hierarchy network synchronization by changing two network structural characteristics―the biggest betweenness of the hierarchy network and average distances.

2. Mathematical Model and Basis

2.1. The Hierarchical Network Model

General hierarchical network can be generated by an initial module through some iterative ways. Firstly, we need to establish a complete graph with node $M$ as the initial module and randomly take a node as the center. The rest of the nodes are called peripheral nodes. Then copy the $M-1$ initial module, and connect the center node of the initial module with the peripheral nodes of the replica to form the second network called a new module. And copy the new module into the network, then comes the third layer. This process can be an infinite loop, which constitutes a hierarchical network of the self-similar hierarchical module structure.

Taking the hierarchial network in Figure 1 as an example, its construction processes are as follow:

Figure 1(a) is the initial module, a complete graph made up of four nodes, and then we select node 1 as a center node while other nodes are called peripheral nodes;

Make three copies of Figure 1(a), link all peripheral nodes (node 8 - 16) of three copies with the central node (node 1) of the initial network together, and then connect the central nodes (node 5 - 7) from three copies which form the two layers network as shown in Figure 1(b).

Next, Make three copies of Figure 1(b), then link all the most peripheral nodes (the nodes corresponding to node 8 - 16 in the replica) with the central node of initial network (node 1) together. Finally, connect the central node (the node corresponding to node 1 in the replica) of three copies together, forming a three layers network model as shown in Figure 1(c). And so on, a hierarchical network model with more layers can be constructed.

There are $M^I$ nodes in the network with $I$ layer (in which, $M$ is initial network node number). We can see from the network structure and Figure 1(c) that the hierarchical network is extremely regular, and has obvious characteristics of hierarchy and module, and even self-similar feature. We will study the synchronizability and the optimization problem of hierarchical network.

2.2. Description of Network Synchronizability

Considering a dynamic network with numerous identically dynamical systems as nodes, its state equation is:

${\stackrel{\dot{}}{x}}_i\left(t\right)=F\left(x_i\left(t\right)\right)-\delta {\displaystyle \underset{j=1}{\overset{N}{\sum }}{L}_{ij}H\left(x_j\left(t\right)\right)},i=1,2,\cdots ,N$ (1)

Among which, $x_i\in R^m$ is the state variables of i node, ${\stackrel{\dot{}}{x}}_i\left(t\right)=F\left(x_i\left(t\right)\right)$ is the dynamic equation of i node. The constant $\delta >0$ is the coupling strength

and $H(.):R^m\to R^m$ is the internal coupling function between the state variables of each node. $L={\left(L_{ij}\right)}_{N\times N}\in R^{N\times N}$ is the Laplace matrix of the network (external coupling matrix).

When $t\to \infty$ , it satisfies

$\underset{t\to \infty }{\lim }{x}_i\left(t\right)=S\left(t\right)$ (2)

Then the dynamic network (1) is said to achieve synchronization. The synchronization manifold is the solution to the isolated node equation, satisfying

$\stackrel{\dot{}}{s}\left(t\right)=F\left(s\left(t\right)\right)$ (3)

Mark that the synchronization area of the network (1) is $C$ , and the eigenvalue of the matrix $L={\left(L_{ij}\right)}_{N\times N}\in R^{N\times N}$ is ${\lambda }_k,k=1,\cdots ,N$ . From the main stability function theory, when ${\lambda }_k$ satisfied

$\delta {\lambda }_k\in C,k=2,\cdots ,N$

The synchronization manifold of network (1) is asymptotically stable. According to the different situations of the synchronous region, we generally divide the network into three types shown as follow.

Type I network: the synchronous region is $C=\left(-\infty ,{\alpha }_1\right),{\alpha }_1<0$

Type II network: the synchronous region is $C=\left({\alpha }_1,{\alpha }_2\right),{\alpha }_2<{\alpha }_1<0$

Type III network: the synchronous region is an empty set. This type of network cannot achieve the synchronous state for any coupling strength and coupling matrix.

In addition, there are also synchronous regions for multiple limited regions, but such network is rare.

This type of network is determined by the internal and isolated node dynamics of the network, which is irrelevant to the topology of the network. For networks of type I and type II, only when it satisfied $\delta {\lambda }_2>{\alpha }_1$ or ${\lambda }_N/{\lambda }_2<{\alpha }_2/{\alpha }_1$ , the synchronous flow of the network can be asymptotically stable ( ${\lambda }_2$ , ${\lambda }_N/{\lambda }_2$ is the minimum non-zero eigenvalue of corresponding Laplace matrix and the maximum nonzero eigenvalues), and when ${\lambda }_2$ gets bigger or ${\lambda }_N/{\lambda }_2$ gets smaller, the network synchronous ability will be stronger. Therefore, we usually use ${\lambda }_2$ or ${\lambda }_N/{\lambda }_2$ to depict network synchronizability.

3. The Analysis of Hierarchical Network Synchronizability

This section makes a numerical simulation with different initial module node number and different layers of the hierarchical network model respectively. Through the comparison of the changes of ${\lambda }_2$ and ${\lambda }_N/{\lambda }_2$ , we analyze the influence of the size of the initial module and network layer on hierarchical network model synchronizability.

3.1. The Impact of Initial Module Size on Synchronizability

A numerical simulation of the hierarchical network model of different initial nodes is presented. Select the same number of layers and the five complex network of initial nodes $M=4$ , $M=5$ , $M=6$ , $M=7$ , $M=8$ respectively.

In Figure 2(a), Figure 2(b), the relationships between ${\lambda }_2$ 、 ${\lambda }_N/{\lambda }_2$ and the number of initial network nodes are given. And it can be seen from the figure that with the increase of the number of initial network nodes, at that time, $I\ge 4$ the whole ${\lambda }_2$ presents an increasing state, but ${\lambda }_N/{\lambda }_2$ monotonically increasing.

This shows that for the type I network, when the layer number of the hierarchical network is certain, the synchronizability of the hierarchical network increases with the increase of the number of initial module nodes. On the other hand, for type II hierarchical network, its synchronizability decreases with the increase of the number of initial module nodes.

3.2. The Impact of Network Layer Number on Synchronizability

When the number of layers is certain, the study on the relationship between the initial module size and the network synchronizability can only provide a horizontal comparison between the different networks. By contrast, based on the mechanism of the hierarchical network, the influence of hierarchical network layer on the network synchronizability has more research values which can provide magnificent guidance of analysis and design for the generation and growth of the hierarchical network.

It can be seen by observing the Figure 3(a), Figure 3(b) that with the increase of the number of layer network, it decreases slowly and increases exponentially. This shows that, regardless of type I or type II hierarchical network, with the growth of network layer number, network synchronizability reduces. In particular, for type II hierarchical networks, the network's synchronizability declines dramatically as the number of layers grows.

4. The Optimization of Layer Network Synchronizability

4.1. Improvement of the Synchronizability of the Network by Reducing the Maximum Network Node Betweenness

Because the general network synchronizability is negatively related to the

maximum betweenness, which means the largest node betweenness is, the worst the network synchronizability is. We try to improve the synchronizability of the network by reducing the maximum node betweenness.

Large-scale hierarchical network belongs to the network of node betweenness with great differences. In order to effectively reduce the network center node betweenness, we apply the method of Segmentation to make a tiny perturbation in the Internet structure to reduce the maximum network node betweenness and improve the synchronizability of the network.

The structural perturbation procedure of “Segmentation method” is as follows:

In order to study the effect of “segmentation method”, we compare the changes of the maximum node betweenness $b_{\max }$ , ${\lambda }_2$ , ${\lambda }_N/{\lambda }_2$ before and after segmentation through numerical simulation. This section selects different number of initial nodes and different layers of the hierarchical network to do numerical Simulation.

Figure 4(a) is changes of maximum node betweenness $b_{\max }$ in the process of segmenting the maximum node betweenness of two models in initial node $M=4$ , layer $I=3$ and the initial node $M=6$ , layer $I=3$ . The leap of $b_{\max }$ between the number of 0 and 1 in the reconnective operation times is caused by adding auxiliary nodes. In the process of reconnective operation after the single partition, the maximum node betweenness of the network decreases sharply. In the process of reconnective operation after the single partition, the maximum node betweenness of the network decreases sharply. $b_{\max }$ decreases from $4.20\times {10}^4$ and $3.80\times {10}^4$ to $3.64\times {10}^4$ and $3.40\times {10}^4$ . Figure 4(b) is changes of maximum node betweenness $b_{\max }$ in the process of “5-segmention” in the hierarchical network when initial node number $M=5,I=4$ . After operating “5-segmention” for 100 times, $b_{\max }$ decreases from $2.87\times {10}^5$ to $1.07\times {10}^4$ . Therefore, the segmentation method has a great impact on reducing the maximum node betweenness of the hierarchy network.

Taking the hierarchial network as an example when $M=5,I=4$ , the network has 625 nodes and the maximum betweenness of four nodes is $2.87\times {10}^5$ , $4.32\times {10}^4$ , $5.53\times {10}^3$ , $5.48\times {10}^3$ , and the number of corresponding nodes is 1, 4, 4 and 16 respectively. Due to segmenting for several times, there are multiple nodes that have the maximum node betweenness of network (For example, after segmenting for several time, the maximum node betweenness of network becomes $4.32\times {10}^4$ . At this point, four nodes in the network will have the maximum node betweenness of network.) Therefore, in the process of repeating “segmentation”, no every operation can reduce the maximum node betweenness of network.

As shown in Figure 5(a), with the increase of the times of “segmentation”, the whole ${\lambda }_2$ is in the periodical growth status. When the “segmentation” operation

can reduce the maximum node betweenness of network, ${\lambda }_2$ can grow substantially. When the “segmentation” operation can not reduce the maximum node betweenness of network, ${\lambda }_2$ enters the periodically tiny perturbations.

It can be seen from Figure 5(b) that ${\lambda }_N/{\lambda }_2$ greatly reduces after the first “segmentation” operation, but after the second “segmentation”, there is a relatively slight increase, and it enters into the periodically reduced state in the subsequent “segmentation” operation. When the "segmentation" operation can reduce the maximum node betweenness of network, ${\lambda }_N/{\lambda }_2$ can reduce substantially; when the “segmentation” operation can not reduce the maximum node betweenness of network, ${\lambda }_N/{\lambda }_2$ enters the periodical tiny perturbations.

Figure 6 is the numerical simulation result between “segmentation” operations times and ${\lambda }_2$ , ${\lambda }_N/{\lambda }_2$ when two hierarchical networks $M=5,I=4$ , and $M=4,I=4$ at different $p$ values, This result is the average of the operative results after 10 times.

We observed that different $p$ have a greater effect on the changes of ${\lambda }_2$ and ${\lambda }_N/{\lambda }_2$ in Figure 6. In general, after selecting the appropriate $p$ value, ${\lambda }_2$ will increase to two times as its original one after the second jump.

The change of ${\lambda }_N/{\lambda }_2$ is more special, although the change is less stable, since ${\lambda }_N/{\lambda }_2$ will drop to about 1/2 after the first segmentation. At this time, we believe that the network synchronizability has been improved to a certain extent. In order to maintain the other characteristics of the network, the “segmentation” should be terminated.

To sum up, the Segmentation Method can effectively reduce the network’s maximum betweenness of nodes, and the synchronizability of the hierarchical network is significantly improved.

4.2. Improving Network Synchronization by Reducing the Average Path

In this section, we try to reduce the average path length of the network and improve the synchronizability of the network.

Scholars like Zhao Ming put forward a kind of Random Cross Boundary

Method, which can change the rest of the network structure characteristics without changing the degree of each node in the network conditions and separately discuss two controversial structure characteristics of network average and the degree distribution. However, due to the complete randomness of the random crossing method, no every cross-connection can achieve the goal of reducing the average distance of the network. In the experiment, it was found that a large number of random cross-linking was invalid.

In the experiment based on the hierarchical network model, the operational efficiency of random crossing method is very low, and the effective rate is often less than 1%. In order to ensure the reconnective operation can effectively reduce the average distance of the network and preserve the characteristics of constant node degree at the same time. We put forward a new reconnection mechanism-Parallel reconnection method, shorthand for PRC method (Parallel reconnection).

In order to investigate the influence of the mean distance of the hierarchical network on its synchronizability, we use the PRC method to change the average distance of the network.

We make every reconnective operation with a purpose. The steps of the PRC method are as follows:

1) Selecting the two longest distance nodes i and j in the network at random, and connecting them.

2) Selecting the longest distance node a neighboring i and connecting with node b neighboring j at random (a and b is unconnection).

3) Judging whether the average distance is reduced after reconnecting the network. If it does, it works and the alternation can be kept. Otherwise, the network will be restored to the previous unreconnected state.

4) Repeating steps (1)-(3) until achieve the average distance or pre-set operation times of the desired network.

We should note that when the average distance of the network is $L>3$ , because of $l_{ij}>3$ , $l_{ab}>2$ , node a and b must have no connection.

Therefore, when $L>3$ , we do not need to judge whether the selected nodes are connected with other nodes in the PRC method, they can directly parallel reconnect. At this time, the operational efficiency of the PRC Method is very high, which can not only improve the effect of reducing the average distance of the network, but also keep the nodes and degrees of the network unchanged at the same time (Figure 7).

On the other hand, for different hierarchical network models, PRC method, a limitation is that after a certain number of effective reconnections, the effectiveness of the reconnection will fall sharply, so that PRC method reduces the hierarchical network average distance limitation. But before that, almost every parallel reconnection can reduce the network average distance, and the efficiency of the PRC operation can be maintained over 90%.

Figure 8 is the simulation results of average distance of three hierarchical networks and the times for effectively PRC when $M=5,I=4$ , $M=6,I=4$

and $M=7,I=4$ . The result is 10 times the average operational results. The efficiency of PRC operation is about 93%, 94% and 97%. It can be seen from the Figure 8, Figure 9(a) and Figure 9(b). Taking the hierarchical network model of $M=5,I=4$ as an example, after 100 times of effectively PRC, $L$ decreases constantly, and gradually decreases from 3.1695 to 3.0173. At the same time, ${\lambda }_2$ increases from 0.3736 to 0.6842 and ${\lambda }_N/{\lambda }_2$ decreases from 912.7612 to 474.9729.

This shows that the smaller the average distance of the network is, the easier the network is to achieve synchronization, and the stronger capability of network synchronizability. However, a large number of simulative experiments have found that although hierarchical network synchronizability can get stable improvement in the situation of keeping the network degree and degree distribution unchanged. But for some hierarchical networks, the changes of ${\lambda }_2$ and ${\lambda }_N/{\lambda }_2$ sometimes are small, and the PRC method seems to be limited in enhancing the network synchronizability.

5. Conclusions

This paper mainly studied that a hierarchical network of self-similar module structure synchronizability is associated with the initial module size and the layer number of network. The study found out that when the network layer was and remained unchanged, for type one network, the initial module of hierarchical network node number would increase, and the network synchronizability would be stronger. On the other hand, for type two hierarchical networks, the synchronizability weakened with the increase of the number of initial module node. While for the hierarchical internet of the same initial number of nodes, with the increase of network layers, the network would become increasingly difficult to achieve synchronization.

As for the problem of hierarchical network synchronizability and optimization, “Segmentation Method” can reduce the maximum node betweenness. When the value of p can be chosen appropriately, network synchronizability can be greatly improved. The PRC method proposed in this paper is to optimize

network synchronizability by reducing the average distance of the hierarchical network. Though the method is deficient in improving the extent of hierarchical network synchronizability, its stability is good. And the PRC method can subtly and separately analyze the two controversial structure characteristics―average distance and degree distribution, which changes its hierarchical network average distance only and the degree distribution remains unchanged.

Although these two methods can both improve the synchronizability of hierarchical network, but which one is better? Whether these two methods are also applicable to other types of web? There are more questions for us to delve into and that is our direction to head for in the future.

Acknowledgements

This work is supported by the National Natural Science Foundation of China under Grant 61563013 and 61663006.

Cite this paper

Lin, H., Jia, Z. and Long, Y.S. (2017) The Synchronizability and Optimized Analysis of the Hierarchical Network. Communications and Network, 9, 207-218. https://doi.org/10.4236/cn.2017.93015

References