Я хочу генерировать случайные ациклические графы в R igraph.
В основном меня интересуют неориентированные графы.
Ациклический неориентированный граф - это лес, т. Е. Граф, связанными компонентами которого являются деревья.
Я знаю, что функция sample_pa генерирует для m = 1 безмасштабных ациклических графов по модели Барабаси-Альберта.Мне интересно, можем ли мы заставить igraph генерировать ациклические графы для более высоких значений m?
Это математически невозможно.Дерево на n узлах имеет n-1 ребер, а в лесу их меньше.Для более высоких значений m в sample_pa было бы больше ребер, следовательно, было бы циклов.
Или мы можем генерировать ациклические графы согласно некоторому другому алгоритму в igraph R
Просмотрите генераторы случайных графов в igraph.Несколько из них выведут деревья.Например, проверьте sample_growing с помощью citation = TRUE.
Однако, ни один из них не будет одинаково выбирать деревья .Предположительно, вместо того, чтобы просто генерировать любое дерево , вы захотите узнать кое-что о распределении, из которого они исходят.
Недавно я добавил унифицированный образец дерева, а также унифицированное связующее дерево.сэмплер в igraph, но его пока нет в интерфейсе R.Вы можете попробовать это с интерфейсом Mathematica (или, конечно, в C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
Но из ориентированных графов всегда можно получить неориентированные версии.
Но не ациклические единицы.
Легко генерировать произвольно направленный ациклический граф путем случайного заполнения верхней части матрицы смежности желаемымчисло 1 с.
Когда вы конвертируете это в ненаправленное, оно обычно не будет ациклическим.
Например, это не ациклично, как ненаправленным:
Фактически, любой простой неориентированный граф может быть ориентированным , так что направленная версия будет ациклической.Существует небольшая связь между неориентированными ациклическими и направленными ациклическими графами.