A sort list based on the mutual binding of its elements

Question

Given the list of elements, let's say [1,2,3,4] , and their pair affiliation, let's say

 [[0, 0.5, 1, 0.1] [0.5, 0, 1, 0.9] [ 1, 1, 0, 0.2] [0.1, 0.9, 0.2, 0]] 

For those familiar with graph theory, this is basically an adjacency matrix.

What is the fastest way to sort the list so that the distance in the list is best correlated with the pair affiliation, i.e. pairs of nodes with high affinity should be close to each other.

Is there a way to do this (even a greedy algorithm will be fine) without going into MDS and ordination theory?

As a bonus question:

Note that some pair relations can be represented ideally, as for the list [1,2,3] and pair affiliation:

 [[0, 0, 1] [0, 0, 1] [1, 1, 0]] 

perfect order will be [1,3,2] . But some branches cannot, like this one:

 [[0, 1, 1] [1, 0, 1] [1, 1, 0]] 

where any order is equally good / bad.

Is there any way to talk about the quality of the order? In terms of how well does he represent affiliate affiliation?

Answer 1

Here, a slightly tested algorithm that takes an adjacency matrix sets the elements / nodes in the order of appearance, and then tries to find equilibrium. Since I just chose a very simple formula for the gravitational force formula. Perhaps the addition of a repulsive force will improve it.

 /* * Sort the nodes of an adjacency matrix * @return {Array<number>} sorted list of node indices */ function sort1d(mat) { var n = mat.length; // equilibrium total force threshold var threshold = 1 / (n * n); var map = new Map(); // <index, position> // initial positions for(var i = 0; i < n; i++) { map.set(i, i); } // find an equilibrium (local minima) var prevTotalForce; var totalForce = n * n; do { prevTotalForce = totalForce; totalForce = 0; for(var i = 0; i < n; i++) { var posi = map.get(i); var force = 0; for(var j = i + 1; j < n; j++) { var posj = map.get(j); var weight = mat[i][j]; var delta = posj - posi; force += weight * (delta / n); } // force = Sum[i, j=i+1..n]( W_ij * ( D_ij / n ) map.set(i, posi + force); totalForce += force; } console.log(totalForce, prevTotalForce); } while(totalForce < prevTotalForce && totalForce >= threshold); var list = []; // Map to List<[position, index]> map.forEach(function(v, k) { list.push([v, k]); }); // sort list by position list.sort(function(a, b) { return a[0] - b[0]; }); // return sorted indices return list.map(function(vk) { return vk[1]; }); } var mat = [ [0, 0.5, 1, 0.1], [0.5, 0, 1, 0.9], [1, 1, 0, 0.2], [0.1, 0.9, 0.2, 0] ]; var mat2 = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ]; console.log(sort1d(mat)); // [2, 0, 1, 3] console.log(sort1d(mat2)); // [0, 1, 2]