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 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.

 
more » « less
Award ID(s):
1633355 1739823 2039716
NSF-PAR ID:
10229487
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Proceedings of the National Academy of Sciences
Date Published:
Journal Name:
Proceedings of the National Academy of Sciences
Volume:
118
Issue:
21
ISSN:
0027-8424
Page Range / eLocation ID:
Article No. e2019994118
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Virtual water flows are used to map the indirect water consumption connections implied by the supply chain of a city, region, or country. This information can be used to manage supply chains to achieve environmental policy objectives and mitigate environmental risks to critical supply chains. A limitation of prior work is that these flows are typically analyzed using monolayer networks, which ignores crucial intersectoral or interlayer couplings. Here, we use a multilayer network to account for such couplings when analyzing blue virtual water flows in the United States. Our multilayer network consists of 115 different regions (nodes), covering the entire conterminous United States; 41 coupled economic sectors (layers); and ∼2 × 107possible links. To analyze the multilayer network, we focus on three fundamental network properties: topological connectivity, mesoscale structure, and node centrality. The network has a high connectivity, with each node being on average connected to roughly 2/3 of the network's nodes. Interlayer flows are a major driver of connectivity, representing ∼54% of all the network's connections. Five different groups of tightly connected nodes (communities) characterize the network. Each community represents a preferred spatial mode of long‐range virtual water interaction within the United States. We find that large (populous) cities have a stronger influence than small ones on network functioning because they attract and recirculate more virtual water through their supply chains. Our results also highlight differences between the multilayer and monolayer virtual water network, which overall show that the former provides a more realistic representation of virtual water flows.

     
    more » « less
  2. INTRODUCTION A brainwide, synaptic-resolution connectivity map—a connectome—is essential for understanding how the brain generates behavior. However because of technological constraints imaging entire brains with electron microscopy (EM) and reconstructing circuits from such datasets has been challenging. To date, complete connectomes have been mapped for only three organisms, each with several hundred brain neurons: the nematode C. elegans , the larva of the sea squirt Ciona intestinalis , and of the marine annelid Platynereis dumerilii . Synapse-resolution circuit diagrams of larger brains, such as insects, fish, and mammals, have been approached by considering select subregions in isolation. However, neural computations span spatially dispersed but interconnected brain regions, and understanding any one computation requires the complete brain connectome with all its inputs and outputs. RATIONALE We therefore generated a connectome of an entire brain of a small insect, the larva of the fruit fly, Drosophila melanogaster. This animal displays a rich behavioral repertoire, including learning, value computation, and action selection, and shares homologous brain structures with adult Drosophila and larger insects. Powerful genetic tools are available for selective manipulation or recording of individual neuron types. In this tractable model system, hypotheses about the functional roles of specific neurons and circuit motifs revealed by the connectome can therefore be readily tested. RESULTS The complete synaptic-resolution connectome of the Drosophila larval brain comprises 3016 neurons and 548,000 synapses. We performed a detailed analysis of the brain circuit architecture, including connection and neuron types, network hubs, and circuit motifs. Most of the brain’s in-out hubs (73%) were postsynaptic to the learning center or presynaptic to the dopaminergic neurons that drive learning. We used graph spectral embedding to hierarchically cluster neurons based on synaptic connectivity into 93 neuron types, which were internally consistent based on other features, such as morphology and function. We developed an algorithm to track brainwide signal propagation across polysynaptic pathways and analyzed feedforward (from sensory to output) and feedback pathways, multisensory integration, and cross-hemisphere interactions. We found extensive multisensory integration throughout the brain and multiple interconnected pathways of varying depths from sensory neurons to output neurons forming a distributed processing network. The brain had a highly recurrent architecture, with 41% of neurons receiving long-range recurrent input. However, recurrence was not evenly distributed and was especially high in areas implicated in learning and action selection. Dopaminergic neurons that drive learning are amongst the most recurrent neurons in the brain. Many contralateral neurons, which projected across brain hemispheres, were in-out hubs and synapsed onto each other, facilitating extensive interhemispheric communication. We also analyzed interactions between the brain and nerve cord. We found that descending neurons targeted a small fraction of premotor elements that could play important roles in switching between locomotor states. A subset of descending neurons targeted low-order post-sensory interneurons likely modulating sensory processing. CONCLUSION The complete brain connectome of the Drosophila larva will be a lasting reference study, providing a basis for a multitude of theoretical and experimental studies of brain function. The approach and computational tools generated in this study will facilitate the analysis of future connectomes. Although the details of brain organization differ across the animal kingdom, many circuit architectures are conserved. As more brain connectomes of other organisms are mapped in the future, comparisons between them will reveal both common and therefore potentially optimal circuit architectures, as well as the idiosyncratic ones that underlie behavioral differences between organisms. Some of the architectural features observed in the Drosophila larval brain, including multilayer shortcuts and prominent nested recurrent loops, are found in state-of-the-art artificial neural networks, where they can compensate for a lack of network depth and support arbitrary, task-dependent computations. Such features could therefore increase the brain’s computational capacity, overcoming physiological constraints on the number of neurons. Future analysis of similarities and differences between brains and artificial neural networks may help in understanding brain computational principles and perhaps inspire new machine learning architectures. The connectome of the Drosophila larval brain. The morphologies of all brain neurons, reconstructed from a synapse-resolution EM volume, and the synaptic connectivity matrix of an entire brain. This connectivity information was used to hierarchically cluster all brains into 93 cell types, which were internally consistent based on morphology and known function. 
    more » « less
  3. Abstract Functional connectivity networks of the human brain are commonly studied using tools from complex network theory. Existing methods focus on functional connectivity within a single frequency band. However, it is well-known that higher order brain functions rely on the integration of information across oscillations at different frequencies. Therefore, there is a need to study these cross-frequency interactions. In this paper, we use multilayer networks to model functional connectivity across multiple frequencies, where each layer corresponds to a different frequency band. We then introduce the multilayer modularity metric to develop a multilayer community detection algorithm. The proposed approach is applied to electroencephalogram (EEG) data collected during a study of error monitoring in the human brain. The differences between the community structures within and across different frequency bands for two response types, i.e. error and correct, are studied. The results indicate that following an error response, the brain organizes itself to form communities across frequencies, in particular between theta and gamma bands while a similar cross-frequency community formation is not observed following the correct response. 
    more » « less
  4. null (Ed.)
    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 for 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. 
    more » « less
  5. Abstract Complex biological, neuroscience, geoscience and social networks exhibit heterogeneous self-similar higher order topological structures that are usually characterized as being multifractal in nature. However, describing their topological complexity through a compact mathematical description and deciphering their topological governing rules has remained elusive and prevented a comprehensive understanding of networks. To overcome this challenge, we propose a weighted multifractal graph model capable of capturing the underlying generating rules of complex systems and characterizing their node heterogeneity and pairwise interactions. To infer the generating measure with hidden information, we introduce a variational expectation maximization framework. We demonstrate the robustness of the network generator reconstruction as a function of model properties, especially in noisy and partially observed scenarios. The proposed network generator inference framework is able to reproduce network properties, differentiate varying structures in brain networks and chromosomal interactions, and detect topologically associating domain regions in conformation maps of the human genome. 
    more » « less