Complex Networks

In 2012 we started exploring the field of Economic and Financial Networks through the prism of Graph Theory. We are still highly committed in the field with two PhD students and four graduate students working exclusively on this project. Our main goal in these research studies is to obtain a reduced version of the initial network which: a) contains an adequate amount of the total information for each goal (the amount of needed information depends on the application) and b) is more efficient easier to control and analyze. We refer to this as the representation goal. This task has been undertaken in the literature mainly through the MST approach in a variety of economic systems including stock markets (Bonanno et al, 2004; Tse et al, 2010), banking networks (Papadimitriou et al, 2013), macroeconomic networks (Hill, 1999; Gilmore et al, 2010; Dias, 2013) and others. Nonetheless, the Minimum Spanning Tree has inherent limitations that stem from its algorithmic calculation process. We investigated these limitations and proposed a more efficient methodology based on a modified Minimum Dominating Set (MDS) algorithm, a methodology mainly used in the routing of computer and communications networks. The new method is called Threshold-Minimum Dominating Set (T-MDS). By comparing these methodologies (MST, MDS and T-MDS) we can allege that the T-MDS can: a) identify the smallest subset of nodes which b) represents the whole network more efficiently than the two other alternatives.

Consider the network depicted in Figure 1. In this network, the values of the edges correspond to distances and thus nodes with more similar behavior are connected by a low distance edge and vice-versa. The similarity can be calculated using correlation based metrics, concordance based metrics or even a z-score multivariate distance.

Figure 1. The nodes, edges and distances of the initial network

Figure 2. The core nodes of the MST based method.

The MST-based approach identifies a set of four core nodes, namely nodes 2, 3, 5 and 6, to describe the behavior of the entire network. They can be used as gauges for the behavior of their neighborhood. Whenever a shift in the behavior of a core node occurs, it reflects a change in the behavior of its neighborhood. Consequently, the state of each neighborhood (and eventually of the entire network) can be represented by the core nodes, which is the basic concept of the methodology in Papadimitriou et al. (2013).

However, by closely examining the topological features of the core nodes, we observe that:

Hence, the MST-based approach “misses” some essential relations (e.g. the e25 edge), and at the same time maintains some edges that connect nodes with low similarity in the process of identifying the core nodes (e.g. the e34 edge). These are important drawbacks that could affect the efficiency of the MST-based solution to the representation goal.

Next, we apply the simple MDS methodology in the theoretical seven nodes’ network of Figure 1.

Figure 3. Minimum Dominating Set (gray nodes)

Τhe absence of the no-loop restriction, in the MDS algorithm, increases the number of the considered edges in the network, which in turn is manifested through larger neighborhoods (since more nodes remain interconnected). As the network becomes denser, fewer MDS nodes are needed to reach the representation goal. Consequently, it is more probable that the cardinality of the MDS nodes’ set will be smaller than the corresponding MST one. Indeed, by applying the MDS technique, we are able to represent the behavior of the whole network using just three nodes (one less than the MST methodology). This fact is noteworthy but not critical to our cause. We do search for a small subset of nodes, but most importantly we search for a set that best represents the entire network. The MDS nodes’ set, as opposed to the MST-based one, is a better representation of the network: all the small distance edges are included in the representative nodes’ neighborhoods. This implies that all node pairs with similar behavior are included in the neighborhoods. On the other hand though, the same is true for all the large distance edges (see in Figure 3 the edges e34, e35, e46 and e67). These edges connect nodes with dissimilar behavior and their inclusion in the MDS neighborhoods may jeopardize the representation goal. Node 4 in the example belongs to the neighborhoods of nodes 3 and 6. In both cases, the edges linking node 4 with the two representative nodes describe long distances, meaning that the node in question does not have similar behavior with the nodes that represent it. Consequently, every decision that we make for node 4 based on the behavior of nodes 3 and 6 is potentially unreliable.


Threshold-Minimum Dominating Set (T-MDS)

We suggest that the limitations of the MST-based approach and the classical MDS technique can be effectively addressed with the inclusion of one extra step prior to the identification of the MDS: the imposition of a threshold on the edges’ distances in the initial network. By doing so, we ensure that only the edges with low distance (i.e. the edges which connect nodes with high similarity) survive, while all the other edges are eliminated.

Definition: We call a Threshold – Minimum Dominating Set the two step methodology for the identification of the most representative nodes of a network, defined as:

Step 1. A thresholding on the edges’ distances leading to the elimination of all edges that correspond to large distances.

Step 2. The identification of the MDS nodes on the remaining network.

The suggested process is depicted in Figure 4. In the left part of the Figure, in Step 1 we impose a threshold of 𝑝=4 to remove any edges (depicted with the dashed lines) with distance greater than 4. Thus, we eliminate the edges that connect nodes with dissimilar behavior; this results in the isolation of nodes 3 and 6 from the rest of the network. Then, the MDS is identified on the right part of Figure 4..

Figure 4. Threshold-Minimum Dominating Set (colored nodes)

Apparently, the Minimum Dominating Set consists of only three nodes: one dominant node (node 2) and two isolated ones (nodes 3 and 6). The dominant node of the network describes the behavior of the interconnected nodes 1, 4, 5, and 7. The edges connecting each of these nodes with the dominant one represent a short distance and thus this node can successfully act as a representative agent for the neighborhood.

