Generate random graphs that satisfy the triangle inequality

Question

I would like to generate random graphs that might be geometric graphs in some (unknown) dimension. So I would like every triangle in the graph to satisfy the triangle inequality on its (random) edge lengths/weights. I need something akin to the Erdős/Rényi model such as, "The weighted random graph model," but with the triangle geometric constraint.

The earlier MO question, "Probability that random weights on $K_n$ satisfy triangle inequality," seems quite relevant, but I don't immediately see how it leads to a method for generating the random graphs I need.

So my question is:

Q. How can one generate random Erdős/Rényi weighted graphs that satisfy the triangle inequality for every triangle in the graph?

Answer 1

I am not sure I understand the issues: First you generate an ER (or your favorite model) random graph. The constraints that the edge lengths are in $[0, 1]$ and satisfy all possible triangle inequalities defines a polytope in $\mathbb{R}^E,$ and you are just trying to find a uniform random point in the polytope, which is a well-studied problem, see, e.g. Uniformly Sampling from Convex Polytopes

Answer 2

I would generate random graph and discard the longest sides in each n-gon violating the inequality.

Answer 3

let $|e_{ij}|$ denote the length of the edge adjacent to vertices $i$ and $j$, then subtracting $\Delta^*:=\min\limits_{\lbrace i,j,k\rbrace}\left|e_{ik}\right|+\left|e_{kj}\right|-\left|e_{ij}\right|$ from every edge-weight renders the resulting graph metric and preserves the variance of the edge-weights.

Answer 4

The following also works for generating directed graphs with non-negative edgeweights $\omega_{ij}$ satisfying $\omega_{ij}\le\omega{ik}+\omega_{kj}$: if $r_{ij}$ is a random positive value then setting $\omega_{ij}=c+r_{i,j},\ c\ge\max_{i,j}r_{ij}$ renders the graph metric:
\begin{align}\omega_{ik}+\omega{kj}-\omega{ij}&=2c+r_{ik}+r_{kj}-c-r_{ij}\\ &= c+r_{ik}+r_{kj}-r_{ij}\\ &\ge c-r_{ij}\\ &\ge\max_{u,v}r_{uv}\,-\,r_{ij}\\ &\ge 0 \end{align}

Answer 5

Make an intermediate graph $H$ with arbitrary random nonnegative edge lengths. Now define a graph $G$ with the same edges, with the length of each edge $vw$ in $G$ being the distance between $v$ and $w$ in $H$.