Random graphs

Analysis of different networks from regular to random using the Watts-Strogatz27 or Barabási-Albert28 models would be the first step in assessing synchronizability. But the graph generation algorithms proposed in those methods are better suited for realistic large networks whereas our interest is in small graphs with finer control on randomness. (Results using these algorithms are presented later in the text). We propose an algorithm to generate graphs of varying connectivity (see Methods) where (p=1) implies a fully connected graph (high mean-degree) and (p=0) gives a sparsely connected graph (low mean-degree). Examples of graphs generated with 10 nodes and varying (P) is shown in Fig. 2. The strength of connectivity between any node pair is equal.

Figure 2

Connectivity reduction in small graphs. We start with a fully connected graph of size ({boldsymbol{N}}) and equal edge strength across the network ({{boldsymbol{A}}}_{{boldsymbol{ij}}{boldsymbol{,}}{boldsymbol{i}}{boldsymbol{ne }}{boldsymbol{j}}}{boldsymbol{=}}{boldsymbol{1}}). Picking each edge at random, the edge is removed with probability ({boldsymbol{1}}{boldsymbol{-}}{boldsymbol{p}}). If removing the edge makes the graph disconnected, the action is reversed. We repeat the process of selection for removal for ({boldsymbol{N}}) cycles.

For stronger connectivity, the AP synchronized solution quickly becomes unstable as shown in Fig. 3. The results reveal that regardless of connectivity, the probability of antiphase solution decreases to zero with increasing network size.

Figure 3

Effect of connectivity with network size on anti-phase synchronization. Probability of anti-phase synchronization reduces with network size and with degree of connectivity in random graphs. When connectivity is low, AP synchronization is stable for larger sizes. Differences in stability between odd and even sizes are evident. Fully connected even-sized networks are easier to synchronize as partitioning in to two groups is easier than fully connected odd-sized networks odd-sized networks. The odd-even effect reduces with decreasing connectivity.

To confirm that the results hold for established random graph generation algorithms as well, we now look at networks generated using the Barabási-Albert algorithm and Watts-Strogatz algorithm.

Barabási-Albert model

Many “real world” networks such as citation networks, the world wide web, and biological networks have hubs and have a ‘scale-free’ (power-law) nature. The Barabási-Albert28 algorithm generates graphs with growth and preferential attachment resulting in a scale free graph. Although the algorithm typically produces its power-law characteristics for large (N), we apply it here to generate small network sizes. For a network of size (N), the algorithm is seeded with a network of ({m}_{0}) nodes and (N-{m}_{0}) nodes are added sequentially where each node connects to (m) existing nodes, with a preference to form links to nodes with a higher degree (rich-get-richer paradigm). For (m=1), the B-A algorithm produces graphs close to the star topology, as the preferential attachment for the hub would mean that every new node has a high chance of forming a link to the hub. We set (m=2) for more variation in the degree distribution, seeding the algorithm with ({m}_{0}=2,{rm{A}}=[1,0{rm{;}}0,1]) and ({m}_{0}=3,{rm{A}}=[0,1,0{rm{;}}1,0,1{rm{;}}0,1,0]). The probability as shown in Fig. 4 agree with our main result.

Figure 4

Results with alternative random-graph algorithms. Networks generated using the Barabási-Albert (BA) algorithm and the Watts-Strogatz (WS) algorithm are shown for different parameter values. The WS networks generated were generated from ({boldsymbol{k}}={boldsymbol{1}}) and ({boldsymbol{k}}={boldsymbol{2}}) connected nearest neighbors on each side initially. The plots are for networks in the small-world region of ({boldsymbol{p}}={boldsymbol{0}}{boldsymbol{.}},{boldsymbol{5}}). The BA algorithm was used to generate networks starting from ({{boldsymbol{m}}}_{{boldsymbol{0}}}={boldsymbol{2}}) nodes and adding each node connected to ({boldsymbol{m}}) existing nodes. Typically, ({{boldsymbol{m}}}_{{boldsymbol{0}}}={boldsymbol{m}}), which is the m = 2 case shown here. It drops to zero very quickly. The ({boldsymbol{m}}={boldsymbol{1}}) case remains very similar to the star topology as each new node only forms one link most probably to the same node. This allows for a higher probability of synchronization up to higher network sizes.

Watts-Strogatz model

