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.

Keywords: graph distance; graph ensembles; network comparison.

Figure 1.

Mean and standard deviations of the within-ensemble distances for G_(n,p) and RGG. By repeatedly measuring the distance between pairs of G_(n,p) and RGG networks of the same size and density, we begin to see characteristic behaviour in both the graph ensembles as well as the graph distance measures themselves. In each subplot, the mean within-ensemble graph distance is plotted as a solid line with a shaded region around for the standard error (〈D〉 ± σ_〈D〉; note that in most subplots above, the standard error is too small to see), while the dashed lines are the standard deviations. (Online version in colour.)

Figure 2.

Mean and standard deviations of the within-ensemble distances for G_(n,〈k〉) networks. Here, we generate pairs of ER networks with a given average degree, 〈k〉, and measure the distance between them with each distance measure. In each subplot, we highlight 〈k〉 = 1 and 〈k〉 = 2. In each subplot, the mean within-ensemble graph distance is plotted as a solid line with a shaded region around for the standard error (〈D〉 ± σ_〈D〉; note that in most subplots above, the standard error is too small to see), while the dashed lines are the standard deviations. (Online version in colour.)

Figure 3.

Mean and standard deviations of the within-ensemble distances for Watts–Strogatz networks. Here, we generate pairs of Watts–Strogatz networks with a fixed size and average degree but a variable probability of rewiring random edges, p_r. In each subplot, we also plot the clustering and path length curves as in the original Watts–Strogatz paper [19] to accentuate the ‘small-world’ regime with high clustering and low path lengths. The mean within-ensemble graph distance is plotted as a solid line with a shaded region around for the standard error (〈D〉 ± σ_〈D〉; note that in most subplots above, the standard error is too small to see), while the dashed lines are the standard deviations. (Online version in colour.)

Figure 4.

Mean and standard deviations of the within-ensemble distances for soft configuration model networks with varying degree exponent. Here, we generate pairs of networks from a (soft) configuration model, varying the degree exponent, γ, while keeping 〈k〉 constant (n = 1000). In each subplot, we highlight γ = 3. The mean within-ensemble graph distance is plotted as a solid line with a shaded region around for the standard error (〈D〉 ± σ_〈D〉; note that in most subplots above, the standard error is too small to see), while the dashed lines are the standard deviations.

Figure 5.

Mean and standard deviations of the within-ensemble distances for preferential attachment networks. Here, we generate pairs of preferential attachment networks, varying the preferential attachment kernel, α, while keeping the size and average degree constant. As α → ∞, the networks become more and more star-like, and at α = 1, this model generates networks with power-law degree distributions. The mean within-ensemble graph distance is plotted as a solid line with a shaded region around for the standard error (〈D〉 ± σ_〈D〉; note that in most subplots above, the standard error is too small to see), while the dashed lines are the standard deviations. (Online version in colour.)