1. Introduction

In the past two decades, complex networks have been extensively studied and have gained rich research results. In particular, discoveries of the small world effect [1] and the scale-free feature [2] of complex networks have promoted the research of network structure [3] - [11] . And it has been known that the topology of a network often plays an important role in the feature of dynamical network.

Since Barabási and Albert have addressed that two key mechanisms-growth and preferential attachment. BA scale-free network model [2] was proposed to promote the understanding of the real network. Subsequently, an increasing number of studies have been devoted to creating a new model [12] - [19] . Bollobas and Riordan proposed another version of the scale-free model, which is called the linearized chord diagram (LCD) model [14] , in the model multiple-edges and self-loops can be allowed. Xiang Li et al. proposed a local-world evolving network model [15] , which represents a transition between power-law and exponential scaling. Y.J. Cao et al. proposed a neighbourhood evolving model [16] , which also yields a transition between power-law and exponential. In order to enhance the synchronizability of the growth network, X.F. Wang et al. have constructed the synchronization-optimal growing network [12] , it is easier to achieve synchronization than BA scale-free networks, however, it is more particularly fragile with respect to deliberate attacks. Hence, for improving the synchronization robustness against the selective removal of vertices in complex networks, X.F. Wang et al. have also proposed the synchronous preference of complex dynamical networks [13] , and its synchronizability is investigated and found to be robust against both random and specific removal of nodes. There are many scale-free growth network models [17] [19] , all of which are obtained by changing the preferential attachment mechanism.

In the real-world networks, there is another priority connection mechanism, “neighbor” effect. For example, when you enter a strange city to visit your friends, you will just make friends with the friends of your present friends. Based on the growth and neighbor preferential principles, we propose a dynamical networks model, which is called the NPG model in this paper. To further clarify the topology of the NPG network, we confirm the statistical properties of the new network in three aspects-the degree probability distribution, the clustering coefficient and the average path length. In fact, the three concepts play an important role in the development of complex network theory [20] [21] . Theoretical analysis and numerical simulations indicate the new network is not only a scale-free network whose degree distribution obeys the power-law and its power exponent is related to the edge-adding number m, but also a small-world network which has large clustering coefficient and small average path distance. Meanwhile, its synchronizability is much stronger than that of BA scale-free network [2] , even stronger than that of synchronization-optimal network [12] . And the NPG network is robust with respect to random attacks and is fragile to specific removal of a small fraction of nodes.

2. The Construction of the NPG Model

Our model is defined as follows:

1) Initial network: Starting with a globally coupled network with $m_0$ nodes.

2) Growth: At every time step a new vertex is added and is connected to m ( $m\le m_0$ ) nodes that already-existing in the system.

3) Preferential attachment:

a) The new node is connected to an existing node i only for one edge. The connection probability ${\Pi }_i$ depends on the degree of the existing node:

${\Pi }_i=\frac{k_i}{{\displaystyle {\sum }_j{k}_{{}_j}}}$ (1)

b) Select the first $m-1$ nodes successively in the order of descending degree (when the degree of the nodes is the same, first select the older node) from all the neighbor nodes of the node i which is connected to the new node. Add $m-1$ edges between the new node and the $m-1$ nodes.

After $t\gg m_0$ time steps, we obtain a neighbor-preferential growth network with $N=m_0+t$ vertices.

3. Statistical Characteristics of the NPG Model

3.1. Degree Distribution

The degree distribution as one of the most important statistical features of complex networks. We calculate the degree probability distribution $P\left(k\right)$ , using the mean-field approach [22] . By the connection mechanism of the algorithm of the model, we know that the model has $m-1$ “hubs” which are connected to all nodes and a big node which is connected to most nodes, as shown in Figure 1(a) (in the later simulation we also see the phenomenon ). For convenience, the big node is also called the “hub”. And there is no doubt that the m “hubs” are connected to each other.

Suppose the initial network has $m_0$ nodes and the degree of the node i is $k_i\left(t\right)$ at time t. When t is large enough, we can ignore the number of edges in the initial network and $m_0+t\approx t$ . Divided the nodes into two categories: the m “hubs” and the common nodes. When a new node is added to the network, the probability of the new node is connected to the node i is $\Pi \left(i\right)$ . If node i belongs to the “hubs”, the $\Pi \left(i\right)=1$ , but we will ignore the node i in the degree probability distribution, due to the number of the “hubs” is much smaller than the total number of nodes in the network ( $m\ll t$ ). Then we only need to consider when the node i belongs to the common nodes, the probability of the new node is connected to the node i is ${\Pi }_i$ in the preferential attachment (i), if the new node is not connected to node i, the preferential attachment (ii) will work, but the new node is also not connected to node i, because it will be connected to the “hubs”. So when the node i belongs to the common nodes, only the preferential attachment (i) works. In a word, the connection probability of node i is

