Networks provide a powerful and compact representation of the internal structure of complex systems consisting of agents that interact with each other. Examples include social networks, the World Wide Web and biological networks of molecules, cells or entire species. Traditional network science assumes that the network nodes are connected by a single edge that captures all interactions between them. However, this is an oversimplification as most real-world networks are built through different types of interactions among the nodes. Examples include social networks, where two individuals can be connected through different types of social ties originating from friendship, collaboration or family relationships; air transportation networks, where different airports can be connected through different airlines; and the brain, where different regions can be interacting across different frequency bands or time points. In recent years, multilayer networks, which incorporate multiple channels of connectivity, have been introduced to model these different modes of communication. A core task in network analysis is to identify and understand communities as they can reveal meaningful structure and provide a better understanding of the overall functioning of networks, such as uncovering functional pathways in metabolic networks, related pages in the World Wide Web or groups of friends in social networks and more. Community detection methods on simple graphs are not sufficient to deal with the complexity of multilayer networks for they cannot leverage the multiple modes of interaction between nodes. This project aims to develop a comprehensive multilayer community detection framework with the help of two complementary approaches, namely heuristic quality function optimization and statistical inference. The connections between these two approaches will be established for multilayer network models with varying degrees of complexity starting with temporal networks going to fully coupled multilayer networks.

This project addresses the problem of community detection in multilayer networks through three research thrusts. First, novel normalized-cut based quality functions will be defined for temporal, multiplex and multilayer networks, and computationally efficient algorithms will be developed to optimize these new cost functions. The convergence and consistency of the resulting algorithms will be studied. Next, generalized stochastic block models for temporal, multiplex and multilayer networks will be developed. Connections between maximizing a posteriori probabilities derived from these models and optimizing the heuristic quality functions will be established. Finally, the new community detection methods will be applied to multilayer functional connectivity networks, e.g. temporal and multi-frequency networks, constructed from electroencephalogram (EEG) data to assess well-known task-related networks. This new computational framework for multilayer network community detection can be applied to different types of networks including social, biological and ecological networks; we expect an impact on the fields of brain connectomics and cognitive neuroscience through collaborations with neuroscientists at Michigan State University. As part of the project, a diverse group of interdisciplinary researchers will be trained, and K-12 outreach activities that seek to engage female students will be organized.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Michigan State University
East Lansing
United States
Zip Code