Генерация случайных простых связных графов с заданной разреженностью

Question

Я пытаюсь найти эффективный алгоритм для генерации простого связного графа с заданной разреженностью. Что-то вроде:

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

Answer 1

Идея высокого уровня

1. Создание (равномерно выбранного) случайного остовного дерева с N узлами и N - 1 ребрами.
2. Пока не будет достигнуто запрошенное число ребер, добавьте ребро между любыми двумя случайными узлами.

Создание связующего дерева

Ответ на основе разделов от ypnos - хорошее начало, но смещение вводится путем всегда выбора посещаемого узла для одного конца нового ребра. Путем случайного выбора посещаемого узла на каждой итерации узлы, которые посещаются в начале, имеют больше итераций, из которых они могут быть выбраны. Поэтому более ранние узлы с большей вероятностью будут иметь высокую степень (число ребер), чем те, которые были выбраны позже.

Пример смещения

Например, для 4-узлового связанного графа, а не для генерации линейного графа путей , то есть 75% возможных связующих деревьев, этот тип смещения вызовет звезду график должен быть сгенерирован с вероятностью, превышающей 25%.

Смещение не всегда плохо. Оказывается, такой уклон хорош для генерации связующих деревьев, похожих на реальные компьютерные сети. Однако для создания действительно случайного связного графа исходное остовное дерево должно быть равномерно выбрано из набора возможных остовных деревьев (см. Статью Uniform Spanning Tree * из Википедии ).

Подход с произвольной ходьбой

Один из подходов к созданию однородного связующего дерева - случайное блуждание. Ниже приводится цитата из статьи Создание случайных остовных деревьев быстрее, чем время покрытия Уилсона, описывающая простой алгоритм случайного блуждания .

Начните с любой вершины и выполните простую случайную прогулку по графику. Каждый раз, когда встречается вершина, отметьте ребро, с которого она была обнаружена. Когда все вершины обнаружены, отмеченные ребра образуют случайное остовное дерево. Этот алгоритм легко закодировать, он имеет небольшие постоянные времени выполнения и имеет хорошее доказательство того, что он генерирует деревья с правильными вероятностями.

Это хорошо работает для простого связного графа, однако, если вам нужен алгоритм для ориентированного графа, прочитайте статью далее, так как она описывает алгоритм Уилсона. Вот еще один ресурс для случайных связующих деревьев и алгоритма Уилсона.

Осуществление

Поскольку меня также интересовала эта проблема, я кодировал реализации Python различных подходов, в том числе подхода случайного блуждания. Не стесняйтесь взглянуть на Суть кода на GitHub.

Ниже приведена выдержка из кода подхода случайного блуждания:

# 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)

Answer 2

Для каждого узла нужен хотя бы один край.

Начните с одного узла. На каждой итерации создайте новый узел и новое ребро. Край должен соединить новый узел со случайным узлом из предыдущего набора узлов.

После того, как все узлы созданы, создайте случайные ребра, пока не будет выполнено S. Не создавайте двойных ребер (для этого вы можете использовать матрицу смежности).

Случайный граф сделан в O (S).

Answer 3

Основываясь на ответе Уэсли Боуга , я разработал следующую реализацию javascript с cytoscape.js для обработки графиков:

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);

Для получения полного примера исходного кода, посетите my github repo :)

Answer 4

Создайте минимальное связующее дерево , используя что-то вроде Алгоритм Прима , и оттуда случайным образом генерируйте дополнительные ссылки в соответствии с необходимой вам разреженностью.