Reshuffling the adjacency matrix of an undirected random graph based on connectivity

Question

I have a nxn adjacency matrix A of an undirected random graph, so Aij can be either 0 or 1. If Aij is 1 that means there is an edge between ith and jth node. If it is 0 that means there is no edge between them.

I want to reshuffle the matrix based the degree of the vertices. All the vertices which have degree less than equal to k, I want to put them at the end. Let say there are m such vertices, so last m rows and columns of my new adjacency matrix will represent these vertices.

I want to implement this in MATLAB. I have no idea how to solve it efficiently. Just one think I know how to find such vertices.

a = 1:n;
ver = a(sum(A) < k+1 );

Any help is appreciated.

Answer 1

Since your graph is undirected, your adjacency matrix A is symmetric. As you already noted you can tell the degree of the vertices simply by summing the rows (or columns) of A:

deg = sum(A, 2);

Now you can sort the vertices based on their degree

[sd si] = sort(deg, 'decrease'); %// sort in a decreasing order

You can use the sorted indices (si) to re-arrange A:

A = A(si,si);

Note that you MUST apply the same permutation to both rows and columns of A, otherwise...

Now that your graph is ordered by the degree of vertices the once with smaller degree would naturally be at the end of A.