Как построить матрицу смежности с использованием MATLAB

Question

Я хочу создать график, показывающий соединения между узлами из матрицы смежности, как показано ниже.

gplot кажется лучшим инструментом для этого. Однако, чтобы использовать его, мне нужно передать координату каждого узла. Проблема в том, что я не знаю, где должны быть координаты, я надеялся, что функция будет способна найти хороший макет для меня.

Например, вот мой выход, используя следующие произвольные координаты:

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-"); 

Что трудно читать, но если я буду играть вокруг с координатами немного и изменить их на следующие его становится намного читабельнее.

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

Я не ожидаю отлично оптимизированной координаты или что-нибудь, но как я могу сказать MATLAB автоматически выяснить набор координат для меня, что выглядит хорошо, используя какой-то algorithm, так что я могу нарисуйте что-то похожее на верхнее изображение.

Заранее спасибо.

Answer 1

Начиная с R2015b, MATLAB теперь имеет набор графиков и сетевых алгоритмов. Для этого примера, вы можете create an undirected graph object и затем построить его с помощью 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

Одним из способов было бы написать собственный алгоритм, используя какое-то электростатическое отталкивание, как в связанной с вами бумаге. Вероятно, можно сделать менее 40 строк Matlab (кажется, others have tried). Но иногда лучше использовать внешние инструменты, чем делать все в Matlab. Лучшим инструментом для рисования графиков является, вероятно, Graphviz, который поставляется с набором инструментов для рисования разных графиков стиля. Для неориентированных графов используется один из neato. Я не знаю, какой алгоритм он использует для распространения узлов, но я думаю, что это что-то похожее на те, что указаны в вашей статье (в одной из ссылок даже упоминается Graphviz!).

Входные данные для этих инструментов - очень простой текстовый формат, который достаточно легко создать с использованием Matlab. Пример (это работает на Linux, вы, возможно, придется изменить его немного на окнах):

% 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') 

что дает файлу test.dot:

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

и, наконец, изображение тест.PNG (обратите внимание, что ваша матрица смежности перечисляет соединения первого элемента с самим собой, который показывает, как петли в точке А):

В качестве более сложного примера можно прокладывать Баки-бол как в документации gplot:

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

с результатом (обратите внимание, что расположение делается Neato, он не использует XY):

Answer 3

Если граф связный, способ построения ху массива, чтобы перейти к gplot как у (:, [2 3]) где v - матрица собственных векторов матрицы Лапласа, упорядоченная от наименьших собственных значений до наибольших. Таким образом, мы можем сделать это следующим образом:

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

или так:

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

Второй должен быть более эффективным, особенно если большая.

Это создаст хороший участок при нормальных обстоятельствах. Это не гарантирует работу; в частности, не гарантировано назначать различным узлам разные координаты. Но обычно это работает очень красиво.

Некоторые теории за это можно найти на https://arxiv.org/pdf/1311.2492.pdf