Watts and Strogatz showed that many real world networks have a ‘small-world’ nature27, where the networks display a low average path length while maintaining a high-clustering coefficient. The WS algorithm starts with a ring of nodes connected to (k) nearest neighbors on each side and randomly rewires each edge with probability ({p}_{{WS}}). Graphs generated using (k=1) typically have long chains with few branches. This allows for better AP Sync. However, this would not be realistic. Setting  (k=2) and simulating networks from ({p}_{{WS}}=0) to ({p}_{{WS}}=1), we find the same overall result. The results in the small-word regime at ({p}_{{WS}}=0.5) are shown in Fig. 4. Both WS and BA model achieve AP synchronization for low connectivity, confirming our result. The real-world nature of these networks indicates that clustering into two groups may be present in real networks with repulsive interactions and low connectivity.

Symmetry and distance effects

Although the general classical network models adopt random graphs, it has been shown that symmetry is ubiquitous in real world networks29 which may allow for AP synchronization. Homogeneous coupling is obviously symmetric to any degree, but networks with heterogeneous coupling can have degrees of symmetry as well. The simplest case is when the oscillator coupling strengths are mirrored about a plane, forming two symmetric groups. The coupling matrix (A) is bisymmetric in this case. Allowing mirror symmetry enhances AP synchronization, P(AP-Sync) slightly for higher (N) as shown in Fig. 5. Creating a plane of separation in the graph by setting the cross-diagonal elements of (A) close to 0, has an impact on increasing AP synchronization. Along with symmetry, this enhances the ability of the network to AP synchronize as shown in Fig. 5. But regardless of these additional structural incentives, AP synchronization appears to vanish beyond approximately 20.

Figure 5

Effects of structure – symmetry and distance of coupling. The color matrices are plotted using the adjacency matrices of the networks, where the color represents the edge strength between nodes ({rm{i}}) and ({rm{j}}). Since the networks are undirected, all matrices are symmetric about the main diagonal. Symmetry in the network implies the adjacency matrix is bisymmetric (last row). The results show that symmetry enhances AP synchronization slightly. Coupling is varied as a function of distance for initially homogeneous (Reg) and random networks (see Methods). The star topology and regular cases give perfect AP synchronization regardless of network size. For random networks, nearest neighbor coupling allows the best chances of AP synchronization. As the interaction persists longer over distance, probability of AP synchronization reduces.

A clear demarcation into two structural groups would allow antiphase synchronization at large network sizes given enough time. A network with a star topology is a simple example where AP synchronization is possible for arbitrarily large network size (Fig. 5). But as expected, one of the clusters has only one node – the hub – and all other nodes are in the antiphase cluster.

Distance is another structural parameter that may influence the formation of opposing clusters. In real networks, interaction levels (measured by edge strength, ({A}_{{ij}})) may decrease with distance. An inverse-square and inverse-linear dependence on distance was placed on fully connected graphs with homogenous and random edge strengths (see Methods). For the network resulting from the homogeneous case, AP synchronization is achieved at arbitrary sizes, given enough time, similar to the star-topology case. However, for the random case, our central result holds, the probability of AP synchronization vanishes above 20. Nearest-neighbour coupling allows AP synchronization to persist for slightly larger network sizes. (Fig. 5).

Presence of both attractive and repulsive coupling

Setting the range of ({A}_{i,j}) to ([-mathrm{1,1}]) while (phi =0) allows incorporation of both attractive and repulsive coupling in the network. The presence of attractive coupling does not change the overall result; we find a non-monotonic curve as the network size increases for some cases (Fig. 6). I.e. there is a preference for antiphase synchronization over in-phase synchronization for moderate network sizes.

Figure 6

Simultaneous presence of attractive and repulsive coupling. For the more general case of arbitrary direction of coupling, the overall result presented holds, however a regime of preference for AP synchronization is observed.

The addition of attractive coupling does not de-stabilize the system drastically for moderate network sizes. The upper bounds on network size remain effectively unchanged. This can be attributed to the tendency of attractive oscillators to join the corresponding antiphase clusters.

Non-identical oscillators

Allowing a normal distribution (σ = 0.05) in the natural frequency of the oscillators makes the size limits on the network more stringent. The probability of AP sync vanishes with lower network sizes than their corresponding identical-frequency case for all structural cases (Fig. 7).

Figure 7

Effect of normally distributed frequency. Further generalization of the analysis to normally distributed frequencies of oscillators reduces the limit at which AP sync can be observed.

Since most real-world systems would be composed of non-identical oscillators, this result implies that AP synchronization is rarely stable beyond very small network sizes in real systems. The inhomogeneity of the oscillators may be the decisive factor over the coupling topology for AP synchronization in real networks.

Source link

Leave a Reply

Your email address will not be published. Required fields are marked *