Community detection, link prediction, and layer interdependence in multilayer networks

Abstract

Complex systems are often characterized by distinct types of interactions between the same entities. These can be described as a multilayer network where each layer represents one type of interaction. These layers may be interdependent in complicated ways, revealing different kinds of structure in the network. In this work we present a generative model, and an efficient expectation-maximization algorithm, which allows us to perform inference tasks such as community detection and link prediction in this setting. Our model assumes overlapping communities that are common between the layers, while allowing these communities to affect each layer in a different way, including arbitrary mixtures of assortative, disassortative, or directed structure. It also gives us a mathematically principled way to define the interdependence between layers, by measuring how much information about one layer helps us predict links in another layer. In particular, this allows us to bundle layers together to compress redundant information, and identify small groups of layers which suffice to predict the remaining layers accurately. We illustrate these findings by analyzing synthetic data and two real multilayer networks, one representing social support relationships among villagers in South India and the other representing shared genetic substrings material between genes of the malaria parasite.

References in corpus (17)

• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Mixture models and exploratory analysis in networks
• An efficient and principled method for detecting communities in networks
• Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (1999)
• Eigenvector centrality of nodes in multiplex networks
• On Tensors, Sparsity, and Nonnegative Factorizations
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• A network approach to analyzing highly recombinant malaria parasite genes
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Inversion method for content-based networks
• Null Models and Community Detection in Multi-Layer Networks

Cited by in corpus (54)

• Social physics
• Graph Representation Learning: A Survey
• Multilayer Networks in a Nutshell
• Progresses and Challenges in Link Prediction
• Bayesian stochastic blockmodeling
• Inference of hyperedges and overlapping communities in hypergraphs
• Community Detection in Large Hypergraphs
• A General Method to Find Highly Coordinating Communities in Social Media through Inferred Interaction Links
• Consistencies and inconsistencies between model selection and link prediction in networks
• Community detection with node attributes in multilayer networks
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Constrained information flows in temporal networks reveal intermittent communities
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Reconstructing networks
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Reciprocity, community detection, and link prediction in dynamic networks
• Multilayer patent citation networks: A comprehensive analytical framework for studying explicit technological relationships
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Community Detection and Improved Detectability in Multiplex Networks
• Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
• Structure and inference in hypergraphs with node attributes
• Generative model for reciprocity and community detection in networks
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• A framework to generate hypergraphs with community structure
• A Stochastic Block Model Approach for the Analysis of Multilevel Networks: an Application to the Sociology of Organizations
• Anomaly detection and community detection in networks
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Community detection and reciprocity in networks by jointly modeling pairs of edges
• Principled Multilayer Network Embedding
• Algorithmic complexity of multiplex networks
• Reconstruction of multiplex networks via graph embeddings
• Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
• Inference of Edge Correlations in Multilayer Networks
• Detecting Hidden Layers from Spreading Dynamics on Complex Networks
• Information Evolution in Complex Networks
• Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• The interplay between ranking and communities in networks
• Multiplex reconstruction with partial information
• Community Detection in networks by Dynamical Optimal Transport Formulation
• The latent cognitive structures of social networks
• The Atlas for the Aspiring Network Scientist
• Multiplex Graph Association Rules for Link Prediction
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• Feature Learning and Network Structure from Noisy Node Activity Data
• Anomaly, reciprocity, and community detection in networks
• Efficient Community Detection in Boolean Composed Multiplex Networks
• Modeling Node Exposure for Community Detection in Networks
• OFFER: A Motif Dimensional Framework for Network Representation Learning
• Data-driven Clustering in Ad-hoc Networks based on Community Detection
• Discrimination universally determines reconstruction of multiplex networks