How to graph adjacency matrix using MATLAB

Question

I want to create a plot showing connections between nodes from an adjacency matrix like the one below.

gplot seems like the best tool for this. However, in order to use it, I need to pass the coordinate of each node. The problem is that I don't know where the coordinates should be, I was hoping the function would be capable of figuring out a good layout for me.

For example here's my output using the following arbitrary coordinates:

 A = [1 1 0 0 1 0;
      1 0 1 0 1 0;
      0 1 0 1 0 0;
      0 0 1 0 1 1;
      1 1 0 1 0 0;
      0 0 0 1 0 0];

 crd = [0 1;
        1 1;
        2 1;
        0 2;
        1 2;
        2 2];

 gplot (A, crd, "o-");

Which is hard to read, but if I play around with the coordinates a bit and change them to the following it becomes much more readable.

   crd = [0.5 0;
         0 1;
         0 2;
         1 2;
         1 1;
         1.5 2.5];

I don't expect perfectly optimized coordinates or anything, but how can I tell MATLAB to automatically figure out a set of coordinates for me that looks okay using some sort of algorithm so I can graph something that looks like the top picture.

Thanks in advance.

Answer 1

As of R2015b, MATLAB now has a suite of graph and network algorithms. For this example, you can create an undirected graph object and then plot it using the overloaded plot function:

% Create symmetric adjacency matrix
A = [1 1 0 0 1 0;
     1 0 1 0 1 0;
     0 1 0 1 0 0;
     0 0 1 0 1 1;
     1 1 0 1 0 0;
     0 0 0 1 0 0];
% Create undirected graph object
G = graph(A);
% Plot
plot(G);

Answer 2

One way would be to write your own algorithm using some sort of electrostatic repulsion as in the paper you linked. Can probably be done in less than 40 lines of Matlab (it seems others have tried). But sometimes, it is better to use external tools than to do everything in Matlab. The best tool for drawing graphs is probably Graphviz, which comes with a suite of tools for drawing different style graphs. For undirected graphs, the one to use is neato. I don't know which algorithm it uses to distribute the nodes, but I guess it is something similar to the ones in your paper (one of the references even mentions Graphviz!).

The input for these tools is a very simple text format, which is easy enough to generate using Matlab. Example (this works on linux, you might have to change it a bit on windows):

% adjacency matrix
A = [1 1 0 0 1 0;
     1 0 1 0 1 0;
     0 1 0 1 0 0;
     0 0 1 0 1 1;
     1 1 0 1 0 0;
     0 0 0 1 0 0];

% node labels, these must be unique
nodes = {'A', 'B', 'C', 'D', 'E', 'F'};

n = length(nodes);
assert(all(size(A) == n))

% generate dot file for neato
fid = fopen('test.dot', 'w');
fprintf(fid, 'graph G {\n');
for i = 1:n
    for j = i:n
        if A(i, j)
            fprintf(fid, '    %s -- %s;\n', nodes{i}, nodes{j});
        end
    end
end
fprintf(fid, '}\n');
fclose(fid);

% render dot file
system('neato -Tpng test.dot -o test.png')

Which yields the file test.dot:

graph G {
    A -- A;
    A -- B;
    A -- E;
    B -- C;
    B -- E;
    C -- D;
    D -- E;
    D -- F;
}

and finally an image test.png (note that your adjacency matrix lists a connection of the first item with itself, which shows as the loop at node A):

As a more complex example, you could plot a bucky-ball as in the documentation of gplot:

[A, XY] = bucky;
nodes = arrayfun(@(i) num2str(i), 1:size(A,1), 'uni', 0);

with result (note that the layout is done by neato, it does not use XY):

Answer 3

If your graph is connected, a way to construct the array xy to pass to gplot is as v(:,[2 3]) where v is the matrix of eigenvectors of the Laplacian matrix, ordered from smallest eigenvalues to largest. So we can do it this way:

L=diag(sum(A))-A;
[v,~]=eig(L);
xy=v(:,[2 3])
gplot(A,xy)

or this way:

L=diag(sum(A))-A;
[v,~]=eigs(L,3,'SM')
xy=v(:,[2 1])
gplot(A,xy)

The second one should be more efficient, especially if A is big.

This will create a nice plot under normal circumstances. This is not guaranteed to work; in particular, it is not guaranteed to assign different nodes different coordinates. But usually it works pretty nicely.

Some theory behind this can be found at https://arxiv.org/pdf/1311.2492.pdf