является ли ориентированный граф предпочтительного присоединения графа ацикличным?

Я генерирую графики, используя модель Барабаши-Альберта, реализованную igraph:

Graph.Barabasi(10,5,directed=True)

Как я могу быть уверен, что сгенерированные ориентированные графы ацикличны? Есть ли какое-то основное свойство, которое подразумевает это?

Я нашел здесь вот что о рассматриваемой модели:

Однако этой модели не хватает некоторых свойств всемирной паутины: • Если мы рассматриваем модель как создающую направленную сеть, то она генерирует ациклические графы, которые плохо представляют Интернет.

но как я могу быть уверен в этих свойствах графов, сгенерированных igraph?


graph directed-acyclic-graphs algorithm igraph directed-graph
person Rafael Angarita    schedule 08.02.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Алгоритм генерирует случайные безмасштабные сети.

Вот описание того, как это работает, из wikipedia. :

Сеть начинается с начальной сети из m0 узлов. [...] Новые узлы добавляются в сеть по одному. Каждый новый узел связан с m существующими узлами с вероятностью, пропорциональной количеству связей, которые уже есть у существующих узлов.

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

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

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

Но это свойство также сохраняется для больших значений m, когда добавленные ребра направлены.

Примечание: здесь предполагается, что начальный граф ациклический. Если бы у нас был цикл в маленьком начальном графе, этот цикл, конечно, остался бы по мере того, как генерируются новые узлы и граф растет.

person user1884905    schedule 08.02.2013