How to map adjacency matrix using MATLAB

Question

I want to create a graph showing the connections between nodes from an adjacency matrix, as shown below.

gplot seems to be the best tool for this. However, 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 able to find a good layout for me.

For example, here my output uses 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-"); 

It's hard to read, but if I play around a bit with the coordinates and change them to the next, it will become more readable.

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

I do not expect ideally optimized coordinates or anything else, but how can I tell MATLAB to automatically determine the coordinate set for me, which looks fine, using some so I can draw something similar to the top image.

Thanks in advance.

Answer 1

Starting with R2015b, MATLAB now has a set of graphs and network algorithms. In this example, you can create an undirected graph object and then build 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 is to write your own algorithm using some kind of electrostatic repulsion, as in the paper associated with you. Perhaps it is possible to make Matlab in less than 40 lines (it seems others have tried ). But sometimes it's better to use external tools than do everything in Matlab. The best tool for drawing graphs is probably Graphviz , which comes with a set of tools for drawing different style graphs. For undirected graphs, one of them is neato . I don’t know what algorithm it uses to distribute nodes, but I think it is something similar to the ones that are indicated in your article (one of the links even mentions Graphviz!).

The input for these tools is a very simple text format that is fairly easy to create with Matlab. Example (this works on Linux, you may 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') 

What the test.dot file gives :

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

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

As a more complex example, you can draw a bucky-ball, as in the gplot documentation:

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

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

Answer 3

If your graph is connected, the way to build the xy array to go to gplot is v (:, [2 3]), where v is the matrix of eigenvectors of the Laplace matrix, ordered from the smallest eigenvalues ​​to the largest. Therefore, we can do it as follows:

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

or as follows:

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

The second should be more effective, especially if A is large.

This will create a good story under normal circumstances. This does not guarantee work; in particular, it is not guaranteed to assign different coordinates to different nodes. But usually it works very nicely.

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