Générer aléatoirement un graphique basé sur le nombre de connexions sur chaque nœud

Question

J'essaie de générer un graphique basé sur certaines données dont je dispose.

Ce graphique aurait dû N nœuds où le nombre d'arêtes de chaque nœud est égal à un nombre aléatoire P(k), où k est "l'index" du nœud (principalement arbitraire).

Ma question est la suivante : existe-t-il un véritable moyen de procéder ?Je pense que j'ai besoin de plus de données qui déterminent soit la densité, soit un autre degré de connexions (N1->N2->N3), mais je n'en suis pas entièrement sûr.

Answer 1

Vous souhaitez essentiellement générer un graphique avec une certaine séquence de degrés (que vous souhaitez aléatoire, mais ce n'est pas pertinent) ;c'est ce qu'on appelle le problème de réalisation de graphe qui est résolu par ex.par le Algorithme de Havel-Hakimi dans le sens où l'algorithme renverra un graphique (simple) avec la séquence de degrés souhaitée si cela est possible (de telles séquences sont appelées graphique).Notez que toutes les séquences finies ne $\mathbb N$ sont graphiques comme par ex.toute séquence dont la somme des membres est un nombre impair ne peut pas être graphique par le lemme de la poignée de main (qui stipule que la somme de tous les degrés d'un graphe est égale à 2 fois le nombre d'arêtes d'un graphe et donc paire).De plus, les solutions ne seront en général pas uniques :La séquence des diplômes $(2, 2, 2, 2, 2, 2)$ par exemple peut être réalisé par le graphe de cycle $C_6$ de taille $6$ ou l'union disjointe $C_3 \mathop{\dot\cup} C_3$ de deux graphiques de cycle $C_3$ de taille $3$ chaque.

De nombreuses bibliothèques de graphes pour langages de programmation ont des implémentations d'algorithmes pour ce problème, par exemple la bibliothèque Python réseaux.