Wie wird die Adjazenzmatrix mit MATLAB

Question

graphisch dargestellt? Ich möchte ein Diagramm erstellen, das Verbindungen zwischen Knoten aus einer Adjazenzmatrix wie der folgenden zeigt.

gplot scheint das beste Werkzeug. Um es zu verwenden, muss ich jedoch die Koordinaten jedes Knotens übergeben. Das Problem ist, dass ich nicht weiß, wo die Koordinaten sein sollten, ich hatte gehofft, dass die Funktion in der Lage wäre, ein gutes Layout für mich herauszufinden.

Zum Beispiel ist hier meine Ausgabe folgende beliebige Koordinaten:

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

Welche schwer zu lesen ist, aber wenn ich spielen, um mit den etwas Koordinaten und sie es folgende, um die Änderung wird viel lesbarer.

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

Ich erwarte nicht perfekt optimiert Koordinaten oder so, aber wie kann ich MATLAB sagen, um automatisch einen Satz von Koordinaten für mich herausfinden, dass eine Art mit algorithm sieht okay so kann ich Grafik etwas, das wie das obere Bild aussieht.

Vielen Dank im Voraus.

Answer 1

Ab R2015b verfügt MATLAB jetzt über eine Reihe von Grafik- und Netzwerkalgorithmen. Für dieses Beispiel können Sie create an undirected graph object und dann zeichnen sie die overloaded plot function mit:

% 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

Ein Weg wäre, Ihren eigenen Algorithmus mit einer Art elektrostatischer Abstoßung zu schreiben, wie in dem von Ihnen verlinkten Papier. Kann wahrscheinlich in weniger als 40 Zeilen Matlab gemacht werden (es scheint others have tried). Aber manchmal ist es besser, externe Tools zu verwenden, als alles in Matlab zu tun. Das beste Werkzeug zum Zeichnen von Graphen ist wahrscheinlich Graphviz, das mit einer Reihe von Werkzeugen zum Zeichnen verschiedener Stildiagramme ausgestattet ist. Für ungerichtete Graphen ist der zu verwendende Graph neato. Ich weiß nicht, welchen Algorithmus es verwendet, um die Knoten zu verteilen, aber ich denke, es ist etwas ähnlich zu dem in Ihrem Papier (eine der Referenzen erwähnt sogar Graphviz!).

Die Eingabe für diese Werkzeuge ist ein sehr einfaches Textformat, das einfach mit Matlab erzeugt werden kann. Beispiel (dies funktioniert auf Linux, könnte man es ein bisschen auf Fenster ändern müssen):

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

die die Datei test.dot ergibt:

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

und schließlich ein Bild Test.png (beachten Sie, dass Ihre Adjazenzmatrix eine Verbindung des ersten Elements mit sich führt, die als Schleife am Knoten A zeigt):

Als komplexeres Beispiel, könnten Sie eine Bucky-Ball plotten wie in der Dokumentation von gplot:

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

mit Ergebnis (beachten sie, dass das Layout von neato getan wird, verwendet sie nicht XY):

Answer 3

Wenn Ihr Graph verbunden ist, eine Möglichkeit, die Anordnung xy zu konstruieren, um gplot zu Pass ist als v (:, [2 3]) Dabei ist v die Matrix der Eigenvektoren der Laplace-Matrix, geordnet von kleinsten Eigenwerten zum größten. So können wir es auf diese Weise tun:

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

oder so:

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

Die zweite sollte effizienter sein, vor allem, wenn ein großer ist.

Dies wird unter normalen Umständen eine schöne Handlung erstellen. Dies funktioniert nicht garantiert; insbesondere ist es nicht garantiert, verschiedenen Knoten unterschiedliche Koordinaten zuzuordnen. Aber normalerweise funktioniert es ziemlich gut.

Einige Theorie dahinter können https://arxiv.org/pdf/1311.2492.pdf