PaperlayerView exact revision on arXiv

Source-linked AI summary

Recurrence networks - A novel paradigm for nonlinear time series analysis

Reik V. Donner, Y. Zou, Jonathan F. Donges, Norbert Marwan, Juergen Kurths

arXiv:0908.3447v1nlin.CD

TL;DR

The paper addresses limitations in existing methods for transforming time series into complex networks. It interprets recurrence matrices as network adjacencies and derives how recurrence-network topology relates to invariant phase-space density. The resulting descriptors complement recurrence quantification analysis while remaining insensitive to temporal ordering.

  • Problem

    Existing time-series-to-network methods can have methodological limitations, lack generality, and lack direct links between local time-series properties and network topology.

  • Method

    The paper constructs unweighted, undirected recurrence networks by interpreting recurrence matrices based on mutual phase-space distances as adjacency matrices.

  • Results

    Recurrence-network topological measures are interpreted in terms of local density, geometrical proximity, phase-space fragmentation, and spatial filling, yielding complementary quantitative characteristics for RQA.

  • Takeaways & Limitations

    Recurrence networks provide a unifying framework applicable to univariate and multivariate time series, with or without embedding and with non-equidistant time scales.

  • Takeaways & Limitations

    Because time ordering is lost, recurrence networks reflect invariant phase-space density and generally cannot distinguish deterministic chaotic dynamics from stochastic dynamics.

Abstract

from arXiv · show

This paper presents a new approach for analysing structural properties of time series from complex systems. Starting from the concept of recurrences in phase space, the recurrence matrix of a time series is interpreted as the adjacency matrix of an associated complex network which links different points in time if the evolution of the considered states is very similar. A critical comparison of these recurrence networks with similar existing techniques is presented, revealing strong conceptual benefits of the new approach which can be considered as a unifying framework for transforming time series into complex networks that also includes other methods as special cases. It is demonstrated that there are fundamental relationships between the topological properties of recurrence networks and the statistical properties of the phase space density of the underlying dynamical system. Hence, the network description yields new quantitative characteristics of the dynamical complexity of a time series, which substantially complement existing measures of recurrence quantification analysis.

1. Introduction

Recurrence plots provide a single-trajectory basis for studying dynamical systems, while recurrence networks reinterpret their matrices as network adjacencies. This framework addresses limitations of existing time-series network methods and links network topology to phase-space properties and recurrence quantification.

  • Motivation: Recurrence analysis studies repeated phase-space states and can visualize them from a single trajectory through recurrence plots.The time series is represented using reconstructed phase-space points, with recurrences defined by a threshold distance.
  • Existing recurrence analysis: RQA characterizes dynamic complexity through statistical properties of diagonal and vertical recurrence-plot lines.Common measures include line-length maxima, means, and Shannon entropy, but many are sensitive to embedding parameters that can induce spurious correlations.
  • Existing recurrence analysis: Recurrence matrices preserve fundamental invariant properties, including correlation dimension D2 and correlation entropy K2, independently of embedding parameters.The recurrence plot also preserves topologically relevant phase-space information sufficiently to reconstruct a time series, modulo rescaling of its probability distribution function.
  • Recurrence networks: The paper proposes interpreting a recurrence matrix as the adjacency matrix of an unweighted, undirected complex network.The construction links observational states according to their mutual phase-space proximity and produces a spatial network embedded in the reconstructed phase space.
  • Recurrence networks: Recurrence networks offer a unifying alternative to time-series network methods whose vertices and edges may lack a direct dynamical interpretation.The paper presents a critical review of existing approaches before developing the recurrence-network framework and its topological interpretation.
  • Recurrence networks: Network-theoretic descriptors can quantify higher-order statistical properties of the invariant phase-space density and provide complementary measures within RQA.The framework reinterprets recurrence-network topology in terms of phase-space properties of the underlying dynamical system.

2. Approaches for transforming time series into complex networks - A comparative review

