[PYTHON] Hinter dem Graph Drawing Algorithmus und Networkx
0. Wie zeichnet man ein Diagramm?
Um in zwei Dimensionen zeichnen zu können, müssen jedem Scheitelpunkt geeignete Koordinaten zugewiesen werden. Der Graph enthält jedoch nur die Informationen des Scheitelpunkts und der Kante. Wie ordnen Sie die Eckpunkte an? ??
Dieser Artikel beschreibt den ** Fruchterman-Reingold-Algorithmus **, der Grafiken gut anordnet. In Python können Sie es problemlos mit einer Bibliothek namens "networkx" verwenden. Es ist jedoch zu einfach und frustrierend, daher werde ich die Implementierung von GitHub von networkx verfolgen und den Mechanismus überprüfen.
Der Ablauf dieses Artikels ist wie folgt.
- Versuchen Sie sich zu bewegen
- Erläuterung des Algorithmus
- Folgen Sie der Implementierung von Networkx
1. Versuchen Sie sich zu bewegen
Für diejenigen, die zufrieden sind, wenn es funktioniert, werde ich zuerst ein Implementierungsbeispiel zeigen. In Google Colaboratory ist networkx bereits installiert, sodass Sie es sofort durch Kopieren ausprobieren können.
Zufällig angeordnet → random_layout ()
import networkx as nx
import matplotlib.pyplot as plt
N = 500 #Anzahl der Eckpunkte
K = 5
P = 0.05
G = nx.watts_strogatz_graph(N,K,P) #Entsprechende Grafik
pos = nx.random_layout(G, seed=0)
#Zeichnen Sie ein Diagramm
plt.figure(figsize=(15,15))
nx.draw_networkx(G, pos, with_labels=False, node_shape='.')
plt.axis("off")
plt.show()
Beeindruckend…. will nicht sehen….
Es ist unerträglich, in einer zufälligen Anordnung zu sehen.
Schön arrangiert → spring_layout ()
import networkx as nx
import matplotlib.pyplot as plt
N = 500 #Anzahl der Eckpunkte
K = 5
P = 0.05
G = nx.watts_strogatz_graph(N,K,P)
pos = nx.spring_layout(G)
#Zeichnen Sie ein Diagramm
plt.figure(figsize=(15,15))
nx.draw_networkx(G, pos, with_labels=False, node_shape='.')
plt.axis("off")
plt.show()
Es ist schön arrangiert.
Was ist ein "gutes Arrangement"?
Denken Sie etwas strenger über "gute Platzierung" nach. Angenommen, Sie haben jetzt die folgenden Informationen für das Diagramm $ G $.
Es gibt unzählige Möglichkeiten, dieses Diagramm in zwei Dimensionen anzuordnen. (Sie können sie wie zuvor zufällig anordnen.) Wenn möglich, möchte ich sie jedoch so anordnen, dass sie leicht zu sehen sind. Nennen wir ein Arrangement, das die folgenden Bedingungen erfüllt, ein "gutes Arrangement".
① Die Verbindungsbeziehung der Seiten spiegelt sich in der Entfernung wider
Mit anderen Worten, ** durch Seiten verbundene Punkte sollten nahe beieinander platziert werden, und Punkte, die nicht durch Seiten verbunden sind, sollten weit entfernt platziert werden **. Im Fall einer benachbarten Matrix wird der nicht verbundene Teil auf "inf" gesetzt, so dass anscheinend alle Punkte unabhängig vom Vorhandensein oder Fehlen von Kanten auf dieselbe Weise behandelt werden können.
➁ Oberteile überlappen sich nicht
Wenn sich die Scheitelpunkte überlappen, können Sie die Seiten nicht sehen, was ein Problem darstellt.
Ich möchte ein Diagrammlayout finden, das die beiden oben genannten Bedingungen erfüllt. Das ** mechanische Modell (kraftorientierter Graph) ** macht dies möglich.
Und im vorherigen networkx.spring_layout () wird der ** Fruchterman-Reingold-Algorithmus ** verwendet. Dieses Mal werde ich dies vorstellen. Schauen Sie sich das GIF unten an, um sich ein Bild von dieser Technik zu machen.
Ab der zufälligen Erstplatzierung wird es allmählich sauberer! !! ([Von hier entlehnt] Kommentarartikel zum mechanischen Modell)
Möchten Sie den Algorithmus kennenlernen?(y/n)
y
Lass es uns wissen.
2.Fruchterman-Reingold algorithm
Macht definieren
Im dynamischen Modell wird eine Kraft auf die Spitze ausgeübt, um sie zu bewegen. Der Fruchterman-Reingold-Algorithmus gibt Ihnen ** Anziehungskraft ** und ** Abstoßungskraft **.
Die Gravitationskraft wirkt auf die durch die Seiten verbundenen Eckpunkte. Andererseits wirkt die Abstoßungskraft auf Eckpunkte, die nicht durch Seiten verbunden sind. Dies entspricht der vorherigen Bedingung (1) "Die Verbindungsbeziehung der Seiten spiegelt sich in der Entfernung wider".
Sie können die Leistung auf beliebige Weise definieren, aber verwenden wir zunächst die im Dokument vorgeschlagene Definition.
Anziehung: $ f_a = \ dfrac {d ^ 2} {k} $ Abstoßung: $ f_r = - \ dfrac {k ^ 2} {d} $
$ d $: Abstand zwischen Eckpunkten
Es ist wie eine Frühlingsformel und intuitiv. Das Diagramm der Beziehung zwischen Kraft und Abstand ist wie folgt.
Die Grafiken und Formeln zeigen Folgendes:
- Je weiter die Anziehungskraft ist, desto stärker wirkt sie
- Je näher die Abstoßungskraft ist, desto stärker wirkt sie.
- Anziehungskraft und Abstoßungskraft werden in einem bestimmten Abstand $ k $ gleich
Wenn der Abstand $ k $, bei dem die Kräfte antagonisieren, auf eine geeignete Größe eingestellt ist, kann die obige Bedingung tops "Spitzen überlappen sich nicht" erfüllt werden.
Algorithmus
Schauen wir uns nun den Algorithmus an.
- Anfangs zufällig platzieren
- Berechnen Sie die Anziehungs- und Abstoßungskräfte für jeden Scheitelpunkt
- Bewegen Sie die Eckpunkte entsprechend der Kraft. Verlassen Sie den Rahmen jedoch nicht.
- Senken Sie die Temperatur $ t $
- Wiederholen Sie die Schritte 2 bis 4 einige Male
Ich bekomme eine unbekannte Variable $ t $. Die Temperatur $ t $ ist ein Parameter, der die Bewegung der Eckpunkte begrenzt. Mit anderen Worten, der Bewegungsbetrag sollte in Bezug auf den in Schritt 2 berechneten Bewegungsrichtungsvektor (sagen wir $ v $) $ t $ oder weniger betragen.
Wir werden diese Temperatur angemessen reduzieren. Obwohl sich die Bewegungsmenge am Anfang groß ist, wird sie sich am Ende nicht viel bewegen. (Garantiert Konvergenz)
In dem Papier wird in Schritt 3 die Kollision mit der Wand als elastische Reflexion behandelt, um sie auf dem Bildschirm zu platzieren. Wenn Sie mehr darüber erfahren möchten, lesen Sie bitte [Originalpapier "Diagrammzeichnung durch erzwungene Platzierung"] Papier. (Wird bei der Implementierung von networkx nicht berücksichtigt ...)
~~ Nachdem wir den Algorithmus kennen, implementieren wir ihn. ~~ ↑ Es ist ärgerlich, also überlasse ich die Implementierung dem Leser.
In diesem Artikel werden wir uns ansehen, wie man networkx implementiert, ohne die Räder neu zu erfinden.
3. Sehen Sie sich die Networkx-Implementierung an
Lassen Sie uns lernen, indem wir die menschliche Umsetzung sehen. Zu diesem Zeitpunkt ist jedoch NetworkX 2.4 dasjenige, und die Teile, die die Ausnahmebehandlung usw. nicht erklären, werden weggelassen.
Zu Beginn des Artikels habe ich networkx.spring_layout () verwendet, um das Diagramm "gut" zu zeichnen. Wenn Sie sich GitHub ansehen,
spring_layout = fruchterman_reingold_layout
Ich beziehe mich nur darauf! Schauen wir uns als nächstes das Referenzziel fruchterman_reingold_layout an.
def fruchterman_reingold_layout(G,
k=None,
pos=None,
#Kürzung
seed=None):
"""Langer Docstring
"""
import numpy as np
G, center = _process_params(G, center, dim)
"""
Verschiedene initialisierte Teile (weggelassen)
"""
"""
Von hier an ist unten wichtig
"""
try:
# Sparse matrix
if len(G) < 500: # sparse solver for large graphs
raise ValueError
A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='f')
if k is None and fixed is not None:
# We must adjust k by domain size for layouts not near 1x1
nnodes, _ = A.shape
k = dom_size / np.sqrt(nnodes)
pos = _sparse_fruchterman_reingold(A, k, pos_arr, fixed,
iterations, threshold,
dim, seed)
except ValueError:
A = nx.to_numpy_array(G, weight=weight)
if k is None and fixed is not None:
# We must adjust k by domain size for layouts not near 1x1
nnodes, _ = A.shape
k = dom_size / np.sqrt(nnodes)
pos = _fruchterman_reingold(A, k, pos_arr, fixed, iterations,
threshold, dim, seed)
if fixed is None and scale is not None:
pos = rescale_layout(pos, scale=scale) + center
pos = dict(zip(G, pos))
return pos
Im Teil "Try-Except" werden die aufzurufenden Funktionen entsprechend der Größe des Diagramms unterteilt. (Ist die if-Anweisung nicht nutzlos ...? Bitte sag es mir.)
Rufen Sie _fruchterman_reingold () an, wenn $ Anzahl der Eckpunkte <500 $ ist
- $ Anzahl der Eckpunkte \ geq 500 $, rufen Sie
_sparse_fruchterman_reingold ()auf
** Wenn Sie viele Eckpunkte haben, verwenden Sie anscheinend einen Sparse-Solver. ** Wir haben den Algorithmus-Teil noch nicht erreicht, also schauen wir uns _fruchterman_reingold () an.
def _fruchterman_reingold(A, k=None, pos=None, fixed=None,
iterations=50, threshold=1e-4, dim=2,
seed=None):
# Position nodes in adjacency matrix A using Fruchterman-Reingold
# Entry point for NetworkX graph is fruchterman_reingold_layout()
# Sparse version
import numpy as np
if pos is None:
# random initial positions
pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)
else:
# make sure positions are of same type as matrix
pos = pos.astype(A.dtype)
# optimal distance between nodes
if k is None:
k = np.sqrt(1.0 / nnodes)
# the initial "temperature" is about .1 of domain area (=1x1)
# this is the largest step allowed in the dynamics.
t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1
# simple cooling scheme.
# linearly step down by dt on each iteration so last iteration is size dt.
dt = t / float(iterations + 1)
displacement = np.zeros((dim, nnodes))
for iteration in range(iterations):
displacement *= 0
# loop over rows
for i in range(A.shape[0]):
if i in fixed:
continue
# difference between this row's node position and all others
delta = (pos[i] - pos).T
# distance between points
distance = np.sqrt((delta**2).sum(axis=0))
# enforce minimum distance of 0.01
distance = np.where(distance < 0.01, 0.01, distance)
# the adjacency matrix row
Ai = np.asarray(A.getrowview(i).toarray())
# displacement "force"
displacement[:, i] +=\
(delta * (k * k / distance**2 - Ai * distance / k)).sum(axis=1)
# update positions
length = np.sqrt((displacement**2).sum(axis=0))
length = np.where(length < 0.01, 0.1, length)
delta_pos = (displacement * t / length).T
pos += delta_pos
# cool temperature
t -= dt
err = np.linalg.norm(delta_pos) / nnodes
if err < threshold:
break
return pos
Dies ist der Implementierungsteil des Algorithmus. Ich werde zusammenfassen, wie man mit Anziehungskraft und Abstoßungskraft umgeht.
-Optimaler Abstand zwischen den Kabeln:
- Punkt-zu-Punkt-Abstand: $ \ text {distance} = \ max (\ text {distance}, 0.01) $ --Point-Wert der benachbarten Punktematrix: $ A_i $ --Temperatur $ t $: $ \ max (\ text {Breite des Definitionsbereichs der anfänglichen Platzierung}, \ text {Breite des Wertebereichs der anfänglichen Platzierung}) * 0,01 $
- So senken Sie die Temperatur:
t- = dt, aber $ dt = \ dfrac {t} {\ text {iteration} + 1} $ - Richtungsvektor: $ \ text {delta} $
- Anziehungskraft: $ f_a = \ dfrac {k ^ 2} {\ text {distance} ^ 2} $ --Repulsive Kraft: $ f_r = --A_i * \ dfrac {\ text {distance}} {k} $
Die optimale Abstandsformel lautet $ C = 1, \ text {area} = 1 $, wenn sie auf das Papier angewendet wird. Einfach! Die Temperatur $ t $ wird zunächst signifikant abnehmen und mit fortschreitender "Iteration" allmählich abnehmen. $ \ Text {delta} $ ist kein Richtungsvektor, aber ich habe ihn geschrieben, weil ich am Ende die Norm anpasse.
Was sehr besorgniserregend ist, ist die Definition von Macht. ** Sowohl anziehende als auch abstoßende Kräfte unterscheiden sich von denen im Papier. ** Gibt es danach eine verbesserte Version, da das Papier von 1991 stammt? Ein weiterer Befund ist, dass bei gewichteten Graphen die Abstoßungskraft mit dem Wert der benachbarten Matrix multipliziert werden sollte.
Wenn Sie versuchen, es selbst zu implementieren, ist es meiner Meinung nach besser, es mit denselben Einstellungen zu implementieren.
Bonus
Ich habe versucht, das Verhalten des Algorithmus zu visualisieren, indem ich ein wenig mit dem Quellcode gespielt habe. (Ich habe 200 Iterationen durchgeführt, indem ich die Parameter angepasst habe.)
Es ist interessant, dass die Stücke unzusammenhängender Punkte allmählich wie Fäden werden. Ich habe etwas in der Nähe der Referenzseite "[Algorithmus zum schönen Zeichnen von Graphen (Netzwerken)] [Artikel zum Kommentar eines mechanischen Modells]" fast ohne eigene Implementierung. Du hast es geschafft.
Zusammenfassung
Ich erklärte den ** Fruchterman-Reingold-Algorithmus **, einen Algorithmus zum Zeichnen von Graphen, um einen Blick hinter die Kulissen von networkx zu werfen, der die Handhabung von Graphen vereinfacht. Sobald Sie den Algorithmus gelernt haben, ist es wichtig, ihn auszuprobieren, aber die Implementierung einer starken Person zu sehen, ist auch eine Lernerfahrung. Wir freuen uns auf Ihre Fragen und Anregungen.
Verweise
[Algorithmus zum schönen Zeichnen von Graphen (Netzwerken)] Kommentarartikel zum mechanischen Modell : Ein wirklich guter Artikel!
[Graphzeichnung durch kraftgerichtete Platzierung, 1992] Papier : Fruchterman und Reingolds Papier
networkx GitHub : Was ich diesmal ein wenig erklärt habe
[Mechanisches Modell (Wikipedia)] [Mechanisches Modell_Wiki] : Ich möchte andere Methoden sehen
[[Python] Zusammenfassung der grundlegenden Verwendung von NetworkX 2.0 Qiita] [Netzwerkx2-Verwendung Qiita] : Leicht verständliche Artikel
Recommended Posts