Sort list based on pair-wise affiliation of its elements

Question

Given a list of elements, say [1,2,3,4], and their pair-wise affiliation, 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 such that the distance in the list best correlates with the pair-wise affiliation, i.e. pairs of nodes with high affiliation should be close to each other.

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

As a bonus question:

Note that some pair-wise affiliations can be represented perfectly, like for the list [1,2,3] and a pair-wise affiliation:

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

the perfect order would be [1,3,2]. But some affiliations can't, like this one:

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

where any order is equally good/bad.

Is there a way to tell the quality of an ordering? In the sense of how well it represents the pair-wise affiliations?

Answer 1

Here's a lightly tested algorithm that takes the adjacency matrix, sets up the elements/nodes in order of appearance, then tries to find an equilibrium. Since it's 1d I just picked a really simple attractive-force formula. Maybe adding repulsive force would 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]