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

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

Для каждого узла вам нужно как минимум одно ребро.

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

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

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

Answer 2

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

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

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

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

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

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

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

Случайный подход

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

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

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

Реализация

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

Для полного примера исходного кода, посетите мой репозиторий Github:)

Answer 4

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