$\Pi \left(i\right)={\Pi }_i=\frac{k_i\left(t\right)}{{\displaystyle {\sum }_j{k}_j\left(t\right)}}=\frac{k_i\left(t\right)}{2mt}$ (2)

Assume the degree of the node i is continuous, and thus the connection probability $\Pi \left(i\right)$ can be interpreted as the rate of change of the ith node’s degree, we can write

$\frac{\partial k_i}{\partial t}=\Pi \left(i\right)=\frac{k_i\left(t\right)}{2mt}$ (3)

The solution of this equation, with the initial condition that node i was added to the system at time $t_i$ with connectivity $k\left(t_i\right)=m$ , is

$k\left(t_i\right)=m{\left(\frac{t}{t_i}\right)}^{\frac{1}{2m}}$ (4)

the probability that a node has a connectivity $k\left(t_i\right)$ smaller than k,

$P\left(k_i\left(t\right)<k\right)$ , can be written as

$P\left(k_i\left(t\right)<k\right)=P\left(t_i>\left(\frac{m^{2m}t}{k^{2m}}\right)\right)$ (5)

Suppose we add nodes at equal time intervals to the network, the probability density of $t_i$ is

$P\left(t_i\right)=\frac{1}{m_0+t}$ (6)

By (5) and (6), then the probability density for $P\left(k\right)$ can be obtained

$P\left(k\right)=\frac{\partial P\left(k_i\left(t\right)<k\right)}{\partial k}=2m\frac{t}{m_0+t}{m}^{2m}{k}^{-2m-1}=2\frac{t}{m_0+t}{m}^{2m}{}^{+1}{k}^{-2m-1}$ (7)

That means, $P\left(k\right)~k^{-2m-1}$ , the degree probability distribution of the NPG model follows power-law distribution, and the power exponent is $-2m-1$ , not fixed. When m is larger, the smaller the power exponent, the steeper the corresponding graph. In Figure 2(a) we can see that when $m=3,5,7$ , the lines will become more and more steep, supporting the analytical result. In particular, there is a limiting case-when $m=1$ , the preferential attachment (ii) is not effective in the NPG model. Namely, in this limiting case the NPG model is the same as BA model, and Eq. (7) is valid for the limiting case. In Figure 2(b), we can also see when $m=1$ , the graphs of BA and the NPG are almost coincident, supporting the analytical result.

3.2. Average Path Length

The average path length is also an important statistical characteristics for studying complex networks, especially when describing the synchronizability of networks. The shorter the average distance length, the stronger the synchronizability [23] [24] [25] , Generally. For the NPG network, the nodes are divided into three sets. Set one: the $m-1$ “hubs” which are connected to all nodes; Set two: a big node which is connected to most nodes; Set three: the common nodes. As shown in Figure 1(a). The path length can be expressed mathematically as follows:

$S_{11}=C_{m-1}^2$ (8)

$S_{12}=m-1$ (9)

$S_{13}=\left(N-m\right)\left(m-1\right)$ (10)

$S_{22}=0$ (11)

$S_{23}=2N-m-k_x-1$ (12)

$S_{33}=2C_{N-m}^2-N+k_x-\frac{m}{2}-\frac{m^2}{2}+1$ (13)

where $S_{ij}$ is the sum of the shortest path lengths of all nodes in set i to all nodes in set j, where $k_x$ is the degree of the big node. So the average path length of the NPG network is S

$S=\frac{{\displaystyle \underset{1\le i\le j\le 3}{\sum }{S}_{ij}}}{C_N^2}$ (14)

When N is large enough, the average length is two. From Figure 3(b), we can get that the numerical results are consistent with the theoretical predictions. In Figure 3(b), we also show that the comparison results of the average path length for the NPG model and BA model. We find the average path length of the NPG network is significantly shorter than that of the BA network.

3.3. The Clustering Coefficient

The small-world characteristic consists of two properties: large clustering coefficient and small average path length. We have demonstrated that the NPG network has a small average path length. The clustering coefficient is C