The review compares several ways to transform time series into complex networks, identifying limitations in how vertices, edges, and topology relate to dynamical systems. Recurrence and fixed-distance neighbourhood approaches provide more direct phase-space interpretations than many alternatives.

  • Approaches reviewed: Existing approaches include symbolic coarse-graining, cycle networks, correlation networks of embedded state vectors, visibility graphs, and neighbourhood networks in phase space.Table 1 summarizes how these methods define vertices and edge criteria.
  • Coarse-graining of phase space: Coarse-graining can lose information about small-amplitude variations because observations near opposite sides of class boundaries may be assigned to different classes.Its network properties depend on both class widths and the specific class definitions.
  • Cycle networks: Cycle networks are difficult to apply when oscillations are non-phase-coherent or contain multiple time scales, and cycle correlations also depend on sampled cycle lengths.These factors complicate the direct interpretation of network properties.
  • Correlation networks of embedded state vectors: Correlation networks require sufficiently large embedding dimensions for reliable coefficient estimates, potentially losing short-term dynamics and introducing embedding-related spurious correlations.The cited standard error is approximately m^-1.
  • Visibility graphs: Visibility graphs are restricted to univariate time series and lack a straightforward interpretation of their convexity constraint in phase-space terms.Their networks can nevertheless distinguish between different types of systems.
  • Neighbourhood relations in phase space: Fixed-number nearest-neighbour networks keep vertex degrees constant and therefore do not directly reveal local phase-space geometry, whereas fixed-distance neighbourhoods make degree centrality informative about local phase-space density.The fixed-number construction may also produce a nonsymmetric adjacency matrix and partially directed network.

3. Quantitative assessment of recurrence networks

Recurrence networks provide a dynamically meaningful framework for converting time series into complex networks, preserving local phase-space relationships and supporting analyses with or without embedding.

  • Existing time-series network methods can define vertices and edges artificially, without a direct link to local properties of the underlying time series.
  • Recurrence networks identify the recurrence matrix with a network adjacency matrix, making vertices represent states and edges indicate phase-space proximity within threshold ǫ.
  • Metric-distance recurrences can construct networks from individual states without embedding, but this discards time ordering and makes deterministic and stochastic dynamics difficult to distinguish.
  • The framework applies to univariate and multivariate time series, with or without oscillatory components, and with or without embedding.
  • The approach relates network vertices, edges, and paths to phase-space structure, enabling local, intermediate, and global topological measures as complementary RQA quantities.

3.1. Local network properties

Local recurrence-network measures connect vertex-level topology to local phase-space density, while recurrence rates and degree distributions provide density-related descriptors across scales.

  • 3.1.1. Degree centrality (local recurrence rate).: Degree centrality counts a vertex’s directly connected neighbours, and normalising by N −1 yields local connectivity.
  • 3.1.3. Correspondence of measures.: Table 3 organizes recurrence-network measures by corresponding phase-space properties across local, intermediate, and global scales.
  • 3.1.1. Degree centrality (local recurrence rate).: Local connectivity corresponds to the local recurrence rate RRv and estimates the phase-space density near state xv.
  • 3.1.2. Edge density (global recurrence rate).: The recurrence rate equals the correlation integral C2(ǫ), which is commonly used to estimate the correlation dimension D2.
  • 3.1.2. Edge density (global recurrence rate).: Local recurrence rates correspond, in the infinite-time limit, to the invariant measure of phase-space balls Bǫ(xv), linking edge density to correlation dimension.

3.2. Intermediate scale network properties

Intermediate-scale recurrence-network measures characterize neighbourhood structure, density heterogeneity, and continuity of the invariant phase-space density through clustering, neighbour degrees, and assortativity.

  • 3.2.1. Clustering coefficient.: The clustering coefficient measures connection density among a vertex’s neighbours and quantifies their local cliquishness.
  • 3.2.2. Global clustering coefficient.: For a fixed dynamical system and phase-space density, the global clustering coefficient is asymptotically determined by threshold ǫ, the resolution scale.
  • 3.2.3. Mean nearest neighbour degree.: A vertex’s degree measures immediate-neighbourhood density, whereas its mean nearest-neighbour degree measures density in the next topological shell.
  • 3.2.3. Mean nearest neighbour degree.: The local degree anomaly combines these measures to characterize local density anomalies and phase-space heterogeneity.
  • 3.2.3. Mean nearest neighbour degree.: Positive degree anomalies indicate local density maxima, negative anomalies indicate minima, and average absolute anomaly measures overall spatial heterogeneity.
  • 3.2.4. Assortativity.: Positive assortativity occurs when density varies little within an ǫ-ball, so the assortativity coefficient reflects continuity of the phase-space density.
  • 3.2.5. Matching index.: The matching index measures neighbourhood overlap; it generally decreases with spatial distance and can remain positive for unconnected vertices when distance exceeds ǫ but is below 2ǫ.

3.3. Global network properties

