Création d'un graphique avec une certaine distribution des degrés?

StackOverflow https://stackoverflow.com/questions/4328837

Question

Je suis en train de générer un graphique aléatoire qui a des propriétés de petite monde (présente une distribution de loi de puissance). Je viens de commencer à utiliser le package NetworkX et découvert qu'il offre une variété de génération de graphes aléatoires. Quelqu'un peut-il me dire s'il possible de générer un graphique où un diplôme de noeud donné suite à une distribution gamma (soit en R ou en utilisant package NetworkX de python)?

Était-ce utile?

La solution

Si vous voulez utiliser le modèle de configuration quelque chose comme cela devrait fonctionner dans NetworkX: 

import random 
import networkx as nx
z=[int(random.gammavariate(alpha=9.0,beta=2.0)) for i in range(100)]
G=nx.configuration_model(z)

Vous devrez peut-être ajuster la moyenne de la séquence z en fonction des paramètres de la distribution gamma. Aussi z n'a pas besoin d'être graphique (vous obtiendrez un multigraphe), mais il a besoin d'une somme, même si vous pourriez avoir à essayer quelques séquences aléatoires (ou ajoutez 1) ...

Les notes de documentation NetworkX pour configuration_model donner un autre exemple, une référence et comment supprimer des bords parallèles et boucles auto: 

Notes
-----
As described by Newman [1]_.

A non-graphical degree sequence (not realizable by some simple
graph) is allowed since this function returns graphs with self
loops and parallel edges.  An exception is raised if the degree
sequence does not have an even sum.

This configuration model construction process can lead to
duplicate edges and loops.  You can remove the self-loops and
parallel edges (see below) which will likely result in a graph
that doesn't have the exact degree sequence specified.  This
"finite-size effect" decreases as the size of the graph increases.

References
----------
.. [1] M.E.J. Newman, "The structure and function
       of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.

Examples
--------
>>> from networkx.utils import powerlaw_sequence
>>> z=nx.create_degree_sequence(100,powerlaw_sequence)
>>> G=nx.configuration_model(z)

To remove parallel edges:

>>> G=nx.Graph(G)

To remove self loops:

>>> G.remove_edges_from(G.selfloop_edges())

Voici un exemple similaire à celui de http://networkx.lanl.gov /examples/drawing/degree_histogram.html qui fait un dessin comprenant une mise en page graphique de la plus grande composante connexe: 

#!/usr/bin/env python
import random
import matplotlib.pyplot as plt
import networkx as nx

def seq(n):
    return [random.gammavariate(alpha=2.0,beta=1.0) for i in range(100)]    
z=nx.create_degree_sequence(100,seq)
nx.is_valid_degree_sequence(z)
G=nx.configuration_model(z)  # configuration model

degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
print "Degree sequence", degree_sequence
dmax=max(degree_sequence)

plt.hist(degree_sequence,bins=dmax)
plt.title("Degree histogram")
plt.ylabel("count")
plt.xlabel("degree")

# draw graph in inset 
plt.axes([0.45,0.45,0.45,0.45])
Gcc=nx.connected_component_subgraphs(G)[0]
pos=nx.spring_layout(Gcc)
plt.axis('off')
nx.draw_networkx_nodes(Gcc,pos,node_size=20)
nx.draw_networkx_edges(Gcc,pos,alpha=0.4)

plt.savefig("degree_histogram.png")
plt.show()

Autres conseils

Je l'ai fait il y a un moment dans la base Python ... IIRC, je la méthode suivante. De mémoire, donc cela ne peut pas être tout à fait exact, mais nous espérons que c'est quelque chose de la valeur:

  1. Choisissez le nombre de noeuds, N, dans votre graphique, et la densité (bords existants sur les bords possibles), D. Ceci implique le nombre d'arêtes, E.
  2. Pour chaque nœud, attribuer son degré en choisissant d'abord un nombre positif aléatoire x et trouver P (x), où P est votre pdf. Le degré du noeud est (P (x) * E / 2) -1.
  3. Choisir un noeud au hasard, et le connecter à un autre noeud aléatoire. Si l'un des noeuds a réalisé son degré assigné, l'éliminer de sélection supplémentaire. Répétez les temps E.

N.B.. que cela ne crée pas un graphe connexe en général.

Je sais ce qui est très en retard, mais vous pouvez faire la même chose, mais un peu plus simple, avec Mathematica.

RandomGraph [DegreeGraphDistribution [{3, 3, 3, 3, 3, 3, 3, 3}], 4]

Ceci générera 4 graphes aléatoires, chaque noeud ayant un degré prescrit.

Y compris le, networkx fournit 4 algorithmes mentionnés ci-dessus qui reçoit le degree_distribution en entrée:

  • configuration_model : expliquer par @eric
  • expected_degree_graph : utiliser une approche probabiliste basée sur le degré attendu de chaque noeud. Il ne vous donnera pas les degrés exacts, mais une approximation.
  • havel_hakimi_graph : celui-ci tente de se connecter d'abord les noeuds avec le degré le plus élevé
  • random_degree_sequence_graph : pour autant que je peux voir, ce qui est similaire à ce que @JonC suggéré; il a un paramètre trials car il n'y a aucune garantie de trouver une configuration appropriée.

La liste complète (y compris certaines versions des algorithmes pour graphes orientés) est ici .

J'ai aussi trouvé quelques papiers:

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top