An Algorithm



next up previous contents
Next: Examples Up: Optimization Previous: Controlling the Location

An Algorithm

The general idea of the proposed algorithm is to place the structurally most important elements first and not to allow less important elements to change the locations assigned to more important elements. This reduces the amount of computations necessary to a considerable degree. While this works perfectly for data where no two nodes have the same structural importance, i.e. where there is a lot of structure in the empirical data , care has to be taken for less structured data: when there are ties in the rank orders of importance, it means that there are nodes that cannot be distinguished from each other.

  1. sort the all nodes of the graph according to their structural importance (your choice of criterion to represent structure)

  2. for all elements from most structurally important to least important do

  3. evaluate all admissible (not marked) locations in the model space for their minimal overall distance to those nodes to which there is a link

  4. assign the node under consideration to a position in the model space which has not been assigned (marked) yet and for which the sum of distances is minimal

  5. mark the position assigned as being taken

  6. repeat step (2-5) until all elements have been assigned

  7. unmark all nodes and repeat step(2-6) several times

In these cases the implementation of the algorithm should take care to assign the priority sequence randomly for each set of indistinguishable nodes for different iteration steps. If there is little or almost no structure in the data, the advantage in computing demands is entirely lost: one has no choice there but to evaluate all possible permutations of locations for an optimal solution.

Finally it should be pointed out that the algorithm uses only rankorders of the overall distances in the model space, which makes it quite robust to different designs of the solution space as long as these designs provide enough variation in the distances among all target locations.



next up previous contents
Next: Examples Up: Optimization Previous: Controlling the Location



Lothar Krempel
Fri Mar 31 13:14:02 MET DST 1995