6
$\begingroup$

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?

$\endgroup$

5 Answers 5

7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Brilliant reformulation, Igor! $\endgroup$ Oct 29, 2016 at 0:07
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.