R^3 中图的优雅表示
如果我有一个合理大小的图（例如~100个节点，每个节点出来的~40条边）并且我想用R^3表示它（即将每个节点映射到R^3中的一个点并画一条直线）原始图中连接的任意两个节点之间的线）以一种易于理解其结构的方式，您认为什么才是一个好的绘图标准？
我知道这个问题是不恰当的；这不客观。通过一个极端的例子更容易理解其背后的想法。假设您有一个连通图，其中每个节点都连接到两个且仅两个其他节点，但两个节点仅连接到一个其他节点。不难看出，当用 R^3 绘制该图时，可以将其绘制为一条直线（节点散布在该线上）。然而，可以用一种几乎不可能看到其非常简单的结构的方式来绘制它，例如通过围绕 R^3 中的某个固定点尽可能地“扭曲”它。因此，对于这个简单的情况，很明显，简单的 3D 表示就是直线。然而，尚不清楚一般情况下这种简单性属性是什么。
所以，问题是：如何定义这个简单性属性？
我对任何类型的答案都很满意，无论是图的可计算“简单性”的定义，还是转换图并收敛到“更简单”3D 表示的贪婪近似算法。
谢谢！
已编辑
同时，我已经将基于力将答案中建议的图形绘制想法付诸实践，并编写了一个 OCaml/openGL 程序来模拟如何在节点之间施加电排斥力（库仑定律）和在边缘上施加类似弹簧的行为（胡克定律）。我已在 YouTube 上发布了该视频。该视频从包含 100 个节点的初始图开始，每个节点具有大约 1-2 个传出边，并将节点随机放置在 3D 空间中。然后我提到的所有力量都已到位，并且系统将在这些力量的作用下移动。一开始，图表很混乱，很难看出结构。接近尾声时，很明显该图几乎是线性的。我也有过使用较大尺寸的图表的经验，但有时图表的几何形状只是一团糟，无论你如何绘制它，你都无法可视化任何东西。这是一个具有 500 个节点的极端示例。
If I have a graph of a reasonable size (e.g. ~100 nodes, ~40 edges coming out of each node) and I want to represent it in R^3 (i.e. map each node to a point in R^3 and draw a straight line between any two nodes which are connected in the original graph) in a way which would make it easy to understand its structure, what do you think would make a good drawing criterion?
I know this question is ill-posed; it's not objective. The idea behind it is easier to understand with an extreme case. Suppose you have a connected graph in which each node connects to two and only two other nodes, except for two nodes which only connect to one other node. It's not difficult to see that this graph, when drawn in R^3, can be drawn as a straight line (with nodes sprinkled over the line). Nevertheless, it is possible to draw it in a way which makes it almost impossible to see its very simple structure, e.g. by "twisting" it as much as possible around some fixed point in R^3. So, for this simple case, it's clear that a simple 3D representation is that of a straight line. However, it is not clear what this simplicity property is in the general case.
So, the question is: how would you define this simplicity property?
I'm happy with any kind of answer, be it a definition of "simplicity" computable for graphs, or a greedy approximated algorithm which transforms graphs and that converges to "simpler" 3D representations.
Thanks!
EDITED
In the mean time I've put force-based graph drawing ideas suggested in the answer into practice and wrote an OCaml/openGL program to simulate how imposing an electrical repulsive force between nodes (Coulomb's Law) and a spring-like behaviour on edges (Hooke's law) would turn out. I've posted the video on youtube. The video starts with an initial graph of 100 nodes each with approximately 1-2 outgoing edges and places the nodes randomly in 3D space. Then all the forces I mentioned are put into place and the system is left to move around subject to those forces. In the beginning, the graph is a mess and it's very difficult to see the structure. Closer to the end, it is clear that the graph is almost linear. I've also experience with larger-sized graphs but sometimes the geometry of the graph is just a mess and no matter how you plot it, you won't be able to visualise anything. And here is an even more extreme example with 500 nodes.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
描述了一种简单的方法，例如，在 http://en.wikipedia.org/ wiki/Force-based_algorithms_%28graph_drawing%29。 “简单性”的基本概念类似于“最小势能”，它在任何有用的意义上并不真正对应于简单性，但在实践中可能足够好。
（如果你有 100 个 40 度的节点，我有点怀疑绘制它们的任何方式是否会以人类可访问的结构的方式揭示很多内容。这是很多边缘。不过，祝你好运！）
One simple approach is described, e.g., at http://en.wikipedia.org/wiki/Force-based_algorithms_%28graph_drawing%29 . The underlying notion of "simplicity" is something like "minimal potential energy", which doesn't really correspond to simplicity in any useful sense but might be good enough in practice.
(If you have 100 nodes of degree 40, I have some doubt as to whether any way of drawing them is going to reveal much in the way of human-accessible structure. That's a lot of edges. Still, good luck!)