Structure and inference in annotated networks
arXiv:1507.04001 · doi:10.1038/ncomms11863
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.
arXiv comment16 pages, 7 figures, 1 table
References in corpus (23)
- Community detection in graphs
- Functional cartography of complex metabolic networks
- Comparing community structure identification
- Spatial Networks
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- The performance of modularity maximization in practical contexts
- Social Structure of Facebook Networks
- Community Detection in Networks with Node Attributes
- Phase transition in the detection of modules in sparse networks
- Subnetwork hierarchies of biochemical pathways
- Uncovering space-independent communities in spatial networks
- Community detection in networks: Structural communities versus ground truth
- Learning Latent Block Structure in Weighted Networks
- Normalized Mutual Information to evaluate overlapping community finding algorithms
- Efficiently inferring community structure in bipartite networks
- Friendship networks and social status
- Covariate-assisted spectral clustering
- A network approach to analyzing highly recombinant malaria parasite genes
- 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 (94)
- 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
- Inference of hyperedges and overlapping communities in hypergraphs
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Reconstructing networks with unknown and heterogeneous errors
- Community Detection in Large Hypergraphs
- Community detection with node attributes in multilayer networks
- Local dominance unveils clusters in 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
- Accurate and scalable social recommendation using mixed-membership stochastic block models
- A Survey on Theoretical Advances of Community Detection in Networks
- 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
- Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
- Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
- Latent Space Model for Multi-Modal Social Data
- Generalized Rich-Club Ordering in Networks
- A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
- Multilayer Networks for Text Analysis with Multiple Data Types
- Algorithmic detectability threshold of the stochastic block model
- Structure and inference in hypergraphs with node attributes
- Network cross-validation by edge sampling
- The Energy Landscape of Neurophysiological Activity Implicit in Brain Network Structure
- Generative model for reciprocity and community detection in networks
- A framework to generate hypergraphs with community structure
- Fast Maximum Likelihood estimation via Equilibrium Expectation for Large Network Data
- Mapping flows on weighted and directed networks with incomplete observations
- Anomaly detection and community detection in networks
- Community detection with nodal information
- Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
- Optimal prediction of decisions and model selection in social dilemmas using block models
- 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
- Covariate Regularized Community Detection in Sparse Graphs
- MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unit
- Inference of Edge Correlations in Multilayer Networks
- Constructions and properties of a class of random scale-free networks
- On community structure validation in real networks
- Structure constrained by metadata in networks of chess players
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Sampling networks by nodal attributes
- Evolutionary of Online Social Networks Driven by Pareto Wealth Distribution and Bidirectional Preferential Attachment
- Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
- Stochastic Block Models are a Discrete Surface Tension
- The Role of Network Analysis in Industrial and Applied Mathematics
- 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
- On consistent vertex nomination schemes
- Node metadata can produce predictability transitions in network inference problems
- Dual regularized Laplacian spectral clustering methods on community detection
- From reductionism to realism: Holistic mathematical modelling for complex biological systems
- Side Information in the Binary Stochastic Block Model: Exact Recovery
- Local Algorithms for Block Models with Side Information
- Mutual Information in Community Detection with Covariate Information and Correlated Networks
- Quantifying metadata relevance to network block structure using description length
- Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
- A Generative Model for Exploring Structure Regularities in Attributed Networks
- Equipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
- Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
- From clusters to queries: exploiting uncertainty in the modularity landscape of complex networks
- On a scalable entropic breaching of the overfitting barrier in machine learning
- A New Approach to Building the Interindustry Input--Output Table
- Error-Correcting Decoders for Communities in Networks
- Testing Alignment of Node Attributes with Network Structure Through Label Propagation
- A Block-based Generative Model for Attributed Networks Embedding
- Modeling Node Exposure for Community Detection in Networks
- Anomaly, reciprocity, and community detection in networks
- Block-corrected Modularity for Community Detection
- Spectral clustering of annotated graphs using a factor graph representation
- Discrimination universally determines reconstruction of multiplex networks