Submission 127: A Maxent-Stress Model for Graph Layout

maxent: a model that tries to minimize the sparse stress, and satisfy the remaining degrees of freedom by maximizing the "entropy" of the vertex set.

pmds(k): PivotMDS, followed by minimizing the sparse stress of all vertex pairs of distance ≤ k hops (Brandes and Pich, 2006).

Minimizing the sparse stress and maximizing the entropy makes the maxent algorithm less likely to place multiple vertices at the same location. At the same time, the algorithm still minimizes the difference between the actual and targeted edge length. The advantage of the maxent algorithm is most evident for non-rigid graphs. For mesh-like rigid graphs, PivotMDS alone is often sufficiently good.