Computing the Exact Radius of Large Graphs

A center of a graph is a node that minimizes the maximum shortest path distance to all other nodes, and the graph radius is the distance from the center to the node furthest from it. The radius is a fundamental graph parameter with numerous applications in theory and practice, including fine-grained complexity reductions [3], parameterized bounds for combinatorial problems [25], and network analysis [26, 13, 18]. The center itself is relevant, for example, in facility location problems [17, 20] or rumor spreading analysis [23, 15].

Formally, given a strongly connected directed graph $G(V,E)$, $|V|=n$, $|E|=m$ with non-negative edge weights $w:E\to {ℝ}^{+}$, the eccentricity of a node $v\in V$ is defined as $ϵ(v):={\max }_{u\in V}c(v,u)$ where $c(.,.)$ denotes the shortest path cost in $G$. The radius of the graph is defined as $r:={\min }_{v\in V}ϵ(v)$ and a node $v$ with $ϵ(v)=r$ is called a center of $G$.

The eccentricity of a node $v$ can be determined by a one-to-all shortest path computation from $v$ in $G$. Therefore, the graph radius can be computed by first solving the all-pair-shortest-path problem (APSP) and then determining the node with the minimum eccentricity. APSP can be solved in $𝒪(n^3)$ by the Floyd-Warshall algorithm or in $O(n^2\log n+nm)$ using $n$ runs of Dijkstra’s algorithm. The natural question arises as whether the radius can be computed significantly faster with an algorithm that is not based on APSP. But recent fine-grained complexity results leave little hope for such a breakthrough. It was proven in [1] that computing the radius is equivalent under subcubic reductions to APSP. Thus, a subcubic algorithm for radius computation would imply a subcubic algorithm for APSP, which is conjectured to not exist. In [3], a conditional lower bound for radius computation was shown which implies that an algorithm with a running time in $𝒪(n^a{m}^b)$ for any constants $a,b$ with is also unlikely to exist. Thus, the Dijkstra based algorithm appears to be optimal up to logarithmic factors even in sparse graphs.

These negative results apply to general input graphs. But, of course, improvements might still be possible for special graph classes. In [2], it was proven that there is a so called fixed parameter subquadratic algorithm with a running time in $2^{𝒪(t\log t)}{n}^{1+o(1)}$ on graphs with treewidth $t$. Clearly, the practical relevance of this algorithm is restricted to input graphs where the treewidth is a small constant and it also has not yet been implemented. In this paper, we devise a randomized algorithm for exact radius computation with an expected running time in $𝒪(d^{3}m{\log }^{2}n)$ where the parameter $d$ denotes the so called combinatorial dimension for which we always have $d=O(n)$. Our algorithm is based on formulating radius computation as an LP-type problem and tailoring existing methods for solving such problems to our use case. In our experimental evaluation, we show that many graph instances indeed exhibit a small combinatorial dimension, and thus our newly developed algorithm computes the radius in these graphs with a near-linear running time.

LP-type problems were first defined by Sharir and Welzl [24]. They are a generalization of linear programs that retain many of their combinatorial properties but are not restricted to linear constraints. For an LP-type problem, there needs to be a finite set of constraints $S$ and a measure function $f$ that assigns a value to each subset of $S$. The function $f$ needs to satisfy the following two properties:

• $\mathrm{■}$

  Monotonicity. For $A\subseteq B\subseteq S:f(A)\le f(B)$. This implies that adding more constraints does not decrease the function value.

• $\mathrm{■}$

  Locality. Let $A\subseteq B\subseteq S$ and $f(A)=f(B)$: If for $s\in S-B$ we have $f(B\cup \{s\})>f(B)$ then $f(A\cup \{s\})>f(A)$.

A basis of an LP-type problem is a set $B\subseteq S$ such that $f(B)=f(S)$ and $\forall B^{\prime }\subset B$ we have . So a basis is a (set-)minimal subset of constraints that defines the same function value as the entire set, and removing any constraint from it changes that value. The combinatorial dimension $d$ of an LP-type problem is defined as the maximum cardinality of a basis. Algorithms for solving LP-type problems aim at quickly identifying such a basis. These algorithms work particularly well in case the basis is much smaller than the size of $S$, which means that $S$ contains many redundant constraints. For example, for $d\in O(1)$, a linear program with $n$ constraints can be solved in expected $𝒪(n)$ time [24].

We now show that the computation of the radius of a given digraph $G(V,E)$ with edge weights is an LP-type problem with a minimization measure function. For ease of exposition, we assume from now on that the shortest path costs $c(v,w)$ between node pairs $v,w\in V$ are all pairwise distinct. This can be ensured by adding a small random number to each edge weight. Under this assumption the center of the graph is uniquely defined. Our measure function is the radius $r:={\min }_{v\in V}ϵ(v)$ where $ϵ(v):={\max }_{u\in V}c(v,u)$ denotes the eccentricity of the node $v$. Thus, each node poses a constraint for the radius value. For a node subset $F\subseteq V$ we define the eccentricity as well as the radius with respect to $F$ as follows:

This means that we only care about distances to nodes in $F$ and not to all nodes in $V$ when defining the radius of a node subset. We now show that $r_F$ fulfills the requirements of a measure function for an LP-type problem.

Our algorithm is heavily inspired by Clarkson’s second algorithm for LP-type problems [8], which is an iterative randomized algorithm. It starts with a small random subset of constraints $R$ (where the notion of small depends on the combinatorial dimension $d$) and computes an optimal solution for $R$. Then, it checks whether any constraints are violated for this solution. If that is not the case, the current solution is obviously optimal. Otherwise, it follows that one or more violators need to be included in $R$ to get a correct solution. To make this more likely to happen in the next round, weights/multipliers are assigned to all constraints. Initially those are uniformly set to one. But whenever a constraint is identified to be a violator, its weight is doubled. In the next round, a new sample $R$ is chosen. The probability of a constraint to be sampled is proportional to its weight. The algorithm repeats the sampling and reweighing process until the optimal solution that satisfies all constraints is identified. This happens in the iteration in which $R$ is a superset of a basis $B$ for the problem.

We now tailor this algorithm to our problem of radius computation. There are two main ingredients needed for the Clarkson algorithm to work: An efficient method that computes the optimal solution for a given sample $R$ and an algorithm that identifies the set of violators or certifies the global optimality of the solution. The radius $r_R$ and the center $c_R$ for a given node subset $R$ can be obtained as follows: We allocate an array of size $n$ which is supposed to store for each node $v\in V$ the maximum distance to the nodes in $R$. Initially, all array entries are set to zero. By running Dijkstra’s algorithm once from each node $w\in R$ on the reverse edges and updating the maximum distance array of a node $v$ whenever a computed shortest path distance $c(v,w)$ exceeds its current value, we can compute the eccentricities ${ϵ}_R$ in $𝒪(|R|(n\log n+m))$ time and deduce the radius and the center from these values in linear time. To compute the set of violators, we need to find all nodes that further away from $c_R$ than $r_R$. This can easily be checked with a single run of Dijkstra’s algorithm from $c_R$. If the shortest path distance from $c_R$ to all nodes $v\in V$ is within $r_R$, we know that $c_R=c_V$ and $R\supset B$. Otherwise, we can gather all nodes with a shortest path distance greater than $r_R$ from $c_R$ and apply the above described reweighing procedure to these violators.

For now, we assume the combinatorial dimension $d$ to be known. With the careful choice of the sample size $|R|$ being set to $6d^2$ we will show that after an expected number of $O(d\log n)$ iterations, the basis $B$ must be part of the sample $R$. As we need $|R|+1$ runs of Dijkstra’s algorithm per iteration as discussed above, the expected total number of Dijkstra computation is in $O(|R|d\log n)$. Thus, the total running time for graph radius computation is in $𝒪(d^3\log n(n\log n+m))$. Algorithm 1 shows the respective pseudo-code. In the algorithm, we maintain for each node $v$ of the node set $V$ a multiplicity (initially ${\mu }_v=1$) to be able to increase the probability of a node being picked in a subsequent iteration by doubling its multiplicity. The weight $\mu (X)$ of the violator set $X$ counts each violator $v\in V$ according to its multiplicity.

Quite obviously, the algorithm produces an optimal solution if it terminates as it has computed the optimum center $c_R$ and radius $r_R$ for a subset $R\subset V$ and all other nodes are within distance $r_R$ from $c_R$.

The goal is now to analyze the expected running time of the algorithm in more detail. The following analysis follows closely the one in [8]. We call an iteration successful if the weight of the violator set $X$ is not too high, that is, $\mu (X)\le \frac{1}{3d}n$. To upper bound the number iterations needed until we have such a successful iteration, we first investigate the expected weight of the violator set.

Clarkson’s algorithm requires knowledge of the combinatorial dimension $d$ of the problem to choose a reasonable size for the sample $R$. For many LP-type problems, the dimension can be bounded a priori. This is true, for example, for the minimum enclosing circle problem where given a set of points in the plane, the goal is to find the smallest circle that contains all points. The combinatorial dimension is known to be at most 3 for this problem [16].

Unfortunately, we will prove next that no such bound exists for the graph radius problem by constructing a graph with combinatorial dimension $d\in \mathrm{\Theta }(n)$.

Our algorithm is implemented in C++ (g++ 11.4.0) and executed on a Ryzen 7950x 16-core machine with 192GB of RAM running Ubuntu Linux 22.04.

We picked several benchmark graphs from the Stanford Large Network Dataset Collection (SNAP), [14]. These were all unweighted graphs ranging from few thousand nodes up to more than half a billion nodes and almost 2 billion edges. Additionally we used as weighted graphs the road networks of Germany and Europe extracted from the OpenStreetMap project data [19]. See Table 1, columns 1–5 for the characteristics of our data sets. For each graph we ran our algorithm on the largest strongly connected component.

The considered SNAP data includes collaboration/social network/interaction data(caAstroPh, email-enron, soc-livejournal1, com-friendster), two web graphs (web-BerkStan, web-Google), a co-purchase-graph (amazon0505) and a peer-to-peer graph (p2p-gnutella, which we interpreted as an undirected graph since the largest strongly connected component was too small). We picked within each category the largest instance(s).

We presented an exact algorithm for computing the center of a graph (directed or undirected, weighted or unweighted) which runs in near-linear time if the combinatorial dimension of the graph is a constant. Our algorithm is essentially an adaptation of an algorithm of Clarkson [8] originally invented for low-dimensional linear programming. In our context, the combinatorial dimension describes the cardinality of a minimal subset of vertices that have the same center and radius than the original graph. While we could show that there exist graphs with combinatorial dimension $\mathrm{\Theta }(n)$, many real-world graphs that model, e.g., social networks, communication patterns, collaborations, road networks etc. empirically exhibit very low combinatorial dimension. Due to that somewhat surprising finding, we can compute the exact graph center even for graphs with billions of edges in few hours where the standard approach would take several hundred years.

In future work, it would be interesting to explore whether efficiency of the algorithm can also be proven for non-distinct shortest paths. Furthermore, while random subset selection is an integral part of the algorithm to prove the respective expected running time bounds, greedy selection strategies were shown to perform well in practice [5] and in theory [6] in the unweighted case. Analyzing those strategies directly or designing new deterministic strategies with performance guarantees in the weighted case could reveal new insights into the problem structure.