0. Comment dessinez-vous un graphique?

Afin de dessiner en deux dimensions, il est nécessaire de donner les coordonnées appropriées à chaque sommet, mais le graphe n'a que les informations du sommet et de l'arête. Comment arrangez-vous les sommets? ??

Cet article décrit ** l'algorithme de Fruchterman-Reingold **, qui organise bien les graphiques. En Python, vous pouvez facilement l'utiliser avec une bibliothèque appelée networkx. Cependant, c'est trop facile et frustrant, donc je vais suivre l'implémentation de GitHub de networkx et vérifier le mécanisme.

Le flux de cet article est le suivant.

Essayez de bouger
Explication de l'algorithme
Suivez la mise en œuvre de Networkx

1. Essayez de bouger

Pour ceux qui sont satisfaits si cela fonctionne, je montrerai d'abord un exemple de mise en œuvre. Avec Google colaboratory, networkx est déjà installé, vous pouvez donc l'essayer immédiatement en copiant.

Arrangé au hasard → random_layout ()

import networkx as nx
import matplotlib.pyplot as plt

N = 500 #Nombre de sommets
K = 5
P = 0.05

G = nx.watts_strogatz_graph(N,K,P) #Graphique approprié
pos = nx.random_layout(G, seed=0)

#Dessinez un graphique
plt.figure(figsize=(15,15))
nx.draw_networkx(G, pos, with_labels=False, node_shape='.')
plt.axis("off")
plt.show()

Sensationnel…. ne veux pas voir…. C'est insupportable de voir dans un arrangement aléatoire.

Bien arrangé → spring_layout ()

import networkx as nx
import matplotlib.pyplot as plt

N = 500 #Nombre de sommets
K = 5
P = 0.05

G = nx.watts_strogatz_graph(N,K,P)
pos = nx.spring_layout(G)

#Dessinez un graphique
plt.figure(figsize=(15,15))
nx.draw_networkx(G, pos, with_labels=False, node_shape='.')
plt.axis("off")
plt.show()

C'est bien arrangé.

Qu'est-ce qu'un «bon arrangement»?

Pensez un peu plus strictement au «bon placement». Par exemple, supposons que vous ayez maintenant les informations pour le graphique $ G $ comme suit.

G = (V, E) $ V $: Ensemble de sommets $ E $: Ensemble de bord

Il existe d'innombrables façons d'organiser ce graphique en deux dimensions. (Vous pouvez les organiser au hasard comme auparavant.) Cependant, si possible, je veux les organiser de manière à ce qu'ils soient faciles à voir. Appelons un arrangement qui remplit les conditions suivantes un «bon arrangement».

① La relation de connexion des côtés se reflète dans la distance

En d'autres termes, ** les points connectés par les côtés doivent être placés à proximité les uns des autres, et les points non connectés par les côtés doivent être placés loin **. Dans le cas d'une matrice adjacente, la partie non connectée est mise à «inf», il semble donc que tous les points peuvent être traités de la même manière indépendamment de la présence ou de l'absence d'arêtes.

➁ Les hauts ne se chevauchent pas

Si les sommets se chevauchent, vous ne pouvez pas voir les côtés, ce qui pose problème.

Je voudrais trouver une mise en page graphique qui satisfait aux deux conditions ci-dessus. Le ** modèle mécanique (graphe orienté force) ** rend cela possible.

Et dans le précédent networkx.spring_layout (), ** l'algorithme de Fruchterman-Reingold ** est utilisé. Cette fois, je vais vous présenter ceci. Jetez un œil au gif ci-dessous pour avoir une idée de cette technique.

力学モデル.gif À partir du placement initial aléatoire, il deviendra progressivement plus propre! !! ([Emprunté ici] [Article de commentaire sur un modèle mécanique])

Vous voulez connaître l'algorithme?(y/n)
y
Sachons.

2.Fruchterman-Reingold algorithm

Définir la puissance

Dans le modèle dynamique, une force est appliquée à l'apex pour le déplacer. L'algorithme Fruchterman-Reingold vous donne ** Attractive Force ** et ** Repulsive Force **.

La force attractive travaille sur les sommets reliés par les côtés. D'autre part, la force répulsive fonctionne sur des sommets qui ne sont pas reliés par des côtés. Cela correspond à la condition précédente (1) "La relation de connexion des côtés se reflète dans la distance".

Vous pouvez définir le pouvoir de n'importe quelle manière, mais pour l'instant, utilisons la définition proposée dans l'article.

Attraction: $ f_a = \ dfrac {d ^ 2} {k} $ Répulsion: $ f_r = - \ dfrac {k ^ 2} {d} $

$ d $: Distance entre les sommets k = C \sqrt{\dfrac{\text{area}}{|V|}}, C \in \mathbb{R} ,\ \ \text{area}Est-ce que la zone de l'écran à dessiner

C'est comme une formule printanière et c'est intuitif. Le graphique de la relation entre la force et la distance est le suivant.

力学モデル_force_vs_distance.jpg Les graphiques et les formules montrent ce qui suit:

Plus l'attraction est éloignée, plus elle fonctionne
Plus la force répulsive est proche, plus elle fonctionne.
La force d'attraction et la force répulsive deviennent égales à une certaine distance $ k $

Si la distance $ k $ à laquelle les forces s'opposent est fixée à une taille appropriée, la condition ci-dessus ➁ "les sommets ne se chevauchent pas" peut être satisfaite.

algorithme

Regardons maintenant l'algorithme.

Placer initialement au hasard
Calculez les forces attractives et répulsives pour chaque sommet
Déplacez les sommets en fonction de la force. Cependant, ne sortez pas du cadre.
Abaissez la température $ t $
Répétez les étapes 2 à 4 un certain nombre de fois

J'obtiens une variable inconnue $ t $. La température $ t $ est un paramètre qui limite la quantité de mouvement des sommets. En d'autres termes, rendez le montant du mouvement inférieur ou égal à $ t $ par rapport au vecteur de direction du mouvement (appelons-le $ v $) calculé à l'étape 2.

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

Nous réduirons cette température $ t $ de manière appropriée. Ensuite, bien que la quantité de mouvement soit importante au début, elle ne bougera pas beaucoup à la fin. (Garantit la convergence)

