Quasi-periodic dynamics and a Neimark-Sacker bifurcation in nonlinear random walks on complex networks
Per Sebastian Skardal



persebastian.skardal@trincoll.edu 
Department of Mathematics, Trinity College, Hartford, CT 06106, USA





We study the dynamics of nonlinear random walks on complex networks. We investigate the role and effect of directed network topologies on long-term dynamics. While a period-doubling bifurcation to alternating patterns occurs at a critical bias parameter value, we find that some directed structures give rise to a different kind of bifurcation that gives rise to quasi-periodic dynamics. This does not occur for all directed network structure, but only when the network structure is sufficiently directed. We find that the onset of quasi-periodic dynamics is the result of a Neimark-Sacker bifurcation, where a pair of complex-conjugate eigenvalues of the system Jacobian passes through the unit circle, destabilizing the stationary distribution with high-dimensional rotations. We investigate the nature of these bifurcations, study the onset of quasi-periodic dynamics as network structure is tuned to be more directed, and present an analytically tractable case of a four-neighbor ring.


02.50.Ga,05.40.Fb,05.45.-a,89.75.Hc

Quasi-periodic dynamics and a Neimark-Sacker bifurcation in nonlinear random walks on complex networks
    Per Sebastian Skardal
    July 2019
======================================================================================================





§ INTRODUCTION


Random walk dynamics have long been utilized for studying complex networks due to the vast information they provide with remarkably simple dynamics <cit.>. Examples where random walks and diffusion processes have proven useful in studying complex networks include Google's PageRank algorithm <cit.>, search and exploration <cit.>, modeling transport processes <cit.>, detection of communities and other network structures <cit.>, and finding geometric and topological embeddings <cit.>. The simplicity of typical random walk dynamics follow from the Markovian, i.e., memory-less, nature of transitions and the fact that transition probabilities (or rates) are static. The result is a linear dynamical system where, assuming the relatively mild condition of a network structure being primitive, the dynamics converge to a unique, globally-attracting fixed point or stationary distribution <cit.>. However, for the purpose of modeling more realistic scenarios where transition rules may not remain constant, the typical random walk model is too restrictive. For such cases we must relax the constraint on transition probabilities (or rates) being static, for which we expect to observe more complicated dynamics.

Here we study the dynamics of nonlinear random walks on complex networks <cit.>. Nonlinear random walks on network represent a recently formulated example of a nonlinear Markov process <cit.> where classical dynamical systems techniques can be applied to study some remarkable dynamical behaviors. In particular, we consider a continuum of discrete-time random walkers on a network and let transition probabilities depend on the current state of the system. Using a bias parameter, random walkers may preferentially be biased towards neighboring nodes that are populated by relatively many or few other random walkers. This simple paradigm may be used to model the transport of resources in different scenarios, whereby individuals or institutions may prefer to allocate their resources to other wealthy or poor individuals or institutions under more capitalistic or humanitarian values, respectively. Such inequities in transition rules might also describe qualitative tendencies in migration patterns (i.e., individuals and families moving towards or away from more populated cities), employment patterns (i.e., individuals seeking to work at larger or smaller companies or institutions), and other scenarios where individuals or units are transported with various biases.

In previous work <cit.> it was shown that nonlinear random walks on networks consist of a weakly nonlinear regime where the bias is sufficiently small in magnitude as well as two strongly nonlinear regimes where the bias is more extreme and either positive or negative. In the weakly nonlinear regime it was proven that, as in the typical linear random, a unique, globally attracting fixed point or stationary distribution exists provided that the network structure is primitive. When the bias is sufficiently positive the steady-state dynamics localize strongly to a small subset of the networks' nodes and a number of such stable states emerge, with multistability becoming more pronounced as the bias becomes larger. Finally, for sufficiently negative bias a period-doubling bifurcation occurs when the network structure is undirected, beyond which the random walk converges to a period-two with relatively large oscillation amplitudes.

