Learning Latent Block Structure in Weighted Networks

Abstract

Community detection is an important task in network analysis, in which we aim to learn a network partition that groups together vertices with similar community-level connectivity patterns. By finding such groups of vertices with similar structural roles, we extract a compact representation of the network's large-scale structure, which can facilitate its scientific interpretation and the prediction of unknown or future interactions. Popular approaches, including the stochastic block model, assume edges are unweighted, which limits their utility by throwing away potentially useful information. We introduce the `weighted stochastic block model' (WSBM), which generalizes the stochastic block model to networks with edge weights drawn from any exponential family distribution. This model learns from both the presence and weight of edges, allowing it to discover structure that would otherwise be hidden when weights are discarded or thresholded. We describe a Bayesian variational algorithm for efficiently approximating this model's posterior distribution over latent block structures. We then evaluate the WSBM's performance on both edge-existence and edge-weight prediction tasks for a set of real-world weighted networks. In all cases, the WSBM performs as well or better than the best alternatives on these tasks.

28 Pages

References in corpus (13)

• Community detection in graphs
• Mixing patterns in networks
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• A Bayesian Approach to Network Modularity
• World citation and collaboration networks: uncovering the role of geography in science
• Parsimonious module inference in large networks
• A network inference method for large-scale unsupervised identification of novel drug-drug interactions
• Scoring dynamics across professional team sports: tempo, balance and predictability
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Cited by in corpus (50)

• Community detection in networks: A user guide
• Social physics
• The physics of brain network structure, function, and control
• Structure and inference in annotated networks
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Graph Frequency Analysis of Brain Signals
• Multiscale and multimodal network dynamics underpinning working memory
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Diversity of meso-scale architecture in human and non-human connectomes
• The many facets of community detection in complex networks
• Predicting missing links and their weights via reliable-route-based method
• Bayesian stochastic blockmodeling
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Nonparametric weighted stochastic block models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Reconstructing networks with unknown and heterogeneous errors
• Cover time for random walks on arbitrary complex networks
• Local dominance unveils clusters in networks
• Structural inference for uncertain networks
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Network structure, metadata and the prediction of missing nodes and annotations
• Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
• Predicting Growth Rate from Gene Expression
• Reconstructing networks
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Multiple-view clustering for identifying subject clusters and brain sub-networks using functional connectivity matrices without vectorization
• Algorithmic detectability threshold of the stochastic block model
• Discovering the hidden community structure of public transportation networks
• Path-dependent connectivity, not modularity, consistently predicts controllability of structural brain networks
• Community detection for weighted bipartite networks
• Parameter Estimation Procedures for Exponential-Family Random Graph Models on Count-Valued Networks: A Comparative Simulation Study
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Inference of Edge Correlations in Multilayer Networks
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Estimating the number of communities in weighted networks
• Democratic summary of public opinions in free-response surveys
• Generalised thresholding of hidden variable network models with scale-free property
• Block Model Guided Unsupervised Feature Selection
• Evolution of global development cooperation: An analysis of aid flows with hierarchical stochastic block models
• Priority Attachment: a Comprehensive Mechanism for Generating Networks
• Model-based edge clustering for weighted networks with a noise component
• Graph Neural Networks Based Analog Circuit Link Prediction
• Detectability threshold in weighted modular networks
• Network-based models for social recommender systems
• Disentangling the structure of ecological bipartite networks from observation processes
• Overlapping community detection in weighted networks