{'fraction_non_alphanumeric': 0.040485252140818266, 'fraction_numerical': 0.012702188392007612, 'mean_word_length': 4.312357846853677, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Probability of Stability of Synchronization in Random Networks of Mismatched Oscillators

The stability of synchronization state in networks of oscillators are studied under the assumption that oscillators and their couplings have slightly mismatched parameters. A generalized master stability function is provided that takes the mismatches into account. Using this master stability function a lower bound on the probability of synchronization is derived for regular and random network models. The probability of stability of synchronization is then used to study the phase transition behavior of the networks. Numerical examples using van der Pol oscillators are used to illustrate the results and verify the validity of the analysis. Moreover, the synchronization trend as a function of statistics of mismatches in the coupling and local dynamics is investigated using this numerical example.


I. INTRODUCTION
The problem of synchronization in a network of identical oscillators was first introduced by Wiener [1], [2]. Pursuit of the idea by Winfree in his pioneering work [3] led to this problem being recognized as being important and relevant in many fields of research including biology, physics, and engineering [4]. More recently, the introduction of the framework of master stability function by Pecora and Carroll [5], enabled the investigation of the impacts of network structure and the dynamical properties of individual nodes on the stability of the synchronization state [5], [6]. Following the idea of using master stability function to study the network of oscillators, most efforts have been concentrated on the impact of the topology (structure) of different types of networks on the stability of the synchronization state: In [5], the short and long wavelength bifurcation phenomena have been studied on regular networks (lattices). Other works look at linking the topological properties such as minimum, maximum and average node degrees, to the stability of the synchronization state in networks [6]- [9]. Due to the interesting properties of small-world networks, which have been introduced in the seminal work of Watts and Strogatz [10], [11], most of the following studies were focused on the small-world and scalefree networks. It has been shown that due to better dynamical flow (efficient communications), the synchronization can be stabilized more easily in small-world networks compared to regular networks [2], [8], [12]. It has also been shown that the synchronizability of networks improves in homogeneous networks in contrast to heterogeneous ones [13].
Although the study of the synchronization of networks of the identical nodes appears to be matured, few attempts have been made to study networks with nonidentical nodes or couplings. The experiments reported in [14] suggest that in the networks where the oscillator dynamics and their couplings vary slightly from each other, the oscillators can be nearly synchronized. That is, the states converge to the vicinity of a certain trajectory (synchronization manifold). In [15] and [16], a sensitivity analysis of synchronization have been performed for a network of mismatched oscillators. It has been shown that near-synchronization behavior can occur in a network of mismatched oscillators using master stability function. The general stability of the synchronization in network of dynamical systems with nonidentical dynamics for each node is studied in [17] and [18] using the Lyapunov direct method. In [19], an approximate master stability function is proposed and the coupling strength is optimized to achieve "best synchronization properties".
In this paper, we investigate the synchronization of a network of mismatched oscillators with mismatched couplings. Our formulation also allows the consideration of uncertainties in network link weights, thus generalizing [16] in addition to its main contributions. Since in presence of mismatch there is no unique synchronization state in the network, we use the concept of ε-synchronization [15], where the steady states of the nodes in the network fall into an ε-neighborhood of a certain trajectory (synchronization manifold). We then use a generalized master stability function to study the behavior of the network around the synchronization state. The proposed generalized master stability function bounds the oscillator states to a neighborhood of average synchronization trajectory as a function of Lyapunov exponents of the dynamical network. These Lyapunov exponents, in turn, are related to eigenvalues of the Laplacian matrix of the network. We then provide a probabilistic treatment of synchronization behavior in terms of mismatch parameters for regular and random network models. We calculate probability of stability of synchronization, and use it to investigate phase transitions of the synchronization in the network as the network and node parameters vary. Finally, we verify our analytical results by a numerical example for a network of van der Pol oscillators [20] with mismatched oscillators and couplings.

II. NOTATION AND MAIN VARIABLES
The set of real (column) n-vectors is denoted by R n and the set of real m×n matrices is denoted by R m×n . We refer to the set of non-negative real numbers by R + . Matrices and vectors arXiv:1407.7273v1 [math.DS] 27 Jul 2014 are denoted by capital and lower-case bold letters, respectively. Identity matrix is shown by I. The Euclidean (L 2 ) vector norm is represented by · . When applied to a matrix, · denotes the L 2 induced matrix norm, A = λ max (A T A). Table I summarizes the main variables used.
Coupling function from node j to node i u i Input vector for node i Fx Jacobian of vector f with respect to x Fγ Jacobian of vector f with respect to γ Hx Jacobian of coupling vector h with respect to x Hy Jacobian of coupling vector h with respect to y H θ Jacobian of coupling vector h with respect to θ III. SYSTEM DESCRIPTION Consider a network of N oscillators, indexed by N = {1 · · · N }. Assume that the dynamics of each isolated oscillator is governed bẏ where x i ∈ R n and γ i ∈ P ⊆ R p are the state and parameter vectors of local dynamics of node i, respectively. P denotes the set of possible parameter vectors, and f : R n+p → R n describes the local dynamics of an isolated node.
The dynamics of coupled oscillators are given aṡ where θ ij ∈ Q ⊆ R q is the parameter vector of coupling dynamics from node j to node i, Q denotes the set of possible parameter values for couplings. The adjacency matrix of the network is A = [a ij ], where a ij ∈ R + is the weight of the link from node j to node i. There is no connection if a ij = 0. Note that we allow the more general case of directed and wighted networks. Moreover, h : R 2n+q → R n models the coupling from node j to node i. We assume that h(x, y, θ) is Hamiltonian. That is, we assume that H x = −H y , where H x and H y denotes the Jacobians of h(x, y, θ) with respect to x and y, respectively. This is a very general assumption and encompasses the diffusive coupling model predominantly used in the literature [13], [16], [19], where it is assumed that Note that this generalized model also incorporates uncertainties in the adjacency matrix of the network, A = [a ij ] + [δa ij ], considered in [16], by absorbing δa ij into θ ij , i.e., IV. INVARIANT SYNCHRONIZATION MANIFOLD Let s be a weighted average of the trajectories of all oscillators where i∈ N α i = 1. Define the deviation of the trajectory of oscillator i from s as Moreover, let L = [l ij ] be the Laplacian matrix of the network [21], Proof: Taking derivative of (2) yieldṡ is the weighted average in-degree of the network. Linearization of (4) around (s,γ,θ) results iṅ where H x and H θ are Jacobians of h with respect to its first and third variable, respectively. Recalling that i∈ N α i = 1, we haveṡ For s to be an invariant manifold, the last term in the above equation must be zero. This is achieved if α i are chosen to satisfy Equation (5), in turn, will be satisfied if j ∈ N (a ij α j − a ij α i ) = 0 for all i ∈ N , which in matrix form can be represented as That is, α is a null vector of L T .
Remark 1. We note that, by definition, L has zero row sum. Thus, it is singular. Consequently, L T always has a null vector, α. This means that any network has at least one invariant manifold.

Remark 2.
If the the network is connected, the invariant synchronization manifold is unique. This is due to the fact that for connected networks the nullity of L is one. Thus, α and, therefore, s are unique.
Remark 3. In the special case where the network is undirected, L is symmetric. Thus, it also has zero column-sum.
is its null vector, and the invariant manifold, s, is the simple average of the trajectories.
With α i chosen such that s is an invariant manifold, we haveṡ where s(0) and x(0) are initial states.

V. GENERALIZED MASTER STABILITY FUNCTION
In this section we introduce a master stability function which generalizes those in [15] and [16] by taking into account the parameter mismatch in the links and applies to directed and weighted networks.
As it has been shown in previous section, every connected network has a unique invariant manifold. Hence, we can define ε-synchronization as This definition means that the error from the manifold is contained in a ball of radius ε. We note that our definition is different but closely related to that given in [18].
Substituting (1) and (2) in (3), and using Taylor series, the dynamics of the error with respect to the synchronization manifold, e i , is given bẏ where 1 X is the indicator function of X. Stacking (7) for all i yields the dynamics of the deviation of node trajectories from s:ė and a i is the ith row of A.
Let L = PJP −1 be the Jordan decomposition of L, where P = [p ij ] is a similarity transform and J is in Jordan form. Then, (8) can be rewritten aṡ . Using the similarity transform where and q ij are the elements of Q = P −1 . It is clear that stability of η and e are equivalent.
To study the stability of (9), let us first consider the simpler case where J consists of a single Jordan block, i.e.
where φ m satisfies For any Laplacian matrix, we have µ M = 0. If the network is connected, we further have n M = 1. Thus, which together with (11) yields lim sup t→∞ e 2 ≤ P 2 Lemma 2 upper bounds the right hand side of (12) by the left hand side of (10).

Corollary 1. A symmetric network of oscillators is ε-
where φ j satisfies Proof: Since L is symmetric, it can be diagonalized by unitary matrix P = U = [u ij ], where U H U = I. Thus, each Jordan block will be of size 1. This means that M = N , n m = 1, and J(i) = i. Thus, (10) reduces to Remark 4. In proof of Corollary 1, since unitary transformation preserves Euclidean norm, (12) holds with equality. Thus, Corollary 1 is relatively less conservative than Theorem 1.

VI. PROBABILITY OF STABILITY
In the remaining of the paper, we make the following assumptions: This implies that L is diagonalizable by a unitary matrix, Assumption 2. Mismatch parameters, δγ i and δθ ij , are independent zero mean Gaussian random vectors with covariance matrices, Under Assumption 2, v i are linear combination of independent Gaussian random variables. Thus, they are jointly Gaussian. To calculate the probability of (13) being satisfied, we need to find the probability density function of Proof: See Appendix B.
We now provide upper bounds on the probability of stable synchronization for unweighted regular, Erdös-Rényi, and Newman-Watts networks.
Theorem 2. Under Assumptions 1 and 2, the probability of stable synchronization of an unweighted K-regular network of oscillators is lower bounded by where P (·, ·) is the regularized gamma function, Proof: Since the network is unweighted and K-regular, we have d i = N k=1 a 2 ik = K. According to Lemma 3 the blocks of the covariance matrix, Σ v , are Hence, v i are uncorrelated. The mean value of v i can be computed as which follows noting that δγ i and δθ ij have zero mean and d in = K. Since v i are jointly Gaussian, uncorrelated, and have zero mean, they are independent. Now, let us define the whitened Gaussian random vectors The last equality is due to the fact that with the whitening of v i , z i is no longer time variable. In other words, z i is a random variable (not a random process). Since z i 2 is the norm squared of a white Gaussian n-vector, it has a chisquared distribution with n degrees of freedom. Applying the result of Corollary 1, where σ is defined in (15  . which using the results in [22] yields (14).
Theorem 3. Under Assumptions 1 and 2, the limiting probability of stable synchronization of an unweighted Erdös-Rényi (ER) network of oscillators, with parameter p, as N → ∞, is lower bounded by Proof: The largest eigenvalue of the Laplacian matrix of any symmetric network is bounded below by the maximum degree of the network. For large ER networks (N → ∞), it is also bounded above by N p + N p(1 − p) [8]. Thus Similarly, the smallest non-zero eigenvalue of ER network can be bounded as According to Lemma 3, the diagonal blocks of covariance matrix of v are as N → ∞, and the off diagonal entries are Therefore, Consequently, as N → ∞, v i become independent. The remaining of the proof is similar to that of Theorem 2 and is omitted in the interest of brevity.
To study the synchronization in small-world networks, we consider the Newman-Watts model [11]. This model constructs a small-world network by starting from a K-regular ring network (Fig. 1) as substrate, then randomly adds new links with probability p.

Proof: The Laplacian matrix of a Newman-Watts small world network is
where L Ring and L ER are the laplacians of a K-regular ring and an Erdös-Rényi network with parameter p. Using Weyl's inequalities we can bound the minimum and maximum eigenvalues of the small-world [21] max{µ Ring where the eigenvalues of a K-regular ring is [21] µ Ring and subscripts min and max refer to smallest non-zero and maximum eigenvalue of L in corresponding configurations, respectively. The remaining of the proof is similar to that of Theorem 3 and is omitted in the interest of brevity.

VII. NUMERICAL EXAMPLE
In this section we verify our analytical results using numerical examples. We consider the van der Pol oscillator [20] which has the following dynamics We note that since the van der Pol oscillator has a limit cycle, as t → ∞, s is a periodic trajectory. Hence, the Jacobians are also periodic. We can, therefore, solve (6) analytically using Fourier series [20]. We assume that the nodes are coupled through their first states by Thus, the Jacobians of f(.)and h(.) around (s,γ,θ) are , Fig. 2 depicts the maximum Lyapunov exponent of F x − µH x as a function of µ, where µ is the eigenvalue of Laplacian matrix of the network. Furthermore, It is clear that v i are independent of δθ ij1 . Also, covariance matrix of v i of a K-regular ring network forγ = 1 can be calculated from (16) as where sup((1−s 2 1 )s 2 ) 2 is determined by simulation to be 9.93 and the supremums are calculated over one period of the limit cycle. Hence, σ = max( √ Kθ 1 σ θ2 , 3.15σ γ ). Now, consider a 6-regular ring network of size N = 100, where γ ∼ N (1, 0.01) and θ ∼ N ([1 0] T , 0.01I). Fig. 3 depicts the synchronization manifold, s, and a sample trajectory,  x 1 , converging to s. Fig. 4 presents the analytical lower bound on the probability of stable ε-synchronization in the considered ring network, as a function of σ θ2 and σ γ for ε = 0.40. As it can be seen, the probability of synchronization falls sharply as the variances of mismatches increase. Moreover, we observe that the range of σ γ and σ θ2 for which the network is stable with high probability is rectangular. This is explained by noting that σ is related to the maximum of σ γ and σ θ2 , as it can be seen in (19). Another observation from Fig. 4 is that even small mismatches leads to instability of the synchronization state even with a relatively large tolerance of ε = 0.40.
We now proceed to compare a ring network, an Erdös-Rényi network and a Newman-Watts (small-world) network. For a fair comparison, we choose the network parameters such that all networks have the same number of nodes and the same average node degree. That is, we consider a N = 100 node, 10-regular ring, an Erdös-Rényi network with N = 100 and randomness parameter p = 0.1, and a Newman-Watts network generated from a N = 100 node, 6-regular ring and link addition probability p = 0.4 × 100/94 = 0.4167. Fig. 5 presents the probability of stability versus network size, N , for these three networks with ε = 0.4. As it can be seen for the Ring network ( Fig. 5 (a)), as N increases, even though the variance of the mismatch input is constant, σ = 3.15σ γ , the ε-synchronization of the network deteriorates. This is because as the degree of the nodes are kept constant and network size increases, the algebraic connectivity 1 of the network, µ ring N −1 = k − 2 sin(kπ/2N ) cos((k + 2)π/2N ) sin(π/N ) , decreases. For large N , in our example, smaller algebraic connectivity means smaller MLE (See Fig. 2), hence the probability of ε-synchronization falls sharply. Fig. 5 (b) presents the probability of ε-stability of the Erdös-Rényi network. It is interesting to note that since the network is disconnected for smaller network sizes, the network is not synchronized. As network size continues to grow, the network becomes connected and synchronization behavior emerges. This behavior continues until the growth in the network size, increases the variance of the mismatch input, v, to the extent that the network falls out of ε-stability. Fig. 5 (c) presents the probability of ε-stability for the Newman-Watts network. It is interesting to note the mechanisms at work as N increases: At first, when N is small there are very few added links given a small value of p. Thus, the network has not yet transitioned into a small-world and its algebraic connectivity is still quite close to that of the ring topology. Thus, as the size of the network increases its second smallest eigenvalue decreases. Since the variance of mismatch, v, is constant (σ b = 3.15σ γ ), the probability of stability decreases. As N continues to increase, by adding links in random, sufficient number of long range connections are established and the small-world transition is achieved. Consequently, algebraic connectivity of the network starts to grow rapidly. Hence, λ i increase and, therefore, P LB stab improves. As N continues to increases √ K + N pσ θ2 overtakes 3.15σ γ in the variance of mismatch and its destructive effect surpasses the improvement caused by transition to small-world. Consequently, we observe that P LB stab begins to drop. Figs. 6 (a) through (c) depict the probability of ε-stability as a function of ε in the considered Ring, Erdös-Réyni, and Newman-Watts networks for different N andd: (a) N = 100,d = 10, (b) N = 200,d = 10, and N = 200,d = 20. As it can be seen, the analytical lower bound and the simulation result for the ring network are reasonably close. This is due to the homogeneity of its node degrees, i.e. d i = K, which holds true for the other networks as N approaches infinity. The other point directly observed from these figures is that the rise in the probability of the stability is much sharper in the Erdös-Réyni and Newman-Watts networks, this is because the spread of the spectrum, [µ min , µ max ], for these networks are smaller than that of ring topology. This, in fact, causes the Lyapunov exponents of the traverse modes to be closer to each other and hence the networks become easily and rapidly synchronized. Other interesting observation is that the results for the Erdös-Réyni and Newman-Watts networks are similar. The reason can be sought in the effectiveness of communication in both networks to each other. As it has been shown in [10], even though small-worlds are strongly locally connected (due to  ring substrate), they have almost the same average shortest path length of Erdös-Réyni networks. This results in almost the same communication efficiency in small-worlds as Erdös-Réyni network. Hence, the synchronizability of both types of networks are similar.

VIII. CONCLUSION
We had seen that mismatch in either couplings or the local dynamics does not allow perfect synchronization. Rather, the network can only be synchronized to a neighborhood of the synchronization manifold. Considering this relaxed notion of synchronization we have provided a generalized master stability function that takes the mismatches into account. We then used this master stability function to derive lower bounds on the probability of synchronization in regular, Erdös-Rényi, and Newman-Watts networks. We verified our results using numerical examples involving networks of van der Pol oscillators. These examples clearly shows the different phase transition behavior of the different network models.

APPENDIX B COVARIANCE OF v
The covariance of v is