Complex network approach for recurrence analysis of time series


24 pages

Please download to get full document.

View again

of 24
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Complex network approach for recurrence analysis of time series
    a  r   X   i  v  :   0   9   0   7 .   3   3   6   8  v   2   [  n   l   i  n .   C   D   ]   6   O  c   t   2   0   0   9 Complex network approach for recurrence analysis of time series Norbert Marwan a , Jonathan F. Donges a,b , Yong Zou a , Reik V. Donner a,c,d ,J¨urgen Kurths a,b a  Potsdam Institute for Climate Impact Research, P.O. Box 601203, 14412 Potsdam,Germany  b Department of Physics, Humboldt University Berlin, Newtonstr. 15, 12489 Berlin,Germany  c Institute for Transport and Economics, Dresden University of Technology,Andreas-Schubert-Str. 23, 01062 Dresden, Germany  d  Graduate School of Science, Osaka Prefecture University, 1-1 Gakuencho, Naka-ku,Sakai, 599-8531, Japan  Abstract We propose a novel approach for analysing time series using complex net-work theory. We identify the recurrence matrix (calculated from time series)with the adjacency matrix of a complex network and apply measures for thecharacterisation of complex networks to this recurrence matrix. By using thelogistic map, we illustrate the potential of these complex network measuresfor the detection of dynamical transitions. Finally, we apply the proposedapproach to a marine palaeo-climate record and identify the subtle changesto the climate regime. Key words:  recurrence plot, complex networks, dynamical transitions,palaeo-climate PACS:  05.40.-a, 05.45.-a, 05.45.Tp, 91.10.Vr, 91.50.Jc 1. Introduction In many scientific disciplines, such as engineering, astrophysics, life sci-ences and economics, modern data analysis techniques are becoming increas-ingly popular as a means of understanding the underlying complex dynamics Email address:  (Norbert Marwan) Preprint submitted to Physics Letters A October 6, 2009   of the system. Methods for estimating fractal or correlation dimensions, Lya-punov exponents, and mutual information have been widely used [1, 2, 3, 4]. However most of these methods require long data series and in particulartheir uncritical application, especially to real-world data, may often lead topitfalls.In the last two decades, the method of recurrence plots has been devel-oped as another approach to describe complex dynamics [5]. A recurrenceplot (RP) is the graphical representation of a binary symmetric square matrixwhich encodes the times when two states are in close proximity (i.e. neigh-bours in phase space). Based on such a recurrence matrix, a large and diverseamount of information on the dynamics of the system can be extracted andstatistically quantified (using recurrence quantification analysis, dynamicalinvariants, etc.). Meanwhile this technique has been the subject of muchinterest from various disciplines [6] and it has been successfully applied to anumber of areas: the detection of dynamical transitions [7, 8] and synchro- nisation [9], the study of protein structures [10, 11] and in cardiac and bone health conditions [12, 13], in ecological regimes [14, 15], economical dynamics [16, 17], in chemical reactions [18] and to monitor mechanical behaviour and damages in engineering [19, 20], to name a few. It is important to empha- sise that recurrence plot based techniques are even useful for the analysisof short and non-stationary data, which often presents a critical issue whenstudying real world data. The last few years have witnessed great progress inthe development of RP-based approaches for the analysis of complex systems[5, 21, 22, 23, 24]. During the last decade, complex networks have become rather popularfor the analysis of complex and, in particular, spatially extended systems[25, 26, 27, 28]. Local and global properties (statistical measures) of complex networks are helpful to understand complex interrelations and informationflow between different components in extended systems, such as social, com-puter or neural networks [25], food webs, transportation networks, powergrids [29], or even in the global climate system [30]. The basis of complex network analysis is the adjacency matrix, representing the links between thenodes of the network. Like the recurrence matrix, the adjacency matrix isalso square, binary, and symmetric (in the case of an unweighted and undi-rected network).In fact, the recurrence matrix and the adjacency matrix exhibit a stronganalogy: a recurrence matrix represents neighbours in phase space and anadjacency matrix represents links in a network; both matrices embody a pair-2  wise test of all components (phase space vectors resp. nodes). Therefore, wemight well proceed to explore further analogies even in the statistical analysisof both the recurrence and the adjacency matrix.Quantitative descriptors of RPs have been first introduced in a heuristicway in order to distinguish different appearances of RPs [6]. We may alsoconsider to apply measures of complex network theory to a RP in order toquantify the RP’s structure and the corresponding topology of the underlyingphase space trajectory. In this (more heuristic) sense, it is actually notnecessary to consider the phase space trajectory as a network.Recently, the very first steps in the direction of bridging complex networktheory and recurrence analysis have been reported [31, 32]. In these works, the local properties of phase space trajectories have been studied using com-plex network measures. Zhang et al. suggested using cycles of the phasespace trajectory as nodes and considering a link when two cycles are rathersimilar [32, 33]. The resulting adjacency matrix can be in fact interpreted as a special recurrence matrix. The recurrence criterion here is the matchingof two cycles. A complementary approach was suggested by Xu et al. whostudied the structural shape of the direct neighbourhood of the phase spacetrajectory by a motif classification [31]. The adjacency matrix of the un-derlying network corresponds to the recurrence matrix, using the recurrencecriterion of a fixed number of neighbours (instead of the more often usedfixed size of the neighbourhood [5]).Other approaches for the study of time series by a complex network anal-ysis suggested using linear correlations [34] or another certain condition onthe time series amplitudes (“visibility”) [35].In this letter, we demonstrate that the recurrence matrix (analogously to[31]) can be considered as the adjacency matrix of an undirected, unweightednetwork, allowing us to study time series using a complex network approach.This ansatz on creating complex network is more natural and simple thanthe various suggested approaches [33, 34, 35]. Complex network statistics is helpful to characterise the local and global properties of a network. Wepropose using these complex network measures for a quantitative descriptionof recurrence matrices. By applying these measures, we obtain additionalinformation from the recurrence plots, which can be used for characterisingthe dynamics of the underlying process. We give an interpretation of thisapproach in the context of the dynamics of a phase space trajectory. Nev-ertheless, many of these measures neither have an analogue in traditionalRQA nor in nonlinear time series analysis in a wider sense, and hence, open3  up new perspectives for the quantitative analysis of dynamical systems. Weillustrate our approach with a prototypical model system and a real-worldexample from the Earth sciences. 2. Recurrence plots and complex networks A recurrence plot is a representation of recurrent states of a dynamicalsystem in its  m -dimensional phase space. It is a pair-wise test of all phasespace vectors  x i  ( i  = 1 ,...,N,x  ∈ R m ) among each other, whether or notthey are close: R i,j  = Θ( ε  −  d ( x i ,x  j )) ,  (1)with Θ( · ) being the Heaviside function and  ε  a threshold for proximity [5].The closeness  d ( x i ,x  j ) can be measured in different ways, by using, e.g.,spatial distance, string metric, or local rank order [5, 36]. Mostly, a spatial distance is considered in terms of maximum or Euclidean norm  d ( x i ,x  j ) =  x i  −  x  j  . The binary recurrence matrix  R  contains the value one for allclose pairs   x i  −  x  j   < ε . A phase space trajectory can be reconstructedfrom a time series  { u i } N i =1  by time delay embedding [37] x i  = ( u i ,u i + τ  ,...,u i + τ  ( m − 1) ) ,  (2)where  m  is the embedding dimension and  τ   is the delay.The resulting matrix  R  exhibits the line of identity (the main diagonal) R i,i  = 1. Using a spatial distance as the recurrence criterion, the RP issymmetric. Small-scale features in a RP can be observed in terms of diagonaland vertical lines. The presence of such lines reflects the dynamics of thesystem and is related to divergence (Lyapunov exponents) or intermittency[7, 12, 24]. Following a heuristic approach, a quantitative description of RPs based on these line structures was introduced and is known as recurrencequantification analysis (RQA) [6]. We use the following two RQA measures(a comparable study using other measures can be found in [12]).Similarly evolving epochs of the phase space trajectory cause diagonalstructures parallel to the main diagonal. The length of such diagonal linestructures depends on the predictability and, hence, the dynamics of thesystem (periodic, chaotic, stochastic). Therefore, the distribution  P  ( l ) of diagonal line lengths  l  can be used for characterising the system’s dynamics.Several RQA measures are based on  P  ( l ). However, here we focus only on4  the maximal diagonal line length, L max  = max  { l i } N  l i =1  ,  (3)where  N  l  =  l ≥ l min P  ( l ) is the total number of diagonal lines. For thedefinition of a diagonal line, we use a minimal length  l min  [5]. The lengthof diagonal lines corresponds to the predictability time. In particular, thecumulative distribution of the line lengths can be used to estimate the cor-relation entropy  K  2 , i.e. the lower limit of the sum of the positive Lyapunovexponents [5]. Hence the inverse of   L max  gives a first rough impression of thedivergence (Lyapunov exponent) of the system.Slowly changing states, as occurring during laminar phases (intermit-tency), result in vertical structures in the RP. Therefore, the distribution P  ( v ) of vertical line lengths  v  can be used to quantify laminar phases oc-curring in a system. A useful measure for quantifying such laminar phasesis the ratio of recurrence points forming vertical structures to all recurrencepoints, LAM   =  N v = v min vP  ( v )  N v =1  vP  ( v ) ,  (4)which is called laminarity [5].Now let us consider the phase space vectors as nodes of a network andidentify recurrences with links. An undirected and unweighted network isrepresented by the binary adjacency matrix  A , where a connection betweennodes  i  and  j  is marked as  A i,j  = 1. Excluding self-loops, we obtain  A  fromthe RP by removing the identity matrix, A i,j  =  R i,j  −  δ  i,j ,  (5)where  δ  i,j  is the Kronecker delta. Removing the identity is not a problem,as this is also done in the analysis of RPs (e.g. when considering a Theilerwindow for RQA) [5]. Henceforth, we regard the recurrence matrix (withapplied Theiler window) to be an adjacency matrix. Note that this way eachstate vector in phase space is represented by one distinct node; even if twotime-separated state vectors are identical, they are identified with two differ-ent nodes (which are perfect neighbours and therefore linked independentlyof the threshold  ε ; such nodes are also called twins [38]).Local and global properties of a network are statistically described bycomplex network measures based on the adjacency matrix  A i,j . To illustrate5
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks