PaperlayerView exact revision on arXiv

Source-linked AI summary

An experimental evaluation of static k-center clustering algorithms on graphs

Sebastian Forster, Martin Grösbacher

arXiv:2610.29781v1cs.DS

TL;DR

Graph k-center has little systematic experimental evaluation on large-scale graphs, despite its relevance to network analysis and the practical role of shortest-path computation. This paper implements and compares graph k-center algorithms across synthetic and real-world graphs, finding that the strongest running-time approach depends on graph and parameter characteristics rather than being universal.

  • Problem

    Systematic experimental evidence on graph k-center algorithms’ running time is limited, despite graph distances arising naturally in network analysis.

    Source: §1 · p. 2, §1.1 · p. 3

  • Method

    The paper implements and experimentally compares classical and recent graph k-center algorithms, including a simplified Thorup variant, with sequential and parallel support.

    Source: §1.2 · p. 3, §8 · p. 11

  • Results

    No algorithm is universally superior: farthest-point methods are usually fastest on weighted graphs, while MIS methods can compete or outperform them on sparse weighted and dense unweighted graphs at larger k.

    Source: §8 · p. 11

  • Takeaways & Limitations

    The comparison provides practical implementations and empirical insights for graph-based k-center algorithms.

    Source: §8 · p. 11

    The study excludes a fully dynamic shortest-path alternative because no practical insertion-specialized algorithms were known to the authors, and the fully dynamic option would be essentially equivalent to Lazy Dijkstra here.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

The $k$-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select $k$ centers such that the maximum distance from any object to its closest center is minimized. The $k$-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for $k$-center clustering in metric spaces, a comprehensive experimental comparison of graph-based $k$-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2001] and Abboud et al. [SOSA 2023]. Our study considers both running time, solution quality and the effects of parallelism on a variety of synthetic and real-world datasets. Our goal is to provide a comprehensive comparison of state-of-the-art $k$-center algorithms on graphs and identify the strengths and weaknesses of different approaches in practice.

1 Introduction

The paper studies graph k-center, where the objective is to minimize the maximum distance from a vertex to its nearest center. It addresses the limited empirical evaluation of graph-based algorithms by comparing their running time, solution quality, and parallel scaling.

1 Introduction

  • Graph k-center minimizes the maximum shortest-path distance from any vertex to its nearest center.The centers are selected from the graph’s vertices.Source: §1 · p. 2

1.1 Related Work

  • In graphs, Thorup’s algorithm runs in ˜O(m + n) time, exploits a closest-source-distance primitive via a straightforward Dijkstra modification, and removes the classic algorithms’ iterative center-selection chain.Abboud, Cohen-Addad, Lee, and Manurangsi showed that the two classic approaches can also be implemented in near-linear time in graphs.Source: §1.1 · p. 2
  • Prior graph k-center experiments were limited to randomly generated graphs with at most 150 nodes, while metric k-center studies used moderate input sizes.Source: §1.1 · p. 3

1.2 Research Questions

  • The study compares running time, solution quality, and parallel scaling across graph classes using polynomial-time algorithms with approximation factor close to 2 and established SSSP implementations.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define the graph k-center setting and the work-depth model used to analyze parallel algorithms. They assume positive integer edge weights bounded polynomially in the number of vertices.

2.1 Basic Concepts

  • The graph is undirected with positive integer edge weights, and the highest weight N is assumed polynomial in n.The paper motivates the bound by observing that N is much smaller than n in massive real-world datasets.Source: §2.1 · p. 3
  • Graph k-center selects at most k vertices to minimize the maximum shortest-path distance to a selected center.Source: §2.1 · p. 3

2.2 Parallel Model and Primitives

  • In the work-depth model, parallel running time on P processors is O(W/P + D), where W is work and D is depth [9].Work is total operations; depth is the longest chain of sequential dependencies.Source: §2.2 · p. 4

3 SSSP algorithms

The paper’s k-center algorithms repeatedly use single-source shortest-path computations, so their performance depends substantially on the efficiency of those routines. The study adapts standard sequential and parallel SSSP methods with shared distance updates and an optional radius cap.

3.1 Parallel and Single-Core Routines

  • Repeated SSSP computations make shortest-path efficiency an important determinant of the k-center algorithms’ overall performance.Source: §3.1 · p. 4
  • The study uses breadth-first search for unweighted graphs and Dijkstra’s algorithm or Δ-stepping for weighted graphs, with sequential and parallel variants.It does not explicitly evaluate parallelization effects in the unweighted setting.Source: §3.1 · p. 4
  • The routines use lazy updates to insert a vertex only when its distance improves, and optionally relax edges only while the path distance stays within radius r.Source: §3.1 · p. 4

4 Maximal Distance-r Independent Set Algorithms

The section presents feasibility checks based on maximal distance-r independent sets, including Abboud et al.’s approach and an implementation-oriented simplification of Thorup’s algorithm. Both connect repeated shortest-path computations to the search for a radius that can be covered by at most k centers.

4.1 Abboud MIS

  • Abboud MIS binary-searches for the smallest radius covering the graph with at most k centers, using a maximal distance-r independent set as its feasibility check.The check selects a center when its current distance exceeds r and updates distances through an SSSP routine.Source: §4.1 · pp. 4–5
  • Abboud MIS has an expected O(n log^2 n + m log n) feasibility-check running time independent of k; each vertex experiences only O(log n) successful distance decreases in expectation.The stated bound is for the maximal distance-r independent-set algorithm; sequential SSSP calls make phase overhead accumulate per selected center.Source: §4.1 · pp. 4–5
  • Abboud et al.’s edge-weight rounding guarantees polynomially bounded integer weights but incurs a (1 + ϵ) approximation-factor loss; this study does not use that scheme.Source: §4.1 · p. 4

4.2 Simplifying Thorup’s Algorithm

  • The simplified Thorup feasibility check replaces Cohen’s size-estimation routine with geometrically decreasing guesses of δ and repeated sampling, retaining no worse asymptotic running time than Thorup’s algorithm.The original size-estimation routine is comparatively involved and, to the authors’ knowledge, lacks a publicly available implementation.Source: §4.2 · p. 5
  • When δ is within a constant factor of δ*, heavy vertices are eliminated with constant probability per round, so a phase reduces δ* by a constant factor in expectation.The analysis bounds the number of rounds in this estimation regime and maintains δ > δ* with high probability at phase starts and after updates.Source: §4.2 · p. 6
  • The simplified check terminates after O(log^2 n) rounds with high probability, and its sequential running time is O(log^3 n · (m + n log n)) with Lazy Capped Dijkstra.The parallel work bound using Lazy Capped Δ-stepping is O(log^3 n (E_LCDS + P_LCDS)).Source: §4.2 · p. 6
  • For practical experiments, the simplified algorithm uses four rounds per phase with ϵ = 1; this does not meet the rounds-per-phase assumption for its high-probability termination guarantee, but the fallback preserves correctness.Source: §4.2 · p. 6

5 Farthest-Point Selection Algorithms

The section presents exact and approximate farthest-point methods for graph k-center, alongside their sequential and parallel implementations. The approximate variant uses distance bags to select nearly farthest vertices, while a practical limitation excludes an alternative dynamic shortest-path approach.

5.1 Gonzalez

  • Gonzalez selects an arbitrary first center, then repeatedly chooses the vertex farthest from the current centers, yielding a 2-approximation.The algorithm invokes one SSSP computation per selected center.Source: §5.1 · p. 6
  • On weighted graphs, Gonzalez with Dijkstra runs in O(k(m + n log n)); parallel Lazy ∆-stepping accumulates SSSP work and depth across k iterations.The parallel bounds are W = O(k(ELDS + PLDS)) and D = O(kDLDS).Source: §5.1 · pp. 6–7
  • The study excludes a dynamic shortest-path alternative because practical edge-insertion-specific implementations were unavailable, while fully dynamic methods would be essentially equivalent to Lazy Dijkstra here.The cited approach supports source-edge insertions, which are sufficient for this setting.Source: §5.1 · p. 7
  • The α-approximate Gonzalez variant selects a random vertex from the highest nonempty distance bag instead of the exact farthest vertex, yielding a (2 + ϵ)-approximation when α = 1 + ϵ.Bag-based selection supports efficient approximate farthest-vertex identification with lazy distance updates.Source: §5.1 · p. 7
  • The bag-based method uses an augmented SSSP routine to update distances and affected bags; its expected running time is O((n log^2 n + m log n) log n).The randomized charging argument bounds successful distance improvements per vertex per bag by O(log n) in expectation.Source: §5.1 · p. 7

6 Experimental Setup

The experiments compare sequential and parallel k-center algorithms on synthetic and real-world graphs, measuring running time and relative solution quality. The setup spans graph types and sizes, with parallel scaling tests conducted on selected instances before the full sweep.

