Inferring the mesoscale structure of layered, edge-valued and time-varying networks

Abstract

Many network systems are composed of interdependent but distinct types of interactions, which cannot be fully understood in isolation. These different types of interactions are often represented as layers, attributes on the edges or as a time-dependence of the network structure. Although they are crucial for a more comprehensive scientific understanding, these representations offer substantial challenges. Namely, it is an open problem how to precisely characterize the large or mesoscale structure of network systems in relation to these additional aspects. Furthermore, the direct incorporation of these features invariably increases the effective dimension of the network description, and hence aggravates the problem of overfitting, i.e. the use of overly-complex characterizations that mistake purely random fluctuations for actual structure. In this work, we propose a robust and principled method to tackle these problems, by constructing generative models of modular network structure, incorporating layered, attributed and time-varying properties, as well as a nonparametric Bayesian methodology to infer the parameters from data and select the most appropriate model according to statistical evidence. We show that the method is capable of revealing hidden structure in layered, edge-valued and time-varying networks, and that the most appropriate level of granularity with respect to the additional dimensions can be reliably identified. We illustrate our approach on a variety of empirical systems, including a social network of physicians, the voting correlations of deputies in the Brazilian national congress, the global airport network, and a proximity network of high-school students.

17 pages, 9 figures

References in corpus (25)

• The structure and dynamics of multilayer networks
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Diffusion dynamics on multiplex networks
• An information-theoretic framework for resolving community structure in complex networks
• Robust Detection of Dynamic Community Structure in Networks
• Phase transition in the detection of modules in sparse networks
• Contact patterns among high school students
• Dynamic stochastic blockmodels for time-evolving social networks
• Mitigation of infectious disease at school: targeted class closure vs school closure
• Parsimonious module inference in large networks
• Learning Latent Block Structure in Weighted Networks
• Uncovering latent structure in valued graphs: A variational approach
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Analytical computation of the epidemic threshold on temporal networks
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Biased imitation in coupled evolutionary games in interdependent networks
• A network inference method for large-scale unsupervised identification of novel drug-drug interactions
• Absorbing and Shattered Fragmentation Transitions in Multilayer Coevolution
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Stochastic block model and exploratory analysis in signed networks
• Predicting future conflict between team-members with parameter-free models of social networks
• Stochastic Block Models for Multiplex networks: an application to networks of researchers
• Exact ICL maximization in a non-stationary time extension of the latent block model for dynamic networks

Cited by in corpus (59)

• Community detection in networks: A user guide
• The physics of spreading processes in multilayer networks
• Social physics
• A network approach to topic models
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Community detection, link prediction, and layer interdependence in multilayer networks
• Multilayer Networks in a Nutshell
• On community structure in complex networks: challenges and opportunities
• The new challenges of multiplex networks: measures and models
• The many facets of community detection in complex networks
• Modeling sequences and temporal networks with dynamic community structures
• Bayesian stochastic blockmodeling
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Nonparametric weighted stochastic block models
• Reconstructing networks with unknown and heterogeneous errors
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Emergence of multiplex communities in collaboration networks
• Multilink Communities of Multiplex Networks
• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Randomized reference models for temporal networks
• Multiplex core-periphery organization of the human connectome
• Community detection with node attributes in multilayer networks
• Disentangling bipartite and core-periphery structure in financial networks
• Detection of timescales in evolving complex systems
• Joint Embedding of Graphs
• Constrained information flows in temporal networks reveal intermittent communities
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Network structure, metadata and the prediction of missing nodes and annotations
• Inference for multiple heterogeneous networks with a common invariant subspace
• Multilayer Network Science: from Cells to Societies
• Different approaches to community detection
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Community extraction in multilayer networks with heterogeneous community structure
• Social Stability and Extended Social Balance - Quantifying the Role of Inactive Links in Social Networks
• Latent Space Model for Multi-Modal Social Data
• Multilayer Networks for Text Analysis with Multiple Data Types
• The International Postal Network and Other Global Flows As Proxies for National Wellbeing
• Detection and localization of change points in temporal networks with the aid of stochastic block models
• Algorithmic detectability threshold of the stochastic block model
• Brain tumour genetic network signatures of survival
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Atomic subgraphs and the statistical mechanics of networks
• Clustering of heterogeneous populations of networks
• Null Models and Community Detection in Multi-Layer Networks
• Inference of Edge Correlations in Multilayer Networks
• Computational limits to the legibility of the imaged human brain
• The Role of Network Analysis in Industrial and Applied Mathematics
• Stochastic Block Models are a Discrete Surface Tension
• Consistent detection and optimal localization of all detectable change points in piecewise stationary arbitrarily sparse network-sequences
• Residual2Vec: Debiasing graph embedding with random graphs
• A network community detection method with integration of data from multiple layers and node attributes
• The Infinity Mirror Test for Graph Models
• The Atlas for the Aspiring Network Scientist
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• A Reinforcement Approach for Detecting P2P Botnet Communities in Dynamic Communication Graphs
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Multi-level hypothesis testing for populations of heterogeneous networks
• Community detection over a heterogeneous population of non-aligned networks