Complex systems can, to a first approximation, be characterized by the fact that their dynamics emerging at the macroscopic level cannot be easily explained from the microscopic dynamics of the individual constituents of the system. This property of complex systems can be identified in virtually all natural systems surrounding us, but also in many social, economic, and technological systems. The defining characteristics of complex systems imply that their dynamics can often only be captured from the analysis of simulated or observed data. Here, we summarize recent advances in nonlinear data analysis of both simulated and real-world complex systems, with a focus on recurrence analysis for the investigation of individual or small sets of time series, and complex networks for the analysis of possibly very large, spatiotemporal datasets. We review and explain the recent success of these two key concepts of complexity science with an emphasis on applications for the analysis of geoscientific and in particular (palaeo-) climate data. In particular, we present several prominent examples where challenging problems in Earth system and climate science have been successfully addressed using recurrence analysis and complex networks. We outline several open questions for future lines of research in the direction of data-based complex system analysis, again with a focus on applications in the Earth sciences, and suggest possible combinations with suitable machine learning approaches. Beyond Earth system analysis, these methods have proven valuable also in many other scientific disciplines, such as neuroscience, physiology, epidemics, or engineering.
