Генерирование сильносвязанных, равномерно распределенных случайных диграфов

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

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

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

Ответ 1

Может кто-то порекомендовать мне схему высокого уровня, которая позволяет мне генерировать сильно связанные, равномерно распределенные случайные диаграфы?

У меня была аналогичная проблема, генерирующая деревья выражений для тестовых данных. Я обнаружил, что если вы узнаете, как подсчитывать уникальные деревья, проблема становится легкой. Я имею в виду, что я нашел для полных двоичных деревьев с N внутренними узлами число уникальных деревьев на основе N - это Каталонские числа. Тогда для двоичных деревьев, имеющих унарные ветки с N суммарными узлами, число уникальных деревьев на основе N есть Числа Моцкина.

Затем я нашел Онлайновая энциклопедия целых последовательностей. Поэтому, если вы знаете значение N, которое может однозначно идентифицировать граф, и вы знаете соответствующее количество уникальных графов для этого N и поместите эти подсчеты в поиск OEIS, вы должны вернуть страницу, которая поможет вам в вашем поиске. например Каталонские номера для полных двоичных деревьев или Номера Моцкина для регулярная двоичная структура. По пути я обнаружил, что одним из ключей к их созданию было отношение повторения.

Или вы можете использовать ключевые слова в поиске, но это может не получить точный хит. Я только нашел числа Моцкина, используя последовательность чисел, а не через ключевые слова.

Вот запрос OEIS для сильно связанного орграфа

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

Мое лучшее предположение для последовательности OEIS для этого вопроса:

Число ациклических орграфов с n немаркированными узлами. A003087

Что имеет ссылку на Равномерная случайная генерация больших ациклических орграфов

TL; DR

Для некоторой связанной истории см. мой вопрос: Улучшение алгоритма для перечисления бинарных деревьев

Ответ 2

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