The Threshold-Minimum Dominating Set (T-MDS) retains the advantages of the Minimum Spanning Tree and the classical Minimum Dominating Set while overcoming their inherent limitations: it is a compact and reliable subset able to describe efficiently the topology of the entire network. Among the three presented methodologies, the T-MDS based approach yields the best solution to the representation goal. The described methodology was successfully applied using a simple computer to real world networks that include more than 4000 nodes.


Application Range

Banking networks

We used the T-MDS methodology to create an auxiliary supervision/monitoring mechanism that can be used by the banking system supervising authority, usually the central bank. This system is both efficient with respect to the required resources needed and can also promptly identify a set of banks that are in distress so that immediate and appropriate action can be taken by the supervising authority. The T-MDS is used to identify the smallest and most efficient subset of banks that can be used as a) sensors of distress of a manifesting banking crisis and b) provide a path of possible contagion. We propose the use of this method as a supplementary monitoring tool in the arsenal of a Central Bank. One dataset we used includes the 122 largest American banks in terms of their interbank loans. At threshold level of t = 0.8 our method identifies 47 T-MDS nodes, with 21 of them being isolated ones. According to this, the interconnected nodes in the thresholded network are 101, and they can be monitored by the 26 dominant nodes.


U.S. Gross State Product Synchronization

In this study we created the U.S. states’ network, based on their Gross State Product (GSP). We use it to explore the inter-relations of the GSP growth rates and the degree of their business cycle synchronization. Moreover, this approach allowed us to identify a subset of states that can efficiently describe the collective behavior of the entire network. The policy implications are obvious: the monitoring of these key states from the federal fiscal and monetary authorities may provide an alternative and efficient tool in the designing and implementation of economic policy. To do so, we used four alternative measures of similarity: correlation, weighted correlation, the sign concordance index (SCI), and the weighted sign concordance index. Both types of measures (correlations and SCI) have indicated an increased similarity between the U.S. states GSP in the more recent years, evidenced both by the T-MDS methodological analysis and the simple network metrics. In both cases the weighted versions (where the more recent GSP values received a higher weight) corresponded to denser networks in which the overall correlations are higher. Thus, this can be viewed as evidence of an increased business cycles synchronization

Figure 5. Network topology in the case of a weighted Sign Concordance Index and threshold level t=0.75 (nodes sized according to their node degree)

Another interesting result is identification and examination of crisis dispersion paths between the U.S. states. The imposition of a threshold on the network’s edges removes low strength edges and allows only for the existence of the highly important and informative ones. This procedure creates a map of GSP inter-relations that could be used as a guide for contagion in the case of a crisis manifestation in one or more U.S. states. By studying this map, policy authorities could intervene timely and effectively to contain the crisis and/or curtail its effects and further contagion.


The U.K. Consumer Price Index

During the summer of 2014, our PhD student Georgios Sarantitis was employed as a research associate at the Bank of England. His job description was exclusively to apply the T-MDS methodology on the calculation of the United Kingdom’s Consumer Price Index (CPI). He modeled the United Kingdom’s Consumer Price Index as a complex network and he applied clustering and optimization techniques to study the network’s evolution through time. By doing this, he provided a dynamic, multi-level analysis of the mechanism that drives inflation in the U.K. The analysis that we performed on our team revealed that the CPI-classes’ network exhibits an evolving topology through time which depends substantially on the prevailing economic conditions in the U.K. We identified non-overlapping communities of these U.K. CPI classes and we observed that they do not correspond to the actual categories they officially belong to; a finding suggesting that diverse forces are driving the inter-relations of the CPI classes which are stronger for classes in different categories rather than for the classes within them. Finally, we created and presented a reduced version of the U.K. CPI that fulfils all the core inflation measure criteria and can possibly be used as an appropriate measure of the underlying inflation in the U.K. Since this new measure uses only 14 out of the 85 U.K. CPI classes, it can be employed to complement the Bank of England’s arsenal of core inflation measures without the need for further resource allocation.


Income Inequality 

We investigated the developing patterns of inequality in the U.S. using complex network analysis and the Threshold-Minimum Dominating Set (T-MDS). We used two alternative measures of income inequality, the top 1% share of income and the Gini coefficient. We performed a dynamic analysis over four consecutive periods running from 1916 to 2012.

Our findings reveal a heterogeneous pattern of income inequality and economic integration of the U.S. states according to each focal period. Furthermore, the empirical findings differentiate slightly with respect to the two inequality measures employed.


Business Cycle Synchronization

We examined the issue of business cycle synchronization from a historical perspective in 27 developed and developing countries from the 1870s to the 2010s. Based on the T-MDS, our results reveal heterogeneous patterns of international business cycle synchronization during fundamental globalization periods since the 1870s. In particular, the proposed methodology reveals that worldwide business cycles decoupled during the Gold Standard, though they were synchronized during the Great Depression. The Bretton Woods era was associated with a lower degree of synchronization as compared to that during the Great Depression, while worldwide business cycle synchronization increased to unprecedented levels during the latest period of floating exchange rates and the Great Recession. This provides empirical evidence in support of lower business cycle synchronization within periods of fixed exchange rates and lack of an independent monetary policy.


References