Global recurrence-network properties describe geometric relations among phase-space states rather than the system’s temporal evolution. Path-based measures quantify distances, proximity, and fragmentation on the network, with direct geometric interpretations in phase space.

  • 3.3.1. Shortest path length: Shortest path lengths count the minimum number of unit-length edges between vertices, while discarding the temporal order of observations.In the periodic example, nine time iterations separate vertices 1 and 10, but their network shortest path has length l_1,10 = 3.
  • 3.3.1. Shortest path length: The recurrence matrix and network adjacency matrix are equivalent, so network paths represent phase-space distances between recurrent states in units of the threshold ǫ.Different shortest paths can connect the same pair of nodes, as illustrated by three paths of length l_1,7 = 3 in the aperiodic example.
  • 3.3.2. Average path length: Average path length L is bounded below by the mean phase-space separation and geometrically approximates geodesic distances along the attractor’s network backbone.The lower-bound relation follows from the triangular inequality and the interpretation of graph edges as ǫ-sized steps.
  • 3.3.3. Diameter: The network diameter provides an ǫ-based upper bound for the estimated phase-space attractor diameter.This connects the maximum shortest path in the recurrence network with the largest estimated distance across the attractor.
  • 3.3.4. Closeness centrality: Closeness centrality is high when a state reaches most other vertices through few ǫ-jumps, and geometrical closeness bounds its topological counterpart.Thus, centrality measures encode average geometric proximity rather than temporal importance.
  • 3.3.5. Betweenness centrality: High vertex or edge betweenness identifies sparse phase-space regions separating denser clusters, indicating attractor fractionation at the resolution set by ǫ.Vertex betweenness is not interpreted as information transfer in recurrence networks; its meaning is geometric.

4. Examples

The paper evaluates recurrence-network measures on chaotic maps and oscillators, showing how threshold-dependent topology reflects phase-space density, geometry, and invariant structures.

  • Model systems: The examples use the Hénon map, Rössler system, and Lorenz system, with no additional embedding for the continuous systems.Temporal correlations between subsequent observations in the continuous systems are excluded by removing all sojourn points.
  • Threshold dependence: The average path length L exhibits the theoretically expected inverse dependence on the threshold ǫ.The figures examine L, clustering C, and assortativity R as functions of ǫ using the maximum norm.
  • Threshold dependence: For intermediate thresholds, the global clustering coefficient C increases approximately linearly, whereas very small thresholds can disconnect finite-sample recurrence networks.The detailed dependence remains system-specific.
  • Threshold dependence: At small ǫ, recurrence networks are highly assortative because neighboring phase-space regions have weak density variation and similar degrees.As ǫ grows, larger regions with varying density are included, reducing this local similarity.
  • Local network properties: Degree centrality follows local phase-space density, with dense regions such as the Lorenz scroll merger showing higher degree values.The reported visualization uses a recurrence rate RR = ρ ≈ 0.03, while smaller ǫ is needed to reveal local fine structure.
  • Local network properties: Closeness centrality is high near the attractor’s phase-space centre of gravity and low in regions far from that centre.The clustering coefficient captures higher-order density characteristics beyond degree centrality and also depends on neighborhood spatial filling.
  • Local network properties: Clustering profiles can reveal invariant objects, including regions near the Hénon stable manifold and trapping regimes of unstable periodic orbits in continuous systems.Finite-size effects prevent this correspondence from appearing in every phase-space region, and nearby UPOs may merge when separated by less than ǫ.
  • Local network properties: Betweenness centrality is sensitive to local attractor fragmentation, with high values at sparse regions separating dense clusters and low values near many outer boundaries.The limit ǫ → 0 could not be explored because of numerical limitations.

4.4. Spatial distributions of edge properties

Edge-level recurrence-network measures reveal how intermittent dynamics organize phase-space distances, neighborhood overlap, and geometric bottlenecks.

  • Logistic-map example: The logistic-map example uses an intermittent chaotic regime, where extended square recurrence patterns correspond to mutually connected vertices from nearby successive states.The example is specified at a = 3.679, with ǫ = 0.015σx and N = 1000.
  • Matching index: As phase-space distance d_i,j approaches zero, the matching index μ_i,j approaches one; as d_i,j approaches 2ǫ, μ_i,j approaches zero.During laminar phases, states remain close and matching is high; near termination, chaotic variation increases distance and lowers matching.
  • Edge betweenness: Edge betweenness behaves oppositely to matching index during intermittency, increasing near laminar-phase termination as state variation grows.During laminar phases, alternative shortest connections distribute flow across many edges, producing low edge betweenness.
  • Edge betweenness: Average edge betweenness in rarely visited low-density regions may exceed that in high-density regions by orders of magnitude.These isolated high-betweenness edges identify phase-space regions between intervals of higher density.

