Генерация графа с n вершинами, m ребрами равномерно по случайному алгоритму - PullRequest
Новая
       55

Генерация графа с n вершинами, m ребрами равномерно по случайному алгоритму

0 голосов
/ 29 мая 2018

Простой вопрос, не нашли простого ответа.Я хочу граф с N вершинами, M ребрами, равномерно наугад.В разумные сроки сложности (я бы сказал, квазилинейный в худшем случае).Существует ли такой алгоритм, и если да, то что это?

РЕДАКТИРОВАТЬ: Уточнение: график не является ненаправленным, не имеет много ребер или ребер петли.

Ответы [ 2 ]

0 голосов
/ 29 мая 2018

Для эффективной генерации случайного графа вы можете использовать модель Эрдеша – Рени .Это классический подход в теории графов.Код Java (использующий библиотеку графов) для генерации случайного графа выглядит примерно так: 

Graph g = new SingleGraph("Erdos-Renyi model");
// adding the first nodes
g.addNode("0");
g.addNode("1");
// creates the first edge
g.addEdge("0_1", "0", "1");
Integer i = 2;
while(i < numNodes) {
    Node source = g.addNode(i.toString());
    Node dest = g.getNode(random.nextInt(i)+"");
    g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
    i++;
 }

Существуют также другие модели для генерации графов, такие как модель Барабази – Альберта .Эта модель генерирует график, где чем больше связан узел, тем больше вероятность того, что он получит новые ссылки (описывая феномен «богатые становятся более богатыми»).Java-код для генерации случайного графа с использованием модели Барабази-Альберта: 

Graph g = new SingleGraph("Barabasi–Albert model");    
g.addNode("0");
g.addNode("1");
g.addEdge("0_1", "0", "1");
int sumDegree = 2;
Integer i = 2;
while(i < numNodes) {
    Node source = g.getNode(i.toString());
    if(source == null) {
          source = g.addNode(i.toString());
    }
    Node dest = g.getNode(random.nextInt(i)+"");
    double probability = dest.getDegree() * 1.0/sumDegree;
    double r = nextDouble();
    if(probability > r) {
       g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
        sumDegree = sumDegree + 2;
         i++;
       }
  }

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

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

0 голосов
/ 29 мая 2018

Должно быть простым.Просто сгенерируйте N вершин.Тогда M края.Выберите случайные вершины в качестве источника и назначения.Поскольку у вас нет дополнительных требований (например, языков автоматов), это распределяется равномерно. 

V <- {1, ..., N}
E <- {}
for 1 to M do
    edge <- (random(V), random(V))
    E.push(edge)
return (V, E)

РЕДАКТИРОВАТЬ: Уточнение: график не ориентирован, не имеет многоугольников или петель.

Продолжайте генерировать случайные ребра, пока у вас не будет действительного ребра: 

V <- {1, ..., N}
E <- {}
for 1 to M do
    repeat
        source <- random(V)
        edge <- (source, random(V \ {source}))
    until E does not contain edge
    E.push(edge)
return (V, E)

Для пункта назначения используйте random(V \ source) для исключения петель.E does not contain edge не должно заботиться о направлении.Т.е. следует учитывать 

(a, b) = (b, a)

Для эффективности contains при реализации следует использовать некоторую хешированную структуру.

Проблема заключается в цикле repeat.В зависимости от того, как быстро работает random и насколько близко M к количеству возможных ребер, это может занять некоторое время.Вы можете ускорить это, используя такие методы, как алгоритм Флойд-Ривеста (также см. Алгоритм для выбора одной случайной комбинации значений? ).

Если M довольно мала по сравнению с максимальной величиной, она должна работать быстро (линейно в N и M), так как вы не получаете много краевых столкновений.

...