Pith. sign in

REVIEW 3 major objections 5 minor 74 references

Mind the Gap: The Disconnect Between Synthetic and Natural Edge Weights in Parallel Single-Source Shortest Path

T0 review · 3 major / 5 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Synthetic uniform edge weights change which parallel SSSP algorithms win and how they must be tuned, relative to natural weights on real graphs.

desk verdict Solid empirical systems paper: natural vs synthetic weights really do retune and reorder SOTA parallel SSSP; the indictment of Graph500-style practice is directionally right but rests on sample and independence assumptions the authors partly flag themselves. read the letter →

arxiv 2607.26821 v1 pith:J62GBN5Q submitted 2026-07-29 cs.DC

Marco D'Antonio , Thai Son Mai , Hans Vandierendonck This is my paper · ORCID
classification cs.DC
keywords parallelSSSPedge-weightdistributionΔ-steppingbenchmarkingbiaslog-normalweightsparametertuningasynchronousshortestpaths
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Most parallel single-source shortest-path algorithms are benchmarked on graphs whose edge weights are drawn from simple synthetic recipes, usually uniform. Real networks instead carry heavy-tailed or log-normal weights whose body and tail look nothing like those recipes. Because bucket width, step count, and redundant work all depend on the weight distribution, the synthetic choice is not a neutral label: it changes optimal parameters and can reverse which implementation is fastest. The paper fits the empirical weight distributions of seventeen large road, traffic, social, semantic and biological graphs, contrasts them with six literature synthetics, and times seven state-of-the-art parallel SSSP codes under every combination. The result is that current practice systematically misrepresents real-world ranking and tuning, so benchmarks and algorithm design must treat weight distribution as a first-order variable.

What carries the argument

Side-by-side statistical characterization (Clauset-style MLE, KS, likelihood-ratio tests of body and tail) of seventeen natural weight distributions versus six literature synthetics, followed by exhaustive Δ/ρ sweeps and timed runs of seven parallel SSSP implementations, which together quantify sensitivity, mis-tuning penalty, and ranking inversion.

What would settle it