In this paper we focus on the strongly nonlinear regime with negative bias. In particular, we investigate the behavior of nonlinear random walks on networks that are more and more directed. As noted above, when the network structure is undirected a period-doubling bifurcation occurs where the stationary distribution loses stability and the random walk converges to a period-two orbit. However, when the underlying network structure is directed we observe more complicated dynamics in many cases. In such cases the system still exhibits a bifurcation where the stationary distribution loses stability, however beyond this point the dynamics no longer converge to a period-two orbit, but rather to a quasi-periodic orbit. We find that these dynamics stem from the nature of the bifurcation itself, which is no longer period-doubling, but rather a Neimark-Sacker bifurcation <cit.>, marked by a pair of complex eigenvalues crossing the unit circle. Such quasi-periodic dynamics do not occur for all directed networks, but typically, only when the structure is “sufficiently” directed. That is, in typical cases a sufficiently large perturbation needs to be made to an existing undirected network structure to observe quasi-periodic dynamics, whether it be via rewiring or up/down-weighting enough links. However, in some cases the dynamics become quasi-periodic with arbitrarily small “directedness”, as we see in an example with a four-neighbor ring network where results can be obtained analytically.

The remainder of this paper is organized as follows. In Sec. <ref> we present the equations of motion and illustrate the periodic and quasi-periodic dynamics that occur on undirected and directed networks. In Sec. <ref> we illustrate the occurrence of a Neimark-Sacker bifurcation and derive the genesis of quasi-periodic orbits. In Sec. <ref> we examine the onset of quasi-periodicity. In Sec. <ref> we consider the special case of a multi-neighbor ring where results can be obtained analytically. Finally, in Sec. <ref> we conclude with a discussion of our results.



§ EQUATIONS OF MOTION AND NETWORK DIRECTEDNESS


A typical discrete-time random walk on a complex network describes the evolution of a probability vector p(t) given by

    p_i(t+1)=∑_j=1^Nπ_ijp_j(t)

or in vector form

    p(t+1)=Πp(t)

where Π is the transition matrix whose entry π_ij describes the conditional probability of moving from node j to node i in one time step given that a random walker is currently at node j. To ensure that p(t) remains a probability, i.e., p(t)∈Ω where

    Ω = {p∈ℝ^N|p_i≥0 for i=1,…,N, and ∑_i=1^Np_i=1},

we require Π to be column stochastic so that the entries are non-negative and the columns sum to one. The entries π_ij are themselves derived from the network structure using the adjacency matrix A whose entry a_ij describes the weight of the link from node j to node i. In general, A can be binary, i.e., entries take values 0 if no link exists or 1 if a link exists, or weighted, however here we will assume that no negatively weighted links exist. A network is undirected if for each link j→ i an equal and opposite link i→ j exists, so that a_ji=a_ij, or equivalently, A^T=A. An unbiased random walk on a network is described by transition probabilities π_ij=a_ij/k_j^out where k_j^out=∑_i=1^Na_ij is the out-degree of node j. A random walk can be made biased by choosing transition probabilities to preferentially route random walkers towards or away from certain nodes, e.g., based on their degree.

Here we will study nonlinear random walks on complex networks by generalizing Eq. (<ref>) so that, rather than let Π be static, it depends explicitly on the current system state, obtaining 

    p(t+1) = Π(p(t))p(t).

In the most general framework a different function f_ij can be used to define each entry of the transition matrix so that entries are given by

    π_ij(p)=a_ijf_ij(p)/∑_l=1^Na_ljf_lj(p).

Note that the mapping F(p)=Π(p)p maps probability vectors to probability vectors, i.e., F:Ω→Ω provided that the functions f_ij are positive, i.e., f_ij:Ω→(0,∞) and all nodes have positive degree. 

To model situations where random walkers are preferentially routed towards other nodes with relatively many or few other random walkers we consider the specific choice of an exponential biasing function with bias parameter α, namely defining

    π_ij(p) = a_ijexp(α p_i)/∑_l=1^Na_ljexp(α p_l),

