Aléatoire simple graphe connexe génération avec sobriété

J'essaie de trouver un algorithme efficace pour générer un simple graphe connexe avec sobriété. Quelque chose comme:

Input:
    N - size of generated graph
    S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
    simple connected graph G(v,e) with N vertices and S edges
Ce document prétend fournir un algorithme efficace pour la génération aléatoire d'connecté graphiques. Je n'ai pas passé à travers les détails, mais ils revendiquent de meilleures performances, en particulier pour les grands réseaux. complexnetworks.fr/wp-content/uploads/2011/01/random.pdf

OriginalL'auteur F0RR | 2010-01-11

  1. 19

    Pour chaque nœud vous avez besoin d'au moins une arête.

    De commencer avec un seul nœud.
    À chaque itération, de créer un nouveau nœud et un nouveau bord. Le bord est de connecter le nouveau nœud avec un nœud aléatoire à partir du nœud précédent jeu.

    Après tous les nœuds sont créés, créer aléatoire bords jusqu'à ce que S est remplie. Assurez-vous de ne pas créer de double bords (pour cela vous pouvez utiliser une matrice de contiguïté).

    Aléatoire graphique se fait en O(S).

    Juste fait quelque chose comme cela en Java. En outre, il est préférable d'ajouter aléatoire des nœuds tout en créant minimum graphe connexe. Sinon, vous aurez toujours la seule verticale couvrant dernier nœud, pas plus de deux verticales couvrant nœud précédent et ainsi de suite. Alternativement, vous pouvez juste obtenir isomorphe graphe généré par la matrice d'adjacence de manipulations.
    C'est simple et bon, mais il n'est pas O(S) si le graphe est dense, en raison de la double bords vérifier. Je veux dire, dans le pire des cas (presque) jamais O(S), mais si le graphe est dense, même le temps prévu de la complexité si pas d'O(S).

    OriginalL'auteur

  2. 32

    De Haut Niveau De L'Idée

    1. Générer un (uniformément choisi) aléatoire spanning tree avec N nœuds et N - 1 bords.
    2. Jusqu'à ce que le nombre requis de bords a été atteinte, ajouter une arête entre deux aléatoire des nœuds.

    De la création de la Spanning Tree

    La partition de réponse par ypnos est un bon début, mais le biais est introduit par la sélection d'un nœud visité pour une fin d'un nouveau bord. Par la sélection aléatoire d'un nœud visité à chaque itération, les nœuds qui sont visités vers le début, ont plus d'itérations à partir de laquelle ils ont une chance d'être sélectionné. Donc, plus tôt les nœuds sont plus susceptibles d'avoir un degré élevé (nombre d'arêtes) que ceux repris plus tard.

    Exemple de Partialité

    Titre d'exemple, pour un 4 nœud connecté graphique plutôt que de générer un linéaire chemin graphique, qui est ce que 75% de la possible arbres de recouvrement sont, ce type de biais sera la cause de la star graphique être généré avec plus de 25% de probabilité qu'il devrait être.

    Aléatoire simple graphe connexe génération avec sobriété

    Biais n'est pas toujours une mauvaise chose. Il s'avère que ce type de biais est bon pour générer des arbres de recouvrement qui sont similaire à la vraie monde des réseaux informatiques. Toutefois, afin de créer une véritable aléatoire graphe connexe la première spanning tree doit être choisi de manière uniforme dans les arbres de recouvrement (voir Wikipedia Uniforme Spanning Tree article).

    Marche Aléatoire Approche

    Une approche pour la génération d'un uniforme spanning tree est par une marche aléatoire. Ci-dessous est une citation du livre La génération Aléatoire d'Arbres de recouvrement Plus Rapidement que le Couvercle du Temps par Wilson décrivant simple marche aléatoire algorithme.

    Commencer à n'importe quel sommet et de faire une simple marche aléatoire sur le graphe. Chaque fois qu'un sommet est rencontré pour la première fois, marquer la limite à partir de laquelle il a été découvert. Lorsque tous les sommets sont découverts, l'marqué les bords forment un hasard stp. Cet algorithme est facile à code, un petit cours d'exécution constantes de temps, et a une belle preuve qu'il génère des arbres avec le droit des probabilités.

    Cela fonctionne bien pour un simple graphe connexe, cependant si vous avez besoin d'un algorithme pour un graphe orienté, puis lire le papier mesure où elle décrit l'Algorithme de Wilson. Voici une autre ressource pour aléatoire arbres stp et Wilson Algorithme.

    Mise en œuvre

    Comme je l'ai été aussi intéressés à ce problème, j'ai codé en Python implémentations de diverses approches, y compris la marche aléatoire approche. N'hésitez pas à jeter un coup d'oeil à la L'essentiel du code sur GitHub.

    Ci-dessous est un extrait du code de la marche aléatoire approche:

    # Create two partitions, S and T. Initially store all nodes in S.
S, T = set(nodes), set()

# Pick a random node, and mark it as visited and the current node.
current_node = random.sample(S, 1).pop()
S.remove(current_node)
T.add(current_node)

graph = Graph(nodes)

# Create a random connected graph.
while S:
    # Randomly pick the next node from the neighbors of the current node.
    # As we are generating a connected graph, we assume a complete graph.
    neighbor_node = random.sample(nodes, 1).pop()
    # If the new node hasn't been visited, add the edge from current to new.
    if neighbor_node not in T:
        edge = (current_node, neighbor_node)
        graph.add_edge(edge)
        S.remove(neighbor_node)
        T.add(neighbor_node)
    # Set the new node as the current node.
    current_node = neighbor_node

# Add random edges until the number of desired edges is reached.
graph.add_random_edges(num_edges)
    Très belle réponse!
    Quelle est la complexité de la marche aléatoire approche? N'a pas la "choisissez un noeud au hasard; l'ignorer si elle avait déjà été utilisée" modèle potentiellement être indépendant des temps d'exécution?
    Comme le papier par Wilson discute, le Andrei Broder algorithme s'exécute à l'intérieur de la housse temps d'un graphe non-dirigé, qui est délimitée par des O(n^3) pour le pire des graphiques, mais aussi faible que O(n lg n) pour presque tous les graphes---où n est le nombre de sommets.
    Qu'est-ce que l'utilisation de graphique.add_random_edges(num_edges)? Parce que dans la pointe est déjà ajouté dans le graphique.add_edge(edge).
    Le code antérieur poignées partie 1 de l'idée de la création d'un graphique avec N-1 bords. La deuxième partie de la question d'origine demande comment créer un graphique d'une sobriété c'est à dire, un nombre spécifique de bords. Si l' ` |E| < (|S| - 1)` puis d'autres arêtes devront être ajoutées (point 2 de l'idée). La valeur de num_edges dans le code d'exemple est ambigu sur son propre. Il dépend de la mise en œuvre de add_random_edged() quant à savoir si ou de ne pas l'argument spécifie le nombre total d'arêtes demandé ou le nombre de nouveaux bords qui devrait être ajouté.

    OriginalL'auteur

  3. 2

    Basé sur Wesley Baugh's réponse, je suis venu avec le code javascript suivant la mise en œuvre avec cytoscape.js à manipuler des graphiques:

    function generateRandomGraph(cy, numNode, avgDegree, weightMin, weightMax) {
//create nodes
for (var i = 0; i < numNode; i++) {
cy.add({
group: "nodes",
data: {
id: "n" + i
}
});
}
//perform random walks to connect edges
var nodes = cy.nodes(),
S = nodes.toArray(),
T = []; //visited
var currNodeIdx = randomIntBetween(0, S.length);
var currNode = S[currNodeIdx];
S.splice(currNodeIdx, 1);
T.push(currNode);
while (S.length > 0) {
var neighbourNodeIdx = randomIntBetween(0, S.length);
var neighbourNode = S[neighbourNodeIdx];
cy.add({
group: "edges",
data: {
weight: randomIntBetweenInclusive(weightMin, weightMax),
source: currNode.id(),
target: neighbourNode.id()
}
});
S.splice(neighbourNodeIdx, 1);
T.push(neighbourNode);
currNode = neighbourNode;
}
//add random edges until avgDegree is satisfied
while (nodes.totalDegree() / nodes.length < avgDegree) {
var temp = sampleInPlace(nodes, 2);
if (temp[0].edgesWith(temp[1]).length === 0) {
cy.add({
group: "edges",
data: {
weight: randomIntBetweenInclusive(weightMin, weightMax),
source: temp[0].id(),
target: temp[1].id()
}
})
}
}
}
generateRandomGraph(cy, 20, 2.8, 1, 20);

    Pour exemple complet de code source, visitez mon dépôt github 🙂

    Merci. C'est vraiment cool pour visualiser le graphique généré

    OriginalL'auteur

  4. 1

    Générer un minimum spanning tree en utilisant quelque chose comme L'algorithme de Prim, et à partir de là, au hasard de générer des liens supplémentaires vers le selon le caractère que vous voulez.

    OriginalL'auteur