Re-run the same seven implementations on a substantially larger or differently sampled set of naturally weighted graphs (or on production workloads whose weights follow neither the paper's log-normal bodies nor the six synthetics) and check whether optimal Δ/ρ values and algorithm rankings still diverge systematically from the uniform-weight baselines.

Watch

Extended reading notes

Core claim

Evaluating parallel SSSP with the synthetic uniform weights common in the literature alters optimal parameter configurations and can invert the observed performance hierarchy relative to the same algorithms run on naturally weighted real-world graphs; edge-weight distribution is a first-order driver of both computational work and the structure of synchronous steps.

Load-bearing premise

The seventeen chosen natural graphs and six literature synthetic recipes are representative enough of real workloads and community practice that the observed bias and hierarchy inversions indict existing benchmarking standards in general.

Editorial extensions

If this is right

  • Default or portable Δ and ρ values tuned on uniform weights are unreliable on real graphs and must be re-tuned to the target weight distribution.
  • Asynchronous or relaxed-priority designs show lower sensitivity to weight variation than strictly synchronous Δ-stepping variants and are therefore preferable when weight distributions are unknown or highly skewed.
  • Future public benchmarks should replace or augment uniform weights with generators whose body and tail match the log-normal-plus-heavy-tail pattern observed on real data.
  • Algorithm designers should treat weight distribution as a first-class input when claiming practical superiority, not merely topology or core count.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same weight-sensitivity critique likely extends to other weight-dependent graph kernels (betweenness, hop-constrained paths, weighted matching) that are still routinely evaluated under uniform synthetics.
  • Once weight generators become statistically faithful, automated or online Δ/ρ adaptation may become more valuable than further hand-tuned static defaults.
  • Topology–weight coupling (hubs that force regression to Bellman–Ford behaviour) suggests that synthetic generators must also preserve joint structure, not only marginal weight histograms.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper argues that parallel SSSP benchmarking practice, which predominantly assigns synthetic uniform (or simple normal) edge weights to unweighted graphs, is disconnected from real-world weight distributions and thereby biases algorithm rankings and parameter choices. It statistically characterizes edge weights on 17 naturally weighted graphs (road networks from OSM plus skewed-degree graphs from HipMCL, SuiteSparse, and Benson repositories) via Clauset-style MLE/KS/likelihood-ratio fitting of body and tail, contrasts them with six literature synthetic recipes, and evaluates seven state-of-the-art parallel SSSP codes (GAP, GBBS, Wasp, Δ*-stepping, ρ-stepping, MultiQueue Dijkstra, parallel Bellman-Ford). The central empirical claims are that natural weights are typically log-normal in the body with heavy (often log-normal rather than pure power-law) tails, that synthetic uniforms alter optimal Δ/ρ and can invert tuned performance hierarchies relative to natural weights, and that synchronous Δ-based algorithms are more sensitive than asynchronous ones.

Significance. If the results hold under broader sampling, the work is significant for the parallel graph algorithms and HPC benchmarking communities: it supplies concrete evidence that a long-standing convenience assumption (uniform weights) is not neutral, supplies a reusable statistical characterization pipeline and public OSM road datasets, and yields actionable guidance (tune Δ/ρ on the target weight distribution; prefer asynchronous or carefully dynamic methods for robustness). Strengths include the breadth of the algorithm suite, full per-distribution retuning sweeps, frontier-size diagnostics that explain work and step-count effects, and explicit acknowledgment of large-n p-value collapse. The paper does not claim a new algorithm; its value is diagnostic and methodological.

major comments (3)
  1. [§3.2, §5–7] §3.2 and §5–6: All synthetic trials independently redraw w(e) from a marginal distribution, destroying any natural topology–weight dependence (road length vs. geometry, similarity vs. clusters, packet counts vs. hubs). Section 7 explicitly cites the interplay literature [20] yet the experiments never isolate marginal shape from dependence structure. Consequently the reported rank inversions, sensitivity factors (Fig. 3), and Δ shifts (Fig. 6) confound the two. This is load-bearing for the claim that existing standards are biased; either an experiment that preserves empirical (topology, weight) pairs while reshaping the marginal, or a clearly scoped limitation that the results speak only to independent reassignment, is required before the indictment of Graph500/GAP-style practice can be stated at the present strength.
  2. [§1, §3.1, §7] §1, §3.1 and §7: The leap from “on these 17 graphs + 6 literature recipes” to “current benchmarking methods unintentionally bias” and “challenge existing benchmarking standards” rests on an untested representativeness assumption. The sample is dominated by OSM roads and a handful of biological/co-authorship/traffic matrices; domain-specific semantics (bounded [0,1] similarities, integer co-authorship counts, extreme hubs in mawi) and implementation artifacts enter every comparison. A short, explicit external-validity paragraph stating which workload classes are and are not covered, and tempering the Graph500 indictment accordingly, is needed for the central claim to travel.
  3. [§6.1, Fig. 5] §6.1 and Fig. 5: Aggregated Δ mis-tuning penalties are computed only over the intersection of Δ values that finished under a 10-minute cap across all implementations. Heavily mis-tuned points are therefore censored precisely where penalties would be largest, and the intersection size (average 22 points) is not reported per cell. This weakens the comparative robustness claims (e.g., “GBBS most robust”). Either complete the sweeps with a higher cap / early-stop reporting, or replace the geometric-mean penalty with a survival-style or winsorized statistic that makes the censoring explicit.
minor comments (5)
  1. [Table 2] Table 2 and §3.2: The half-normal absolute-value truncation of the two normal synthetics is a reasonable reading of prior work, but should be stated once in the table caption so readers do not have to reconstruct it from the text.
  2. [Fig. 2, Fig. 6] Fig. 2 and Fig. 6: Marker conventions (square = integer, circle/hollow = float) are useful but easy to miss; a single legend entry repeated in both captions would help.
  3. [§2.3] §2.3: MultiQueue is evaluated at fixed c=2, s=64 and labeled “parameter-free.” A one-sentence caveat that stickiness remains a latent parameter (as the authors themselves note) would avoid over-claiming.
  4. [Table 3] Observation 2 / Table 3: For the two road graphs where the pure power-law tail is not rejected, the %tail is ~0.009%. Emphasizing that the non-rejection is driven by extreme sparsity of the tail would prevent over-reading the PL column.
  5. Minor typographical: “assignes” → “assigns” (§3.2); “impor-” line break artifacts in the PDF; ensure all arXiv/DOI links resolve in the camera-ready.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical measurement study whose rankings, Δ optima, and sensitivity metrics are computed from external runs, not forced by construction from fitted inputs.

full rationale

The paper is a benchmarking and characterization study. Its load-bearing claims (natural vs synthetic weight distributions differ; optimal Δ/ρ and tuned algorithm rankings shift under synthetic uniforms; synchronous algorithms are more weight-sensitive) are established by (i) statistical fits of empirical edge-weight histograms via the external Clauset et al. pipeline and (ii) wall-clock and frontier measurements on seven third-party or independently implemented SSSP codes under six literature weight recipes plus natural weights. The ‘sensitivity factor’ is explicitly defined as a geometric-mean summary of observed |log speedups|, not a quantity algebraically identical to a fitted parameter. Distribution-body/tail fits (log-normal, power-law) are descriptive and are never reused as predicted performance. Self-citation of the authors’ Wasp implementation is ordinary inclusion of one of seven evaluated codes and does not underwrite uniqueness or forbid alternatives. No step reduces a claimed prediction or first-principles result to its own inputs by definition. Representativeness and topology–weight dependence are external validity concerns, not circularity.

Assumptions & free parameters 5 free parameters · 5 assumptions · 2 invented entities

Empirical systems paper. Load-bearing background is standard SSSP/Δ-stepping semantics and the Clauset et al. fitting pipeline; experimental knobs (MultiQueue stickiness, Δ grid, source sampling, timeout policy) shape measured rankings but are not hidden physical constants. No new physical entities. The main generalization step is treating the curated graph+implementation sample as diagnostic of community benchmarking practice.

free parameters (5)
  • MultiQueue scaling c and stickiness s = c=2, s=64
    Fixed at c=2 and s=64 to treat MQ as 'parameter-free'; different values are known to move performance and could change robustness conclusions.
  • Δ/ρ power-of-two sweep grid = 2^{-20} .. 2^{25}
    Optima are taken from 2^-20..2^25 (integers ≥1 for integer weights). Grid choice and ten-minute timeout truncation define which configuration is called optimal.
  • per-graph xmin and body/tail fit parameters (α, μ, σ) = graph-specific (Table 3)
    MLE/KS-selected tail cutoffs and log-normal/power-law parameters characterize natural weights (Table 3); they support Observations 2–3 though the performance hierarchy claim does not algebraically depend on the fitted numbers.
  • synthetic distribution parameterizations (Table 2) = as in Table 2
    UG500/UBEAM/UDHUL/UDONG/NPANI/NANON settings are taken from literature or reviewer suggestion; which synthetics are included defines the measured 'disconnect.'
  • sensitivity factor aggregation
    Geometric mean of absolute log speedups vs natural weights; a hand-defined summary that ranks algorithm fragility.
assumptions (5)
  • domain assumption SSSP on directed/undirected graphs with non-negative weights; parallel correctness allows redundant relaxations
    Standard problem statement in §2.3; negative weights only mentioned for Bellman-Ford capability, not used as primary workload.
  • domain assumption Clauset et al. MLE + KS xmin + semi-parametric bootstrap + likelihood-ratio testing is an appropriate characterization pipeline for edge weights
    Adopted in §4.1 from [25]; body analysis drops full bootstrap as prohibitive and relies on likelihood ratios.
  • domain assumption The seven selected implementations adequately represent state-of-the-art parallel SSSP practice
    GAP, GBBS, Wasp, Δ*/ρ-stepping, MultiQueue Dijkstra, parallel Bellman-Ford (§2.3); omitted designs could differ in sensitivity.
  • ad hoc to paper Averaging 22 sources in the largest (S)CC on the stated dual-socket Zen3 machine is enough to compare algorithms and weight models
    Experimental protocol §3.3; source choice and NUMA interleaving affect absolute times.
  • ad hoc to paper Half-normal absolute-value truncation of proposed normal synthetics is a fair reading of prior normal-weight usage
    §3.2 notes missing parameters in [57] and non-negativity constraint.
invented entities (2)
  • sensitivity factor (geo-mean absolute log speedup vs natural weights)
    purpose: Single scalar to compare how much each algorithm's runtime moves under synthetic weights
    Defined in §5.2 / Fig. 3b; useful summary but paper-specific, not an external physical quantity.
  • aggregated Δ mis-tuning penalty
    purpose: Quantify slowdown from non-optimal Δ across graphs and weight models
    §6.1 Fig. 5; depends on intersection of successful sweep points after timeouts.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mind the Gap: The Disconnect Between Synthetic and Natural Edge Weights in Parallel Single-Source Shortest Path." pith.science (2026). https://pith.science/paper/J62GBN5Q

@misc{pith2026260726821,
  author       = {Pith},
  title        = {Pith review of: Mind the Gap: The Disconnect Between Synthetic and Natural Edge Weights in Parallel Single-Source Shortest Path},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J62GBN5Q}},
  note         = {Machine review of arXiv:2607.26821}
}
read the original abstract