6.2 Datasets

  • Real-world instances included social, road, and rating graphs, spanning roughly one million vertices and three million edges to over 60 million vertices and 1.8 billion edges.The study also generated small and large weighted and unweighted synthetic graphs.Source: §6.1 · p. 8, §6.2.1 · p. 8, §6.2.3 · p. 9

6.1 General Setup

  • Experiments measured running time, relative solution quality, and parallel scaling for sequential and parallel variants, with k values up to approximately √n.Weighted and unweighted graphs used corresponding sequential and parallel SSSP routines; the median of three runs was reported unless stated otherwise.Source: §6.1 · p. 8

6.2.1 Synthetic Graphs

  • Synthetic Erdős–Rényi graphs covered six densities, ρ = 2, 4, 8, 16, 32, and 64, with 120 small instances and 12 large instances.Small graphs had 10^5 vertices and large graphs 10^7 vertices; weighted edges received integer weights from 1 to 10,000.Source: §6.2.1 · p. 8

6.2.3 Road Networks

  • The road-network instances are very sparse (ρ < 2) and have high diameter because their weights represent physical distances across the US.The study used the two largest road-network graphs available from the 9th DIMACS challenge.Source: §6.2.3 · p. 9
  • Rating graphs were very dense and low-diameter; rating weights were transformed so higher ratings corresponded to shorter edge weights.A subset of graphs was also used for parallel-scaling tests before the full experimental sweep.Source: §6.2.3 · p. 9, Figure 7.1 · p. 9

7 Experimental Results

The experiments compare parallel scaling, running time, and solution quality across graph classes. Parallelism benefits some dense graphs but not sparse, high-diameter road graphs; algorithm performance also varies with k and graph structure.

7.1.1 Parallelism on Social Networks

  • On social networks, farthest-point algorithms and Simplified Thorup benefit from parallelism up to about 64 threads, with running times reduced by roughly factors of 2 to 5.Abboud MIS responds differently by graph density and k: parallelism hurts on sparse YouTube, helps on denser LiveJournal and Orkut by up to about 2×, and becomes substantially slower as k approaches √n.Source: §7.1.1 · p. 10
  • On the sparse, high-diameter road network, no algorithm benefits from parallelism; single-core execution remains faster, including in the full sweep.The dedicated scaling experiment used at most 32 threads, while the full sweep also included 64-thread executions.Source: §7.1.1 · p. 10, Figure 7.2 · p. 10

7.2 Running Time and Solution Quality

  • On social networks, MIS-based approaches are generally slower than farthest-point algorithms for low k but catch up as k approaches √n.Simplified Thorup outperformed farthest-point algorithms on Orkut and Twitter, but not Friendster; the authors suggest virtual-machine execution may influence the latter result.Source: §7.2 · p. 10
  • On road networks, all algorithms run best in single-core mode; Abboud MIS eventually outperforms the farthest-point algorithms as k increases, while Simplified Thorup remains slower.Weighted graphs with high diameter require many feasibility checks, making Simplified Thorup’s additional phases dominate running time.Source: §7.2 · p. 11, Figure 7.4 · p. 11
  • MIS-based algorithms produce road-network solutions approximately 10% to 12% better than the Gonzalez baseline across tested k values.Approximate Gonzalez also generally outperforms vanilla Gonzalez on these instances.Source: §7.2 · p. 11, Figure 7.5 · p. 11

8 Conclusion

The study compares classical and recent static graph-based k-center algorithms using shared optimized shortest-path routines. Its results show that performance depends on graph and parameter characteristics, with no universally superior algorithm.

8 Conclusion

  • All four implemented algorithms share optimized shortest-path routines in the Graph-Based Benchmark Suite, supporting a fair comparison of practical performance.The evaluated set includes Gonzalez, Thorup, an improved Hochbaum–Shmoys variant by Abboud et al., and an α-approximate Gonzalez variant.Source: §8 · p. 11
  • No single algorithm is universally superior: farthest-point methods are usually fastest on weighted graphs, while MIS methods can win on sparse weighted or dense unweighted graphs at larger k.On road networks, MIS methods generally report better weighted-instance solutions, with relative differences of approximately 10% to 12%.Source: §8 · p. 11
  • Graph density, edge weights, diameter, and k substantially influence practical performance, while parallel speedups depend on the algorithm and graph topology.Parallel execution is highly beneficial on sufficiently large instances that are not particularly sparse.Source: §8 · p. 11
  • The study provides practical implementations and an extensive experimental comparison of modern graph-based k-center algorithms.The authors hope the implementation techniques and empirical insights will facilitate future work on scalable clustering algorithms for large-scale graphs.Source: §8 · p. 11