$C={\displaystyle \underset{i=1}{\overset{N}{\sum }}\frac{C_i}{N}}$ (15)

where $C_i$ is the local clustering coefficient for node i.

$C_i=\frac{E\left(i\right)}{C_{k_i}^2}$ (16)

where $E\left(i\right)$ is the number of edges in the neighbor set of the node i, and $k_i$ is the degree of node i. First of all, we simply analyze the structure of the NPG network (see Figure 1):

1) When the degree of node i is equal to the edge-adding number m ( $k_i=m$ ), the clustering coefficient of node i is one.

2) Get rid of the “hubs” from the neighbor set of any node i which exist in Set 2 and Set 3 to form a new neighbor set in which edges is not exists between nodes.

Simply prove ii), if there is a connection between node i and j in this new neighbor set, then node i or node j with $m+1$ edges into the network system, which is impossible. Namely, conclusion ii) is established. The local clustering coefficients of the nodes in Set 2 and Set 3 are $C_i$

$C_i=\frac{C_{k_i}^2-C_{k_i-m+1}^2}{C_{k_i}^2},k_i\ne m$ (17)

The local clustering coefficients of the nodes in Set 1 are ${C^{\prime }}_i$ , according to the degree of the nodes in the network, it is easy to prove the following equation

${C^{\prime }}_i=\frac{mN-N+1}{C_{k_i}^2}$ (18)

The degree $k_i$ of the “hubs” satisfies $k_i+1=N$ , so

$\frac{C_{k_i}^2-C_{k_i-m+1}^2}{C_{k_i}^2}=\frac{2k_i\left(m-1\right)-m^2-m}{k_i\left(k_i-1\right)}~o\left(\frac{1}{k_i}\right)$ (19)

${C^{\prime }}_i=\frac{mN-N+1}{C_{k_i}^2}=\frac{2\left(m-1\right)k_i}{k_i\left(k_i-1\right)}~o\left(\frac{1}{k_i}\right)$ (20)

namely, ${C^{\prime }}_i\approx C_i$ . Finally, for the NPG network, the clustering coefficient of node i is

