Django - Nodes & Edges

Calculer la force d'un lien (edge)

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour,

je travaille actuellement sur un projet dont une partie de la structure est la suivante :

J’ai extrait plusieurs (nombre indéterminé à l’avance) "UniqueValue" (valeurs qui match avec un pattern donné) d’un objet "DataRow" (ligne, soit ensemble de cellules, dans un fichier Excel, de longueur variable). Ces "UniqueValue" ont des relations ManyToMany entre elles, de sorte à pouvoir générer un schéma relationnel. Pour cela, j’ai une table intermédiaire "DataRelation" qui fait office de table pivot. Voilà les modélisations simplifiée Django :

from django.contrib.postgres.fields import ArrayField
from django.db import models

class DataRow(models.Model):
    content = ArrayField(models.TextField(), blank=True)

class UniqueValue(models.Model):
    raw_content      = models.TextField(blank=True)
    modified_content = models.TextField(blank=True)

    linked_values    = models.ManyToManyField("self", through="DataRelation")

class DataRelation(models.Model):
    source           = models.ForeignKey(UniqueValue,
                                         on_delete=models.CASCADE,
                                         related_name='sources')
    target           = models.ForeignKey(UniqueValue,
                                         on_delete=models.CASCADE,
                                         related_name='targets')
    data_row         = models.ForeignKey(DataRow,
                                         on_delete=models.CASCADE,
                                         related_name='relations')

La "force" d’un lien serait calculée en fonction du nombre de fois qu’il apparait (par exemple node1->node1 apparait avec data_row1, data_row2, data_row3 etc…).

J’ai ainsi dans ma base de donnée quelques centaines de milliers de "DataRow", avec environ 200k UniqueValue et un paquet de liens bien sûr. J’arrive à dessiner un graph relationnel basique (au moyen de Sigma JS), afin de déterminer quelles "UniqueValue" sont en relation. Ce que je voudrais, c’est pouvoir ajouter une "force" aux liens, comme sur l’image suivante :

Graph

La méthode que j’utilise actuellement est de parcourir chaque "UniqueValue", puis toutes ses "linked_values". Je dessine à chaque fois un node s’il n’est pas déjà dessiné, puis j’ajoute les edges correspondantes. Je ne vois pas comment calculer la "force" d’un lien directement. Ca donne à peu près ça :

unique_values = UniqueValue.objects.all()

for unique_value in unique_values:
    linked_values = UniqueValue.linked_values.all()

    for linked_value in linked_values:
        # draw node if not exists
        # draw edge if not exists
        ...

Je débute en visualisation de données et j’aimerais trouver un moyen plus efficace pour effectuer cela. Pouvez-vous m’aiguiller ?

Édité par leir

+0 -0

Salut,

Est-ce que tu ne pourrais pas compter les instances de DataRelation, pour définir ta force ?

Parce que ce si tu as 3 liens node1->node2, tu auras 3 instances de DataRelation. Après j’ai pas assez d’expérience avec Django pour être tout à fait sûr, mais j’imagine que tu peux accéder aux données de ta classe associative.

+0 -0
Auteur du sujet

Hello, merci de ta réponse !

Alors oui effectivement, c’est une possibilité. J’ai fait une tentative dans ce sens, voilà ce que ça donne :

  1. Je fais une requête qui charge les UniqueValue dont j’ai besoin.
  2. Je fais une boucle, et pour chaque UniqueValue, je charge les UniqueValue qui sont en relation avec celle-ci, au moyen d’une requête avec un COUNT. C’est là que le calcul de la force du lien se fait.
  3. J’attends depuis 30 minutes et c’est pas fini, un graph assez lourd. Ce n’est pas utilisable directement pour mes utilisateurs.

Merci encore de ton aide. Je pense que je dois calculer cette "force" au moment de l’import des fichiers xls. Par exemple, si un lien entre deux UniqueValue existe déjà (dans un sens ou dans l’autre, ça dépend ce que je veux), j’incrémente un score que je stocke ailleurs. A moins que tu ou quelqu’un d’autre voie une autre solution.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte