Topological properties and fractal analysis of a recurrence network constructed from fractional Brownian motions

Homology groups of embedded fractional Brownian motion

A well-known class of nonstationary self-similar time series is the fractional Brownian motion (fBm) considered to model ubiquitous stochastic processes in nature. Due to noise and trends superimposed on data and even sample size and irregularity impacts, the well-known computational algorithm to compute the Hurst exponent (H) has encountered superior results. Motivated by this discrepancy, we examine the homology groups of high-dimensional point cloud data (PCD), a subset of the unit D-dimensional cube, constructed from synthetic fBm data as a pipeline to compute the H exponent. We compute topological measures for embedded PCD as a function of the associated Hurst exponent for different embedding dimensions, time delays, and amount of irregularity existing in the dataset in various scales. Our results show that for a regular synthetic fBm, the higher value of the embedding dimension leads to increasing the H dependency of topological measures based on zeroth and first homology groups. To achieve a reliable classification of fBm, we should consider the small value of time delay irrespective of the irregularity presented in the data. More interestingly, the value of the scale for which the PCD to be path connected and the postloopless regime scale are more robust concerning irregularity for distinguishing the fBm signal. Such robustness becomes less for the higher value of the embedding dimension. Finally, the associated Hurst exponents for our topological feature vector for the S&P500 were computed, and the results are consistent with the detrended fluctuation analysis method.

Computationally efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes

Among various algorithms of multifractal analysis (MFA) for complex networks, the sandbox MFA algorithm behaves with the best computational efficiency. However, the existing sandbox algorithm is still computationally expensive for MFA of large-scale networks with tens of millions of nodes. It is also not clear whether MFA results can be improved by a largely increased size of a theoretical network. To tackle these challenges, a computationally efficient sandbox algorithm (CESA) is presented in this paper for MFA of large-scale networks. Distinct from the existing sandbox algorithm that uses the shortest-path distance matrix to obtain the required information for MFA of networks, our CESA employs the compressed sparse row format of the adjacency matrix and the breadth-first search technique to directly search the neighbor nodes of each layer of center nodes, and then to retrieve the required information. A theoretical analysis reveals that the CESA reduces the time complexity of the existing sandbox algorithm from cubic to quadratic, and also improves the space complexity from quadratic to linear. Then the CESA is demonstrated to be effective, efficient, and feasible through the MFA results of (u,v)-flower model networks from the fifth to the 12th generations. It enables us to study the multifractality of networks of the size of about 11 million nodes with a normal desktop computer. Furthermore, we have also found that increasing the size of (u,v)-flower model network does improve the accuracy of MFA results. Finally, our CESA is applied to a few typical real-world networks of large scale.

Fractal analysis of recurrence networks constructed from the two-dimensional fractional Brownian motions

In this study, we focus on the fractal property of recurrence networks constructed from the two-dimensional fractional Brownian motion (2D fBm), i.e., the inter-system recurrence network, the joint recurrence network, the cross-joint recurrence network, and the multidimensional recurrence network, which are the variants of classic recurrence networks extended for multiple time series. Generally, the fractal dimension of these recurrence networks can only be estimated numerically. The numerical analysis identifies the existence of fractality in these constructed recurrence networks. Furthermore, it is found that the numerically estimated fractal dimension of these networks can be connected to the theoretical fractal dimension of the 2D fBm graphs, because both fractal dimensions are piecewisely associated with the Hurst exponent H in a highly similar pattern, i.e., a linear decrease (if H varies from 0 to 0.5) followed by an inversely proportional-like decay (if H changes from 0.5 to 1). Although their fractal dimensions are not exactly identical, their difference can actually be deciphered by one single parameter with the value around 1. Therefore, it can be concluded that these recurrence networks constructed from the 2D fBms must inherit some fractal properties of its associated 2D fBms with respect to the fBm graphs.

Multifractal temporally weighted detrended cross-correlation analysis to quantify power-law cross-correlation and its application to stock markets

A new method-multifractal temporally weighted detrended cross-correlation analysis (MF-TWXDFA)-is proposed to investigate multifractal cross-correlations in this paper. This new method is based on multifractal temporally weighted detrended fluctuation analysis and multifractal cross-correlation analysis (MFCCA). An innovation of the method is applying geographically weighted regression to estimate local trends in the nonstationary time series. We also take into consideration the sign of the fluctuations in computing the corresponding detrended cross-covariance function. To test the performance of the MF-TWXDFA algorithm, we apply it and the MFCCA method on simulated and actual series. Numerical tests on artificially simulated series demonstrate that our method can accurately detect long-range cross-correlations for two simultaneously recorded series. To further show the utility of MF-TWXDFA, we apply it on time series from stock markets and find that power-law cross-correlation between stock returns is significantly multifractal. A new coefficient, MF-TWXDFA cross-correlation coefficient, is also defined to quantify the levels of cross-correlation between two time series.

Fractal and multifractal analyses of bipartite networks

Bipartite networks have attracted considerable interest in various fields. Fractality and multifractality of unipartite (classical) networks have been studied in recent years, but there is no work to study these properties of bipartite networks. In this paper, we try to unfold the self-similarity structure of bipartite networks by performing the fractal and multifractal analyses for a variety of real-world bipartite network data sets and models. First, we find the fractality in some bipartite networks, including the CiteULike, Netflix, MovieLens (ml-20m), Delicious data sets and (u, v)-flower model. Meanwhile, we observe the shifted power-law or exponential behavior in other several networks. We then focus on the multifractal properties of bipartite networks. Our results indicate that the multifractality exists in those bipartite networks possessing fractality. To capture the inherent attribute of bipartite network with two types different nodes, we give the different weights for the nodes of different classes, and show the existence of multifractality in these node-weighted bipartite networks. In addition, for the data sets with ratings, we modify the two existing algorithms for fractal and multifractal analyses of edge-weighted unipartite networks to study the self-similarity of the corresponding edge-weighted bipartite networks. The results show that our modified algorithms are feasible and can effectively uncover the self-similarity structure of these edge-weighted bipartite networks and their corresponding node-weighted versions.

Dynamic-Sensitive centrality of nodes in temporal networks

Locating influential nodes in temporal networks has attracted a lot of attention as data driven and diverse applications. Classic works either looked at analysing static networks or placed too much emphasis on the topological information but rarely highlighted the dynamics. In this paper, we take account the network dynamics and extend the concept of Dynamic-Sensitive centrality to temporal network. According to the empirical results on three real-world temporal networks and a theoretical temporal network for susceptible-infected-recovered (SIR) models, the temporal Dynamic-Sensitive centrality (TDC) is more accurate than both static versions and temporal versions of degree, closeness and betweenness centrality. As an application, we also use TDC to analyse the impact of time-order on spreading dynamics, we find that both topological structure and dynamics contribute the impact on the spreading influence of nodes, and the impact of time-order on spreading influence will be stronger when spreading rate b deviated from the epidemic threshold bc, especially for the temporal scale-free networks.

Multifractal analysis of weighted networks by a modified sandbox algorithm

Complex networks have attracted growing attention in many fields. As a generalization of fractal analysis, multifractal analysis (MFA) is a useful way to systematically describe the spatial heterogeneity of both theoretical and experimental fractal patterns. Some algorithms for MFA of unweighted complex networks have been proposed in the past a few years, including the sandbox (SB) algorithm recently employed by our group. In this paper, a modified SB algorithm (we call it SBw algorithm) is proposed for MFA of weighted networks. First, we use the SBw algorithm to study the multifractal property of two families of weighted fractal networks (WFNs): "Sierpinski" WFNs and "Cantor dust" WFNs. We also discuss how the fractal dimension and generalized fractal dimensions change with the edge-weights of the WFN. From the comparison between the theoretical and numerical fractal dimensions of these networks, we can find that the proposed SBw algorithm is efficient and feasible for MFA of weighted networks. Then, we apply the SBw algorithm to study multifractal properties of some real weighted networks - collaboration networks. It is found that the multifractality exists in these weighted networks, and is affected by their edge-weights.

Visibility Graph Based Time Series Analysis

