From Single to Multilayer Networks: Understanding Network Functionality Through a Topological Perspective
Many natural phenomena and disparate social systems, from power grids to food webs to blockchains, can be described as dynamic networks. However, many essential properties of network functionality and organization can be captured only by using higher order graph characteristics. This thesis proposes novel topological and geometric methods to analyze higher order structures in complex networks in three areas:anomaly detection in dynamic single layer networks, anomaly detection in dynamic multilayer networks, and resilience analysis of critical infrastructure. First, we develop a distribution-free framework for anomaly detection by recasting a dynamic sequence of single layer networks into a univariate series of graph characterizations such as mean degree, average clustering coefficient, etc. Then, we adopt a change point detection method for (weakly) dependent time series based on efficient scores, and enhance the finite sample properties of change point method by approximating the asymptotic distribution of the test statistic using the sieve bootstrap. We apply the developed technique to a functional magnetic resonance imaging (fMRI) data from an anxiety-inducing exercise and then to the Enron communication graph, and find that our new method delivers impressively accurate and realistic results in terms of identifying locations of true change points compared to the results reported by competing approaches. In many applications, the appearance of anomalous patterns in higher order graph connectivity, such as new multi-node routes within human brain neuronal network (i.e. brain connectome), are often undetectable at earlier stages – thereby, hindering many disease preventive initiatives. Thus in the next research thrust, we introduce a novel topological technique to identify anomalous events in the sequence of dynamic multilayer blockchain networks by employing the tools of topological data analysis (TDA), in particular clique persistent homology. We represent the networks as a weighted graph, equipping them with a nested clique complexes and extract topological summaries in the form of the persistence diagrams. In addition to the novelty of our technique, we introduce a multidimensional container (which we call stacked persistence diagram) and prove its stability under input data fluctuations. We validate our new topological anomaly detection framework in application to dynamic multilayer networks from the Ethereum Blockchain and the Ripple Currency Networks. Motivated by increasing threats on power systems from various extreme events such as adverse weather and cyber/physical attacks, research on complex network resiliency and vulnerability is recently gaining a substantial traction. In this final project, we evaluate the transmission grid resilience using three local metrics devised under the framework of topological data analysis. We evaluate the performance of these metrics on a synthetic power system that is built on the footprint of the Texas power system, and compare their performance against the values reported by conventional reliability metrics. By comparing the TDA summaries with the power system reliability metrics, our findings show that local topological summaries can successfully capture changes in the grid resilience.