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.
1. Introduction
Quantifying the extent to which two finite graphs structurally differ from one another is a common, important problem in the study of networks. We see attempts to quantify the dissimilarity of graphs in both theoretical and applied contexts, ranging from the comparison of social networks [1–3], to time-evolving networks [4–8], biological networks [5], power grids and infrastructure networks [9], object recognition [10], video indexing [11] and much more. Together, these network comparison studies all seek to define a notion of dissimilarity or distance between two networks and to then use such a measure to gain insights about the networks in question.
However, it is often unclear which network features a given graph distance will or will not capture. For this reason, rigorous benchmarks must be established in order to better understand the tendencies and biases of these distances. We adopt the perspective that random graph ensembles are the appropriate tool to achieve this task. Specifically, by sampling pairs of graphs from within a given random ensemble with the same parameterization and measuring the graph distance between them, we create a benchmark that allows us to better understand the sensitivity of a given graph distance to known statistical features of an ensemble. Ultimately, a good benchmark would characterize the behaviour of graph distances between graphs sampled from both within an ensemble and between different ensembles. We tackle the former in this paper, noting a rich diversity of behaviours among commonly used graph distance measures. Even though this work focuses on within-ensemble graph distances, these results guide our understanding of how any two sets of networks structurally differ from each other regardless of whether those sets are generated by the same random ensemble or another network-generating process. Put simply, the approach introduced in this work is general and can be used to develop a number of graph distance benchmarks.
There are many approaches used to quantify the dissimilarity between two graphs, and we highlight 20 different ones here. Given the large number of algorithms considered in this work, we find it useful to systematically characterize each of these measures. We do so by breaking them down into ‘description-distance’ pairs. That is, every graph distance measure can be thought of as (i) computing some description or property of two graphs and (ii) quantifying the difference between those descriptions using some distance metric.
(a) Formalism of graph distances
(i) Graph descriptors
Definition 1.1.
A graph description Ψ is a mapping from a set of graphs to a space ,
The set is that of all finite labelled simple graphs, and the space is known as the graph descriptor space. Typically, is for integers l, m or is a space of probability distributions. Given a description Ψ, the descriptor of graph G, denoted ψG, is the element of to which G is mapped; ψG = Ψ(G).
(ii) Descriptor distances
Definition 1.2.
A distance maps a pair of descriptors to a non-negative real value,
(i) | d(x, y) = d(y, x) (symmetry) | ||||
(ii) | d(x, x) = 0 (identity law) |
The properties listed in this definition are general and mirror those in the literature [12]. They do not restrict the large possibility of measures we might use, while also providing a clean separation between how we choose to describe graphs and how we calculate the differences between those descriptions. A common property when considering distance measures is the triangle inequality; however, we have not included this in the list above as not all commonly used graph distances obey this property [13]. As in the case of pseudometrics, d(x, y) = 0 does not always imply x = y [7].1
(iii) Graph distances
Definition 1.3.
Given a set of graphs , a graph description Ψ, its descriptor space , and a distance d on , the associated graph distance measure is a function defined by
Every graph distance quantifies some notion of dissimilarity between two graphs.2
(iv) Network spaces
Definition 1.4.
Given a distance d and description Ψ on descriptor space and a set of graphs , the associated network space, denoted , is the set of descriptors mapped to by Ψ from graphs in , equipped with d as a distance measure.
The network space consists of points in , namely —giving rise to distance values, one for each pair of descriptions of elements of .
Fundamental questions naturally arise. Does a network space capture known properties of a given ensemble of graphs? This question we can begin to answer by considering sets of graphs with known properties: i.e. random graph models.
(v) Models
Definition 1.5.
A model is a process which generates a probability distribution over a set of graphs , where is a vector of parameters needed by the model to generate the distribution.
Models (or null models) represent a collection of maximally random graphs constrained by a set of parameters, which we use to generate sets of graphs [14]. The probability distribution of model is then defined over the set of graphs that have non-zero probability of being generated given the model and its parameters . For many well-known models, we have a deep understanding of how the structure of sampled graphs is influenced by the parameter values. Using our knowledge of how parameters affect graph structure, we can see how well the expected features of a given model are reflected by the structure of each network space.
(b) This study
Herein, we apply a variety of graph distances to pairs of independently and identically sampled networks from a variety of random network models, over a range of parameter values for each, and consider the within-ensemble distance distribution as a function of the type of graph and model parameters. While our focus is on the means of the distance distributions, we also include the standard deviations in each figure. Ultimately, we report the within-ensemble graph distances for 20 different graph distances from the software package,
2. Methods
(a) Ensembles
We study the behaviour of for sets of graphs sampled from under a variety of parameterizations. There are many graph ensembles that one could use to compute within-ensemble graph distances, and we begin by focusing on two broad classes: ensembles that produce graphs with homogeneous degree distributions and those that produce graphs with heterogeneous degree distributions. In total, we study the within-ensemble graph distance for five different ensembles.
(i) ErdőLgs–Rényi random graphs
Graphs sampled from the ErdőLgs–Rényi model (ER), also known as G(n,p), have (undirected) edges among n nodes, with each pair being connected with probability p [15,16]. This model is commonly used as a benchmark or a null model to compare with observed properties of real-world network data from nature and society. In our case, it allows us to explore the behaviour of graph distance measures on dense and homogeneous graphs. In fact, this model maximizes entropy subject to a global constraint on expected edge density, p.
One well-studied construction of this ensemble is when p = 〈k〉/n, in which n nodes are connected uniformly at random such that nodes in the resulting graph have an average degree of 〈k〉. This ensemble is particularly useful for identifying which graph distance measures are able to capture key structural transitions that happen as the average degree increases. For convenience, we will refer to this ensemble as G(n,〈k〉).
(ii) Random geometric graphs
We work with random geometric graphs of n nodes and edge density p, generated by sprinkling n coordinates uniformly into a one-dimensional ring of circumference 1, and connecting all pairs of nodes whose coordinate distance (arc length) is less than or equal to p/2. Compared to G(n,p), this model produces graphs that have a high average local clustering coefficient, which is a property commonly found in real network data. Note that setting the connection distance to p/2 means that p parameterizes the edge density exactly as in G(n,p) [17,18].
(iii) Watts–Strogatz graphs
Watts–Strogatz (WS) graphs allow us to study the effects that random, long-range connections have on regular lattices. A WS graph is initialized as a one-dimensional regular ring-lattice, parameterized by the number of nodes n and the even-integer degree of every node 〈k〉 (each node connects to the 〈k〉/2 closest other nodes on either side). Each edge in the network is then randomly rewired with probability pr, which generates graphs with both relatively high average clustering and relatively short average path lengths for a wide range of pr ∈ (0, 1) [19].
(iv) (Soft) configuration model with power-law degree distribution
We generate expected degree sequences from distributions with power-law tails with a mean of 〈k〉. We construct an instance of a ‘soft’ configuration model, the maximum entropy network ensemble with a given sequence of expected degrees, by connecting node-pairs with probabilities determined via the method of Lagrange multipliers [20–22]. Through this method, we are able to construct networks with a tunable degree exponent, γ. The degree exponents that we test range from those that skew the distribution heavily, resulting in a highly heterogeneous ultra-small-world network (γ ∈ (2, 3)), to those that generate more homogeneous networks (γ > 3). In contrast to the homogeneous ensembles we tested—all of which have homogeneous degree distributions—the requirement of heterogeneity in these graphs constrains the possible edge densities to be vanishingly small. Otherwise, in the high-edge density regime, degrees cannot fluctuate to appreciably larger-than-average values, and we have a natural degree scale imposed by the network size.
(v) Nonlinear preferential attachment
The final ensemble of networks included here are grown under a degree-based nonlinear preferential attachment mechanism [23–25]. A network of n nodes is grown as follows: each new node is added to the network sequentially, connecting its m edges to nodes already in the network vi ∈ V with probability , where ki is the degree of node vi and α modulates the probability that a given node already in the network will collect new edges. When α = 1, this model generates networks with a power-law degree distribution (with degree exponent γ = 3), and a condensation regime emerges as n → ∞ when α > 2, producing a star network with O(n) nodes all connected to a main hub node [25].
(b) Graph distance measures
The study of network similarity and graph distance has yielded many approaches for comparing two graphs [5,26]. Typically, these methods involve comparing simple descriptors based on either aggregate statistical properties of two graphs—such as their degree or average path length distributions [4]—or intrinsic spectral properties of the two graphs, such as the eigenvalues of their adjacency matrices, or of other matrix representations [27]. The description distances also tend to fall into two broad categories: either classic definitions of norms or distances based on statistical divergence. While different approaches are better suited for capturing differences between certain types of graphs, they obviously are expected to share several properties.
The simplest graph distances aggregate element-wise comparisons between the adjacency matrices of two graphs [28–31] and extensions thereof [32]; these methods depend explicitly on the node labelling scheme (and hence are not invariant under graph isomorphism [33]), which may limit their utility when comparing graphs with unknown labels (e.g. graphs sampled from random graph ensembles, as we do here). Several measures collect empirical distributions [34] or a ‘signature’ vector [1] from each graph and take the distance between them (using the Jensen–Shannon divergence, Canberra distance, earth mover’s distance etc.4 ), which, among other things, facilitates comparison of differently sized graphs [4,36]. Another family of approaches compare spectral properties of certain matrices characterized by the graphs [37], such as the non-backtracking matrix [7,38] or Laplacian matrix [27]. The relevant spectral properties associated with these distances are invariant under graph isomorphism [33,39]. Some graph distances have been shown to be metrics (i.e. they satisfy properties such as triangle inequality, etc.) [13], whereas others have not. These are not exhaustive descriptions of every graph distance in use today, but they represent coarse similarities between the various methods. We summarize the 20 graph distances we consider in table 1 and more extensively define them in electronic supplementary material, B.
graph distance | label | |
---|---|---|
1 | Jaccard [29] | |
2 | Hamming [30] | |
3 | Hamming–Ipsen–Mikhailov [37] | |
4 | Frobenius [28] | |
5 | polynomial dissimilarity [5] | |
6 | degree JSD [34] | |
7 | portrait divergence [4] | |
8 | quantum spectral JSD [40] | |
9 | communicability sequence [41] | |
10 | graph diffusion distance [42] | |
11 | resistance perturbation [8] | |
12 | NetLSD [3] | |
13 | Lap. spectrum; Gauss. kernel, JSD [27] | |
14 | Lap. spectrum; Loren. kernel, Euc. [27] | |
15 | Ipsen–Mikhailov [43] | |
16 | non-backtracking eigenvalue [7] | |
17 | distributional non-backtracking [38] | |
18 | D-measure distance [9] | |
19 | DeltaCon [2] | |
20 | NetSimile [1] |
(c) Description of experiments
See table 2 for the full parameterization of these sampled graphs. In each experiment, we generate N = 103 pairs of graphs for every combination of parameters. With these sampled random graphs, we measure the distance between pairs from the same parameterization of the same model, , and report statistical properties of the resulting vectors of distances. In other words, our experiments consist of calculating mean within-ensemble graph distances,
ensemble | fixed parameter(s) | key parameter |
---|---|---|
G(n,p) | n = 500 | p ∈ {0.02, 0.06, …, 0.98} |
RGG | n = 500 | p ∈ {0.02, 0.06, …, 0.98} |
G(n,〈k〉) | n = 500 | 〈k〉 ∈ {10−4, …, n} |
WS | n = 500, 〈k〉 = 8 | pr ∈ {10−4, …, 100} |
SCM | n = 1000, 〈k〉 = 12 | γ ∈ {2.01, 2.06, …6.01} |
PA | n = 500, 〈k〉 = 4 | α ∈ { − 5, − 4.95, …, 5} |
We then study the behaviour of 〈D〉 for various . The error on the mean within-ensemble graph distance is estimated from the following standard error of the mean , where σD is the standard deviation on the within-ensemble graph distance D, estimated by sampling as well. For all experiments, we used N = 103 pairs of graphs, which is sufficient in general as can be seen from the small standard error relative to the mean in all figures. In each plot, we also include the standard deviations σD of the within-ensemble graph distances, and we highlight when the standard deviation offers particularly notable insights into the behaviour of certain distances.
Lastly, there are several distances that assume alignment in the node labels of G and G′. Because we are sampling from random graph ensembles, the networks we study here are not node-aligned, and as such, care should be taken when interpreting the output of these graph distances. For every description of graph distances in electronic supplementary material, B, we note if node alignment is assumed.
3. Results
In the following sections, we broadly describe the behaviour of the mean within-ensemble graph distance (in general denoted 〈D〉) for the distance measures tested. The general structure of this section is motivated by critical properties of the ensembles studied here. We highlight features of the within-ensemble graph distance for two broad characterizations of networks: homogeneous and heterogeneous graph ensembles, focusing on specific ensembles within each category.
All of the main results from the experiments described below are summarized in table 3, which practitioners may find especially useful when considering which tools to use for comparing networks with particular structures. When relevant, we highlight certain distance measures to emphasize interesting within-ensemble graph distance behaviours.
model | property | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
G(n,p) | complement symmetry | ||||||||||||||||||||
G(n,p) | derivative with network size, n | 0 | 0 | 0 | + | — | — | — | ∼ | — | ∼ | — | — | — | — | — | + | — | — | + | ∼ |
RGG | maximum: | ||||||||||||||||||||
G(n,〈k〉) | detects the giant 1-core | ||||||||||||||||||||
G(n,〈k〉) | detects the giant 2-core | ||||||||||||||||||||
G(n,〈k〉) | derivative with network size, n | 0 | — | — | + | — | — | ∼ | 0 | — | + | + | + | — | — | — | ∼ | — | — | + | — |
WS | small-world > random | ||||||||||||||||||||
WS | path length sensitivity | ||||||||||||||||||||
WS | clustering sensitivity | ||||||||||||||||||||
SCM | maximum: 2 < γ < 3 | ||||||||||||||||||||
SCM | monotonic decay as γ grows | ||||||||||||||||||||
PA | heterogeneous > homogeneous | ||||||||||||||||||||
PA | maximum: α ≈ 0 (uniform) | ||||||||||||||||||||
PA | maximum: α ≈ 1 (linear) | ||||||||||||||||||||
PA | maximum: 1 < α ≤ 2 |
(a) Results for homogeneous graph ensembles
(i) Dense graph ensembles
Here, we present our results for the two models that produce homogeneous and dense graphs.
The G(n,p) model possesses three notable features that we might expect graph distance measures to recover. Note that while we might expect graph distances to recover these features, we are not asserting that every graph distance measure should capture these properties.
(i) | The size of the ensembles shrink to a single isomorphic class in the limits p → 0 and p → 1, corresponding respectively to an empty and complete graph of size n. In both limits, we might therefore expect 〈D(Mn,p)〉 to go to zero for any method that considers unlabelled graphs. | ||||
(ii) | The G(n,p) model creates ensembles of graphs and graph complements symmetric under the change of variable p′ = 1 − p. By definition, every graph G has a complement such that every edge that does (or does not) exist in G does not (or does) exist in . Therefore, for every graph in G(n,p), one can expect to find its complement occurring with the same probability in G(n,1−p). We might expect 〈D(Mn,p)〉 = 〈D(Mn,1−p)〉 if graph distances can capture this symmetry. | ||||
(iii) | A density of produces the G(n,p) ensemble with maximal entropy (all graph configurations have an equal probability). As a result, we might also expect 〈D(Mn,p)〉 to have a global maximum at . |
The RGG model shares features 1 and 3 with the G(n,p) model, but not feature 2. Moreover, the most significant differences between the two models is that edges are not independent in the RGG model. Correlations between edges lead to local structure (i.e. higher-order structures like triangles) and to correlations in the degree distribution. We therefore do not expect distance measures focused on the degree distribution to produce exactly the same mean within-ensemble distance curve in RGG as in G(n,p). Conversely, any distance measure that does produce the exact same within-ensemble distance curve for RGG and G(n,p) either fails to account for these correlations, or the effect of these correlations is negligible on the overall distance between two graphs drawn from the ensemble. This is the case for
Our results for homogeneous graph ensembles are shown in figure 1. Only 5 out of 20 graph distances capture all the features discussed above, namely: 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.)
(ii) Sparse graph ensembles
While the previous section highlighted dense RGG and ER networks, we now turn to the within-ensemble graph distance of sparse homogeneous graphs sampled from G(n,p), such that p = 〈k〉/n. In the case of sparse graphs, the edge density decays to zero in the n → ∞ limit as the mean degree 〈k〉 remains fixed. We found it important to cast this distinction between dense G(n,p) because of critical transitions that take place as 〈k〉 increases. As network scientists, these early transition points in sparse networks are foundational, with implications for a number of network phenomena (i.e. the occurrence of outbreaks in disease models [44], etc.).
In fact, the presence of such critical transitions in random graph models underscores the utility of this approach for studying graph distance measures. That is, a sudden change in the within-ensemble graph distance signals abrupt changes in the probability distribution over the set of graphs in the ensemble (i.e. the emergence of novel graph structures that are markedly different from the greater population of graphs in an ensemble). This may show up as a local or global maximum within-ensemble graph distance near parameter values for which this transition occurs. Conversely, if a sudden decrease in within-ensemble graph distance is observed, then there may be a sudden disappearance or reduction in largely dissimilar graphs in the ensemble.
In the case of G(n,p) where p = 〈k〉/n, which we will refer to with the shorthand, G(n,〈k〉), the following critical transitions emerge:
(iv) | At 〈k〉 = 1, we see the emergence of a giant component in ER networks (likewise, a 2-core emerges at 〈k〉 = 2). We might expect, for example, a within-G(n,〈k〉) graph distance to have a local maximum at such values. |
Ultimately, we observe that distance measures that are fundamentally associated with flow-based properties of the network (i.e. if a distance measure is based on a graph’s Laplacian matrix, communicability, or other properties important to diffusion, such as path-length distributions etc.) are the ones most sensitive for picking up on this property (figure 2).5
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.)
What figure 2 highlights, which the dense ensembles in figure 1 could not, is the rich and varied behaviour characteristic of sparse graphs. For example, the distance measures with maxima at (
Importantly, while the qualitative behaviours discussed here are general features of the models and distances, the quantitative value of the average within-ensemble graph distance also depends on network size. There are no specific structural transitions to discuss around this dependency, but it can be an important problem when comparing networks of different sizes without a good understanding of how network distances might behave. Interested readers can find our results in electronic supplementary material, A, where we use G(n,〈k〉) to vary network size while keeping all other features fixed.
(iii) Small-world graphs
The final homogeneous graph ensemble studied here is the WS model. This model generates networks that are initialized as lattice networks, and edges are randomly rewired with probability, pr. At certain values of pr, we see two key phenomena occur:
(v) | ‘Entry’ into the small-world regime: Even as the edges in the network are minimally rewired, the average path length quickly decreases relative to its initial (longer) value. This is highlighted by the blue curve in figure 3, corresponding to Lp/L0, where L0 is the average path length before any edges have been rewired. For the parameterizations used in this study, the largest (negative) slope of this curve is at pr ≈ 2 × 10−3. We might expect a within-ensemble graph distance to be sensitive to this or nearby values of pr, as this region corresponds to changes in the graphs’ common structural features. | ||||
(vi) | ‘Exit’ from the small-world regime: After enough edges have been rewired, the network loses whatever clustering it had from originally being a lattice, reducing to approximately the clustering of an ER graph. This is highlighted by the violet curve in figure 3, corresponding to Cp/C0, where C0 is the average clustering before any edges have been rewired. For the parameterizations used in this study, the largest (negative) slope of this curve is at pr ≈ 3 × 10−1. Again, we might expect a within-ensemble graph distance to be sensitive to this large decrease in clustering. |

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, pr. 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.)
Together, the above features characterize WS networks. Importantly, we are interested in whether a distance measure is sensitive to these ‘entry’ and ‘exit’ values of pr; sensitive here is deliberately broadly defined. For instance, as in the case of
Here, insensitivity to these critical points is also an informative property to highlight in a distance measure. As one example,
Lastly, we ask whether the within-ensemble graph distance of random networks (i.e. when pr → 1) is greater than that of small-world networks; this is indicated by a within-ensemble graph distance curve that is higher at pr = 1 than those between 10−3 < pr < 10−1 in figure 3. This property holds for distance measures that depend on node labelling (e.g. 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.
(b) Results for sparse heterogeneous ensembles
The sparse graph setting is much closer to that of real networks, which often also have heavy-tailed degree distributions [46]. This motivated the selection of the following two heterogeneous, sparse ensembles.
(i) Soft configuration model: heavy-tailed degree distribution
We study these graphs using a (soft) configuration model with a power-law expected degree distribution; i.e. the expected degree κ of a node is drawn proportionally to κ−γ. From this model, we expect two important features that graph distance measures could recover:
(vii) | For γ < 3, we know the variance of the degree diverges in the limit of large graph size n [46]. Since there should be large variations on the degree sequences for two finite instances, we might also expect the graph distances to produce maximal distance 〈D〉. | ||||
(viii) | We might also expect a monotonic decay in the within-ensemble graph distance as γ increases. For large γ, most expected node-degrees will be approximately the average degree, making the network as a whole structurally similar to an ER graph. On the other hand, when γ is small (especially when γ ≤ 3), there is a wide diversity in the degrees of nodes within the graph, and of the expected degrees of nodes across graphs (since expected degrees are i.i.d. sampled from a Pareto distribution). |
Out of the 20 studied, most distances capture both of these features. Since γ tunes the degree-heterogeneity (larger γ yielding more homogeneous graphs), a decrease in the average distance among pairs of graphs might be expected. For large γ, most expected node-degrees will be approximately the average degree, making the network as a whole structurally similar to an ER graph. On the other hand, when γ is small (especially when γ ≤ 3), there is a wide diversity in the degrees of nodes within the graph, and of the expected degrees of nodes across graphs (since expected degrees are i.i.d. sampled from a Pareto distribution). Thus a reasonable expectation would be that pairs of graphs on average become further apart as γ is decreased. This is observed in many distances, but with the exceptions of
Only one graph distance produces completely unexpected behaviour:
(ii) Nonlinear preferential attachment
The final ensemble we include here is the nonlinear preferential attachment growth model. By varying the preferential attachment kernel, parameterized by α, we can capture a range of network properties:
(ix) | As α → −∞, this model generates networks with maximized average path lengths, whereby each new node connects its m links to nodes with the smallest average degree; conversely α → ∞ generates star-like networks [47], an effect known as condensation. | ||||
(x) | At α = 1, linear preferential attachment, we see the emergence of scale-free networks [23], whereas uniform attachment α = 0 gives each node an equal chance of receiving the incoming node’s links. |
When α = 1, this ensemble theoretically generates networks with power-law degree distributions (with degree exponent, γ = 3 [24]), which is reminiscent of the results in figure 5 where we measure the within-ensemble graph distances while varying γ.
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.)
Various mean within-ensemble distances are maximized in the range α ∈ [1, 2], which is indicative of the diversity of possible graphs that can be produced by the preferential attachment mechanism in the small-α regime. For α ≪ 0, newly arriving nodes connect primarily to the lowest-degree existing nodes (for example, leading to long chains of degree-2 nodes when m = 1), making many distance measures record i.i.d. pairs of graphs as similar. For α ≫ 0, new nodes tend to connect to the highest-degree existing node, leaving a star-like network—then likewise many graph-pairs are deemed very similar. In the intermediate range (e.g. linear preferential attachment, α = 1), a much wider variety of possible graphs can arise. Thus on average, i.i.d. pairs are (usually) measured as furthest apart in that range.
For preferential attachment networks, we again see curious behaviour for
The descriptor, ψG that
Finally, as we note in §i, we are not asserting that a graph distance measure should detect the unique behaviour of linear preferential attachment (α = 1). Nor are we advocating for practitioners to abandon the use of
4. Discussion
Graph ensembles are core to the characterization and broader study of networks. Graphs sampled from a given ensemble will highlight certain observable features of the ensemble itself, and in this work, we have used the notion of graph distance to further characterize several commonly studied graph ensembles. The present study focused on one of the simplest quantities to construct given a distance measure and a graph ensemble, namely the mean within-ensemble distance 〈D〉. Note, however, that there are many ensembles for which the present methods could be repeated, as well as more graph distance measures, and infinitely many other statistics that could be examined from the within-ensemble distance distribution. Despite examining the within-ensemble graph distances for only five different ensembles, we observed a richness and variety of behaviours among the various distance measures tested. We view this work as the starting point for more inquiries into the relationship between graph ensembles and graph distances.
One promising future direction for the study of within-ensemble graph distances is the prospect of deriving functional forms for various distance measures, as we do for
We have here only studied the behaviour of graphs within a given ensemble and parameterization, which is essentially the simplest possible choice. This leaves wide open any questions regarding distances between graphs sampled from different ensembles—or even different from two different parameterizations of the same ensemble. These will be the topic of follow-up works. Nevertheless, such follow-ups will likewise only cover a very small fraction of all possible combinations.
We hope that our approach will provide a foundation for researchers to clarify several aspects of the network comparison problem. First, we expect that practitioners will be able to use the within-ensemble graph distance in order to rule out suboptimal distance measures that do not pick up on meaningful differences between networks in their domain of interest (e.g.what is an informative ‘description-distance’ comparison between brain networks may not be as informative when comparing, for example, infection trees in epidemiology). Second, we expect that this work will provide a foundation for researchers looking to develop new graph distance measures (or hybrid distance measures, such as
There were 20 different graph distances used in this work, with undoubtedly more that we have not included. Each of these measures seek to address the same thing: quantifying the dissimilarity of pairs of networks. We see the current work as an attempt to consolidate all such methods into a coherent framework—namely, casting each distance measure as a mapping of two graphs into a common descriptor space, and the application of a distance measure within that space. Not only that, we also suggest that stochastic, generative, graph models—because of known structural properties and certain critical transition points in their parameter space—are the ideal tool to use for characterizing and benchmarking graph distance measures.
Classic random graph models can fill an important gap by providing well-understood benchmarks on which to test distance measures before using them in applications. Much like in other domains of network science, having effective and well-calibrated comparison procedures is vital, especially given the great diversity of graph ensembles under study and of networks in nature.
Data accessibility
The experiments in this paper were conducted using the
Authors' contributions
All authors contributed to the conception of the project. H.H., A.D. and L.H.D. devised the formalism used in this work. H.H., B.K. and S.M. conducted simulations of the within-ensemble distances. S.M. led the development of the
Competing interests
We declare we have no competing interests.
Funding
B.K. acknowledges support from the National Defense Science and Engineering Graduate Fellowship (NDSEG) Program. G.S. and C.M. acknowledge support from the Natural Sciences and Engineering Research Council of Canada and the Sentinel North program, financed by the Canada First Research Excellence Fund. L.H.D. and A.D. acknowledge support from the National Science Foundations grant no. DMS-1829826. This work was supported in part by the Network Science Institute at Northeastern University and the Vermont Complex Systems Center.
Footnotes
1 For example, two cospectral but non-identical graphs would have distance zero according to any spectral distance measure.
2 Throughout this paper, we use the term ‘graph distance’ or ‘distance’ to refer to a dissimilarity measure between two graphs satisfying the properties we detail in §a. This language is somewhat imprecise from a mathematical perspective; many graph distances do not meet all the criteria of distance metrics. We have chosen to keep the term ‘graph distance’ at the cost of some informality to maintain consistency with much of the existing literature we draw upon. We thank one of the anonymous reviewers for their help in clarifying this matter.
3 See https://github.com/netsiphd/netrd/. This software package includes several more distances that were not included in these analyses, and as it is an open-source project, we anticipate that it will be updated with new distance measures as they continue to be developed.
4 From our preliminary analyses, the particular choice of metric can dramatically change the distance values, though we do not report this here. For an extensive description of distance metrics in general, see [12,35].
5 Note that the two distance measures based on the non-backtracking matrix (
Acknowledgements
The authors thank Tina Eliassi-Rad, Dima Krioukov, Johannes Wachs and Leo Torres for helpful comments about this work throughout.