4
$\begingroup$

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.

$\endgroup$
20
  • 2
    $\begingroup$ You maybe should precise what your "embeddings" are. I suppose straight-edge embeddings, that respect all constraints of distance among the edges it's given ? Those are rare : to exist, the edge length must respect triangular inequalities, which probably won't happen in random graphs if not built this way (ie directly from an embedding, I guess ?). Also, the dimension $k$ must (in non-degenerate cases) grow with the number of independent cycles in the graph for a solution to be possible. $\endgroup$
    – Hugo Manet
    Mar 10, 2021 at 11:34
  • 2
    $\begingroup$ Please edit your question to define "distance of nodes" and "diameter", Both of these have meanings according to paths in the graph and euclidean distance in space. $\endgroup$ Mar 10, 2021 at 12:32
  • 1
    $\begingroup$ @BrendanMcKay: Done. $\endgroup$ Mar 10, 2021 at 12:48
  • 1
    $\begingroup$ Actually, I am confused. I am probably misreading something. In the current formulation you are looking at something of the form (mean edge length)x(diameter)/(mean distance). If we scale everything by a small positive factor - say $1/10^8$ - the quantity decreases by the same factor. $\endgroup$ Mar 10, 2021 at 14:24
  • 3
    $\begingroup$ You might want to look into expander graphs. These graphs roughly have the property that any two nodes are within distance $O(\log n)$. This implies that in many cases, they can't be 'efficiently' embedded into euclidean space since the distances are so small (but you have many points to embed). There is a chapter in this great book (link.springer.com/book/10.1007/978-1-4613-0039-7#toc) that talks about it (see the chapter 'embedding finite metric spaces into normed spaces). $\endgroup$ Mar 10, 2021 at 15:36

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @BucketHalfull: Thanks for your elaborate answer. Some ten years ago I asked this question in which the second largest eigenvalue of the adjacency matrix and positions of vertices played a role - now a circle closes. $\endgroup$ Mar 22, 2021 at 16:59
  • $\begingroup$ Thanks @Hans-PeterStricker! I am not a professional mathematician. But I noticed that "emergence of order" seems to be only getting hotter as a research topic. For that to happen though, the growth of the graph must not be completely (Gaussian) random. $\endgroup$ Mar 29, 2021 at 7:30
  • $\begingroup$ What do you mean by "growth of graphs"? $\endgroup$ Mar 29, 2021 at 7:50
  • $\begingroup$ By growth I simply meant how vertices and edges are added. If a small graph is considered "ordered", then how could it not become "unordered" when more vertices and edges are added? It must have to do with the way the addition is done. $\endgroup$ Apr 2, 2021 at 0:18
2
+50
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.