$C_i=\{\begin{array}{l}\frac{C_{k_i}^2-C_{k_i-m+1}^2}{C_{k_i}^2}{k}_i\ne m\\ 1k_i=m\end{array}$ (21)

by (21),it can be seen when the degree of the node becomes larger, the local

clustering scales as $C\left(k\right)~o\left(\frac{1}{k}\right)$ , where $C\left(k\right)$ denotes the average clustering values of nodes with degree k. In Figure 4, this phenomenon is also seen. When calculating the clustering coefficient C, we only consider the common nodes. We have

$C={\displaystyle \underset{k=m+1}{\overset{l}{\sum }}P\left(k\right)}\left(\frac{C_k^2-C_{k-m+1}^2}{C_k^2}\right)+P\left(k=m\right)$ (22)

$l$ is a constant and $l\ll N$ ，since the degree distribution is

$P\left(k\right)=A{k}^{-2m-1}$ ，where $k=m,m+1,\cdots ,l$ . And ${\displaystyle \underset{k=m}{\overset{l}{\sum }}A{k}^{-2m-1}}=1$ , the average clustering coefficient C can be rewritten as

$C=\frac{{\displaystyle \underset{k=m+1}{\overset{l}{\sum }}{k}^{-2m-1}}\left(\frac{C_k^2-C_{k-m+1}^2}{C_k^2}\right)+m^{-2m-1}}{{\displaystyle \underset{k=m}{\overset{l}{\sum }}{k}^{-2m-1}}}$ (23)

The numerical results are demonstrated in Figure 3(a), we can get that a little fluctuations between the numerical results and analysis results, which may

attribute to the fluctuations of the power-law exponent of degree distribution. But it does not affect the network with a large clustering coefficient. In Figure 3(a), we show the comparison result of the clustering coefficient for BA model and the NPG model. We find that the clustering coefficient of the proposed model is larger than that of BA model obviously. And the clustering coefficient of the new model will increase as m increases.

The above simulation results show that the new network is a scale-free network and its power exponent is related to the edge-adding number m. What’s more, it has a large clustering coefficient and a short average path length, which represent a small-world effect. So the model has the characterization of both scale-free and small-world networks.

4. Synchronization in Complex Dynamical Networks

4.1. Synchronization Stability Criterion of Complex Dynamical Networks

Consider a complex dynamical network consisting of N identical linearly and diffusively coupled vertices, with each vertex being an n-dimensional dynamical oscillator. The state equation of the network can be written as [25] [26] [27] :

$\stackrel{\dot{}}{x}=f\left(x_i\right)+c{\displaystyle \underset{j=1}{\overset{N}{\sum }}{a}_{ij}\Gamma x_j},i=1,2,\cdots ,N,$ (24)

where $x_i=\left(x_{i1},x_{i2},\cdots ,x_{in}\right)\in R^n$ are the state variables of vertex i and the constant coupling strength c is assumed positive. Furthermore, $\Gamma \in R^{n\times n}$ is a constant $0-1$ diagonal matrix denoted as $\Gamma =diag\left(r_1,r_2,\cdots ,r_n\right)\in R^{n\times n}$ [27] . If there is a connection between vertex i and vertex j $\left(i\ne j\right)$ , then $a_{ij}=a_{ji}=1$ ; otherwise, $a_{ij}=a_{ji}=0$ $\left(i\ne j\right)$ . We take

$a_{ii}=-{\displaystyle \underset{\begin{array}{l}j=1\\ j\ne i\end{array}}{\overset{N}{\sum }}{a}_{ij}}=-k_i,i=1,2,\cdots ,N,$ (25)

where the degree $k_i$ of vertex i is defined to be the number of its outreaching connections. Defined that dynamical network (24) is (asymptotically) synchronized if

$x_1\left(t\right)=x_2\left(t\right)=\cdots =x_N\left(t\right)=s\left(t\right)$ as $t\to \infty$ (26)

where $s\left(t\right)$ is a solution of an isolated vertex [28] . Suppose that the network is connected in the sense that there are no isolated clusters. Then, $A={\left(a_{ij}\right)}_{N\times N}$ is a symmetric and irreducible matrix, whose eigenvalues are

$0={\lambda }_1>{\lambda }_2\ge {\lambda }_3\ge \cdots \ge {\lambda }_N$ [28] . It has been proved that under certain assumptions the synchronized state (26) is exponentially stable if

$c\ge \left|d/{\lambda }_2\right|$ (27)

where d is a constant, which was further specified to be $h_{\max }$ , the maximal Lyapunov exponent of an individual n-dimensional chaotic dynamical system [27] .

Given the dynamics of an isolated vertex, the synchronizability of network (24) with respect to a specific coupling configuration A is said to be strong if the network can synchronize with a small coupling strength c. Inequality (27) implies that the synchronizability of network (24) can be characterized by the second-largest eigenvalue of its coupling matrix, i.e., the smaller the second- largest eigenvalue, the stronger the synchronizability of a network.

4.2. Synchronizability of the NPG Network

For clarity, we take $m_0=m=\bar{m}$ in the construction of a NPG or BA network, and denote by $A_{np}\left(\bar{m},N\right)$ and $A_{ba}\left(\bar{m},N\right)$ the coupling matrices of the dynamical network (24) with NPG and BA topologies, respectively, which has N nodes and $\bar{m}\left(N-\bar{m}\right)$ edges. In all numerical simulation, the second-largest eigenvalue of $A_{np}\left(\bar{m},N\right)$ and $A_{ba}\left(\bar{m},N\right)$ are denoted by ${\lambda }_{2np}\left(\bar{m},N\right)$ and

${\lambda }_{2ba}\left(\bar{m},N\right)$ , respectively.

The eigenvalues are obtained by averaging the results of 10 groups of networks. Figure 5 show the value of ${\lambda }_{2ba}\left(\bar{m},N\right)$ and ${\lambda }_{2np}\left(\bar{m},N\right)$ as function of N, and find ${\lambda }_{2ba}\left(\bar{m},N\right)$ and ${\lambda }_{2np}\left(\bar{m},N\right)$ decreases to a negative constant ${\bar{\lambda }}_{2ba}\left(\bar{m}\right)$ and ${\bar{\lambda }}_{2np}\left(\bar{m}\right)$ as N increases, with $\bar{m}=3,5,7$ , respectively. In particular, as shown in Figure 5, for BA scale-free model, we get

${\bar{\lambda }}_{2ba}\left(\bar{m}\right)\approx -1.2329,-2.8758,-4.6110$ for $\bar{m}=3,5,7$ , respectively. And in Figure 5 we have ${\bar{\lambda }}_{2np}\left(\bar{m}\right)\approx 2,4,6$ of the NPG network for $\bar{m}=3,5,7$ , respectively. That implies the synchronizability of the NPG network is much stronger than that of the BA scale-free network.

Recently, X. F. Wang et al. proposed a model of synchronization-optimal growing network [12] . In their model, when a new node is added to the network, the criterion for choosing the m vertices to which the new vertice connects is to

optimize the synchronizability of the obtained network, namely, in order to allow the second-largest eigenvalue of the corresponding coupling matrix to be minimized. After $t\gg m_0$ time steps, a synchronization-optimal growing network is obtained with $N=m_0+t$ vertices. Its second-largest eigenvalue

${\bar{\lambda }}_{2so}\left(\bar{m}\right)=-1.9898,-3.9635,-5.8710$ for $\bar{m}=3,5,7$ respectively [12] . This indicates that the synchronizability of the NPG network is stronger than that of the synchronization-optimal growing network. What’s more, the time complexity of the algorithm of the NPG network model is much lower than that of synchronization-optimal growing network model.

We find the second-largest eigenvalue ${\bar{\lambda }}_{2np}$ of the NPG network is closer to the second-largest eigenvalue ${\lambda }_{2mc}$ ( ${\lambda }_{2mc}=-3,-5,-7$ , for $m=3,5,7$ ) of the multi-center growth model [12] . Because the topology of the NPG network is so similar to that of the multi-center network, both of them have several “hubs”.

The second-largest eigenvalues of dynamical network with BA scale-free topology, synchronization-optimal growth topology, NPG topology and multi- center topology are shown in the Table 1.

4.3. Robustness and Fragility

Clearly, when we remove some nodes in a network will change its coupling matrix. If the second-largest eigenvalue of the coupling matrix remains unchanged, namely, the synchronizability of the network will remain unchanged after the removal of a small fraction of nodes, which indicates the robustness of the synchronizability of the network. If the second-largest eigenvalue of the coupling matrix changes greatly after the removal of some its nodes, which implies the fragility of the synchronizability of the network. Now we have two ways to remove a small fraction $f$ ( $0<f\ll 1$ ) of nodes in the work: random or specific.

We let $A\in R^{N\times N}$ and $\tilde{A}\in R^{\left(N-\lceil fN\rceil \right)\times \left(N-\lceil fN\rceil \right)}$ be the coupling matrices of the original network with N nodes and the new network after removal of $\lceil fN\rceil$ nodes, respectively. The second-largest eigenvalues of $A$ and $\tilde{A}$ are denoted by ${\lambda }_2$ and ${\tilde{\lambda }}_2$ , respectively.

In the simulation, we take $N=1000$ and $m=m_0=3$ . It has been shown that even when as many as 5% of randomly chosen nodes are removed from a BA scale-free network, the new second-largest eigenvalue ${\tilde{\lambda }}_{2ba}$ will not be changed too much (Figure 6(a)). And the new second-largest eigenvalue ${\tilde{\lambda }}_{2np}$ of the NPG network remains unchanged when 5% of vertices are randomly removed. This indicates that both the BA scale-free model and the NPG model are robust against random attacks, the robustness of the NPG model is stronger, especially. However, the NPG model is more fragile to specific removal of a small fraction of nodes than a BA network (Figure 6(b)), due to the topology of the NPG network is very similar to that of the multi-center network, and the whole network is broken into isolate when several “biggest” vertices are removed.

5. Conclusion

In this paper, we have proposed the neighbor preferential mechanism and construct the neighbor-preferential growth network model. Theoretical analysis and numerical simulations show the NPG model is a scale-free small-world network model. What’s more, its power exponent will increase drastically as the edge- adding number m increases. And the NPG model can reproduce star coupled network feature and globally coupled network property, for its average path length is close to two and its clustering coefficient of is close to one. Moreover, the synchronizability of the NPG network model is much stronger than that of BA scale-free network [2] , even stronger than that of synchronization-optimal network [12] . Due to the topology of the NPG network is so similar to that of the multi-center network, the NPG model is robust against random attacks and is more fragile to specific failures. Perhaps this model helps to future understand the real-world networks. However, there are still many problems need to be further studied, for example, how to adjust the number of the “hubs”? How does the clustering coefficient change with the number of the “hubs”? How many the “hubs” in the model are more in line with the real-world networks? And so on. There questions are waiting for us to investigate.