Network comparison and the within-ensemble graph distance.

Area of Science:

• Network Science
• Graph Theory
• Data Analysis

Background:

• Quantifying network differences is a persistent challenge in network science.
• Numerous diverse, ad hoc methods have been developed for network comparison.
• A standardized benchmarking approach is lacking for evaluating these methods.

Purpose of the Study:

• To propose random network ensembles as natural benchmarks for network comparison methods.
• To demonstrate the utility of expected within-ensemble graph distance for characterizing generative models.
• To provide a framework for understanding and selecting appropriate graph distance measures.

Main Methods:

• Utilized established random network models (Erdős-Rényi, random geometric, Watts-Strogatz, configuration model, preferential attachment) as benchmarks.
• Calculated the expected graph distance between networks sampled from the same generative model.
• Applied 20 common graph distance measures to classic network models and their parameterizations.

Main Results:

• The expected within-ensemble graph distance effectively captures key characteristics of network generative models.
• Demonstrated the calculation of within-ensemble graph distance for various network models.
• Provided empirical results using 20 distinct graph distance metrics.

Conclusions:

• Random network ensembles serve as valuable benchmarks for network comparison techniques.
• Within-ensemble graph distance is a useful metric for understanding generative models.
• This framework aids developers in creating better graph distances and practitioners in choosing suitable tools.