skip to main content

Title: Topological clustering of multilayer networks

Multilayer networks continue to gain significant attention in many areas of study, particularly due to their high utility in modeling interdependent systems such as critical infrastructures, human brain connectome, and socioenvironmental ecosystems. However, clustering of multilayer networks, especially using the information on higher-order interactions of the system entities, still remains in its infancy. In turn, higher-order connectivity is often the key in such multilayer network applications as developing optimal partitioning of critical infrastructures in order to isolate unhealthy system components under cyber-physical threats and simultaneous identification of multiple brain regions affected by trauma or mental illness. In this paper, we introduce the concepts of topological data analysis to studies of complex multilayer networks and propose a topological approach for network clustering. The key rationale is to group nodes based not on pairwise connectivity patterns or relationships between observations recorded at two individual nodes but based on how similar in shape their local neighborhoods are at various resolution scales. Since shapes of local node neighborhoods are quantified using a topological summary in terms of persistence diagrams, we refer to the approach as clustering using persistence diagrams (CPD). CPD systematically accounts for the important heterogeneous higher-order properties of node interactions within and more » in-between network layers and integrates information from the node neighbors. We illustrate the utility of CPD by applying it to an emerging problem of societal importance: vulnerability zoning of residential properties to weather- and climate-induced risks in the context of house insurance claim dynamics.

« less
; ; ; ;
Award ID(s):
1633355 1739823 2039716
Publication Date:
Journal Name:
Proceedings of the National Academy of Sciences
Page Range or eLocation-ID:
Article No. e2019994118
Proceedings of the National Academy of Sciences
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Recent advances in network science, control theory, and fractional calculus provide us with mathematical tools necessary for modeling and controlling complex dynamical networks (CDNs) that exhibit long-term memory. Selecting the minimum number of driven nodes such that the network is steered to a prescribed state is a key problem to guarantee that complex networks have a desirable behavior. Therefore, in this paper, we study the effects of long-term memory and of the topological properties on the minimum number of driven nodes and the required control energy. To this end, we introduce Gramian-based methods for optimal driven node selection formore »complex dynamical networks with long-term memory and by leveraging the structure of the cost function, we design a greedy algorithm to obtain near-optimal approximations in a computationally efficiently manner. We investigate how the memory and topological properties influence the control effort by considering Erdős–Rényi, Barabási–Albert and Watts–Strogatz networks whose temporal dynamics follow a fractional order state equation. We provide evidence that scale-free and small-world networks are easier to control in terms of both the number of required actuators and the average control energy. Additionally, we show how our method could be applied to control complex networks originating from the human brain and we discover that certain brain cortex regions have a stronger impact on the controllability of network than others.« less
  2. Abstract Understanding the mechanisms by which neurons create or suppress connections to enable communication in brain-derived neuronal cultures can inform how learning, cognition and creative behavior emerge. While prior studies have shown that neuronal cultures possess self-organizing criticality properties, we further demonstrate that in vitro brain-derived neuronal cultures exhibit a self-optimization phenomenon. More precisely, we analyze the multiscale neural growth data obtained from label-free quantitative microscopic imaging experiments and reconstruct the in vitro neuronal culture networks (microscale) and neuronal culture cluster networks (mesoscale). We investigate the structure and evolution of neuronal culture networks and neuronal culture cluster networks by estimatingmore »the importance of each network node and their information flow. By analyzing the degree-, closeness-, and betweenness-centrality, the node-to-node degree distribution (informing on neuronal interconnection phenomena), the clustering coefficient/transitivity (assessing the “small-world” properties), and the multifractal spectrum, we demonstrate that murine neurons exhibit self-optimizing behavior over time with topological characteristics distinct from existing complex network models. The time-evolving interconnection among murine neurons optimizes the network information flow, network robustness, and self-organization degree. These findings have complex implications for modeling neuronal cultures and potentially on how to design biological inspired artificial intelligence.« less
  3. Networks have been widely used to represent the relations between objects such as academic networks and social networks, and learning embedding for networks has thus garnered plenty of research attention. Self-supervised network representation learning aims at extracting node embedding without external supervision. Recently, maximizing the mutual information between the local node embedding and the global summary (e.g. Deep Graph Infomax, or DGI for short) has shown promising results on many downstream tasks such as node classification. However, there are two major limitations of DGI. Firstly, DGI merely considers the extrinsic supervision signal (i.e., the mutual information between node embedding andmore »global summary) while ignores the intrinsic signal (i.e., the mutual dependence between node embedding and node attributes). Secondly, nodes in a real-world network are usually connected by multiple edges with different relations, while DGI does not fully explore the various relations among nodes. To address the above-mentioned problems, we propose a novel framework, called High-order Deep Multiplex Infomax (HDMI), for learning node embedding on multiplex networks in a self-supervised way. To be more specific, we first design a joint supervision signal containing both extrinsic and intrinsic mutual information by high-order mutual information, and we propose a High- order Deep Infomax (HDI) to optimize the proposed supervision signal. Then we propose an attention based fusion module to combine node embedding from different layers of the multiplex network. Finally, we evaluate the proposed HDMI on various downstream tasks such as unsupervised clustering and supervised classification. The experimental results show that HDMI achieves state-of-the-art performance on these tasks.« less
  4. In this paper, we propose a supervised graph representation learning method to model the relationship between brain functional connectivity (FC) and structural connectivity (SC) through a graph encoder-decoder system. The graph convolutional network (GCN) model is leveraged in the encoder to learn lower-dimensional node representations (i.e. node embeddings) integrating information from both node attributes and network topology. In doing so, the encoder manages to capture both direct and indirect interactions between brain regions in the node embeddings which later help reconstruct empirical FC networks. From node embeddings, graph representations are learnt to embed the entire graphs into a vector space.more »Our end-to-end model utilizes a multi-objective loss function to simultaneously learn node representations for FC network reconstruction and graph representations for subject classification. The experiment on a large population of non-drinkers and heavy drinkers shows that our model can provide a characterization of the population pattern in the SC-FC relationship, while also learning features that capture individual uniqueness for subject classification. The identified key brain subnetworks show significant between-group difference and support the promising prospect of GCN-based graph representation learning on brain networks to model human brain activity and function.« less
  5. Abstract

    We develop a topological analysis of robust traffic pace patterns using persistent homology. We develop Rips filtrations, parametrized by pace, for a symmetrization of traffic pace along the (naturally) directed edges in a road network. Our symmetrization is inspired by recent work of Turner (2019Algebr. Geom. Topol.191135–1170). Our goal is to construct barcodes which help identify meaningful pace structures, namely connected components or ‘rings’. We develop a case study of our methods using datasets of Manhattan and Chengdu traffic speeds. In order to cope with the computational complexity of these large datasets, we develop an auxiliary application of themore »directed Louvain neighborhood-finding algorithm. We implement this as a preprocessing step prior to our main persistent homology analysis in order to coarse-grain small topological structures. We finally compute persistence barcodes on these neighborhoods. The persistence barcodes have a metric structure which allows us to both qualitatively and quantitatively compare traffic networks. As an example of the results, we find robust connected pace structures near Midtown bridges connecting Manhattan to the mainland.

    « less