Network based time series analysis has made considerable achievements in the recent years. By mapping mono/multivariate time series into networks, one can investigate both it's microscopic and macroscopic behaviors. However, most proposed approaches lead to the construction of static networks consequently providing limited information on evolutionary behaviors. In the present paper we propose a method called visibility graph based time series analysis, in which series segments are mapped to visibility graphs as being descriptions of the corresponding states and the successively occurring states are linked. This procedure converts a time series to a temporal network and at the same time a network of networks. Findings from empirical records for stock markets in USA (S&P500 and Nasdaq) and artificial series generated by means of fractional Gaussian motions show that the method can provide us rich information benefiting short-term and long-term predictions. Theoretically, we propose a method to investigate time series from the viewpoint of network of networks.

Time lagged ordinal partition networks for capturing dynamics of continuous dynamical systems

We investigate a generalised version of the recently proposed ordinal partition time series to network transformation algorithm. First, we introduce a fixed time lag for the elements of each partition that is selected using techniques from traditional time delay embedding. The resulting partitions define regions in the embedding phase space that are mapped to nodes in the network space. Edges are allocated between nodes based on temporal succession thus creating a Markov chain representation of the time series. We then apply this new transformation algorithm to time series generated by the Rössler system and find that periodic dynamics translate to ring structures whereas chaotic time series translate to band or tube-like structures-thereby indicating that our algorithm generates networks whose structure is sensitive to system dynamics. Furthermore, we demonstrate that simple network measures including the mean out degree and variance of out degrees can track changes in the dynamical behaviour in a manner comparable to the largest Lyapunov exponent. We also apply the same analysis to experimental time series generated by a diode resonator circuit and show that the network size, mean shortest path length, and network diameter are highly sensitive to the interior crisis captured in this particular data set.

Analyzing long-term correlated stochastic processes by means of recurrence networks: potentials and pitfalls

Long-range correlated processes are ubiquitous, ranging from climate variables to financial time series. One paradigmatic example for such processes is fractional Brownian motion (fBm). In this work, we highlight the potentials and conceptual as well as practical limitations when applying the recently proposed recurrence network (RN) approach to fBm and related stochastic processes. In particular, we demonstrate that the results of a previous application of RN analysis to fBm [Liu et al. Phys. Rev. E 89, 032814 (2014)] are mainly due to an inappropriate treatment disregarding the intrinsic nonstationarity of such processes. Complementarily, we analyze some RN properties of the closely related stationary fractional Gaussian noise (fGn) processes and find that the resulting network properties are well-defined and behave as one would expect from basic conceptual considerations. Our results demonstrate that RN analysis can indeed provide meaningful results for stationary stochastic processes, given a proper selection of its intrinsic methodological parameters, whereas it is prone to fail to uniquely retrieve RN properties for nonstationary stochastic processes like fBm.

Determination of multifractal dimensions of complex networks by means of the sandbox algorithm

Complex networks have attracted much attention in diverse areas of science and technology. Multifractal analysis (MFA) is a useful way to systematically describe the spatial heterogeneity of both theoretical and experimental fractal patterns. In this paper, we employ the sandbox (SB) algorithm proposed by Tél et al. (Physica A 159, 155-166 (1989)), for MFA of complex networks. First, we compare the SB algorithm with two existing algorithms of MFA for complex networks: the compact-box-burning algorithm proposed by Furuya and Yakubo (Phys. Rev. E 84, 036118 (2011)), and the improved box-counting algorithm proposed by Li et al. (J. Stat. Mech.: Theor. Exp. 2014, P02020 (2014)) by calculating the mass exponents τ(q) of some deterministic model networks. We make a detailed comparison between the numerical and theoretical results of these model networks. The comparison results show that the SB algorithm is the most effective and feasible algorithm to calculate the mass exponents τ(q) and to explore the multifractal behavior of complex networks. Then, we apply the SB algorithm to study the multifractal property of some classic model networks, such as scale-free networks, small-world networks, and random networks. Our results show that multifractality exists in scale-free networks, that of small-world networks is not obvious, and it almost does not exist in random networks.