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

Ответ 1

Для каждого node вам нужно хотя бы одно ребро.

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

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

Случайный граф выполняется в O (S).

Ответ 2

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

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

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

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

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

В качестве примера, для 4 node связного графика, а не для генерации линейного path graph, что составляет 75% возможного Это может привести к тому, что диаграмма будет генерироваться с вероятностью 25%, которая должна быть.

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

Случайный подход к прогулке

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

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

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

Реализация

Поскольку меня также интересовала эта проблема, я кодировал реализации Python различных подходов, в том числе метод случайного блуждания. Не стесняйтесь взглянуть на Gist кода на 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)

Ответ 3

На основе Wesley Baugh ответ. Я придумал следующую реализацию 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:)

Ответ 4

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