-
Notifications
You must be signed in to change notification settings - Fork 2
Graph Benchmarks
GraphBrew includes implementations of classic graph algorithms used to measure the performance impact of vertex reordering. This page explains each algorithm and how to run it.
GraphBrew includes eight benchmark binaries. The automated experiment pipeline runs seven by default (TC excluded — see Running-Benchmarks):
| Benchmark | Binary | Description | Complexity |
|---|---|---|---|
| PageRank | pr |
Importance ranking | O(n + m) per iteration |
| PageRank (SpMV) | pr_spmv |
Sparse matrix-vector PageRank | O(n + m) per iteration |
| BFS | bfs |
Shortest paths (unweighted) | O(n + m) |
| Connected Components | cc |
Find connected subgraphs | O(n + m) |
| Connected Components (SV) | cc_sv |
Shiloach-Vishkin CC | O(n + m) |
| SSSP | sssp |
Shortest paths (weighted) | O((n + m) log n) |
| Betweenness Centrality | bc |
Node importance | O(n × (n + m)) |
| Triangle Counting | tc |
Count triangles | O(m^{3/2}) |
PageRank is an iterative algorithm that computes the "importance" of each vertex based on the importance of vertices pointing to it. Originally developed by Google to rank web pages.
Mathematical formulation:
PR(v) = (1-d)/n + d × Σ PR(u)/out_degree(u)
for all u that point to v
Where:
-
d= damping factor (typically 0.85) -
n= number of vertices
./bench/bin/pr -f graph.el -s -o 12 -n 3
See Command-Line-Reference for all options (-i iterations, -t tolerance, -g synthetic graph).
Why reordering helps: PR iterates over all vertices, reading neighbor ranks each iteration. Good ordering = neighbors in cache = fast reads.
BFS explores a graph level by level, finding shortest paths (in terms of hops) from a source vertex to all other vertices.
Level 0: [source]
Level 1: [neighbors of source]
Level 2: [neighbors of level 1]
...
./bench/bin/bfs -f graph.el -s -o 12 -n 16
./bench/bin/bfs -f graph.el -s -o 12 -r 0 -n 3 # specific source
See Command-Line-Reference for all options. GraphBrew implements direction-optimizing BFS (top-down/bottom-up switching) for significant speedups on high-diameter graphs.
Why reordering helps: Vertices at the same BFS level stay nearby in memory → better frontier locality.
Finds all maximal sets of vertices where every pair is connected by a path. Returns the component ID for each vertex.
Graph: A-B-C D-E F
Components: {A,B,C}, {D,E}, {F}
GraphBrew includes two CC algorithms:
- Shiloach-Vishkin (cc_sv): Parallel with label propagation
- Afforest (cc): Faster sampling-based approach
# Standard connected components
./bench/bin/cc -f graph.el -s -o 12 -n 3
# Shiloach-Vishkin variant
./bench/bin/cc_sv -f graph.el -s -o 12 -n 3
Components: 1 # Number of connected components found
Largest: 1000000 # Size of largest component
Finds the shortest weighted path from a source vertex to all other vertices. Uses Dijkstra's algorithm with a priority queue.
./bench/bin/sssp -f graph.wel -s -o 12 -n 3
./bench/bin/sssp -f graph.wel -s -o 12 -r 0 -d 2 -n 5 # source 0, delta=2
Requires weighted graph (.wel). Uses delta-stepping SSSP with parallel bucket processing. See Command-Line-Reference for options.
Measures how often a vertex lies on the shortest path between other vertices. High BC = vertex is a "bridge" in the network.
Formula:
BC(v) = Σ σ(s,t|v) / σ(s,t)
s≠v≠t
Where:
- σ(s,t) = number of shortest paths from s to t
- σ(s,t|v) = number of those paths passing through v
./bench/bin/bc -f graph.el -s -o 12 -n 3
./bench/bin/bc -f graph.el -s -o 12 -r 0 -i 4 -n 3 # source 0, 4 iters
BC is O(n × m) per source vertex. Use -i 1 for quick testing. Each BFS benefits from reordering, so total benefit compounds across iterations. See Command-Line-Reference for options.
Counts the number of triangles (3-cliques) in the graph. Important for:
- Social network analysis
- Clustering coefficient computation
- Community detection
Triangle: A-B, B-C, C-A
# Standard triangle counting
./bench/bin/tc -f graph.el -s -o 12 -n 3
# Parallel version
./bench/bin/tc_p -f graph.el -s -o 12 -n 3
- tc: Sequential with set intersection
- tc_p: Parallel with work balancing
Triangles: N # Total number of triangles
Triangle counting benefits from processing vertices in degree order:
- Low-degree vertices first reduces work
- Combined with reordering for cache efficiency
# One-click: downloads graphs, runs all benchmarks with all algorithms
python3 scripts/graphbrew_experiment.py --full --size small
# Specific benchmarks only
python3 scripts/graphbrew_experiment.py --benchmarks pr bfs --size small
See Benchmark-Suite for automated experiments and Running-Benchmarks for manual usage.
- Trial Time: Time for single execution
- Average Time: Mean over multiple trials (more reliable)
-
Speedup:
baseline_time / algorithm_time
- Run at least 3 trials
- For BFS/SSSP, use multiple source vertices (
-n 16) - Warm up the cache with one untimed trial first
Speedups vary significantly depending on graph topology and reordering algorithm. Run the full pipeline on your target graphs to measure actual improvements.
# Quick verification
make test-topology
# Full verification with all algorithms
make test-topology-full
# Compare outputs between algorithms
./bench/bin/pr -f graph.el -s -o 0 -n 1 > original.txt
./bench/bin/pr -f graph.el -s -o 12 -n 1 > reordered.txt
# Results should match (within floating point tolerance)
- Running-Benchmarks - Detailed command-line reference
- Benchmark-Suite - Automated benchmarking
- Correlation-Analysis - Find the best algorithm for your graphs