A.1 ∆-stepping

The appendix describes parallel Δ-stepping and the modifications used in the paper’s shortest-path routines. Lazy updates avoid resetting distances, while a distance cap restricts the computation to a radius-bounded part of the graph.

A.1 ∆-stepping

  • Parallel Δ-stepping processes light and heavy edges in separate phases, using buckets to organize distance relaxations.The analysis is based on Meyer and Sanders’ arbitrary CRCW PRAM model, where concurrent shared-memory accesses take constant time.Source: §A.1 · p. 12
  • The analysis uses general work-depth bounds for arbitrary positive edge weights rather than relying on the random-weight assumption that simplifies the bounds.Under Meyer and Sanders’ additional assumption of independent uniform edge weights in [0, 1], choosing Δ = Θ(1/deg_max) yields expected linear bounds on n_Δ and m_Δ; the paper does not rely on that assumption.Source: §A.1 · p. 12
  • Lazy updates retain previously known distances and update a vertex only when a new path improves its best-known distance.For one invocation, this can reduce successful relaxations without worsening the asymptotic work or depth bound.Source: §A.1 · p. 12
  • A distance cap r restricts edge relaxations to paths whose distance remains within r, reducing the explored graph and the number of processed buckets.The corresponding counts of explored vertices and edges, reinsertions, and re-relaxations become radius-bounded quantities.Source: §A.1 · pp. 12–13
  • MIS-based algorithms use lazy updates and a distance cap in their SSSP computations, whereas farthest-point algorithms use lazy updates alone..Source: §A.1 · p. 13

A.2 Omitted Proof of Section 4.1

The omitted proof bounds the work of a randomized MIS-based k-center algorithm by charging work to successful distance decreases. Lazy updates and distance caps restrict the work, while sequential SSSP calls add phase overhead.

A.2 Omitted Proof of Section 4.1

  • The expected number of successful distance decreases per vertex is O(log n), yielding O(m log n + n log n) total work attributable to those decreases.The charging argument uses the fact that the next center is drawn uniformly from the current candidate set and the set of candidates that could improve a vertex’s distance shrinks in expectation.Source: §A.2 · p. 14
  • With a distance cap r, expected exploration work is charged only to explored vertices and edges and their corresponding reinsertions and re-relaxations.The proof applies the successful-distance-decrease charging argument within the capped explored subgraph.Source: §A.2 · p. 14
  • Sequential Lazy Capped Δ-stepping calls add total phase overhead O(krP_LCDS) to the work bound.Each invocation incurs phase overhead P_LCDS.Source: §A.2 · p. 14
  • Replacing Lazy Capped Dijkstra with Lazy Capped Δ-stepping changes the cost of each SSSP computation while preserving the randomized O(log n) expected successful-distance-decrease argument.The other algorithms’ analyses are adapted analogously by substituting the corresponding SSSP work and depth bounds.Source: §A.2 · p. 15

A.2.1 Abboud MIS Implementation Details

The implementation uses doubling followed by binary search to find the smallest feasible cluster radius. Capping each SSSP call at its candidate radius helps avoid exploring unnecessarily large portions of the graph.

A.2.1 Abboud MIS Implementation Details

  • Starting a radius search at nW can greatly overestimate the needed radius and trigger SSSP calls that explore unnecessarily large graph regions..Source: §A.2.1 · p. 15
  • The implementation first doubles candidate radii from r_0 = 2 until it finds a feasible radius, then binary-searches between that radius and its predecessor.The search ends at the smallest feasible radius.Source: §A.2.1 · p. 15
  • Even an underestimated candidate radius caps its SSSP calls, allowing them to terminate early while the search proceeds toward feasibility..Source: §A.2.1 · p. 15

A.3 Omitted Proofs of Section 4.2

This section gives proofs of progress and termination for the simplified Thorup algorithm and reports implementation details and experiments on parameter sensitivity, parallelism, running time, and solution quality across social-network and weighted-network instances.