where negative (positive) values of α correspond to biasing random walkers towards nodes that themselves have few (many) random walkers. Together, Eqs. (<ref>) and (<ref>) give the full system dynamics, which ultimately depends on the underlying network structure, encoded by the adjacency matrix A, and the bias parameter α.



Our interest here lies in the nonlinear phenomenon that arises in the strongly nonlinear regime with negative bias and the dependence on network structure, specifically directedness. Recall that for typical undirected networks a period-doubling bifurcation occurs at a critical value of the bias parameter, α=α_c, beyond which the random walk converges to a period-two orbit. To explore the effect of directedness on nonlinear random walk dynamics we consider an illustrative example. In Fig. <ref>(a) we show an undirected network (size N=8 with mean degree ⟨ k⟩=N^-1∑_i=1^Nk_i=2). In the panel below, Fig. <ref>(d), we plot the steady-state probabilities corresponding to the blue and red nodes labelled “i” and “ii” for the nonlinear random walk as a function of α. Note that a period-doubling bifurcation occurs at α_c≈-3.28 above and below which the long-term dynamics are period-one and period-two, respectively. 

Next, to explore the effect of directed network structures we consider structural modifications as follows. Interpreting each undirected link as a pair of equal and opposite directed links, we choose an undirected link at random, delete (at random) one of the directed counterparts, and create (at random) a new directed link elsewhere in the network between two previously disconnected nodes. We make three such modifications to the network illustrated in  Fig. <ref>(a), resulting in the network illustrated in Fig. <ref>(b). Each modified or new directed link is highlighted, plotted in a thick dashed curve with arrows indicating direction. Note that three modifications as described above results in six directed links in total – three resulting from deleting half of an undirected link and three new directed links. In the panel below, Fig. <ref>(e), we again plot the steady-state probabilities corresponding to the blue and red nodes labelled “i” and “ii” for the nonlinear random walk as a function of α. For the modified network the bifurcation is somewhat delayed, now occurring at α_c≈-4.50, as a period-doubling bifurcation that is qualitatively similar to the previous undirected network. 

Lastly, we make three more modification as described above to the network illustrated in Fig. <ref>(b), resulting in Fig. <ref>(c). Again we highlight each modified or new directed link is highlighted as a thick, dashed arrow. In the panel below, Fig. <ref>(f), we again plot the steady-state probabilities corresponding to the blue and red nodes labelled “i” and “ii” for the nonlinear random walk as a function of α. For this new network structure, however, the results are qualitatively different than the previous networks. A bifurcation occurs at α_c≈-5.75 where the fixed point solution loses stability, however the dynamics beyond this point are not period-two, indicating that the bifurcation is no longer period-doubling. In particular, instead of two continuous branches signifying period-two orbits, the long-term dynamics populate the area within an envelope that is similar in shape to the period-two branches observed in the previous cases. 



Numerical simulations suggest that the long-term behavior of the nonlinear random walk on the network illustrated in Fig. <ref>(c) beyond the bifurcation is generically quasi-periodic. To see this, we plot in Fig. <ref> example time series of the long-term probabilities of nodes i and ii at α=-5.76, just beyond the bifurcation. Note in particular that the time series appears to be nearly repeating itself after many iterations, but not exactly. In fact, analyzing longer time series than that shown here suggests that the dynamics are in fact not repeating themselves precisely, but returning to an arbitrarily close position over and over again, indicating quasi-periodic dynamics. (We also note here that straightforward numerical computations of Lyapunov exponents very near zero indicate that these dynamics are not chaotic.) As we will see below, this quasi-periodic behavior arises from a Neimark-Sacker bifurcation that gives rise to high-dimensional rotations in the space Ω.



§ NEIMARK-SACKER BIFURCATION AND QUASI-PERIODICITY




