[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.

  1. Versuchen Sie sich zu bewegen
  2. Erläuterung des Algorithmus
  3. 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()

random.png 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()

nx_spring.png

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 $.

G = (V, E) $ V $: Satz von Eckpunkten $ E $: Kantensatz

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.

力学モデル.gif 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 **.

fa_vs_fr.jpg

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 k = C \sqrt{\dfrac{\text{area}}{|V|}}, C \in \mathbb{R} ,\ \ \text{area}Ist der Bereich des Bildschirms zu zeichnen

Es ist wie eine Frühlingsformel und intuitiv. Das Diagramm der Beziehung zwischen Kraft und Abstand ist wie folgt.

力学モデル_force_vs_distance.jpg Die Grafiken und Formeln zeigen Folgendes:

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.

  1. Anfangs zufällig platzieren
  2. Berechnen Sie die Anziehungs- und Abstoßungskräfte für jeden Scheitelpunkt
  3. Bewegen Sie die Eckpunkte entsprechend der Kraft. Verlassen Sie den Rahmen jedoch nicht.
  4. Senken Sie die Temperatur $ t $
  5. 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.

v = \dfrac{v}{\| v\|} * \min(\| v\|, t)

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

** 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:k = \sqrt{\dfrac{1}{|V|}}

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.) anim_iter200 (1).gif 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

Hinter dem Graph Drawing Algorithmus und Networkx
wxPython: Gleichzeitiges Zeichnen von Animationen und Grafiken
Verständnis und Implementierung des Tonelli-Shanks-Algorithmus (2)
Verständnis und Implementierung des Tonelli-Shanks-Algorithmus (1)
Berechnen Sie die kürzeste Route eines Diagramms mit der Dyxtra-Methode und Python
Verwendung der Grafikzeichnungsbibliothek Bokeh
Erstellen Sie ein Diagramm mit der Plot-Schaltfläche und dem Schieberegler
Euklidische Methode der gegenseitigen Teilung und erweiterte Methode der euklidischen gegenseitigen Teilung
NetworkX-Memo (gerichtete Grafik)
Diagrammzeichnung mit matplotlib
Diagrammzeichnung mit Python
NetworkX-Grafikgeneratorliste
Kaninchen- und Schildkrötenalgorithmus
Löse das Spiralbuch (Algorithmus und Datenstruktur) mit Python!
Zeichnen wir ein Diagramm der Poisson-Verteilung und der kumulativen Poisson-Verteilung in Python bzw. Java.