A.3 Omitted Proofs of Section 4.2

  • The proof shows that O(c log n) rounds eliminate all heavy vertices with high probability, decreasing δ* by a constant factor and preserving the phase invariant with high probability.At the final phase, the invariant implies δ*=0 with high probability, so the algorithm sets T=W and terminates.Source: §A.3 · pp. 15–16

A.3.1 Simplified Thorup Implementation Details; A.5 Augmented SSSP and Approximate Gonzalez Implementation Details

  • The simplified Thorup implementation uses lazy capped ∆-stepping for shortest paths and reuses its computed distances if the Abboud fallback is invoked.Augmented SSSP routines switch bag maintenance on or off with a flag, and their ϵ parameter can be set manually.Source: §A.3.1 · p. 16, §A.5 · p. 16

A.6 Algorithmic Parameter Choices; A.6.1 ∆-stepping

  • Across tested graphs, changing ∆ varied running times by at most approximately 10% in most configurations, so the experiments fixed ∆=8.Simplified Thorup was omitted from the plots because it was generally slower on high-diameter graphs, but its running time was also not substantially affected by ∆.Source: Figure A.1 · p. 17, §A.6 · p. 18

A.6.2 Approximate Gonzalez

  • For Approximate Gonzalez, ϵ=0.5 did not significantly improve running time, and solution-quality effects varied by graph type; the experiments used ϵ=0.5 on road networks and ϵ=0.001 elsewhere.Low ϵ appeared better on dense graphs, whereas higher ϵ improved solution quality on sparse weighted USA-central, even beyond the Gonzalez baseline.Source: §A.6.2 · p. 18

A.6.3 Simplified Thorup’s Algorithm

  • The Simplified Thorup experiments used ϵ=1 and four rounds per phase for the best tested running time without fallbacks, although this empirical choice does not satisfy the theorem’s O(log n)-round guarantee.The fallback was triggered only rarely even with a small constant number of rounds per phase.Source: §A.6.3 · p. 19, Figure A.4 · p. 19

A.6.4 Parallelism on Small Synthetic Graphs; A.6.5 Parallelism on Large Synthetic Graphs

  • Parallelism slows or barely helps all algorithms on small graphs, but benefits most algorithms on large graphs; gains stagnate around 64 threads, while Simplified Thorup struggles on weighted graphs.On large synthetic graphs, Gonzalez variants improve by roughly a factor of 2 at k=200, and Abboud MIS by a factor of 2–5 depending on density; most weighted Simplified Thorup runs time out.Source: §A.6.4 · p. 19, §A.6.5 · pp. 19, 21, Figure A.5 · p. 20

A.6.6 Small Synthetic Graphs

  • On small synthetic graphs, MIS methods can outperform Gonzalez for large-k unweighted cases, while weighted MIS methods run slower and Approximate Gonzalez returns radii 2–5% worse than Gonzalez.On weighted cases, MIS methods occasionally improve on Gonzalez by approximately 2%; on unweighted cases, algorithm radii differ by at most 1.Source: §A.6.6 · pp. 21–22, Figure A.7 · p. 21, Figure A.8 · p. 22

A.6.7 Large Synthetic Graphs

  • On large synthetic graphs, MIS methods perform best on unweighted instances, while weighted instances favor farthest-point approaches; Simplified Thorup improves dense weighted radii by up to 13%.For sufficiently large k, Simplified Thorup outperforms farthest-point approaches on dense unweighted graphs, and Abboud MIS gives radii approximately 2% below Gonzalez on some weighted instances.Source: §A.6.7 · pp. 22, 24, Figure A.9 · p. 23, Figure A.10 · p. 23

A.7 Social Networks

  • On social-network instances, all algorithms report identical radii except Simplified Thorup, which at k = 500 returns radius 3 versus Gonzalez’s 5, about 60% of its baseline.Because these unweighted graphs have small absolute radii, even a difference of two can appear as a 40% relative improvement.Source: §A.7 · p. 24

A.7.1 Other Networks

  • On three dense weighted networks, farthest-point algorithms are fastest; increased candidate radii during feasibility search appear to offset the density advantage of MIS-based approaches.Edge weights are small and derive from transformed ratings.Source: §A.7.1 · p. 24
  • On libimseti and MovieLens, reported radii range from approximately 13 to 17; on Yahoo! Song, they range from roughly 85 to 120 across k values.The 8% gap between Simplified Thorup and Gonzalez at k = 100 corresponds to an absolute radius difference of 1.Source: §A.7.1 · pp. 24–25, Figure A.13 · p. 25
Loading 2610.29781v1…