We generate time series from scale-free networks based on a finite-memory random walk traversing the network. These time series reveal topological and functional properties of networks via their temporal correlations. Remarkably, networks with different node-degree mixing patterns exhibit distinct self-similar characteristics. In particular, assortative networks are transformed into time series with long-range correlation, while disassortative networks are transformed into time series exhibiting anticorrelation. These relationships are consistent across a diverse variety of real networks. Moreover, we show that multiscale analysis of these time series can describe and classify various physical networks ranging from social and technological to biological networks according to their functional origin. These results suggest that there is a unified dynamical mechanism that governs the structural organization of many seemingly different networks. Recently, there is a growing industry in the application of network theory to study traditional nonlinear dynamical systems-possibly nonlinear time series are transformed into networks and then analyzed with various complex network tools [1] [2] [3] [4] . The transformed networks are characterized by a wide range of statistics in the complex network domain, enriching our understanding of the underlying dynamical systems. For example, recurrence networks based on the concept of recurrences in phase space allow us to characterize and classify dynamics, to detect dynamical transitions, as well as to identify invariant substructures [4] . In this sense, the network based analysis provides us with another perspective to understand the dynamical systems. While this recent work has focused on analyzing dynamical systems by constructing networks and applying tools from complex network theory, the inverse direction has been overlooked. Recently, a deterministic method has been proposed by Shimada et al. [5]: the eigenvector corresponding to the maximum eigenvalue of a network's adjacency matrix is treated as the transformed time series. In this regime, the small-world property of a network is reinterpreted as the intensity of the periodicity of the constructed time series. However, this method has very limited utility when applied to the scale-free (SF) networks. Indeed, the abundance of recent work with real networks showing scale-free features has attracted considerable attention since the seminal work of Barabási and Albert [6] . In this paper, we propose a method to transform a SF network into a nonlinear time series based on a finite-memory random walk. In contrast to the approach of Shimada, Ikeguchi, and Shigehara [5]-which, being based on eigenvectors may be considered "structural"-our approach is inherently dynamical. The network is used to define a stochastic dynamical system. Moreover, our approach can also be applied to any network and is not limited to the analysis of small-world features. We find that the constructed time series inherits nontrivial information of the underlying network. In particular, the self-similar features of the obtained time series reveal * zhao.yi@hitsz.edu.cn mixing patterns of the network. Application to real networks provides further evidence of the relationship between the mixing pattern of networks and self-similar features in the constructed time series. More significantly, we find that there is a unified dynamical mechanism hidden in various physical networks with the same function that uncovers the essential differences among social, biological, and technological networks. We start from the construction of time series for a (complex) network with N nodes. The network is fully described by a symmetric adjacency matrix A with elements a ij = 1 if nodes i and j are connected and a ij = 0 otherwise. For a scale-free network, the degree of node i given by k i = N l=1 a il follows a power-law distribution, meaning that a large majority of nodes have low degrees but a small number of nodes (known as "hubs") have high degrees. We then define a finite-memory random walk traversing the network and study its trajectory as a time series-the value of the time series at each point in time being a function of the properties of the currently visited node. The behavior of this random walk is fully described by a transition probability {π ij (t)}. At time t, a walker moves from the current node i to node j with the transition probability π ij (t), dependent on the previous visited node information such that The sign function sgn(·) equals one when τ > 0 and sgn(0) = 0. Here, k(t − 1),k(t − 2), . . . , k(t − τ ) are degrees of nodes being visited at past τ interval times. The parameter τ controls how much historical information is used at each step and further affects the trajectory of the walker. Specially, when τ = 0, the transition probability degenerates to π ij (t) = a ij /k i , which corresponds to the generic memoryless random walk on a network, previously studied in [7, 8] . In contrast, for 0 < τ < ∞, according to Eq. (1), when the walker visits high-degree node, it usually departs from the high-degree nodes for the next τ interval times on average and is then 1539-3755/2014/90(2)/022804(8) 022804-1
Later, Weng et al. REF proposed a transformation method from networks to time series based on a finite-memory random walk.
Time-series analysis of networks: Exploring the structure with random walks
Physical review. E, Statistical, nonlinear, and soft matter physics
Physical review. E, Statistical, nonlinear, and soft matter physics
Physics Medicine