AT&T Labs Research, Florham Park, NJ 07932, USA.
IEEE Trans Vis Comput Graph. 2013 Jun;19(6):927-40. doi: 10.1109/TVCG.2012.299.
In some applications of graph visualization, input edges have associated target lengths. Dealing with these lengths is a challenge, especially for large graphs. Stress models are often employed in this situation. However, the traditional full stress model is not scalable due to its reliance on an initial all-pairs shortest path calculation. A number of fast approximation algorithms have been proposed. While they work well for some graphs, the results are less satisfactory on graphs of intrinsically high dimension, because some nodes may be placed too close together, or even share the same position. We propose a solution, called the maxent-stress model, which applies the principle of maximum entropy to cope with the extra degrees of freedom. We describe a force-augmented stress majorization algorithm that solves the maxent-stress model. Numerical results show that the algorithm scales well, and provides acceptable layouts for large, nonrigid graphs. This also has potential applications to scalable algorithms for statistical multidimensional scaling (MDS) with variable distances.
在图可视化的某些应用中，输入边具有相关的目标长度。处理这些长度是一个挑战，特别是对于大型图。在这种情况下，通常使用应力模型。然而，由于传统的全应力模型依赖于初始的所有对最短路径计算，因此它不可扩展。已经提出了许多快速近似算法。虽然它们在某些图上效果很好，但在本质上维度较高的图上，结果不太令人满意，因为某些节点可能彼此太靠近，甚至共享相同的位置。我们提出了一种解决方案，称为最大熵应力模型，它应用最大熵原理来处理额外的自由度。我们描述了一种力增强的应力最大化算法，用于解决最大熵应力模型。数值结果表明，该算法具有良好的扩展性，并为大型非刚性图提供了可接受的布局。这也有可能应用于具有可变距离的统计多维尺度（MDS）的可扩展算法。
