comment calculer le diamètre du réseau

Question

J'ai des données stockées dans la base de données relationnelle mysql et PHP. J'ai une table appelée « rel » qui a deux champs:

from_node | to_node 
===================== 
1    2 
1    3 
2    3 

et ainsi de suite ......

Comment puis-je calculer le réseau Diamètre d'un réseau. Je sais que c'est le chemin le plus long ou le plus court entre deux paires, mais comment le calculer? Existe-t-il un script PHP ou une fonction qui peut m'aider à le faire?

Answer 1

Dans votre exemple, vous montrez que chaque nœud est relié à tous les autres nœuds. Si tel est le cas tout au long de votre configuration, le diamètre est 1.

Si votre configuration est une ligne comme si dans une formation linéaire:

n=1, n = 2, n = 3, ... n 

Ensuite, votre diamètre est (n + 1)/3 .

Si votre configuration est plus irrégulière, avec une série de noeuds nombre N et le nombre K de liens, votre diamètre est au moinslogN/LogK

Edit: Pour clarifier les choses, je suis le calcul de la moyenne la plus courte distance entre des paires de nœuds.

n1 - n2 - n3 
(n+1)/3 = 4/3 

n1-n2 = 1 hop 
n2 - n3 = 1 hop 
n1- n2 - n3 = 2 hops 
(1+1+2)/3 = 4/3 

Answer 2

Voir les Wikipedia article sur le plan graphique (réseau) liés à la distance et le diamètre. Il mentionne quelques notes sur la façon de trouver le diamètre. This section de l'article sur les composants connexes des graphes suggère également un algorithme pour découvrir ces composants connexes, qui pourrait être adapté très facilement pour vous indiquer le diamètre du graphique. (S'il y a plus d'un composant, alors le diamètre est infini, je crois.) L'algorithme est simple, basé sur une recherche pain/profondeur, donc il ne devrait pas être difficile à mettre en œuvre, et l'efficacité ne devrait pas être un grand problème non plus.

Si vous n'êtes pas prêt à écrire ceci (bien que je ne pense pas que cela demanderait autant d'efforts), je vous recommande de chercher une bonne bibliothèque d'analyse de réseau/graphique. Il y en a quelques-uns, mais je ne suis pas sûr de ceux que vous voudriez voir en utilisant PHP. (Vous devrez probablement utiliser une sorte d'interop.)

Espérons que cela aide, de toute façon.

Answer 3

Je pense vraiment que vous vouliez dire que vous vouliez trouver le cluster coefficient d'un réseau. De plus, vous aimeriez le faire en PHP. Je ne sais pas combien de bonnes bibliothèques d'analyse de réseau ont été portées aux extensions PHP. Cependant, si vous suivez l'article, il ne devrait pas (trop) difficile de trouver le vôtre. Vous n'avez pas besoin de produire de jolis graphiques, il vous suffit de trouver le coefficient.

Si ce n'est pas ce que vous vouliez dire, veuillez mettre à jour/clarifier votre question.

Answer 4

En supposant que vous avez un graphe connexe (sinon la distance maximale est infinie) et tous vos points de noeud sont des nombres ....

Seed une table (à partir, à, distance) avec (From_Node, to_node, 1).Pour chaque tuple, vous devez vous assurer que la valeur de From_Node est toujours inférieure à la valeur de to_node

CREATE TABLE hops (
    from_node int not null, 
    to_node int not null, 
    distance int not null default 0, 
    primary key (from_node, to_node, distance) 
) 

-- first load: 
INSERT INTO hops (from_node, to_node) 
SELECT from_node, to_node FROM rel; 

-- iterative step 
INSERT INTO hops (from_node, to_node, distance) 
SELECT a.from_node, b.to_node, min(a.distance+b.distance) 
FROM hops a, hops b 
WHERE a.to_node = b.from_node 
    AND a.from_node <> b.from_node -- not self 
    AND a.to_node <> b.to_node  -- still not self 
    AND a.from_node <> b.from_node -- no loops 
    AND NOT EXISTS (    -- avoid duplicates 
      SELECT * FROM hops c 
      WHERE c.from_node = a.from_node 
      AND c.to_node = b.to_node 
      AND c.distance = a.distance+b.distance) 
GROUP BY a.from_node, b.to_node 

Exécuter l'insert de façon répétée jusqu'à ce qu'aucune lignes sont insérées. Ensuite, sélectionnez la distance maximale pour obtenir votre diamètre.

EDIT: Pour un graphique dont les sommets sont pondérés, vous juste ensemencer le champ de distance avec les poids plutôt que d'utiliser 1.

Answer 5

Network est un graphe connexe. Alors pourquoi ne pas essayer de construire une représentation graphique de vos données et d'effectuer BFS ou DFS à ce sujet? Vous obtiendrez exactement ce que vous cherchez.

Answer 6

C'est simple:

• Préparez
  • Ajouter un Colum nommé distance
  • Donner à tous les nœuds de la distance -1
• Premier tour
  • Sélectionnez un noeud (par ex. le premier)
  • lui donnent la distance de 1
  • maintenant itérer jusqu'à ce qu'il nœuds avec la distance -1
    • UPDATE table SET distance=:i+1 WHERE from_node IN (SELECT to_node FROM table WHERE distance=:i)
• Deuxième Iteration
  • Pick a noeud qui a la distance maximale (tout) - rappelez-vous qu'il
  • Set toutes les distances Retour à -1
  • Définissez votre noeud remebered à 1
  • Appelez l'itération une seconde fois

Cette fois la distance maximale est le diamètre de votre graphique/réseau.