How to show that random graphs cannot be embedded with short edges

Question

For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio

$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between nodes}} \times \textsf{diameter}$$

where the diameter is the maximal Euclidean distance between nodes. An embedding consists in giving each node of the graph an arbitrary position under the restriction that the minimal Euclidean distance between nodes is 1, and drawing straight lines between adjacent nodes. Note, that such an embedding in general is not planar, and is not supposed to be.

Call $\gamma$ the $k$-unorderedness of the embedding. The $k$-unorderedness of a graph is the minimal unorderedness of its embeddings in $\mathbb{R}^k$. The unorderedness of a graph is its minimal $k$-unorderedness.

For a 10x10 square grid in the natural embedding in $\mathbb{R}^2$, the mean distance is $\approx$ 5.19 while the mean length of edges is 1. This gives – with diameter $\sqrt{200}$ – supposedly $\gamma \approx$ 2.69 for this graph (which would have to be proved but this seems not to be hard).

I wonder how to determine $\gamma$ for a given (Erdös-Renyi) random graph? One obviously cannot check all of its embeddings, and one cannot - as in the case of the square grid - start with a natural guess and prove that it is the best case. So how would I proceed?

What might be a lower bound $\gamma_0$ such that almost all graphs have $\gamma > \gamma_0$?

What would be even more enlightening: To know the expected distribution of edge lengths for $\gamma$-minimal embeddings of random graphs (in units of mean mode distance). How would I guess it? Can it be shown from first principles that it will be a Poisson distribution (like the degree distribution)? Or possibly a scale-free distribution? For the square grid we know the distribution: it's a delta peak at 1.

Answer 1

Perhaps you could look into Spectral Graph Drawing.

Since a single comment with a link does not qualify as an answer in the views of many on this site, and truly I don't have enough reputation to just post a comment, let me try to expand on this post to help myself learn what is considered sufficient material for an answer.

Spectral Graph Drawing is a technique that uses eigenvectors (usually those of small eigenvalues) of the graph's Laplacian matrix as Euclidean coordinates of plotted vertices. The Laplacian matrix of graph $G=(V,E)$, $$ L_{ij}=D_{ii}-A_{ij} $$ ($i,j\in[1,\vert V\vert]$), is formed by subtracting the adjacency matrix from a diagonal matrix whose elements are the degrees of each vertex.

I don't think there is a strict standard on exactly how the coordinates are derived from the eigenvectors. But a brief Google search reveals a common method is to derive coordinates in $\mathbb{R}^2$ from the 2 eigenvectors of the 2 smallest eigenvalues. The $(x,y)$ coordinates of the $k^\mathrm{th}$ vertex will be the $k^\mathrm{th}$ elements of those eigenvectors respectively. In this example method, one can see that a vertex $v$'s coordinate is related to an average of those of its neighbors ($u$'s): $$ \delta_v\cdot x(v)=\sum\limits_{(u,v)\in E}x(u)+\lambda x(v)\\ x(v)=\mathrm{E}[x(u)]\frac{\delta_v}{\delta_v-\lambda}=\mathrm{E}[x(u)](1+\frac{\lambda}{\delta_v-\lambda}) $$ where $\delta_v$ is the degree of vertex $v$ and $\lambda$ is the eigenvalue corresponding to the eigenvector represented in the equation above (of its vertex $v$ element). $\mathrm{E}[\cdot]$ is the arithmetic mean. So intuitively, the "variance" is small when the mean is close to $0$ (i.e. neighbors are evenly placed around the origin) and when $\lambda$ is small compared to $\delta_v$.

The high level sense from easily searchable literature on this topic suggests the issues about how to constrain "fair" embedding as discussed in the comments are addressed in the current art of using Spectral Graph Drawing. The suggested unorderedness metric in the question can be computed from Euclidean distances between the produced coordinates.

I guess the intention of the metric was to measure whether many edges has to be drawn across almost the diameter of the plot. The simple intuitive analysis above shows the Spectral Graph Drawing method inherently tries to minimize such long edges, so it may be a great match for the purpose. Spielman showed examples in a recent video. It is worth watching in whole for a great overview of Spectral Graph Drawing.

There is also related research on the graph Laplacian in the context of random graphs and "entropy".

Finally, I believe it is already known that random graphs will not result in good pictures from Spectral Graph Drawing. If the input signal is noise-like, linear operations will not introduce information. At best, maybe one could introduce a relation between a metric of the plot based on a certain drawing method, and the number of vertices and edges of a random graph.

Answer 2

This is really not an answer to your question, but too long for a comment and I think it may be of interest.

I would like to relate your question to community detection in graphs. There is a wide variety of heuristics that compute partitions of the node set into parts (the communities) such that there are many links within the parts and only few between them (which is quantified by a variety of quality functions). One of the most famous such heuristics is the Louvain algorithm to optimize modularity (and other quality functions) of obtained partitions. It is very fast and performs very well in practice.

Community detection may be used to quickly obtain very good graph embeddings, as shown in this recent paper: LouvainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding by Ayan Kumar Bhowmick, Koushik Meneni, Maximilien Danisch, Jean-Loup Guillaume, and Bivas Mitra, in WSDM 2020.

In another stream of works, it was shown that Louvain finds partitions of high modularity even in random graphs that do not have communities. However, different runs of (a randomized version) of Louvain give very different partitions for such graphs. Instead, the partitions obtained for networks with actual community structure are very stable, which shows that instability of Louvain is specific to random graphs.

In the absence of a more direct solution, this may be seen as a promising direction to ''show that random graphs cannot be embedded with short edges'', IMHO. Indeed, it seems to me that the instability of Louvain (and other) methods on random graphs means that the obtained partitions make little sense, as one may expect. In turn, this means that embeddings of such random graphs, at least using Louvain-based approaches, probably have little sense too. They would therefore result in large values of your $\gamma$ property, and this would, in a sense, be specific to random graphs (or, at least, graphs with no community structure). Don't you think?

This is very empirical, sorry, and a thought more than an answer, as I said. Still, I hope it may help.

Answer 3

For fixed $k$, fixed $p$ and large $n$ I would expect this to be just the minimum possible diameter, scaling like $n^{1/k}$.

In a random graph, any two sets of $\epsilon n$ vertices have the same number of edges (and so of non-edges) between them, so for my guess to be off the mark it must be impossible to approximate the average distance in the graph by looking at some weighted combination of pairs of linearly-sized sets $(A,B)$ where the distance from a point in $A$ to a point in $B$ is approximately the same for almost all pairs of points $a \in A, b \in B$. This would require great variation in the density of vertices in different parts of the space, which would force up the diameter. I don't expect any small improvements from careful arrangement of vertices would be sufficient to counter this increased diameter.