Rearrange a dense distance matrix to a 2x2 non-perfect block diagonal form

Question

I have a distance matrix (square, symmetrical, non-negative, dense). I want to split the objects into two well-connected groups. Mathematically speaking, I want to group (re-arrange) the rows/columns so that when the matrix is viewed as a 2x2 block-diagonal matrix, the diagonal blocks are "close to zero".

Again: Given an square matrix $M$ of size $N$ I want to find a rearranged matrix $M'$ and a division point $k: 1 < k < N$ such that $norm(M_{1..k,1..k})$ and $norm(M_{k+1..N,k+1..N})$ are minimized (where $norm$ is sum, max, sum of squares or some other norm).

P.S. My ultimate goal is to extract a hierarchy of well-connected components from a complete graph.

Answer 1

It sounds like you're looking for a Min-cut of the graph. There is a lot of literature on the subject. You can repeated apply Min-cuts until you have a hierarchy of well connected components.

Answer 2

I have encountered a very similar situation, although in a different field. When dealing with sparse matrices, there are few cases where the elements are present only on the diagonals / in bands around the diagonals. They can be stored very efficiently by just storing the diagonal information and very efficient algorithms can be designed. But, there are cases where the sparse-matrix may not be in the diagonal form. But, we can apply some transformations to the Adjacency matrix (matrix has entry 1 if the position has a non-zero entry, else 0). This is a square, symmetric, non-zero, possibly dense matrix, which we want to transform into a block diagonal form, which is exactly what you want to do. The standard algorithm I know of to do the job is called the Cuthill Mckee algorithm. This algorithm intuitively follows the breadth-first search algorithm. The choice of the first element is crucial and the result of the algorithm is heuristic based on the ordering of the neighbors. In typical cases, the Reversed Cuthill Mckee algorithm gives slightly better results. I hope that helps.