Structure and inference in annotated networks

Abstract

For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network, geographic location of nodes in the Internet, or cellular function of nodes in a gene regulatory network. Here we demonstrate how this "metadata" can be used to improve our analysis and understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. The learned correlations are also of interest in their own right, allowing us to make predictions about the community membership of nodes whose network connections are unknown. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological, and technological domains.

16 pages, 7 figures, 1 table

References in corpus (11)

• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• Subnetwork hierarchies of biochemical pathways
• Community detection in networks: Structural communities versus ground truth
• Learning Latent Block Structure in Weighted Networks
• Emergence of Soft Communities from Geometric Preferential Attachment
• Community Structure Detection in Complex Networks with Partial Background Information
• Phase transitions in semisupervised clustering of sparse networks
• Semi-supervised Eigenvectors for Large-scale Locally-biased Learning

Cited by in corpus (93)

• Community detection in networks: A user guide
• Social physics
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• The ground truth about metadata and community detection in networks
• Community detection in node-attributed social networks: a survey
• A network approach to topic models
• Network Analysis of Particles and Grains
• 20 years of network community detection
• Spectral entropies as information-theoretic tools for complex network comparison
• Visibility of minorities in social networks
• Bayesian stochastic blockmodeling
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Inference of hyperedges and overlapping communities in hypergraphs
• Reconstructing networks with unknown and heterogeneous errors
• Community Detection in Large Hypergraphs
• Local dominance unveils clusters in networks
• Community detection with node attributes in multilayer networks
• Prioritizing network communities
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• A new dominance concept and its application to diversity-stability analysis
• A Survey on Theoretical Advances of Community Detection in Networks
• Accurate and scalable social recommendation using mixed-membership stochastic block models
• Graph Clustering with Graph Neural Networks
• Multiscale dynamical embeddings of complex networks
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Link prediction with hyperbolic geometry
• Subgraph Neural Networks
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Cross-validation estimate of the number of clusters in a network
• Universality of the stochastic block model
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Community Detection and Improved Detectability in Multiplex Networks
• Latent Space Model for Multi-Modal Social Data
• Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Generalized Rich-Club Ordering in Networks
• Multilayer Networks for Text Analysis with Multiple Data Types
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Structure and inference in hypergraphs with node attributes
• Algorithmic detectability threshold of the stochastic block model
• Generative model for reciprocity and community detection in networks
• Network cross-validation by edge sampling
• The Energy Landscape of Neurophysiological Activity Implicit in Brain Network Structure
• Fast Maximum Likelihood estimation via Equilibrium Expectation for Large Network Data
• A framework to generate hypergraphs with community structure
• Anomaly detection and community detection in networks
• Mapping flows on weighted and directed networks with incomplete observations
• Community detection with nodal information
• Optimal prediction of decisions and model selection in social dilemmas using block models
• Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Pairwise Covariates-adjusted Block Model for Community Detection
• Prediction models for network-linked data
• Constructions and properties of a class of random scale-free networks
• MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unit
• Covariate Regularized Community Detection in Sparse Graphs
• Inference of Edge Correlations in Multilayer Networks
• On community structure validation in real networks
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Structure constrained by metadata in networks of chess players
• Sampling networks by nodal attributes
• Evolutionary of Online Social Networks Driven by Pareto Wealth Distribution and Bidirectional Preferential Attachment
• The Role of Network Analysis in Industrial and Applied Mathematics
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Stochastic Block Models are a Discrete Surface Tension
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Community Structure Characterization
• Community Detection in networks by Dynamical Optimal Transport Formulation
• On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
• A network community detection method with integration of data from multiple layers and node attributes
• Node metadata can produce predictability transitions in network inference problems
• From reductionism to realism: Holistic mathematical modelling for complex biological systems
• On consistent vertex nomination schemes
• Dual regularized Laplacian spectral clustering methods on community detection
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Local Algorithms for Block Models with Side Information
• Equipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• From clusters to queries: exploiting uncertainty in the modularity landscape of complex networks
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• A Generative Model for Exploring Structure Regularities in Attributed Networks
• Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
• Quantifying metadata relevance to network block structure using description length
• Block-corrected Modularity for Community Detection
• Modeling Node Exposure for Community Detection in Networks
• Anomaly, reciprocity, and community detection in networks
• Error-Correcting Decoders for Communities in Networks
• Testing Alignment of Node Attributes with Network Structure Through Label Propagation
• Spectral clustering of annotated graphs using a factor graph representation
• A Block-based Generative Model for Attributed Networks Embedding
• Discrimination universally determines reconstruction of multiplex networks
• On a scalable entropic breaching of the overfitting barrier in machine learning