Scientific research works often evaluate Parallel Single-Source 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 real-world 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.

Figures

Figures reproduced from arXiv: 2607.26821 by the authors.

Figure 1
Figure 1. Edge weight distributions of the datasets. For each graph, the left panel displays the Cumulative Distribution [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Performance of SSSP implementations on different graphs for each weight distribution. The left panel indicates [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Sensitivity analysis of the parallel SSSP implementations to synthetic weight distributions. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Size of the frontier (in vertices) in each syn [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. 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 sev…
Figure 6
Figure 6. 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 indicate…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

74 extracted references · 6 canonical work pages

  1. [20]

    Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm,

    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

    work page doi:10.1007/s10618-023-00940-w 2023

  2. [1]

    A social network caught in the Web,

    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

    2003

  3. [2]

    Analysis of topological characteristics of huge online social networking services,

    Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of topological characteristics of huge online social networking services, ” inProceedings 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/12425...

    arXiv 2007

  4. [3]

    Diameter of the World-Wide Web,

    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

    1999

  5. [4]

    The SprayList: a scalable relaxed priority queue,

    D. Alistarh, J. Kopinsky, J. Li, and N. Shavit, “The SprayList: a scalable relaxed priority queue, ” inProceedings 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

    arXiv 2015

  6. [5]

    powerlaw: A Python Package for Analysis of Heavy-Tailed Distributions,

    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

    doi:10.1371/journal.pone.0085777 2014

  7. [6]

    How rare are power-law networks really?

    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

    arXiv 2020

  8. [7]

    Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite,

    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...

    arXiv 2020

Show all 74 references
  1. [8]

    HipMCL: a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks,

    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://d...

    2018 doi

  2. [9]

    Group formation in large social networks: membership, growth, and evolution,

    L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, “Group formation in large social networks: membership, growth, and evolution, ” inProceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD ’06. New York, NY, USA: Assoc...

    2006

  3. [10]

    Emergence of Scaling in Random Networks,

    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

    1999 doi

  4. [11]

    Network biology: understanding the cell’s functional organization,

    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

    2004

  5. [12]

    The architecture of complex weighted networks,

    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

    2004

  6. [13]

    Modeling the evolution of weighted networks,

    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

    2004

  7. [14]

    The GAP Benchmark Suite,

    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

    2017 arXiv

  8. [15]

    On a routing problem,

    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/

    1958

  9. [16]

    Parallel asynchronous label-correcting methods for shortest paths,

    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

    1996 doi

  10. [17]

    Emergence of power law distributions in protein-protein interaction networks through study bias,

    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

    2024 doi

  11. [18]

    Graph structure in the Web,

    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

    2000

  12. [19]

    Scale-free networks are rare,

    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

    2019

  13. [21]

    Casella and R

    G. Casella and R. Berger,Statistical Inference, 2nd ed. New York: Chapman and Hall/CRC, May 2024

    2024

  14. [22]

    R-MAT: A Recursive Model for Graph Mining,

    D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-MAT: A Recursive Model for Graph Mining, ” inProceedings 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:...

    2004 doi

  15. [23]

    One trillion edges: graph processing at Facebook-scale,

    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

    2015

  16. [24]

    Comparison of online social relations in volume vs interaction: a case study of cyworld,

    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, ” inProceedings of the 8th ACM SIGCOMM conference on Internet measurement, ser. IMC ’08. New York, NY, USA: Association for ...

    2008

  17. [25]

    Power-law distributions in empirical data,

    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

    2009 arXiv

  18. [26]

    Wasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing,

    M. D’Antonio, T. S. Mai, P. Tsigas, and H. Vandierendonck, “Wasp: Efficient Asynchronous Single-Source Shortest Path on Multicore Systems via Work Stealing, ” inProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ser. S...

    2025

  19. [27]

    The university of Florida sparse matrix collection,

    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

    2011

  20. [28]

    Demetrescu, A

    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

    2009

  21. [29]

    The p-Value You Can’t Buy,

    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/

    2016

  22. [30]

    Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing,

    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 M...

    2017

  23. [31]

    Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable,

    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

  24. [32]

    A note on two problems in connexion with graphs,

    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

    1959 doi

  25. [33]

    Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths,

    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...

    2021

  26. [34]

    Parallel Point-to- Point Shortest Paths and Batch Queries,

    X. Dong, A. Li, Y. Gu, and Y. Sun, “Parallel Point-to- Point Shortest Paths and Batch Queries, ” inProceedings 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–47...

    2025

  27. [35]

    Massive Social Network Analysis: Mining Twitter for Social Good,

    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, ” in2010 39th International Conference on Parallel Processing, Sep. 2010, pp. 583–593, iSSN: 2332-5690. [Online]. Available: ...

    2010

  28. [36]

    Efron and R

    B. Efron and R. J. Tibshirani,An Introduction to the Bootstrap. New York: Chapman and Hall/CRC, May 1994

    1994

  29. [37]

    Social resilience in online communities: the autopsy of friendster,

    D. Garcia, P. Mavrodiev, and F. Schweitzer, “Social resilience in online communities: the autopsy of friendster, ” inProceedings 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. ...

    2013

  30. [38]

    Rare and everywhere: Perspectives on scale-free networks,

    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

    2019

  31. [39]

    The large-scale organization of metabolic networks,

    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

    2000

  32. [40]

    How Scale-Free Are Biological Networks,

    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

    2006

  33. [41]

    Retrieving Top Weighted Triangles in Graphs,

    R. Kumar, P. Liu, M. Charikar, and A. R. Benson, “Retrieving Top Weighted Triangles in Graphs, ” inProceedings 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. [On...

    2020

  34. [42]

    What is Twitter, a social network or a news media?

    H. Kwak, C. Lee, H. Park, and S. Moon, “What is Twitter, a social network or a news media?” inProceedings 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: ...

    2010

  35. [43]

    Graph structure in the web: aggregated by pay-level domain,

    O. Lehmberg, R. Meusel, and C. Bizer, “Graph structure in the web: aggregated by pay-level domain, ” inProceedings 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: h...

    2014

  36. [44]

    Planetary-scale views on a large instant-messaging network,

    J. Leskovec and E. Horvitz, “Planetary-scale views on a large instant-messaging network, ” inProceedings 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: h...

    2008

  37. [45]

    Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication,

    J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, “Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication, ” inKnowledge Discovery in Databases: PKDD 2005, ser. Lecture Notes in Computer Science, A. M. Jorge, L. Torgo, P. ...

    2005

  38. [46]

    Research Commentary: Too Big to Fail: Large Samples and the p-Value Problem,

    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

    2013

  39. [47]

    Quantifying the Effects of Topology and Weight for Link Prediction in Weighted Complex Networks,

    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

    2018

  40. [48]

    Parallel Shortest Path Algorithms for Solving Large-Scale Instances,

    K. Madduri, D. A. Bader, J. W. Berry, and J. R. Crobak, “Parallel Shortest Path Algorithms for Solving Large-Scale Instances, ” inThe Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society and Center for Discrete Mathematics and Theoretical...

    2006

  41. [49]

    Graph structure in the web — revisited: a trick of the heavy tail,

    R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer, “Graph structure in the web — revisited: a trick of the heavy tail, ” inProceedings of the 23rd International Conference on World Wide Web, ser. WWW ’14 Companion. New York, NY, USA: Association for Computing Machinery, Apr. 2014...

    2014

  42. [50]

    The Graph Structure in the Web − Analyzed on Different Aggregation Levels,

    ——, “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

    2015 doi

  43. [51]

    ∆-stepping: a parallelizable shortest path algorithm,

    U. Meyer and P. Sanders, “ ∆-stepping: a parallelizable shortest path algorithm, ”Journal of Algorithms, vol. 49, no. 1, pp. 114–152, Oct

  44. [52]

    Measurement and analysis of online social networks,

    A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of online social networks, ” inProceedings of the 7th ACM SIGCOMM conference on Internet measurement, ser. IMC ’07. New York, NY, USA: Association for Computing Machinery, Oct. 2...

    2007

  45. [53]

    The shortest path through a maze,

    E. F. Moore, “The shortest path through a maze, ” inProc. 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

    1957

  46. [54]

    Introducing the graph 500,

    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

    2010

  47. [55]

    The structure of scientific collaboration networks,

    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

    2001 doi

  48. [56]

    A lightweight infrastructure for graph analytics,

    D. Nguyen, A. Lenharth, and K. Pingali, “A lightweight infrastructure for graph analytics, ” inProceedings of the Twenty- Fourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. New York, NY, USA: Association for Computing Machinery, Nov. 2013, pp. 456–471. [Onlin...

    2013

  49. [57]

    Performance Analysis of Single- source Shortest Path Algorithms on Distributed-memory Systems,

    T. Panitanarak and K. Madduri, “Performance Analysis of Single- source Shortest Path Algorithms on Distributed-memory Systems, ” inBook of Abstracts of the Sixth SIAM Workshop on Combinatorial Scientific Computing, ser. CSC14. SIAM, Aug. 2014, pp. 60–63

    2014

  50. [58]

    Multi-queues can be state-of-the-art priority schedulers,

    A. Postnikova, N. Koval, G. Nadiradze, and D. Alistarh, “Multi-queues can be state-of-the-art priority schedulers, ” inProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’22. New York, NY, USA: Association for Computing...

    2022 arXiv

  51. [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

    1992

  52. [60]

    Modeling interactome: scale-free or geometric?

    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

    2004

  53. [61]

    MultiQueues: Simple Relaxed Concurrent Priority Queues,

    H. Rihani, P. Sanders, and R. Dementiev, “MultiQueues: Simple Relaxed Concurrent Priority Queues, ” inProceedings 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–...

    2015

  54. [62]

    Ligra: A Lightweight Graph Processing Framework for Shared Memory,

    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

    2013

  55. [63]

    MOLIERE: Automatic Biomedical Hypothesis Generation System,

    J. Sybrandt, M. Shtutman, and I. Safro, “MOLIERE: Automatic Biomedical Hypothesis Generation System, ” inProceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery

  56. [64]

    ArnetMiner: extraction and mining of academic social networks,

    J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, “ArnetMiner: extraction and mining of academic social networks, ” inProceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD ’08. New York, NY, USA: Association for Compu...

    2008

  57. [65]

    A bridging model for parallel computation,

    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

    1990

  58. [66]

    Scale-free networks well done,

    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

    2019 doi

  59. [67]

    Parallel Strong Connectivity Based on Faster Reachability,

    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 and Data Mining, ser. KDD ’17. New York, NY, USA: Associa...

    2023

  60. [68]

    Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues,

    M. Williams, P. Sanders, and R. Dementiev, “Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues, ” inDROPS- IDN/v2/document/10.4230/LIPIcs.ESA.2021.81. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. [Online]. Available: https: //drops.dagstuhl.de/entitie...

    2021 doi

  61. [69]

    The lock- free k-LSM relaxed priority queue,

    M. Wimmer, J. Gruber, J. L. Träff, and P. Tsigas, “The lock- free 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

    2015

  62. [70]

    Weighted Evolving Networks,

    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

    2001

  63. [71]

    Multi Bucket Queues: Efficient Concurrent Priority Scheduling,

    G. Zhang, G. Posluns, and M. C. Jeffrey, “Multi Bucket Queues: Efficient Concurrent Priority Scheduling, ” inProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’24. New York, NY, USA: Association for Computing Machinery, 2024, pp. 1...

    2024

  64. [72]

    Optimizing ordered graph algorithms with GraphIt,

    Y. Zhang, A. Brahmakshatriya, X. Chen, L. Dhulipala, S. Kamil, S. Amarasinghe, and J. Shun, “Optimizing ordered graph algorithms with GraphIt, ” inProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization, ser. CGO 2020. New York, NY, USA: As...

    2020

  65. [2003]

    Available: https://www.sciencedirect.com/science/ article/pii/S0196677403000762

    [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0196677403000762

  66. [2021]

    Available: https://dl.acm.org/doi/10.1145/3434393

    [Online]. Available: https://dl.acm.org/doi/10.1145/3434393

    doi

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.