We now turn our attention to the bifurcations illustrated above. Regardless of the nature of the bifurcation for the specific case chosen, each such bifurcation corresponds to the loss of stability of the fixed point, i.e., stationary distribution, p^* that satisfies p^*=Π(p^*)p^*. The stability of this fixed point is governed by the eigenvalues of the Jacobian DF of the mapping F(p)=Π(p)p, given by


    DF_ij(p) = {[           ∑_k=1^Nα a_ikexp(α p_i){[∑_l=1^Na_lkexp(α p_l)]-a_ikexp(α p_i)}/[∑_l=1^Na_lkexp(α p_l)]^2p_k                                                                                                if i=j,; a_ijexp(α p_i)/∑_l=1^Na_ljexp(α p_l)-α∑_k=1^Na_ika_jkexp(α p_i)exp(α p_j)/[∑_l=1^Na_ljexp(α p_l)]^2p_k                                                                                                if i j. ].


Specifically, the fixed point p^* is stable to perturbations in the space Ω if all eigenvalues λ of DF(p^*) except for one are less than one in magnitude, i.e., satisfy |λ|<1. We note that one eigenvalue, which we denote λ_1, of DF(p^*) is always exactly one, i.e., λ_1=1, due to the conservation of probability of the mapping F(p)=Π(p)p. Thus, stability of p^* follows if all |λ_j|<1 for j=2,…,N and the bifurcation corresponding to the loss of stability occurs when, as α is decreased, one or more eigenvalues meets and then exceeds |λ_j|=1.

To illustrate the nature of the bifurcations that we observe in the nonlinear random walk on different networks, we use the example networks illustrated in Fig. <ref>(a)–(c). In particular, we investigate the spectrum of the Jacobian DF(p^*) at the bifurcation points, observed at α_c≈-3.28, -4.50, and -5.75, respectively. In Fig. <ref>(a)–(c) we plot the spectra of eigenvalues of the three cases, respectively, in the complex plane. Note that each spectrum contains exactly one eigenvalue λ_1=1, as discussed above. Ignoring this trivial eigenvalue, we highlight the critical eigenvalue(s) of maximal magnitude for each case with an additional red circle. Importantly, we see that for both cases (a) and (b) there is a single maximal eigenvalue at precisely λ=-1. This corresponds to a classical period-doubling bifurcation, as the fixed point losses stability, specifically giving rise to period-two oscillations that alternate above and below the fixed point and agreeing with the dynamics we see in Figs. <ref>(d) and (e). Case (c), however, presents a critical difference in that, rather than there being a critical eigenvalue at λ=-1, there are two complex conjugate maximal eigenvalues at λ=exp(± iθ) (with 0<θ<π), which indicates a Neimark-Sacker bifurcation <cit.>. These complex-values critical eigenvalues naturally give rise to behavior just beyond the bifurcation that does not simply oscillate in a period-two orbit, but rather rotate in a high-dimensional space. These rotations are precisely what is observed in Fig. <ref>(f), although this can be seen better from an analysis we will present below. We note that while the non-critical eigenvalues of DF(p^*) for case (b) are also complex, it is the maximal eigenvalues that give rise to dynamics just beyond the bifurcation, explaining why the dynamics from case (b) are in fact period-two.

To shed more light on the nature of the rotations that arise in the case of a Neimark-Sacker bifurcation, we consider perturbations to the fixed point of the form p(t)=p^*+δp(t), where δp(t)≪1 (where, since we are considering probability vectors, we use the ℓ^1 norm). Inserting this into the map, we have that

    p^*+δp(t+1)   =F(p^*+δp(t))
       =F(p^*)+DF(p^*)δp(t)+𝒪(δp(t)^2).

Since F(p^*)=p^* this reduces to 

    δp(t+1)=DF(p^*)δp(t)+𝒪(δp(t)^2),

from which we can see explicitly that the fixed point becomes unstable via a growing perturbation if one or more eigenvalues of DF(p^*) is larger than one in magnitude. In particular, DF(p^*) has a number of important spectral properties which we will take advantage of. Like Π(p^*), the columns of DF(p^*) sum to one, which implies two important things. First, there is always an eigenvalue λ_1=1 (whose corresponding left eigenvector is constant) and whose corresponding right eigenvector v^1 generically has a non-zero sum (and typically has all positive entries). Second, and more importantly, all other eigenvectors, i.e., eigenvectors corresponding to eigenvalues λ_i1 for i=2,,̇N, sum to zero. In particular, this implies that any perturbation δp of which we are interested that conserves the sum ∑_i=1^N(p_i+δ p_i)=1 has no component in the direction of v^1, and therefore can be written only as a linear combination of the other eigenvectors, namely 

    δp(0)=∑_j=2^Nβ_jv^j.

(Note that to ensure that δp(0)≪1 we need β_j≪1.) Inserting this into Eq. (<ref>) yields, after t time steps,

    δp(t)=∑_j=2^Nβ_jλ_j^tv^j.

In particular, when α>α_c and the stationary distribution is linearly stable the relevant eigenvalues are strictly less than one, i.e., |λ_j|<1 for j=2,…,N so that all eigenmodes in Eq. (<ref>) decay to zero as t→∞. However, when α=α_c and the first pair of complex-conjugate eigenvalues are precisely one in magnitude, the modes in the corresponding eigenvector directions do not decay. Denoting these two eigenvalues λ_2 and λ_3, where λ_3=λ_2 and v_3=v_2, we have that, for sufficiently large t, 

    δp(t)→β_2λ_2^tv_2+β_3λ_3^tv_3.

Note also that, since the perturbation δp(0) is real, we have that β_3=β_2. Since |λ_2,3|=1, we may write λ_2,3=e^± iθ, which, after inserting this into Eq. (<ref>), yields rotations of infinitesimal size given by

    δp(t)=2(μu-νw)cos(tθ)-2(μw+νu)sin(tθ),

where v_2,3=u± iw and β_2,3=μ± iν. In particular, Eq. (<ref>) reveals high-dimensional rotations in Ω that take place around the fixed point p^*. In general, provided that the argument θ/π is irrational, then since t takes only integer values the rotations described in Eq. (<ref>) yield quasi-periodic dynamics, never repeating themselves exactly, but coming arbitrarily close infinitely many times. Moreover, it can be observed numerically that decreasing α below the critical bifurcation value α_c yields similar rotational dynamics as predicted at the bifurcation α=α_c but with amplitudes that grow from an initially small perturbation and saturate due to nonlinear effects. This saturation is observed as the envelope in Fig. <ref>(f). These dynamics can be thought of as a generalization to the alternations of period-two dynamics in that, if θ is close to π the dynamics alternate, but with with a slow rotation of angle π-θ each iteration.



§ ONSET OF QUASI-PERIODICITY


The analysis presented above demonstrates how quasi-periodicdynamics emerge when the stationary state loses stability due to a Neimark-Sacker bifurcation. However, the discrete network perturbations (i.e., link rewirings) used in the previous section do little to illuminate the onset of quasi-periodicity as a transition away from periodicity. To better understand this process we consider a network model where the directedness of a network can be varied continuously. 

In this vein, we begin with an undirected, binary network of N nodes with adjacency matrix A, and we construct two additional N× N matrices B and C. Assuming A has M undirected, unweighted links, and thus 2M non-zero (one) entries, we populate both B and C with M entries of 1. Critically, each non-zero entry of B and C is opposite to a zero entry, so if b_ij=1 then b_ji=0 and if c_ij=1, then c_ji=0. Moreover, the non-zero entries of B correspond to entries where no link exist in A, i.e., a_ij=a_ji=0 and the non-zero entries of C correspond to entries where a link does exist in A, i.e., a_ij=a_ji=1. Thus, by adding B to A we introduce new directed links in spots where no link existed previously, and by subtracting C from A we remove one directed half of an undirected link initially in A. Note that since B and C contain M non-zero entries each, M new directed links are created by B and one half of each of the M originally undirected links in A are removed by subtracting C. Finally, in order to obtain a network with truly continuously-varying directedness, we consider the new adjacency matrix A(ϵ) given by

    A(ϵ)=A+ϵ(B-C),

where ϵ∈[0,1] is the directedness parameter with ϵ=0 and 1 corresponding to, respectively, the original undirected network and a new network whose directedness is maximal in the sense that no non-zero entry of A(ϵ) has an opposite non-zero counterpart and the mean-degree of A(ϵ) is conserved.



To explore the onset of quasi-periodicity we consider the undirected network illustrated in Fig. <ref>(a), giving the adjacency matrix A, along with rewiring matrices B and C that yield, at ϵ=1, the directed network illustratted in Fig. <ref>(b). (Note that the undirected network is identical to that illustrated in Fig. <ref>(a).) We then vary ϵ form zero to one, for each value slowly decreasing α as the dynamics simulated until we reach the bifurcation at α=α_c defined by the first eigenvalue or pair of eigenvalues of DF(p^*) crossing the complex unit circle. Once at the bifurcation, we then calculate the phase angle(s) θ of the critical eigenvalue(s), taking the positive angle in the range (-π,π] when eigenvalues come in complex conjugate pairs. In Fig. <ref> we show the results of this numerical exploration, plotting in panels (a) and (b) the critical bias parameter α_c and the angle of the phase off the negative real axis π-θ, respectively, as a function of the directedness parameter ϵ. In particular, we observe that when ϵ surpasses ϵ_c≈0.3625 the critical eigenvalues passing through the complex unit circle begin to come in complex-conjugate pairs with θ∈(0,π). As ϵ is continuously moved through this critical value, two real, negative eigenvalues (i.e., with θ=π) collide at λ=-1 and move off the θ=π branch into the positive and negative imaginary halves of the complex plane. For this particular example θ continues to move off away from the θ=π branch as ϵ is further increased, which appears to be typical in our other numerical explorations (not shown). Finally, since this phenomenon occurs at α=α_c, the onset of quasi-periodicity represents a codimenson-two point at (α,ϵ)=(α_c,ϵ_c).





§ SPECIAL CASE: THE FOUR-NEIGHBOR RING


We conclude by considering a case where the dynamics can be described analytically. In particular, we consider the case of a four-neighbor ring, i.e., a ring where each of the N nodes is connected to each of its two nearest neighbors on each side. (We chose the four-neighbor ring so that the network is primitive, which is not the case for the typical two-neighbor ring.) To generate a directed network structure we introduce a parameter ϵ that weights the links with a chosen orientation. In particular, indexing the nodes in order around the ring, we let a_ij=1+ϵ if i=j+1 or j+2, a_ij=1-ϵ if i=j-1 or j-2, and otherwise a_ij=0.

We now perform a linear stability analysis by seeking the eigenvalues of the Jacobian DF(p^*), whose eigenvalue equation DF(p^*)v=λv implies, for all i=1,…,N,

    λ v_i=∑_j=i-4^i+4DF_ijv_j,

where periodic indexing N+k↦ k and -k↦ N+1-k is assumed. Moreover, since nodal in- and out-degrees are identical for throughout the network we have that the stationary distribution is given by the constant vector p^*=1/N, yielding entries of DF(p) given by

    DF_ij(p^*)={[         -α(1-ϵ^2)/16N             if j=i-4,;        -2α(1-ϵ^2)/16N             if j=i-3,;  (1-ϵ)/4-α(1-ϵ^2)/16N             if j=i-2,; (1-ϵ)/4-2α(1+ϵ^2)/16N             if j=i-1,;        α/N(1-1+ϵ^2/4)               if j=i,; (1+ϵ)/4-2α(1+ϵ^2)/16N             if j=i+1,;  (1+ϵ)/4-α(1-ϵ^2)/16N             if j=i+2,;        -2α(1-ϵ^2)/16N             if j=i+3,;         -α(1-ϵ^2)/16N             if j=i+4. ].

The rotational symmetry and periodic nature of the eigenvector equations suggest that eigenvectors come in the form of v_j=exp(ijϕ) for ϕ=2π k/N for wavenumbers k=0,…,N-1. Inserting this into Eq. (<ref>) yields the following explicit formula for the eigenvalue λ:


    λ   =∑_j=-4^4DF_i,i+jexp(ijϕ)=α/N(1-1+ϵ^2/4)
       -α(1-ϵ^2)/16Ne^-4iϕ-2α(1-ϵ^2)/16Ne^-3iϕ+[(1-ϵ)/4-α(1-ϵ^2)/16N]e^-2iϕ+[(1-ϵ)/4-2α(1+ϵ^2)/16N]e^-iϕ
        + [(1+ϵ)/4-2α(1+ϵ^2)/16N]e^iϕ + [(1+ϵ)/4-α(1-ϵ^2)/16N]e^2iϕ -2α(1-ϵ^2)/16Ne^3iϕ-α(1-ϵ^2)/16Ne^4iϕ.


Thus, Eq. (<ref>) gives an eigenvalue λ for each ϕ=2π k/N for k=0,…,N-1, thereby providing the full eigenvalue spectrum for DF(p^*). Thus, a linear stability analysis can be done for any four-neighbor ring of size N by decreasing α until the first single or pair of eigenvalues given by Eq. (<ref>) surpasses |λ|=1 and then inspecting the properties of the resulting critical eigenvalue(s).





In Fig. <ref> we plot the results from numerical simulations of a four-neighbor ring of size N=10 with directedness parameters ϵ=0.05 and 0.5 in panels (a) and (b), respectively. at each value of α we simulate through a transient of 10^4 iterations and plot the resulting probabilities for a randomly chosen node (since all nodes are topologically equivalent) for the next 16 iterates. The results appears very similar for the two cases, except for the “streakyiness” present for ϵ=0.05. This can be explained by inspecting spectrum of the Jacobian at the bifurcation, which for the two cases occurs at α_c≈-6.415 and -6.432, respectively, according to our predictions using Eq. (<ref>). In Fig. <ref> we plot the spectrum DF(p^*) for each case in panels (a) and (b), respectively. The critical eigenvalues, circled in red, are in fact all complex, however for ϵ=0.05 they lie just off of the negative real axis (π-θ≈ 0.00919), indicating that the dynamics are comprised of a slow rotation about an alternation. For ϵ=0.5 the angle off of the negative real axis is significantly greater (π-θ≈0.0919), yielding rotations that are not nearly as slow, thereby filling a larger amount of space in the 16 iterations plotted in Fig. <ref>. In panels (c) and (d) we zoom-in on the critical eigenvalues for a better view (and to ensure that the eigenvalues for ϵ=0.05 are in fact complex).



Lastly, we inspect the overall system dynamics as a function of ϵ by plotting in Figs. <ref>(a) and (b), respectively, the critical bifurcation value α_c and the angle of the critical eigenvalue off the negative real axis π-θ as the directedness ϵ is increased. Most notably, the angle offset π-θ differs from zero for any non-zero directedness value, indicating that the onset of quasi-periodicity actually does occur at ϵ=0. This is unlike the example network used above (see Fig. <ref>) where the onset occurred at a finite value of ϵ.



§ DISCUSSION


In this paper we have investigated the dynamics that arise in nonlinear random walks on complex networks as network topologies become more and more directed. In particular, we have shown that the loss of stability of the stationary distribution may give rise to quasi-periodic dynamics if the network structure is sufficiently directed. This is in contrast to undirected networks and some “weakly” directed networks where this bifurcation gives rise to period-two orbits via a period-doubling bifurcation. In particular, the quasi-periodic dynamics observed for directed network arises from a Neimark-Sacker bifurcation where, rather than a single eigenvalue passing through -1, a pair of complex conjugate eigenvalues pass through the unit circle, giving rise to high-dimensional rotations about the unstable stationary distribution.

We have also investigated the onset of quasi-periodicity in terms of tuning the directedness of a network. In particular, at the onset we see that the Neimark-Sacker bifurcation occurs as two real-valued eigenvalues have angle close to π, which manifest in alternations with a slow rotation. Finally we showed that in some cases analytical results are attainable, for instance the four-neighbor ring analyzed above.







plain
99
Noh2002PRL J. D. Noh and H., Rieger, Random walks on complex networks, Phys. Rev. Lett. 92, 118701 (2004).
Masuda2017PR N. Masuda, M. A. Porter, and R. Lambiotte, Random walks and diffusion on networks, Phys. Rep. 716-717, 1 (2017).

Brin1998 S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine. In: Computer Networks and ISDN Systems. Proc. of the Seventh International World Wide Web Conference, 30, 107 (1998).
Page1999 L. Page, S. Brin, R. Motwani, and T. Winograd, The pagerank citation ranking: bringing order to the web. Technical Report 1999-66, Stanford InfoLab (1999).
Gleich2015SIAM D. F. Gleich, Pagerank beyond the web, SIAM Rev. 57, 321 (2015).

GomezGardenes2008PRE J. Gómez-Gardeñes and V. Latora,  Entropy rate of diffusion processes on complex networks, Phys. Rev. E 78, 065102(R) (2008).
Sinatra2011PRE R. Sinatra, J. Gómez-Gardeñs, R. Lambiotte, V. Nicosia, and V. Latora, Maximal-entropy random walks in complex networks with limited information, Phys. Rev. E 83, 030103(R) (2011).

Gorenflo2002 R. Gorenflo, F. Mainardi, D. Moretti, G. Pagnini, and P. Paradisi, Discrete random walk models for space–time fractional diffusion, Chem. Phys. 284, 521 (2002).
Nicosia2017PRL V. Nicosia, P. S. Skardal, A. Arenas, and V. Latora, Collective phenomena emerging from the interactions between dynamical processes in multiplex networks, Phys. Rev. Lett. 118, 138302 (2017).

Rosvall2008PNAS M. Rosvall, and C. T.  Bergstrom, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. 105, (2008).
Asllani2018PRL M. Asllani, T. Carletti, F. Di Patti, D. Fanelli, and F. Piazza, Hopping in the crowd to unveil network topology, Phys. Rev. Lett. 120, 158301 (2018).

Coifman2005PNAS R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, Geometric diffusion as a tool for harmonic analysis and structure definition of data: Diffusion maps, Phys. Rev. Lett. 102, 7426 (2005).

 Durrett R. Durrett and R. Durrett, Essentials of Stochastic Processes (Springer, Berlin, 2016).
 MacCluer2000SIAM C. R. MacCluer, The many proofs and applications of Perron’s theorem, SIAM Rev. 42, 487 (2000).
 
 Skardal2019JNS P. S. Skardal and S. Adhikari, Dynamics of nonlinear random walks on complex networks, J. Nonlinear Sci. 29, 1419 (2019).
 
 Kolokoltsov2010 V. N. Kolokoltsov, Nonlinear Markov Processes and Kinetic Equations (Cambridge University Press, Cambridge, 2010).
Frank2013 T. Frank, Strongly nonlinear stochastic processes in physics and the life sciences, ISRN Math. Phys. 2013,149169 (2013).

Sacker2009 R. J. Sacker, Introduction to the 2009 re-publication of the `Neimark-Sacker bifurcation theorem', J. Differ. Equ. Appl. 15, 753 (2009).
Kuznetsov2010 Y. A. Kuznetsov, Elements of Applied Bifurcation Theory (Springer, New York, 2010)




