Aussi, dans le papier, à l'étape 3, la collision avec la paroi est traitée comme une réflexion élastique afin de la placer sur l'écran. Si vous voulez en savoir plus à ce sujet, veuillez lire [Papier original "Dessin graphique par placement forcé"] Papier. (Non pris en compte dans l'implémentation de networkx ...)

~~ Maintenant que nous connaissons l'algorithme, implémentons-le. ~~ ↑ C'est ennuyeux, alors je laisse l'implémentation au lecteur.

Dans cet article, nous verrons comment implémenter networkx sans réinventer les roues.

3. Jetez un œil à l'implémentation Networkx

Apprenons en voyant l'implémentation humaine. Cependant, NetworkX 2.4 est celui du moment, et les parties qui n'expliquent pas la gestion des exceptions, etc. sont omises.

Plus tôt dans l'article, j'ai utilisé networkx.spring_layout () pour dessiner le graphe "bon". Si vous jetez un œil à GitHub,

spring_layout = fruchterman_reingold_layout

Je fais juste référence à ça! Ensuite, regardons la destination de référence fruchterman_reingold_layout.

def fruchterman_reingold_layout(G,
                                k=None,
                                pos=None,
                                #réduction
                                seed=None):
    """Long docstring
    """
    import numpy as np

    G, center = _process_params(G, center, dim)

    """
Diverses parties initialisées (omises)
    """ 
    
    """
A partir de là, c'est important
    """
    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

Dans la partie "try-except", les fonctions à appeler sont divisées en fonction de la taille du graphe. (La déclaration if n'est-elle pas inutile ...? S'il vous plaît dites-moi.)

-Appeler _fruchterman_reingold () si $ nombre de sommets <500 $

$ Nombre de sommets \ geq 500 $, appelez _sparse_fruchterman_reingold ()

** Si vous avez beaucoup de sommets, il semble que vous utilisez un solveur clairsemé. ** Nous n'avons pas encore atteint la partie algorithme, alors jetons un œil à _fruchterman_reingold ().

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

C'est la partie implémentation de l'algorithme. Je vais résumer comment gérer la force attractive et la force répulsive.

-Distance optimale entre les cordons:k = \sqrt{\dfrac{1}{|V|}}

Distance point à point: $ \ text {distance} = \ max (\ text {distance}, 0,01) $
Valeur en points de la matrice de points adjacente: $ A_i $ --Température $ t $: $ \ max (\ text {largeur de la plage de définition du placement initial}, \ text {largeur de la plage de valeurs du placement initial}) * 0.01 $ --Comment abaisser la température: t- = dt, mais $ dt = \ dfrac {t} {\ text {itération} + 1} $ --Vecteur de direction: $ \ text {delta} $
Force d'attraction: $ f_a = \ dfrac {k ^ 2} {\ text {distance} ^ 2} $
Force répulsive: $ f_r = --A_i * \ dfrac {\ text {distance}} {k} $

La formule de distance optimale est $ C = 1, \ text {area} = 1 $ lorsqu'elle est appliquée au papier. Facile! La température $ t $ diminuera significativement au début, et diminuera progressivement au fur et à mesure que l '«itération» progressera. $ \ Text {delta} $ n'est pas strictement un vecteur de direction, mais je l'ai écrit parce que j'ajuste la norme à la fin.

Ce qui est très inquiétant, c'est la définition du pouvoir. ** Les forces attractives et répulsives sont différentes de celles du papier. ** Puisque l'article date de 1991, y a-t-il une version améliorée après cela? Une autre constatation est que dans le cas des graphiques pondérés, la force répulsive doit être multipliée par la valeur de la matrice adjacente.

Lorsque vous essayez de l'implémenter vous-même, je pense qu'il est préférable de l'implémenter avec les mêmes paramètres.

prime J'ai un peu joué avec le code source pour visualiser le comportement de l'algorithme. (J'ai fait 200 itérations en jouant avec les paramètres.) anim_iter200 (1).gif Il est intéressant de noter que les morceaux de points disjoints deviennent progressivement comme des cordes. J'ai obtenu quelque chose de proche du site de référence "[Algorithme pour dessiner magnifiquement des graphes (réseaux)] [Article de commentaire de modèle mécanique]" avec presque aucune implémentation par moi-même. Tu l'as fait.

Résumé

J'ai expliqué ** l'algorithme de Fruchterman-Reingold **, qui est un algorithme de dessin de graphes, pour obtenir un peu de retard sur le networkx qui peut gérer les graphiques facilement. Une fois que vous avez appris l'algorithme, il est important de l'essayer, mais voir l'implémentation d'une personne forte est aussi une expérience d'apprentissage. Nous attendons vos questions et suggestions avec impatience.

Les références

[Algorithme pour dessiner magnifiquement des graphiques (réseaux)] [Article de commentaire sur un modèle mécanique] : Un très bon article!

[Dessin graphique par placement dirigé par la force, 1992] Papier : Article de Fruchterman et Reingold

networkx GitHub : Ce que j'ai expliqué un peu cette fois

[Modèle mécanique (wikipedia)] Mechanical model_wiki : Je veux voir d'autres méthodes

[[Python] Résumé de l'utilisation de base de NetworkX 2.0 Qiita] [Networkx2 usage Qiita] : Articles faciles à comprendre

[PYTHON] Derrière l'algorithme de dessin graphique et Networkx