Network mutual information measures for graph similarity
arXiv:2405.05177 · doi:10.1038/s42005-024-01830-3
Abstract
A wide range of tasks in network analysis, such as clustering network populations or identifying anomalies in temporal graph streams, require a measure of the similarity between two graphs. To provide a meaningful data summary for downstream scientific analyses, the graph similarity measures used for these tasks must be principled, interpretable, and capable of distinguishing meaningful overlapping network structure from statistical noise at different scales of interest. Here we derive a family of graph mutual information measures that satisfy these criteria and are constructed using only fundamental information theoretic principles. Our measures capture the information shared among networks according to different encodings of their structural information, with our mesoscale mutual information measure allowing for network comparison under any specified network coarse-graining. We test our measures in a range of applications on real and synthetic network data, finding that they effectively highlight intuitive aspects of network similarity across scales in a variety of systems.
References in corpus (18)
- Benchmark graphs for testing community detection algorithms
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Networks beyond pairwise interactions: structure and dynamics
- The performance of modularity maximization in practical contexts
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Layer aggregation and reducibility of multilayer interconnected networks
- A Survey on Graph Kernels
- Measuring and modelling correlations in multiplex networks
- Network structure from rich but noisy data
- Entropy of stochastic blockmodel ensembles
- Bayesian stochastic blockmodeling
- Semantic Histogram Based Graph Matching for Real-Time Multi-Robot Global Localization in Large Scale Environment
- Improved mutual information measure for classification and community detection
- Network comparison and the within-ensemble graph distance
- Spatial regionalization based on optimal information compression
- Graph Similarity Description: How Are These Graphs Similar?
- Compressing network populations with modal networks reveals structural diversity