Mind the Gap: The Disconnect Between Synthetic and Natural Edge Weights in Parallel Single-Source Shortest Path Marco D’Antonio
Thai Son Mai
Hans Vandierendonck
Queen’s University Belfast
arXiv:2607.26821v1 [cs.DC] 29 Jul 2026
Abstract
benchmarks effectively mimic the scale-free behavior of real-world networks, their edge weights are assigned via a uniform distribution in [0, 1). As demonstrated in network science literature [12, 13, 47, 70], real-world edge weights rarely fit a uniform distribution; instead, they exhibit heavytailed behaviors. This disconnect between network theory and HPC benchmarking practice raises a critical question: Are we doing SSSP benchmarking right? The discrepancy between natural and synthetic weights becomes even more pronounced when considering that most parallel SSSP algorithms are based on ∆-stepping [51], which groups vertices into buckets of width ∆ based on their tentative distance from the source. The ∆ parameter regulates the trade-off between parallelism and redundant work, since the larger a bucket is, the more vertices can be processed in parallel. However, the increased parallelism comes at a cost: vertices at greater distances may be processed concurrently with, or even before, those at shorter distances. This inevitably leads to redundant work, as these vertices might be re-evaluated when shorter paths are subsequently discovered. Consequently, fine-tuning ∆ is critical for performance. Because optimal bucket sizing depends on the distribution of path lengths, it is intrinsically linked to the underlying edge weight distribution of the graph. This naturally raises the question of whether the underlying weight distribution fundamentally alters the performance profiles of various SSSP algorithms, potentially invalidating claims of highest practical performance derived from uniform distributions. Furthermore, how do these distributions impact the tuning of ∆ and similar algorithmic parameters? And crucially, do parameter-free SSSP algorithms demonstrate better robustness when using diverse weight distributions? In this paper, we address these questions by establishing a ground truth based on real-world, naturally-weighted graphs. We select 17 large-scale graphs, with up to 42 billion weighted edges, spanning road, traffic, social, semantic, and biological networks and characterize their empirical weight distributions. Using established statistical methods [25], we fit theoretical distributions to both the body and the tail of the empirical data. Against this baseline, we evaluate six synthetic weight distributions prevalent in the literature. We then conduct a comprehensive performance analysis across seven state-of-the-art parallel SSSP implementations: five based on ∆-stepping (GBBS [31], GAP [14], Wasp [26], ∆∗ stepping, and ρ-stepping [33]), alongside two parameter-free approaches (MultiQueue-based parallel Dijkstra [61] and
Scientific research works often evaluate Parallel SingleSource Shortest Path (SSSP) algorithms using synthetic, uniformly distributed edge weights. However, real-world graphs exhibit very different, often heavy-tailed, weight distributions. This creates a disconnect between how algorithms are evaluated and their real-world performance, since most SSSP implementations inherently rely on the weight distribution for parameter tuning and work efficiency. In this paper, we explore whether current benchmarking methods unintentionally bias the performance results of these algorithms. To this end, we statistically characterize the weight distributions of 17 realworld graphs from a variety of domains and contrast them with six synthetic distributions used in the literature. Through a comprehensive evaluation of seven state-of-the-art parallel SSSP algorithms, we demonstrate severe sensitivity to edge weights, and show that evaluating with synthetic uniform weights alters optimal parameter configurations and can invert the performance hierarchy. These findings challenge existing benchmarking standards and offer practical insights for rigorous SSSP algorithm design.
1. Introduction Single-Source Shortest Path (SSSP) is a fundamental problem that has been thoroughly studied in the concurrent and parallel algorithms literature, producing implementations that are both theoretically efficient and fast in practice [16, 26, 30, 31, 33, 51, 58, 61, 62, 68, 71, 72]. Driven by the proliferation of internet-scale applications and advancements in compute and storage infrastructures, graph datasets have grown exponentially, with trillion-scale graphs being utilized in private industry as early as 2015 [23]. However, publicly available, large-scale weighted graph datasets suitable for benchmarking remain scarce. For this reason, in order to assess the scaling of an algorithm on large datasets, the standard practice in the literature is to synthesize weights for naturally unweighted graphs. Perhaps unsurprisingly, this has led to a fragmented landscape: a wide variety of synthetic weight distributions are employed across different studies, rarely with explicit justification regarding their representativeness of real-world workloads. A prominent case is the Graph500 benchmark [54], which aims to “provide useful information on the suitability of supercomputing systems for data intensive applications”, using two compute kernels as a benchmark: BFS and SSSP. While the R-MAT [22] topologies chosen for such
1
where the ∼ symbol means “roughly proportional” [66]. Due to this ambiguous definition, empirical distributions are frequently mischaracterized as power laws, with classifications varying heavily depending on the chosen theoretical criteria or the fitting methodology [6, 19, 25, 37, 38, 40, 60, 66]. In this work, we use the definition of Clauset et al. [25] in which a continuous power-law distribution is described by the following probability density: −α α−1 x p(x) = , xmin xmin
parallel Bellman-Ford [15, 53]). We provide a comparison of the ∆ tuning for each implementation and gather insights into how different implementations behave across varying topologies and weight distributions, highlighting large differences between natural and synthetic weights. Furthermore, we compare the performance of fine-tuned implementations under different weight distributions, highlighting the large variety of results and how changing the weight distribution can fundamentally invert which algorithm achieves the highest practical performance. In summary, the main contributions of this paper are as follows: • A statistical characterization of empirical weight distributions across a set of 17 naturally weighted graphs from a variety of domains. • A comprehensive performance evaluation of seven state-of-the-art parallel SSSP implementations, analyzing how different graph topologies and weight distributions impact optimal ∆ tuning. • An empirical demonstration of the sensitivity of parallel SSSP algorithms to the edge weight distribution, alongside practical insights for users, performance analysts, and algorithm designers. The rest of the paper is organized as follows. Section 2 presents the background on graphs, power-law distributions, and parallel SSSP, introducing the implementations compared in our study. The experimental setup of our analysis is presented in Section 3, along with the naturally-weighted graph datasets and the synthetic weight distributions used in literature. Section 4 characterizes the edge weight distribution of the naturally-weighted graphs datasets. Section 5 analyzes the impact on performance of different weight distributions across the compared implementations. The impact of weight distributions on parameter-based algorithms is presented in Section 6. Section 7 concludes the paper with a discussion and insights for different SSSP algorithm practitioners.
where xmin is the lower bound of the power law, and α is a positive scaling parameter. While this rigorous definition is often debated in the context of vertex degrees [66], the statistical approach described by Clauset et al. [25] is universally applicable to any empirical data. An alternative definition for power-law distributions has been provided by Voitalov et al. [66], encompassing all distributions whose probability density function is given by p(x) = ℓ(x)x−α , where ℓ(x) is a slowly varying function, i.e. limx→∞ ℓℓ(tx) (x) = 1 for any t > 0. In this context, the power law described by Clauset et al. is defined as a “pure” power law and represents the special case in which ℓ(x) is a constant.
2.3. Parallel Single-Source Shortest Path We study edge weight distributions in the context of the Single-Source Shortest Path (SSSP) problem, where given G and a source vertex s ∈ V, the objective is to find the shortest distance from s to any vertex v that is reachable from s. In a sequential setting, SSSP is traditionally solved by Dijkstra’s algorithm [32] which selects at each step the vertex v with the shortest tentative distance d[v] using a priority queue, and updates the distance of all of its neighbors, starting with d[s] = 0. Parallel SSSP algorithms generally fall into one of two execution paradigms: synchronous or asynchronous. Synchronous approaches are predominantly based on the Bulk Synchronous Parallel (BSP) model [65], where computation proceeds in distinct supersteps separated by global synchronization barriers. The most prominent algorithm in this category is ∆-stepping [51], which groups vertices into buckets of width ∆ depending on their tentative distance, i.e., bucket i will hold vertices with distance in [i · ∆, (i + 1) · ∆). A bucket is fully processed in parallel during a superstep before threads synchronize and move to the next. The cost of parallelism, however, is redundant work, since vertices will not be processed following the work-efficient ordering of Dijkstra’s algorithm. Moreover, ∆-stepping introduces an additional challenge: finding the optimal ∆ value that balances parallelism against redundant work. The optimal ∆ depends both on the graph topology and on the edge weight distribution, as we will point out later in the paper. The parallel Bellman-Ford algorithm [15, 53] also operates synchronously, offering a parameter-free alternative that converges also in the presence of negative weights, though it is generally slower in practice due to a higher volume of redundant vertex re-evaluations.
2. Background and Related Work 2.1. Graph Notation and Topologies Let G be a directed weighted graph G = (V, E, w) with a set of vertices V, a set of edges E ⊂ V × V, and a weight function w. Throughout this paper, w can either be w : E → R≥0 or w : E → Z≥0 , depending on the dataset or synthetic weight generation method. Table 1 provides a list of all the naturally-weighted graphs in this work, indicating whether they use integral or floating-point weights. Where there is no ambiguity, we denote the number of vertices and edges as n = |V | and m = |E|, respectively.
2.2. Power-Law Distributions In network literature [10] a quantity x obeys a power law if it is drawn from a probability distribution p(x) ∼ x−α ,
2
Alternatively, asynchronous models eliminate strict global barriers, allowing threads to process the active vertex frontier continuously and independently. To achieve scalability without the strict ordering of ∆-buckets, these implementations rely on highly concurrent data structures and execution strategies, such as relaxed priority queues [4, 58, 61, 69] or work-stealing [26, 56, 58]. While asynchronous execution removes the overhead of global barriers, it allows threads to process vertices out of order. Because this can lead to a drastic increase in redundant work, many asynchronous approaches still rely on parameters like local ∆ buckets to guide threads toward shorter paths. Therefore, the efficiency of these algorithms is heavily dictated by their concurrent data structures, the tuning of their parameters, and how both react to the underlying edge weight distribution. In this study, we analyze state-of-the-art parallel SSSP implementations. These include five algorithms based on ∆-stepping (the GAP Benchmark Suite [14], GBBS [31], ∆∗ stepping, ρ-stepping [33], and Wasp [26]), one based on a relaxed priority queue (MultiQueue [61, 68]), and a parallel Bellman-Ford algorithm [15, 33]. The implementations have several differences which in turn affect their performance on different kinds of graphs.
asynchronously: they first process their active bucket, then try to steal vertices with shorter tentative distances from other threads, and finally fall back to their thread-local lists if no higher-priority vertices are available. The MultiQueue. This is a relaxed priority queue structure used to back an asynchronous parallel implementation of Dijkstra’s algorithm. It maintains c · p lock-protected priority queues, where p is the number of threads and c is a scaling multiplier (we set c = 2). Vertices are extracted by randomly selecting two queues and extracting the higherpriority vertex, while generated vertices are pushed to a randomly chosen queue. We use a high-performance implementation [68] in which threads stick to a certain queue for a number of trials. Although stickiness is a parameter that significantly impacts performance [68], we fix it at s = 64 to evaluate the MultiQueue strictly as a parameter-free algorithm.
3. Experimental Setup In this section we present the naturally-weighted graphs datasets, the synthetic distributions gathered from the literature, and the setup of our experiments.
3.1. Datasets
GAP. This framework implements a BSP-based ∆-stepping using thread-local buckets. At each superstep, the globally smallest bucket index is selected, and local vertices are moved to a global frontier to balance the workload. GAP implements the bucket fusion optimization [72], in which each thread processes the local content of the current bucket after processing the frontier in order to reduce synchronization costs.
Large-scale graphs are usually drawn from real-world networks such as road networks, social networks [1, 2, 9, 24, 35, 37, 42, 44, 52, 55], web crawls [3, 18, 43, 49, 50], and biological networks [11, 17, 39, 40, 60]. For our study, we selected real-world weighted graphs of sufficient size to benefit from parallel processing. Table 1 groups the datasets in road graphs and skewed-degree graphs. Road graphs are typically characterized by a large diameter and a low, bounded average degree (e.g., the maximum out-degree in the north-america graph is 24, with an average degree of roughly 1). Skewed-degree graphs are instead characterized by a small diameter and a larger average degree, and are often (loosely) categorized as scale-free networks, in which the degree distribution follows a power law.
GBBS. This implementation leverages the parallel bucketing structure introduced in Julienne [30] and operates in a BSP fashion. Its bucketing interface allows threads to extract all vertices mapped to a specific bucket in parallel and, following vertex label updates, to resize and update the buckets in parallel. ∆∗ -stepping and ρ-stepping. Both algorithms process all vertices up to a specific distance threshold during each step. They differ primarily in how this threshold is calculated: ∆∗ -stepping increments the threshold by a fixed ∆ at each step, whereas ρ-stepping dynamically sets the threshold to the ρ-th smallest distance within the current frontier. The Lazy-Batched Priority Queue is introduced to support this framework and is implemented as a parallel hash-bag to extract and update vertices [67].
Road Graphs. A prominent example of a weighted largediameter graph is a road network, in which vertices represent intersections, edges represent streets, and weights represent street lengths. One of the most frequently used graphs in the literature is the USA road network [7, 14, 30, 72] from the 9th DIMACS challenge [28]; however, the dataset is from 2006 and the current North America dataset contains more than double the number of its edges. For this reason, we converted the June 2025 versions of the OpenStreetMap (OSM) networks into the Matrix Market format by extracting the source and destination of each edge in the network along with its length. The extracted node IDs were re-indexed from 1 to n in the Matrix Market format. We release these datasets publicly with this paper1 These are, to the best of our knowledge, the latest converted versions of the OSM networks publicly available.
Parallel Bellman-Ford. This is a BSP-based version of the classic Bellman-Ford algorithm. The implementation by Dong et al. [33] contains multiple optimizations: only processing active vertices, direction-optimization, and parallel sharing of large neighborhoods. It is not dependent on parameters such as ∆. Wasp. The Wasp algorithm stores unresolved vertices across two data structures: a work-stealing-enabled active bucket and a thread-local list of future buckets. Threads progress
1. The datasets have been extracted using data from OpenStreetMap, available under the Open Database License.
3
TABLE 1: Naturally-weighted graph datasets used in the analysis. An overline on the graph abbreviation means the graph is undirected, an arrow means the graph is directed. n is the number of vertices, m is the number of directed edges – every edge is counted twice in undirected graphs. Abbr.
Graph
− → CA − → AO − → SA − → AF − → NA − → AS − → EU − → PL
Road Graphs central-america 3 648 449 australia-oceania 6 887 586 south-america 22 892 188 africa 35 279 191 north-america 95 654 077 asia 105 430 206 europe 141 140 217 planet 412 323 215
4 549 287 9 079 172 30 870 271 47 019 425 122 973 777 134 903 234 180 706 815 531 871 445
ARC EUK IS MC MW CA CM CS ML
Skewed-degree Graphs archaea 1 644 227 eukarya 3 243 106 isolates-sg1 34 982 171 metaclust 282 195 323 mawi† 226 196 185 coauth-aminer† 92 830 929 coauth-mag† 173 195 937 colisten-spotify† 3 604 455 moliere 30 239 687
204 792 654 359 763 936 20 981 181 510 42 788 019 518 480 047 890 647 673 142 1 089 154 246 1 927 482 013 6 677 301 366
n
TABLE 2: Edge weight distributions used in benchmarking. Type
Uniform
m Normal
Parameters
Proposed in
Abbr.
a = 0, b = 1*
Murphy et al. [54] Beamer et al. [14] Dhulipala et al. [30] Dong et al. [34]
UG500 UBEAM UDHUL UDONG
a = 1, b = 255† a = 1, b = ⌊log|V |⌋† a = 1, b = 218 † µ = 0, σ =q1
µ = 1, σ =
n m
Panitanarak et al. [57]
NPANI
Anonymous Reviewers
NANON
* The uniform distribution is defined in a right-open interval. † The distribution has integer weights.
weighted graph vertices represent songs, and the weight of an edge connecting two songs equals the number of sessions containing both songs.
3.2. Synthetic Weight Distributions Table 2 reports the different synthetic weight distributions we analyze for each graph, based on previous use in the literature. The table highlights that recent benchmarks and studies have mostly relied on uniformly distributed weights. Specifically, the Graph500 benchmark [54] assignes uniformly-distributed floating-point weights in [0, 1), whereas other distributions proposed in other benchmarks [14] and shortest path literature [30, 34] use integer weights. A normal weight distribution has been previously used by Panitanarak et al. [57]. Because the paper does not explicitly state the parameters of their distribution, we assume a standard normal distribution. Because our formulation of the SSSP problem requires non-negative edge weights, we take the absolute value of the generated weights, effectively creating a half-normal distribution. Finally, we include a second normal distribution parameterized specifically for graph density, as suggested by an anonymous reviewer during a prior peer-review process. The p distribution has mean µ = 1 and standard deviation n ; consequently, the standard deviation decreases σ= m as the graph density increases. This distribution is also lefttruncated to ensure weights are non-negative. Additionally, a log-uniform distribution was used by Madduri et al. [48], however, we were unable to replicate their distribution as the paper did not report the generation parameters.
† The graph has integer weights, in all other cases weights are
single-precision floating point values.
Skewed-degree Graphs. While many skewed-degree graphs are used for evaluating performance in different benchmarks [14, 45, 54], most standard benchmark datasets are unweighted graphs. The ten skewed-degree graphs listed in Table 1 are sourced from a mix of general-purpose and specialized domain-specific repositories. The mawi and moliere datasets are obtained from the SuiteSparse Matrix Collection [27], a standard repository for diverse graph and sparse matrix benchmarks. The mawi dataset represents network traffic, where vertices are hosts and edge weights denote the number of packets exchanged between them. The moliere dataset models biomedical knowledge for hypothesis generation [63]. Its vertices represent either a PubMed document, a Unified Medical Language System term, or an n-gram. Edge weights represent semantic distance: the graph features explicit 0-weight edges to connect identical concepts, while larger values model weakly related concepts. The archaea, eukarya, isolates-sg1, and metaclust datasets belong to the HipMCL data repository [8]. All four are sequence similarity graphs, where vertices represent protein sequences and edge weights represent the similarity scores between them. The coauth-aminer, coauth-mag, and colisten-spotify datasets [41, 64] originate from the Austin R. Benson dataset repository2 . Among these, coauth-aminer and coauth-mag are co-authorship graphs, where vertices represent authors and edge weights denote the number of co-authored papers. The colisten-spotify dataset was built starting from a large number of user streaming sessions, each with at most 20 songs. In the
3.3. Experimental Setup All performance measurements are conducted on a dual-socket AMD Zen 3 EPYC 7713 processor with 64 cores per socket, for a total of 128 threads, 1TiB DRAM, and 4 NUMA nodes per socket. All codebases were compiled with GCC 14.1.0, using the default C++ standard of each respective implementation, while enforcing the -O3 and -march=native optimization flags. Experiments were executed using numactl -i all to interleave memory allocations evenly across all available NUMA nodes, which improves memory bandwidth usage by distributing the graph data. The performance measurements are averaged across 22 different start vertices, chosen within the largest
2. Available online at https://www.cs.cornell.edu/~arb/data/.
4
connected component, or the largest strongly connected component if the graph is directed.
that render the empirical data mathematically most probable. All the natural weight distributions that we studied are best modeled using different distributions for their body and their tail. The optimal boundary separating the body from the tail, xmin , is established by finding the value that minimizes the Kolmogorov-Smirnov (KS) distance [59] between the empirical data and the bestfit model for the tail. Edge weight samples larger than xmin are subsequently used to fit the left-truncated distribution for the tail, and the samples smaller than xmin are used to fit the body of the distribution. 2) Goodness-of-Fit: MLE identifies the best-fitting parameter values, but the procedure does not prove that the shape of the distribution function is appropriate. To test the plausibility of the distribution shape, we use a semi-parametric bootstrapping procedure [36]. We generate random datasets following the proposed edge weight distribution. Each dataset consists of a large number of randomly generated edge weights which we independently fit to the proposed distribution function and calculate its KS distance. The p-value is formally defined as the fraction of synthetic datasets whose KS distance is greater than or equal to the empirical KS distance. A high p-value indicates that the empirical deviation from the theoretical model could reasonably be attributed to random statistical fluctuations, whereas a low p-value (typically p ≤ 0.1) signifies that the deviation is too large to be random, resulting in the rejection of the hypothesis. 3) Alternative Hypotheses: Even if a specific distribution passes the goodness-of-fit test, another model might offer a superior fit. Therefore, we perform a likelihood-ratio test to quantitatively compare the primary hypothesized model against alternative candidate distributions appropriate for that data domain. Applying this methodology to the scale of our datasets presented a significant computational challenge. Standard software tools, such as the Python powerlaw package [5] or the plfit implementation, proved computationally prohibitive at this scale, or otherwise required random sampling that could compromise the integrity of the tail analysis. To overcome this, we developed a parallel C++ implementation of the Clauset et al. methodology. Rather than processing raw weight arrays, our implementation operates on an exact histogram of the empirical weight data, precomputes intermediate results, and tests the KS distance of the xmin candidates in parallel.
4. Characterization of Natural Weights As a starting point for our study, we characterize the empirical edge weight distributions of our graph datasets and contrast them against synthetic weight distributions. Let X be the random variable representing the possible edge weights. We define the cumulative distribution function (CDF) as F(x) = P(X ≤ x), and define the complementary CDF (CCDF), as F(x) = 1 − F(x) = P(X > x). Figure 1 shows the CDF and CCDF of the weight distribution. From a first visual inspection we conclude: Observation 1: Synthetic weight distributions are fundamentally different from natural edge weight distributions. Indeed, the empirical CDF and CCDF starkly contrast with those expected from synthetic uniform or normal distributions. Due to space constraints, we only show the weight distributions for some representative graphs; however, all the other graphs follow similar patterns. In particular, all road graphs span a broad range of weights, with low probability of edges with weight larger than 103 ; discrete skewed-degree graphs exhibit far fewer unique weight values, due to both their integer nature, and the low probability of values larger than 10; biological networks – generated via sequence similarity algorithms – exhibit continuous weights strictly bounded between zero and one, resulting in significantly less skewed distributions.
4.1. Fitting Weight Distributions To better understand the properties of real-world graphs, we systematically characterize their empirical edge weight distributions. By doing so, we aim to inform future benchmark design and provide critical context for the performance analysis in Section 5. The CDF and the log-log CCDF provide immediate visual intuition regarding the structure of the data; in particular, they highlight the clear distinction between the body and the (heavy) tail of the distributions, which must be modeled independently. To characterize both the body and the tail of the weight distributions, we adopt the statistical framework established by Clauset et al. [25], which has been previously utilized to analyze the degree distributions of various real-world graphs [19, 37, 49, 50]. Furthermore, although the method was originally formulated to analyze tail behavior, its principles can be adapted to rigorously characterize the body of the distribution as well. The generalized pipeline consists of three steps: 1) Parameter Estimation: We estimate the parameters of the hypothesized distribution using a Maximum Likelihood Estimator (MLE) [21, 25]. The maximum likelihood method estimates the parameters of an hypothesized distribution given the empirical data. This is achieved by maximizing a likelihood function, systematically calculating the distribution parameters
4.2. Analysis of the Distribution’s Tail In the tail analysis, we evaluate the power-law hypothesis against two alternative heavy-tailed models: a power law with an exponential cutoff, and a log-normal distribution. Because our analysis focuses strictly on the tail domain (x ≥ xmin ), we fit a left-truncated log-normal distribution to the data. To perform the goodness-of-fit test, we evaluated the power-law hypothesis using 2500 synthetic datasets –
5
10−6
0.000 1 2 3 4 5 6 7 1 2 3 4 5 6 7
moliere
1.00 0.75
10−4 10−7
0.25
0.00
Weight (10 x )
-4 -3 -2 -1 0
1
2
3
4
1
Weight (10 x )
2
3
eukarya
1.00
10−1
0.50
0.75
0.00
-4 -3 -2 -1 0
Weight (10 x )
1.0 0.5
P(X > x)
1 2 3 4 5 6
Weight (10 x )
100
10−2
Weight
10−7
0.25
4
10−1
0.5
10−4
0.50
0.000 1 2 3 4 5 6
0.50 0.25
P(X ∙ x)
10
0.25
0.000
−6
10−1
0.75
P(X > x)
0.50
colisten-spotify
1.00
metaclust
1.00
1.0
0.75
100 10−1
0.50 10−2
0.25
0.00
0.5
1.0 0.5
Weight
P(X > x)
10−3
P(X ∙ x)
0.25
10−3
P(X ∙ x)
100
0.50 0.25
10−6
P(X > x)
0.75
0.50
Log-normal Body 100
0.75
Weight (10 x )
P(X > x)
mawi
10−3
0.00 0 1 2 3 4 5 6 0 1 2 3 4 5 6
Weight (10 x )
1.00
0.75
Log-normal Tail
coauth-aminer
1.00
P(X ∙ x)
0.00 0 1 2 3 4 5 6 0 1 2 3 4 5 6
100
P(X > x)
10
0.25
−6
Power-law Tail
planet
P(X ∙ x)
0.50
Data CCDF
P(X ∙ x)
P(X ∙ x)
10−3
1.00
P(X ∙ x)
0.75
100 P(X > x)
north-america
P(X > x)
Data CDF 1.00
1.0
Figure 1: Edge weight distributions of the datasets. For each graph, the left panel displays the Cumulative Distribution Function (linear scale) with a superimposed log-normal fit. The right panel shows the Complementary CDF (logarithmic scale) with a power-law and log-normal fit applied to the tail. The x-axis scale varies depending on the specific graph. TABLE 3: Statistical characterization of the tail and body for edge weight distributions across evaluated graph datasets. The analysis shows that while the tail behavior varies between power-law (PL) and log-normal (LN) models, the body of the distribution (x < xmin ) is universally best described by a log-normal fit. Tail Graph
Best Fit
%tail
xmin
central-america australia-oceania south-america africa north-america asia europe planet
PL LN PL PL PL PL PL PL
0.1 % 0.3 % 0.009% 0.009% 0.09 % 0.02 % 0.09 % 0.02 %
archaea eukarya isolates-sg1 metaclust mawi† coauth-aminer† coauth-mag† colisten-spotify† moliere
LN LN LN LN LN LN LN LN PL
11.6 % 31.4 % 23.1 % 25.8 % 0.03 % 0.004% 0.03 % 0.7 % 15.4 %
PL: Power-law; LN: Log-normal; dKS : Kolmogorov-Smirnov distance;
Body dKS
Parameters
Road Graphs 4437.6 0.016 α = 4.01 7378.6 0.007 µ = 3.81, σ = 1.76 21 192.4 0.009 α = 4.08 28 814.6 0.011 α = 3.68 4858.6 0.006 α = 3.58 15 176.4 0.007 α = 3.29 3394.4 0.007 α = 3.85 13 493.6 0.005 α = 3.32 Skewed-degree Graphs 0.7 0.030 µ = −0.29, σ = 0.14 0.6 0.036 µ = −0.49, σ = 0.25 0.6 0.020 µ = −0.78, σ = 0.30 0.5 0.022 µ = −1.58, σ = 0.46 241.0 0.011 µ = −12.80, σ = 5.81 92.0 0.026 µ = −44.33, σ = 4.18 62.0 0.036 µ = −123.18, σ = 7.30 92.0 0.010 µ = −27.46, σ = 5.86 0.1 0.028 α = 3.10
%tail : Percentage of edge weights x ≥ xmin ; † The graph has integer weights.
as suggested by Clauset et al. [25] to achieve a p-value precision of ±0.01. For the vast majority of our datasets, this test resulted in a p-value of p < 0.01, therefore rejecting the power-law hypothesis. We observed statistically plausible fits (p > 0.1) for only two networks: africa (p = 0.7336) and south-america (p = 0.9792). As shown in statistical literature [19, 29, 46], when evaluating hypotheses for massive datasets, p-values are known to rapidly approach zero, as minor empirical fluctuations become statistically significant enough to reject the strict theoretical model. Indeed, the power-law hypothesis was validated only in such datasets where the tail encompasses a very small fraction (roughly 0.009%) of the total edges. To determine which distribution models the tail most accurately, Table 3 reports the superior model determined by the likelihood-
dKS
Parameters
0.043 0.043 0.062 0.032 0.022 0.024 0.009 0.018
µ = 4.38, σ = 1.22 µ = 3.79, σ = 1.66 µ = 4.45, σ = 1.39 µ = 4.55, σ = 1.29 µ = 3.94, σ = 1.43 µ = 4.29, σ = 1.32 µ = 3.85, σ = 1.44 µ = 4.07, σ = 1.42
0.046 0.048 0.037 0.034 0.349 0.506 0.455 0.349 0.035
µ = −0.75, σ = 0.26 µ = −0.85, σ = 0.20 µ = −0.82, σ = 0.20 µ = −0.90, σ = 0.16 µ = 0.35, σ = 0.51 µ = 0.13, σ = 0.41 µ = 0.25, σ = 0.54 µ = 0.53, σ = 0.84 µ = −4.05, σ = 0.87
xmin : Tail starting point;
ratio test. We observe that the log-normal hypothesis is a better tail fit for more than half of the evaluated datasets. This conclusion is further supported visually in Figure 1, where the power-law and log-normal tail fits are indicated by cyan and purple dashed lines, respectively. Observation 2: The tail of the edge weight distribution does not always follow a power-law distribution.
4.3. Analysis of the Distribution’s Body The body of the weight distribution is where the majority of data points reside; for this reason, characterizing the behavior of the body can provide insights useful to replicate natural distributions. Visual inspection of the CDF in Figure 1 suggests a log-normal fit for the data. To confirm this we fit a right-truncated log-normal distribution, setting
6
UG500
NAT
UBEAM
central-america
UDHUL
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF 0.1
Time (s)
0.5
1
2
Speedup
1
10
0.1
1
Speedup
Time (s)
moliere
1
10
1
Speedup
2
2
0.5
Speedup
0.5
1
10
Time (s)
1.5
1
2
0.5
Speedup
1
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF 0.1
Speedup
0.25
metaclust
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF 5
1.0
Time (s)
eukarya
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF Time (s)
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF
4
Time (s)
NANON colisten-spotify
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF
mawi Δ*-step. ρ-step. GBBS GAP Wasp MQ BF
NPANI
coauth-aminer
Δ*-step. ρ-step. GBBS GAP Wasp MQ BF 0.01
UDONG
planet
Time (s)
0.25
Speedup
1
10
100
Time (s)
0.5
Speedup
Figure 2: Performance of SSSP implementations on different graphs for each weight distribution. The left panel indicates the execution time, the right panel shows the speedup of the synthetic weight distributions against the natural weight distribution. Integer weights are indicated with a square symbol, while float weights are indicated with a circle symbol. Road Graphs. For road graphs, we observe that most SSSP implementations execute significantly faster when using synthetic weights rather than natural weights. A notable exception is ρ-stepping, which exhibits high variability; it experiences up to a roughly 2× slowdown on central-america and shows similar, though less pronounced, slowdowns on other road graphs. The performance gap is particularly significant for the parallel Bellman-Ford algorithm: with naturally weighted road graphs, BellmanFord suffers from very high and variable execution times depending on the traversal’s source vertex, whereas synthetic weights artificially mask this inefficiency, resulting in massive apparent speedups. In fact, for certain graphs and synthetic weight distributions – such as africa, australia-oceania, and central-america – BellmanFord is among the most efficient algorithms evaluated.
the upper bound to the xmin value previously identified for the tail. Running a full bootstrap goodness-of-fit test on the distribution body was computationally prohibitive. Furthermore, because the empirical body accounts for 68% to 99.991% of the total data depending on the dataset, any theoretical fit would be rejected by the test due to the same large-sample artifacts discussed in the tail analysis [29, 46]. Instead, we rely on the likelihood-ratio test to compare the log-normal hypothesis against two alternative models: a right-truncated exponential distribution and a righttruncated Weibull distribution. In all cases, the likelihoodratio test confirmed that the log-normal distribution provides a statistically better fit. Figure 1 shows the lognormal body fit with an orange dotted line, while Table 3 indicates the KS distance of the fit and the parameters of the right-truncated log-normal distribution. We observe that graphs belonging to the same structural class exhibit similar distribution parameters, which is reflected in the similar shapes in Figure 1. Integer skewed-degree graphs proved particularly difficult to fit, as evidenced by shown by their larger KS distances and the shape of the curve in the CCDF, which exhibits an initial overestimation of the probability before flattening out as it approaches xmin .
Skewed-degree Graphs. In contrast to road graphs, synthetic weight distributions generally degrade performance on skewed-degree graphs. Substituting natural weights with synthetic counterparts consistently shifts the execution into the slowdown region. In several cases, synthetic distributions induce up to a 4× slowdown compared to the natural weights (visible prominently in implementations like GAP, Wasp, and MQ on coauth-aminer).
Observation 3: The log-normal distribution provides a robust fit for the body of empirical edge weight distributions.
Observation 4: Synthetic weight distributions misrepresent real-world SSSP performance, artificially inflating execution speeds on large-diameter graphs while exhibiting slowdowns and high-variability on skewed-degree topologies.
5. Performance Analysis To evaluate the impact of weight distributions on execution time, we determine the optimal ∆ for each combination of SSSP implementation, graph, and weight distribution. We then compare these best-performing configurations.
5.2. Performance Sensitivity Figure 3a shows the relative speedup obtained when substituting natural weights with synthetic distributions, where each data point corresponds to a distinct graph dataset. We summarize the results in Figure 3b using a sensitivity factor. This metric is computed as the geometric mean of the absolute logarithmic speedups measured
5.1. Performance Impact of Weight Distribution Figure 2 illustrates the execution time of the SSSP implementations across eight representative graphs, highlighting the relative speedup of synthetic weight distributions compared to the natural weight baseline.
7
ρ-step.
GBBS
GAP
Wasp
MQ
BF
8x 4x 2x 1x 0.5x 0.25x 0.125x UG500
UBEAM
UDHUL
UDONG
Weight Distribution
NPANI
NANON
Δ*-step. 2.37x
1.98x
1.60x
2.38x
2.36x
1.69x
ρ-step. 2.29x
1.91x
1.59x
2.29x
1.95x
1.46x
GBBS 2.07x
1.92x
1.50x
2.06x
2.11x
1.40x
GAP 2.74x
2.26x
2.05x
2.79x
2.98x
1.94x
Wasp 1.61x
1.53x
1.36x
1.62x
1.66x
1.41x
MQ 1.37x
1.31x
1.25x
1.36x
1.35x
1.30x
BF 8.32x UG500
6.05x
4.61x
8.28x
7.59x
4.62x
UBEAM
UDHUL
UDONG
NPANI
NANON
Weight Distribution
Sensitivity Factor
Speedup
Δ*-step.
(a) Relative performance of the implementation across different distri- (b) Sensitivity of each implementation to different weight distributions compared to the natural weights baseline. bution showing the relative performance variability.
Figure 3: Sensitivity analysis of the parallel SSSP implementations to synthetic weight distributions. between synthetic distributions and the natural weight distribution. By taking the absolute value, the metric ensures that both performance improvements and degradations are symmetrically captured, preventing opposing fluctuations from canceling each other out. Overall, synthetic weights consistently fail to mirror real-world execution, inducing both severe artificial speedups and massive slowdowns. The Bellman-Ford algorithm is particularly sensitive to the weight distribution with speedups as high as 180× or as low as 0.04×. ∆∗ -stepping, ρ-stepping, GBBS, and GAP exhibit similar overall sensitivity factors in the heatmap; however, the scatter plot reveals distinct underlying behaviors. Specifically, ρ-stepping predominantly suffers slowdowns across all synthetic weight distributions, whereas the other three implementations display a more balanced variance around the natural weight baseline. We investigate the mechanics underlying these performance variations by plotting the frontier size of GAP (a synchronous implementation) on the planet and colisten-spotify datasets in Figure 4. On the planet graph, executing with natural weights requires 7× more iteration steps compared to the UBEAM distribution, while the total number of edge relaxations is only 11% larger. Different edge weights can thus cause a reshuffling of active vertices to different synchronous iterations. This occurs, e.g., when a large edge weight placed in a critical position assigns a large tentative distance to a high-degree vertex, postponing the processing of a large number of neighboring vertices for several iterations. As such, edge weights dictate the required number of BSP steps, independently of topology. On the colisten-spotify graph, the UDONG distribution incurs a 4× slowdown relative to natural weights. Here, the synthetic weights trigger both a 3.4× increase in relaxations and a 2.7× increase in BSP steps, proving that weight distributions can simultaneously inflate both the computational work and the number of synchronous iterations. Such a scenario could be caused by the presence of parallel paths, where the order of processing paths enforces repeated re-activation of the same vertices. In contrast, Wasp and the MultiQueue (MQ) exhibit the lowest sensitivity to weight distributions. This robustness is visually confirmed by their tightly clustered data points in the scatter plot – disrupted only by few outliers – and
UBEAM
NAT
Frontier Size
106
planet
UDONG
colisten-spotify
105 104 103 102 101 100 0
4k
8k
12k 0
Iteration Step
400 800 1.2k
Iteration Step
Figure 4: Size of the frontier (in vertices) in each synchronous execution step in GAP SSSP. their consistently low sensitivity scores across all evaluated distributions (Figure 3a). We attribute the lower sensitivity in these two implementations to asynchrony. Asynchronous algorithms progress the computation by processing the next best vertex, irrespective of their tentative distance compared to an artificial ∆-based distance. Observation 5: Edge weights dictate both computational work and the distribution of work over synchronous steps, causing performance instability for synchronous algorithms. Asynchronous algorithms absorb variations in edge weights, yielding more robust performance.
6. ∆-tuning Analysis For SSSP algorithms based on the ∆-stepping paradigm, the underlying edge weight distribution inherently influences the optimal tuning of the ∆ parameter. To systematically evaluate this impact, we profile the execution time of each implementation across a wide sweep of ∆ values. Specifically, we test power-of-two increments ranging from 2−20 to 225 . For natural and synthetic integer distributions, we restrict this sweep to integer values (∆ ≥ 1).
6.1. Tuning Penalty Figure 5 illustrates the aggregated ∆ mis-tuning penalty – calculated as the geometric mean of the slowdowns relative to the optimal ∆ configuration – across all graphs for each
8
Δ*-step. 4.23x
1.86x
2.82x
1.87x
6.79x
1.98x
5x
5.24x
4.27x
2.59x
2.45x
6.44x
7.07x
GBBS 1.97x
2.01x
1.78x
1.55x
1.69x
2.11x
1.90x
3x
GAP 2.69x
2.88x
3.51x
2.90x
4.01x
2.88x
2.92x
2x
Wasp 4.92x
7.60x
7.85x
5.11x
5.72x
7.32x
5.32x
NAT
UG500
UBEAM
UDHUL
UDONG
NPANI
NANON
Slowdown
ρ-step. 3.95x
Weight Distribution
Observation 7: Different edge weight distributions dictate distinct optimal values for ∆, often shifting the ideal parameter by several orders of magnitude and completely invalidating the portability of parameters tuned on synthetic graphs.
2.12x
As demonstrated in the previous section, no parameterized parallel SSSP implementation is entirely immune to mis-tuning penalties. However, ρ-stepping presents a particularly interesting case. The original work introduced the algorithm as a robust alternative to ∆-stepping, suggesting that a consistently large parameter – such as ρ = 221 – serves as an effective, tuning-free default. Specifically, the paper notes that configurations between 220 and 224 almost always remain within a 20% performance margin of the optimal execution time. Our experimental analysis reveals a more nuanced picture: the tuning behavior of ρ-stepping remains highly coupled to both edge weights and graph topology. As highlighted in Figure 6, for natural weights, the planet graph has an optimal ρ = 213 , which falls far outside the suggested default range. Similarly, on the isolates-sg1 network, even when applying the exact UDONG synthetic distribution evaluated in the original paper, the optimal parameter is found at ρ = 212 . In such cases, increasing the value of ρ further incurs notable performance degradation rather than staying within the expected 20% margin. This demonstrates that theoretical parameter portability is ultimately bound by structural and weight-driven constraints.
1x
Figure 5: Aggregated ∆ mis-tuning penalty across graphs. Values approaching 1.0× indicate robustness to ∆; darker cells reveal severe sensitivity to parameter tuning. weight distribution. We observe that Wasp suffers from the highest average mis-tuning penalty, demonstrating severe sensitivity to suboptimal parameters. This is followed by ρ-stepping, which exhibits high penalties particularly on the UG500 , NPANI , and NANON distributions. Conversely, GBBS proves to be the most robust framework regarding parameter tuning, exhibiting the lowest average slowdowns across all evaluated distributions. Several methodological caveats are necessary to contextualize these results. First, GBBS failed to produce correct results for ∆ < 1 on naturally weighted road networks; these invalid runs are excluded. Second, because heavily mis-tuned ∆ values frequently caused execution times to exceed our strict ten-minute job limit (a threshold sufficient to complete all trials with an optimally tuned ∆), not every implementation successfully completed the entire parameter sweep. To ensure a fair comparison, the aggregated penalties shown in Figure 5 are computed exclusively over the intersection of ∆ values that successfully executed across all implementations for a given graph. This intersection yields an average of 22 valid ∆ data points per configuration.
Observation 8: While theoretically robust, the optimal configuration for ρ-stepping is still tied to both graph topology and edge weight distribution. Consequently, relying on a static large default parameter frequently incurs severe performance penalties in practice.
Observation 6: Mis-tuning slowdown is present across all distributions, highlighting how ∆-tuning is crucial for achieving peak performance. However, the severity of this penalty is fundamentally dictated by algorithmic design, with some frameworks proving highly resilient while others suffer drastic performance degradation when suboptimally configured.
By looking at the overall curve of the performance with different ∆, we notice that the weight distribution impacts the shape of the curve. This is visible for both the isolates-sg1 and colisten-spotify graphs for the GBBS and ρ-stepping implementations. For example, on isolates-sg1, the execution time under the natural weight distribution stabilizes into a plateau for larger ∆ values. Conversely, the UDONG distribution creates a clear global minimum for both implementations, after which performance sharply degrades. This variability directly dictates the complexity and efficiency required of any dynamic ∆-tuning strategy. For instance, while ∆ = 223 has close to optimal performance on GBBS with the natural weight distribution, applying the same ∆ with the UDONG incurs a performance degradation of over an order of magnitude.
6.2. Tuning Behavior To demonstrate the impact of edge weight distributions on the tuning behavior of ∆-based implementations Figure 6 shows the performance of the analyzed SSSP algorithms with different weight distributions when sweeping across values of ∆. Different distributions are indicated by different markers. By focusing on lines of the same color and comparing the optimal ∆ (indicated by a larger, filled marker), we notice that the optimal ∆ is highly volatile. Rather than undergoing minor adjustments, this value frequently shifts by several orders of magnitude across weight distributions.
Observation 9: The edge weight distribution fundamentally alters the shape of the performance curve across ∆ values, frequently transforming robust execution plateaus into highly sensitive minima that drastically amplify mis-tuning penalties.
9
UG500
NAT Δ*-step.
UBEAM GBBS
1 0
3
6
9
12
15
18
21
24
10
1
-20 -15 -10
log 2 ¢
-5
0
5
10
BF
15
20
25
100
10
1
10 1
-20 -15 -10
log 2 ¢
mawi
Time (s)
Time (s)
10
Wasp colisten-spotify
100
100
UDONG
GAP
isolates-sg1
Time (s)
Time (s)
planet
ρ-step.
-5
0
5
log 2 ¢
10
15
20
25
0.1
-20 -15 -10
-5
0
5
10
15
20
25
log 2 ¢
Figure 6: Performance across values of ∆ of different parallel SSSP implementations on four representative graphs and weight distributions. The x-axis shows the logarithm of ∆. The best-performing parameter is indicated by a larger and filled marker. Integer weights are indicated with a filled marker, while float weights are indicated with a hollow marker. Finally, we highlight an interesting phenomenon occurring within the mawi graph. In this specific topology, a single massive hub is connected to 99% of the other vertices in the graph, which are themselves degree-1 leaves. Because work distribution in these frameworks is typically managed at the vertex level rather than the edge level, processing this hub creates severe load imbalance. This structural bottleneck dominates the execution, artificially masking the impact of the edge weight distributions. This masking effect is clearly visible in the performance of GAP and ∆∗ -stepping; across all evaluated weight distributions, these implementations favor an extremely large ∆, inherently regressing their execution model to that of Bellman-Ford. This convergence is validated by the parallel Bellman-Ford algorithm, which performs similarly to the optimal configurations of GAP and ∆∗ -stepping. For clarity in Figure 6, we represent the Bellman-Ford execution time as a single pink horizontal line using only natural weights, as its performance is similar across all weight distributions (as shown in Section 5). Conversely, Wasp implements a structural optimization that prevents degree-1 leaves from being inserted into the scheduling buckets [26], an essential mechanism for achieving high performance on this topology. Strikingly, once this high-degree topological challenge is mitigated, the previously hidden effects of the weight distribution re-emerge: Wasp exhibits distinct performance curves and different optimal ∆ values for each individual distribution.
the tuning of algorithmic parameters, warping the optimal tuning landscape for ∆-based and ρ-stepping algorithms. In light of these findings, we distill our analysis into actionable insights for three distinct audiences within the parallel graph processing community: Users. For users deploying parallel SSSP algorithms on real-world datasets, our results demonstrate that relying on universally suggested default parameters is a dangerous pitfall. Because the tuning landscape is so easily deformed by edge weights, threshold parameters such as ∆ and ρ must be tuned directly on the specific weight distribution of the target graph. When selecting an implementation, users must weigh raw performance against tuning effort. If ease of use and robustness to weight variations are the primary requirements, we suggest utilizing the MultiQueue approach. If resources allow for meticulous parameter tuning, Wasp delivers the best overall execution time while remaining resilient to diverse weight distributions. Alternatively, ∆∗ -stepping serves as a highly performant secondary option, although with larger sensitivity to weight variations compared to asynchronous algorithms. Performance Analysts. For the designers and evaluators of graph systems, our analysis underscores that simple uniform weight distributions are fundamentally not representative of natural weights. All of the real-world weight distributions used in this study have a log-normal body. Evaluating algorithms exclusively on synthetic uniform weights frequently misidentifies the most performant algorithm compared to natural weight baselines. To bridge the gap between benchmark results and realworld deployment, the community must invest a larger effort into developing sophisticated synthetic weight generation. We advocate for adopting synthetic distributions that statistically mirror real-world data, such as log-normal distributions or mixed models featuring a log-normal body with a heavy tail. This, however, requires additional research as the performance of SSSP also depends on the relationship between edge weights and graph topology [20].
Observation 10: Graph topology and edge weights are coupled; topological bottlenecks can force ∆-stepping algorithms to regress to Bellman-Ford execution, masking the impact of the weight distribution.
7. Discussion and Conclusion Parallel SSSP benchmarking has been founded on the assumption that synthetic, uniform weight distributions serve as adequate proxies for real-world data. Our characterization and performance analysis of seven algorithms denies this assumption, proving that edge weights drive algorithmic performance and parameter tuning. We have shown how synthetic weight distributions misrepresent real-world SSSP performance, exhibiting large variability of results with artificial speedups and slowdown across classes of graphs. Furthermore, the weight distributions complicate
Algorithm Designers. Finally, for algorithm designers, this study highlights that future efforts should focus on decoupling efficiency from parameter choice. The steep performance degradation observed in statically configured ρ-stepping and parallel Bellman-Ford illustrates the fragility
10
of strict synchrony. Our findings indicate that asynchronous algorithms are more resilient to diverse weight distributions and the highly skewed weights characteristic of real-world networks. Future designs should prioritize this robustness, pushing toward parameter-free or dynamic thresholding approaches that adapt to high weight skew.
[10] A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, vol. 286, no. 5439, pp. 509–512, Oct. 1999. [Online]. Available: https://www.science.org/doi/full/10.1126/science. 286.5439.509 [11] A.-L. Barabási and Z. N. Oltvai, “Network biology: understanding the cell’s functional organization,” Nature Reviews Genetics, vol. 5, no. 2, pp. 101–113, Feb. 2004. [Online]. Available: https://www.nature.com/articles/nrg1272
Acknowledgment
[12] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, “The architecture of complex weighted networks,” Proceedings of the National Academy of Sciences, vol. 101, no. 11, pp. 3747–3752, Mar. 2004. [Online]. Available: https://www.pnas.org/doi/10.1073/ pnas.0400087101
This work was partially funded by the European Union, Horizon Europe 2021-2027 Framework Programme, Grant No. 101072456, and the UK Research and Innovation, Engineering and Physical Sciences Research Council, Grant No. EP/X029174/1.
[13] A. Barrat, M. Barthélemy, and A. Vespignani, “Modeling the evolution of weighted networks,” Physical Review E, vol. 70, no. 6, p. 066149, Dec. 2004. [Online]. Available: https://link.aps.org/doi/10. 1103/PhysRevE.70.066149
References [1]
[2]
L. Adamic, O. Buyukkokten, and E. Adar, “A social network caught in the Web,” First Monday, Jun. 2003. [Online]. Available: https://firstmonday.org/ojs/index.php/fm/article/view/1057
R. Albert, H. Jeong, and A.-L. Barabási, “Diameter of the World-Wide Web,” Nature, vol. 401, no. 6749, pp. 130–131, Sep. 1999. [Online]. Available: https://www.nature.com/articles/43601
[4]
D. Alistarh, J. Kopinsky, J. Li, and N. Shavit, “The SprayList: a scalable relaxed priority queue,” in Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP 2015. New York, NY, USA: Association for Computing Machinery, Jan. 2015, pp. 11–20. [Online]. Available: https://dl.acm.org/doi/10.1145/2688500.2688523
[5]
J. Alstott, E. Bullmore, and D. Plenz, “powerlaw: A Python Package for Analysis of Heavy-Tailed Distributions,” PLOS ONE, vol. 9, no. 1, p. e85777, Jan. 2014. [Online]. Available: https: //journals.plos.org/plosone/article?id=10.1371/journal.pone.0085777
[6]
I. Artico, I. Smolyarenko, V. Vinciotti, and E. C. Wit, “How rare are power-law networks really?” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 476, no. 2241, p. 20190742, Sep. 2020. [Online]. Available: https://royalsocietypublishing.org/doi/10.1098/rspa.2019.0742
[7]
A. Azad, M. M. Aznaveh, S. Beamer, M. P. Blanco, J. Chen, L. D’Alessandro, R. Dathathri, T. Davis, K. Deweese, J. Firoz, H. A. Gabb, G. Gill, B. Hegyi, S. Kolodziej, T. M. Low, A. Lumsdaine, T. Manlaibaatar, T. G. Mattson, S. McMillan, R. Peri, K. Pingali, U. Sridhar, G. Szarnyas, Y. Zhang, and Y. Zhang, “Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite,” in 2020 IEEE International Symposium on Workload Characterization (IISWC), Oct. 2020, pp. 216–227. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/9251247
[9]
[15] R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958. [Online]. Available: https://www.ams.org/qam/1958-16-01/S0033-569X-1958-0102435-2/
Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of topological characteristics of huge online social networking services,” in Proceedings of the 16th international conference on World Wide Web, ser. WWW ’07. New York, NY, USA: Association for Computing Machinery, May 2007, pp. 835–844. [Online]. Available: https://dl.acm.org/doi/10.1145/1242572.1242685
[3]
[8]
[14] S. Beamer, K. Asanović, and D. Patterson, “The GAP Benchmark Suite,” May 2017, arXiv:1508.03619 [cs]. [Online]. Available: http://arxiv.org/abs/1508.03619
[16] D. P. Bertsekas, F. Guerriero, and R. Musmanno, “Parallel asynchronous label-correcting methods for shortest paths,” Journal of Optimization Theory and Applications, vol. 88, no. 2, pp. 297–320, Feb. 1996. [Online]. Available: https://doi.org/10.1007/BF02192173 [17] D. B. Blumenthal, M. Lucchetta, L. Kleist, S. P. Fekete, M. List, and M. H. Schaefer, “Emergence of power law distributions in protein-protein interaction networks through study bias,” eLife, vol. 13, p. e99951, Dec. 2024. [Online]. Available: https://doi.org/10.7554/eLife.99951 [18] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, “Graph structure in the Web,” Computer Networks, vol. 33, no. 1, pp. 309–320, Jun. 2000. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S1389128600000839 [19] A. D. Broido and A. Clauset, “Scale-free networks are rare,” Nature Communications, vol. 10, no. 1, p. 1017, Mar. 2019. [Online]. Available: https://www.nature.com/articles/s41467-019-08746-5 [20] F. Bu, S. Kang, and K. Shin, “Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm,” Data Mining and Knowledge Discovery, vol. 37, no. 6, pp. 2139–2191, Nov. 2023. [Online]. Available: https://doi.org/10.1007/s10618-023-00940-w [21] G. Casella and R. Berger, Statistical Inference, 2nd ed. Chapman and Hall/CRC, May 2024.
New York:
[22] D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-MAT: A Recursive Model for Graph Mining,” in Proceedings of the 2004 SIAM International Conference on Data Mining (SDM), ser. Proceedings. Society for Industrial and Applied Mathematics, Apr. 2004, pp. 442–446. [Online]. Available: https://epubs.siam.org/doi/abs/10.1137/1.9781611972740.43 [23] A. Ching, S. Edunov, M. Kabiljo, D. Logothetis, and S. Muthukrishnan, “One trillion edges: graph processing at Facebook-scale,” Proceedings of the VLDB Endowment, vol. 8, no. 12, pp. 1804–1815, Aug. 2015. [Online]. Available: https://dl.acm.org/doi/10.14778/2824032.2824077
A. Azad, G. A. Pavlopoulos, C. A. Ouzounis, N. C. Kyrpides, and A. Buluç, “HipMCL: a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks,” Nucleic Acids Research, vol. 46, no. 6, p. e33, Apr. 2018. [Online]. Available: https://doi.org/10.1093/nar/gkx1313
[24] H. Chun, H. Kwak, Y.-H. Eom, Y.-Y. Ahn, S. Moon, and H. Jeong, “Comparison of online social relations in volume vs interaction: a case study of cyworld,” in Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, ser. IMC ’08. New York, NY, USA: Association for Computing Machinery, Oct. 2008, pp. 57–70. [Online]. Available: https://dl.acm.org/doi/10.1145/1452520.1452528
L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, “Group formation in large social networks: membership, growth, and evolution,” in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD ’06. New York, NY, USA: Association for Computing Machinery, Aug. 2006, pp. 44–54. [Online]. Available: https: //dl.acm.org/doi/10.1145/1150402.1150412
[25] A. Clauset, C. R. Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data,” SIAM Review, vol. 51, no. 4, pp. 661–703, Nov. 2009, arXiv:0706.1062 [physics]. [Online]. Available: http://arxiv.org/abs/0706.1062
11
[41] R. Kumar, P. Liu, M. Charikar, and A. R. Benson, “Retrieving Top Weighted Triangles in Graphs,” in Proceedings of the 13th International Conference on Web Search and Data Mining, ser. WSDM ’20. New York, NY, USA: Association for Computing Machinery, Jan. 2020, pp. 295–303. [Online]. Available: https: //dl.acm.org/doi/10.1145/3336191.3371823
[26] M. D’Antonio, T. S. Mai, P. Tsigas, and H. Vandierendonck, “Wasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ser. SC ’25. New York, NY, USA: Association for Computing Machinery, Nov. 2025, pp. 2109–2125. [Online]. Available: https://dl.acm.org/doi/10.1145/3712285.3759872 [27] T. A. Davis and Y. Hu, “The university of Florida sparse matrix collection,” ACM Transactions on Mathematical Software, vol. 38, no. 1, pp. 1:1–1:25, Dec. 2011. [Online]. Available: https://dl.acm.org/doi/10.1145/2049662.2049663
[42] H. Kwak, C. Lee, H. Park, and S. Moon, “What is Twitter, a social network or a news media?” in Proceedings of the 19th international conference on World wide web, ser. WWW ’10. New York, NY, USA: Association for Computing Machinery, Apr. 2010, pp. 591–600. [Online]. Available: https://dl.acm.org/doi/10.1145/1772690.1772751
[28] C. Demetrescu, A. Goldberg, and D. Johnson, Eds., The Shortest Path Problem, ser. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Providence, Rhode Island: American Mathematical Society, Jul. 2009, vol. 74. [Online]. Available: https://www.ams.org/dimacs/074
[43] O. Lehmberg, R. Meusel, and C. Bizer, “Graph structure in the web: aggregated by pay-level domain,” in Proceedings of the 2014 ACM conference on Web science, ser. WebSci ’14. New York, NY, USA: Association for Computing Machinery, Jun. 2014, pp. 119–128. [Online]. Available: https://dl.acm.org/doi/10.1145/2615569.2615674
[29] E. Demidenko, “The p-Value You Can’t Buy,” The American Statistician, vol. 70, no. 1, pp. 33–38, Jan. 2016. [Online]. Available: https://pmc.ncbi.nlm.nih.gov/articles/PMC4867863/
[44] J. Leskovec and E. Horvitz, “Planetary-scale views on a large instant-messaging network,” in Proceedings of the 17th international conference on World Wide Web, ser. WWW ’08. New York, NY, USA: Association for Computing Machinery, Apr. 2008, pp. 915–924. [Online]. Available: https://dl.acm.org/doi/10.1145/1367497.1367620
[30] L. Dhulipala, G. Blelloch, and J. Shun, “Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing,” in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’17. New York, NY, USA: Association for Computing Machinery, Jul. 2017, pp. 293–304. [Online]. Available: https://dl.acm.org/doi/10.1145/3087556.3087580
[45] J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, “Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication,” in Knowledge Discovery in Databases: PKDD 2005, ser. Lecture Notes in Computer Science, A. M. Jorge, L. Torgo, P. Brazdil, R. Camacho, and J. Gama, Eds. Berlin, Heidelberg: Springer, 2005, pp. 133–145.
[31] L. Dhulipala, G. E. Blelloch, and J. Shun, “Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable,” ACM Transactions on Parallel Computing, vol. 8, no. 1, pp. 4:1–4:70, Apr. 2021. [Online]. Available: https://dl.acm.org/doi/10.1145/3434393
[46] M. Lin, H. C. Lucas, and G. Shmueli, “Research Commentary: Too Big to Fail: Large Samples and the p-Value Problem,” Information Systems Research, vol. 24, no. 4, pp. 906–917, 2013. [Online]. Available: https://www.jstor.org/stable/24700283
[32] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, Dec. 1959. [Online]. Available: https://doi.org/10.1007/BF01386390
[47] B. Liu, S. Xu, T. Li, J. Xiao, and X.-K. Xu, “Quantifying the Effects of Topology and Weight for Link Prediction in Weighted Complex Networks,” Entropy, vol. 20, no. 5, p. 363, May 2018. [Online]. Available: https://www.mdpi.com/1099-4300/20/5/363
[33] X. Dong, Y. Gu, Y. Sun, and Y. Zhang, “Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths,” in Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Jul. 2021, pp. 184–197. [Online]. Available: https://doi.org/10.1145/3409964.3461782
[48] K. Madduri, D. A. Bader, J. W. Berry, and J. R. Crobak, “Parallel Shortest Path Algorithms for Solving Large-Scale Instances,” in The Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society and Center for Discrete Mathematics and Theoretical Computer Science, Sep. 2006. [Online]. Available: http://www.diag.uniroma1.it/challenge9/papers/madduri.pdf
[34] X. Dong, A. Li, Y. Gu, and Y. Sun, “Parallel Point-toPoint Shortest Paths and Batch Queries,” in Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’25. New York, NY, USA: Association for Computing Machinery, Jul. 2025, pp. 458–472. [Online]. Available: https://dl.acm.org/doi/10.1145/3694906.3743311
[49] R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer, “Graph structure in the web — revisited: a trick of the heavy tail,” in Proceedings of the 23rd International Conference on World Wide Web, ser. WWW ’14 Companion. New York, NY, USA: Association for Computing Machinery, Apr. 2014, pp. 427–432. [Online]. Available: https://dl.acm.org/doi/10.1145/2567948.2576928
[35] D. Ediger, K. Jiang, J. Riedy, D. A. Bader, C. Corley, R. Farber, and W. N. Reynolds, “Massive Social Network Analysis: Mining Twitter for Social Good,” in 2010 39th International Conference on Parallel Processing, Sep. 2010, pp. 583–593, iSSN: 2332-5690. [Online]. Available: https://ieeexplore.ieee.org/document/5599247
[50] ——, “The Graph Structure in the Web − Analyzed on Different Aggregation Levels,” The Journal of Web Science, vol. 1, no. 1, pp. 33–47, Aug. 2015. [Online]. Available: https://doi.org/10.1561/106.00000003
[36] B. Efron and R. J. Tibshirani, An Introduction to the Bootstrap. New York: Chapman and Hall/CRC, May 1994. [37] D. Garcia, P. Mavrodiev, and F. Schweitzer, “Social resilience in online communities: the autopsy of friendster,” in Proceedings of the first ACM conference on Online social networks, ser. COSN ’13. New York, NY, USA: Association for Computing Machinery, Oct. 2013, pp. 39–50. [Online]. Available: https://dl.acm.org/doi/10.1145/2512938.2512946
[51] U. Meyer and P. Sanders, “∆-stepping: a parallelizable shortest path algorithm,” Journal of Algorithms, vol. 49, no. 1, pp. 114–152, Oct. 2003. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0196677403000762
[38] P. Holme, “Rare and everywhere: Perspectives on scale-free networks,” Nature Communications, vol. 10, no. 1, p. 1016, Mar. 2019. [Online]. Available: https://www.nature.com/articles/s41467-019-09038-8 [39] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, “The large-scale organization of metabolic networks,” Nature, vol. 407, no. 6804, pp. 651–654, Oct. 2000. [Online]. Available: https://www.nature.com/articles/35036627
[52] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of online social networks,” in Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, ser. IMC ’07. New York, NY, USA: Association for Computing Machinery, Oct. 2007, pp. 29–42. [Online]. Available: https://dl.acm.org/doi/10.1145/1298306.1298311
[40] R. Khanin and E. Wit, “How Scale-Free Are Biological Networks,” Journal of Computational Biology, vol. 13, no. 3, pp. 810–818, Apr. 2006. [Online]. Available: https://journals.sagepub.com/action/ showAbstract
[53] E. F. Moore, “The shortest path through a maze,” in Proc. Internat. Sympos. Switching Theory 1957, Parts I,II, ser. The Annals of the Computation Laboratory of Harvard University. Harvard Univ. Press, Cambridge, MA, 1959, vol. vols. XXIX, XXX, pp. 285–292.
12
and Data Mining, ser. KDD ’17. New York, NY, USA: Association for Computing Machinery, Aug. 2017, pp. 1633–1642. [Online]. Available: https://dl.acm.org/doi/10.1145/3097983.3098057
[54] R. C. Murphy, K. B. Wheeler, B. W. Barrett, and J. A. Ang, “Introducing the graph 500,” Cray Users Group (CUG), vol. 19, no. 45-74, p. 22, 2010. [55] M. E. J. Newman, “The structure of scientific collaboration networks,” Proceedings of the National Academy of Sciences, vol. 98, no. 2, pp. 404–409, Jan. 2001. [Online]. Available: https://www.pnas.org/doi/10.1073/pnas.98.2.404
[64] J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, “ArnetMiner: extraction and mining of academic social networks,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD ’08. New York, NY, USA: Association for Computing Machinery, Aug. 2008, pp. 990–998. [Online]. Available: https://dl.acm.org/doi/10.1145/1401890.1402008
[56] D. Nguyen, A. Lenharth, and K. Pingali, “A lightweight infrastructure for graph analytics,” in Proceedings of the TwentyFourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. New York, NY, USA: Association for Computing Machinery, Nov. 2013, pp. 456–471. [Online]. Available: https: //dl.acm.org/doi/10.1145/2517349.2522739
[65] L. G. Valiant, “A bridging model for parallel computation,” Commun. ACM, vol. 33, no. 8, pp. 103–111, 1990. [Online]. Available: https://dl.acm.org/doi/10.1145/79173.79181
[57] T. Panitanarak and K. Madduri, “Performance Analysis of Singlesource Shortest Path Algorithms on Distributed-memory Systems,” in Book of Abstracts of the Sixth SIAM Workshop on Combinatorial Scientific Computing, ser. CSC14. SIAM, Aug. 2014, pp. 60–63.
[66] I. Voitalov, P. van der Hoorn, R. van der Hofstad, and D. Krioukov, “Scale-free networks well done,” Physical Review Research, vol. 1, no. 3, p. 033034, Oct. 2019. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevResearch.1.033034 [68] M. Williams, P. Sanders, and R. Dementiev, “Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues,” in DROPSIDN/v2/document/10.4230/LIPIcs.ESA.2021.81. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. [Online]. Available: https: //drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.81
[58] A. Postnikova, N. Koval, G. Nadiradze, and D. Alistarh, “Multi-queues can be state-of-the-art priority schedulers,” in Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’22. New York, NY, USA: Association for Computing Machinery, Mar. 2022, pp. 353–367, arXiv:2109.00657 [cs]. [Online]. Available: https://dl.acm.org/doi/10.1145/3503221.3508432 [59] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing. USA: Cambridge University Press, Nov. 1992.
[69] M. Wimmer, J. Gruber, J. L. Träff, and P. Tsigas, “The lockfree k-LSM relaxed priority queue,” ACM SIGPLAN Notices, vol. 50, no. 8, pp. 277–278, Jan. 2015. [Online]. Available: https://dl.acm.org/doi/10.1145/2858788.2688547
[60] N. Pržulj, D. G. Corneil, and I. Jurisica, “Modeling interactome: scale-free or geometric?” Bioinformatics, vol. 20, no. 18, pp. 3508–3515, Dec. 2004. [Online]. Available: https://doi.org/10.1093/ bioinformatics/bth436
[70] S. H. Yook, H. Jeong, A.-L. Barabási, and Y. Tu, “Weighted Evolving Networks,” Physical Review Letters, vol. 86, no. 25, pp. 5835–5838, Jun. 2001. [Online]. Available: https://link.aps.org/doi/10. 1103/PhysRevLett.86.5835
[61] H. Rihani, P. Sanders, and R. Dementiev, “MultiQueues: Simple Relaxed Concurrent Priority Queues,” in Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’15. New York, NY, USA: Association for Computing Machinery, Jun. 2015, pp. 80–82. [Online]. Available: https: //dl.acm.org/doi/10.1145/2755573.2755616
[71] G. Zhang, G. Posluns, and M. C. Jeffrey, “Multi Bucket Queues: Efficient Concurrent Priority Scheduling,” in Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’24. New York, NY, USA: Association for Computing Machinery, 2024, pp. 113–124. [Online]. Available: https://dl.acm.org/doi/10.1145/3626183.3659962
[62] J. Shun and G. E. Blelloch, “Ligra: A Lightweight Graph Processing Framework for Shared Memory,” ACM SIGPLAN Notices, vol. 48, no. 8, pp. 135–146, 2013. [Online]. Available: https://dl.acm.org/doi/10.1145/2517327.2442530
[72] Y. Zhang, A. Brahmakshatriya, X. Chen, L. Dhulipala, S. Kamil, S. Amarasinghe, and J. Shun, “Optimizing ordered graph algorithms with GraphIt,” in Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization, ser. CGO 2020. New York, NY, USA: Association for Computing Machinery, Feb. 2020, pp. 158–170. [Online]. Available: https: //dl.acm.org/doi/10.1145/3368826.3377909
[63] J. Sybrandt, M. Shtutman, and I. Safro, “MOLIERE: Automatic Biomedical Hypothesis Generation System,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery [67] L. Wang, X. Dong, Y. Gu, and Y. Sun, “Parallel Strong Connectivity Based on Faster Reachability,” Proc. ACM Manag. Data, vol. 1, no. 2, pp. 114:1–114:29, 2023. [Online]. Available: https://dl.acm.org/doi/10.1145/3589259
13