3
$\begingroup$

I'm looking for a way to position nodes on a 2-dimensional plane in such a way that the distances between the nodes, which are entered exogenously, are represented visually in a way that as good as possible communicates the logical distance between those nodes. Basically, I have a set of nodes A, B, C etc. and between some of them I have a distance: A is 10 from B, 20 from C etc. Some nodes are not connected at all. The distances are not internally geometrically consistent: A may be 10 from B, and 10 from C, but B and C may be 100 from each other.

I want to do this in a way that is 'stable' - i.e. generates the exact same layout each time the algorithm is run. Multi-dimensional scaling algorithms seem to be the way to go about this, but I'm having a hard time finding practical properties of the various MDS algorithms that exist, and the one I've tried is based on iterating from a random start position and therefore doesn't generate the same result every time. It also cannot handle not-connected nodes, afaik.

The practical application for this, and more detail on what I've tried, is described in this question: https://stackoverflow.com/questions/20263829/stable-multi-dimensional-scaling-algorithm

(Original post: I'm not sure what the etiquette is on this (repost question here or just link), but I asked a question on Stackoverflow that I was advised might fit better here. The question is here: https://stackoverflow.com/questions/20263829/stable-multi-dimensional-scaling-algorithm . I can repost here if that is the custom, but I thought I'd err on the side of fewest fragmentation and duplication. Thanks.)

$\endgroup$
  • 1
    $\begingroup$ It would get a lot more attention if you could restate it as an abstract computational problem. One other thing: is this a combinatorial problem? If not then make sure the tags are sufficiently relevant. $\endgroup$ – Parham Nov 28 '13 at 13:14
  • $\begingroup$ OK - I'm not sure if I'll succeed, but I'll try. $\endgroup$ – Roel Nov 28 '13 at 13:48
  • 1
    $\begingroup$ Regarding the question on Stack Overflow and here: we do ask not to post the same question on multiple sites, but in this case I think it makes sense to have a science side of the question here (choice of algorithm) and an engineering side on SO (looking for existing implementations). I strongly suggest that you link the CS version in your SO question and refer to CS for answers proposing an algorithm. $\endgroup$ – Gilles Nov 28 '13 at 14:09
  • 1
    $\begingroup$ One way to do this would be to imagine that your nodes are connected by flexible but inextensible rods, where the length of the rod is proportional to the distance between the nodes. Bending a rod generates a force that is something like inversely proportional to the radius of curvature. Figure out a stable configuration and use that as your layout, including the curved lines, which indicate the distance like a road map. Many, many implementation details left as an exercise! $\endgroup$ – David Richerby Nov 28 '13 at 14:27
  • 1
    $\begingroup$ @Roel flag your question, and request the mods move it. $\endgroup$ – Realz Slaw Nov 28 '13 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.