5. Conclusions

The conclusions present recurrence networks as a unifying time-series framework whose topology can be interpreted through invariant phase-space properties, while preserving an important dynamical limitation.

  • Contribution: Recurrence networks are proposed as a unifying framework for transforming time series into complex networks, addressing limitations and limited generality in existing approaches.The framework is based on recurrence plots.
  • Scientific consequence: Because time ordering is lost, recurrence-network characteristics are dynamically invariant and can detect objects such as unstable periodic orbits or chaotic saddles.These characteristics depend on properties of the invariant density.
  • Limitation: The method cannot distinguish deterministic chaotic systems from stochastic systems, although additional embedding is proposed as a possible way to address this issue.The paper exemplifies the limitation through comparison of the Bernoulli map and uniform noise.
  • Contribution: Network measures are reinterpreted in terms of phase-space properties, including density, geometric proximity, and higher-order structure.The paper uses degree, closeness, betweenness, and clustering measures for this interpretation.
  • Open question: The relationship between local clustering coefficient and the underlying local Lyapunov exponent remains unresolved.The paper identifies this relationship as a topic for future work.
  • Relation to RQA: Recurrence networks provide a complementary view to recurrence quantification analysis because most network measures lack direct equivalents in traditional RQA, and vice versa.The two frameworks may therefore be useful in different situations.

Appendix A. Clustering coefficient of recurrence networks for one-dimensional maps

For one-dimensional maps, computing the recurrence-network clustering coefficient requires system-specific integrals that can be expressed and sometimes evaluated analytically.

  • Analytical computation: Computing the clustering coefficient requires solving system-specific integrals.For one-dimensional maps on [0, 1], these integrals can be explicitly expressed and eventually evaluated analytically.

Appendix A.1. General treatment

The appendix derives local and global clustering coefficients by evaluating probability integrals over carefully chosen phase-space regions. Because three-point relationships are not independent, the integration boundaries must explicitly account for their geometric constraints.

  • Local clustering is computed from integrals over neighborhoods of a vertex at phase-space position x_v.The formulas are written piecewise according to the vertex position and threshold range.
  • The denominator probability treats observations x_i and x_j as independent when both are connected to vertex v.
  • The numerator requires different integration boundaries because the three-point relationship among A_ij, A_vi, and A_vj violates that independence.The appendix emphasizes that correct treatment of these relationships is nontrivial.
  • The global clustering coefficient is obtained by averaging the local clustering coefficient over the full range of phase-space positions.

Appendix A.2. Bernoulli map

For the Bernoulli map, the uniform invariant density permits analytic evaluation of the recurrence-network clustering coefficients. The resulting coefficients match those of uniformly distributed noise, while boundary effects explain deviations from the interior limit.

  • The Bernoulli map has uniform invariant density p(x) ≡ 1, simplifying analytic evaluation of the clustering integrals.
  • 3/4 is the limiting local clustering coefficient for x in ]0, 1[ as ǫ → 0 and N →∞.This equals the value for one-dimensional random geometric graphs.
  • The local clustering coefficient approaches 1 near x → 0 and x → 1 independently of ǫ because of sharp attractor boundaries.
  • Recurrence-network properties cannot distinguish the Bernoulli map from stochastic data with the same uniform density.Figure A2 shows equal curves for the Bernoulli map and uniformly distributed noise.
  • Deviations from the theoretical global value 3/4 arise exclusively from boundary effects and can produce C = 1 for very large thresholds ǫ.

Appendix A.3. Logistic map for a = 4

For the logistic map at a = 4, the appendix compares numerical evaluations of the clustering integrals with recurrence-network measurements. Agreement is excellent, while boundary regions raise the global clustering coefficient as the threshold grows.

  • The logistic map at a = 4 is analyzed using its invariant phase-space density and corresponding integral expressions.
  • Symmetry under x ↦ 1 − x transforms corresponding integral terms into each other and leaves I_2^(4) invariant.This reflects the symmetry of the phase-space density p(x).
  • Numerical solutions agree excellently with recurrence-network clustering coefficients, apart from finite-time-series fluctuations.No explicit closed form is available because the remaining integrals can only be solved numerically.
  • At x = 0 and x = 1, C_v = 1 independently of ǫ, while values are nearly 3/4 inside [ǫ, 1 −ǫ].
  • Boundary intervals expand with increasing ǫ, producing larger local values there and a systematic increase in the global coefficient C.
Loading 0908.3447v1…