Network comparison and the within-ensemble graph distance

Abstract

Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years a multitude of diverse, ad hoc solutions to this problem have been introduced. Here we propose that simple and well-understood ensembles of random networks (such as Erdős-Rényi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model, and preferential attachment networks) are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.

References in corpus (17)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Power laws, Pareto distributions and Zipf's law
• Connectivity of Growing Random Networks
• The statistical mechanics of networks
• Random Geometric Graphs
• The Statistical Physics of Real-World Networks
• Metrics for Graph Comparison: A Practitioner's Guide
• Maximum likelihood: extracting unbiased information from complex networks
• Spectral entropies as information-theoretic tools for complex network comparison
• All scale-free networks are sparse
• NetLSD: Hearing the Shape of a Graph
• Evolutionary reconstruction of networks
• NetSimile: A Scalable Approach to Size-Independent Network Similarity
• Detecting sequences of system states in temporal networks
• netrd: A library for network reconstruction and graph distances
• Graph Comparison via the Non-backtracking Spectrum

Cited by in corpus (10)

• netrd: A library for network reconstruction and graph distances
• Adaptive Dependency Learning Graph Neural Networks
• Network mutual information measures for graph similarity
• Dynamic Hidden-Variable Network Models
• Embedding and trajectories of temporal networks
• An embedding-based distance for temporal graphs
• Flow of temporal network properties under local aggregation and time shuffling: a tool for characterizing, comparing and classifying temporal networks
• A measure of dissimilarity between diffusive processes on networks
• GINA: Neural Relational Inference From Independent Snapshots
• Random Similarity Isolation Forests