A tool for filtering information in complex systems

Abstract

We introduce a technique to filter out complex data sets by extracting a subgraph of representative links. Such a filtering can be tuned up to any desired level by controlling the genus of the resulting graph. We show that this technique is especially suitable for correlation-based graphs, giving filtered graphs that preserve the hierarchical organization of the minimum spanning tree but containing a larger amount of information in their internal structure. In particular in the case of planar filtered graphs (genus equal to 0), triangular loops and four-element cliques are formed. The application of this filtering procedure to 100 stocks in the U.S. equity markets shows that such loops and cliques have important and significant relationships with the market structure and properties.

Fig. 1.

An illustrative example of two graphs that share the same MST but have distinct PMFGs. (A) MST of a simple system of 10 vertices. (B and C) PMFG of two systems with the same MST (the one drawn in A). The thicker lines are identifying links belonging to both the MST and the PMFG, whereas the thinner lines belong to the PMFG only.

Fig. 2.

PMFG obtained from the fully connected graph associated with the correlation coefficient matrix of the 100 most capitalized stocks traded in the U.S. equity markets during the time period from 1995 to 1998. Cross-correlation is computed by using daily returns of stocks. Stocks are indicated with their ticker symbols. For information about a specific ticker symbol, see Table 7, which is published as supporting information on the PNAS web site. The graph is topologically planar: It can be drawn on the plane without edge-crossings. The thicker lines belong to the associated MST. It should be noted that link lengths do not reflect the value of the similarity measure between vertices.

Fig. 3.

Analysis of stability of the MST and PMFG with respect to the statistical uncertainty present in the estimation of the correlation matrix as a function of the number of records of the multivariate time series. By assuming as reference matrix the empirical correlation matrix of the system, we perform 4 sets of 20 realizations, each one of surrogated multivariate time series. Each set is characterized by a different number of records set as follows: 1,000, 4,000, 16,000, and 64,000 records. For each of the simulated realizations, both the MST and PMFG have been constructed. The percent (1 - P) of the number of links of the simulated graphs nonmatching with the links of the MST and PMFG of real data are shown as a function of the number of records of the surrogated time series in a log–log plot. (The error bar indicates one standard deviation of 1 - P computed for each set.)