Comment générer un graphe aléatoire étant donné le nombre de nœuds et d'arêtes?

Je suis à l'aide de python avec igraph bibliothèque:

from igraph import *
g = Graph()
g.add_vertices(4)
g.add_edges([(0,2),(1,2),(3,2)])
print g.betweenness()

Je voudrais générer un graphe aléatoire avec 10000 nœuds et 100000 bords. Les bords peuvent être aléatoires. S'il vous plaît suggérer un moyen d'avoir aléatoire bords (à l'aide de numpy.aléatoire.rand )

OriginalL'auteur Kush Jain | 2013-12-03

  1. 13

    Devez-vous utiliser numpy.random.rand? Si non, il suffit d'utiliser Graphique.Erdos_Renyi, qui permet de spécifier le nombre de nœuds et d'arêtes directement:

    g = Graph.Erdos_Renyi(n=10000, m=100000)

    OriginalL'auteur Tamás

  2. 0

    De le faire avec numpy.random.rand, de générer de l'aléatoire tableau, seuil, avec la probabilité que vous voulez, et ensuite de le passer Graphique.La contiguïté:

    adj = numpy.random.rand(edges, edges)
adj[adj > 0.999] = 1 # sets everything over 0.999 to 1
adj[adj <= 0.999] = 0 # sets everything below to 0
graph = Graph.Adjacency(adj)

    Cela génère un graphe orienté, où les adj[i, j] permet de savoir si il y a un bord de la i -> j. Si vous souhaitez un non-orienté à la place, utilisez Graph.Ajacency(adj, ADJ_UNDIRECTED) - alors il va y avoir un bord si adj[i, j] == 1 ou adj[j, i] == 1.

    Ce n'est pas garanti pour vous donner exactement de 100 000 bords - avez-vous besoin?

    Tout d'abord, ce n'est malheureusement pas ce qu'il voulait. Il veut le nombre d'arêtes. La seconde, c'est une voie très inefficace de la génération aléatoire G(n,p) graphique si le graphe est peu dense.
    Ooh, vous avez raison - j'ai raté le nombre d'arêtes. Je pense que mon approche de base peut toujours travailler pour le nombre de nœuds qu'il parle de la matrice de contiguïté, c'est du gaspillage (100M de cellules pour 100k bords), mais vous avez seulement besoin d'elle pour créer le graphique.

    OriginalL'auteur babbageclunk