algorithm - igraph 优先连接有向图是非循环的吗？

Question

我正在使用 igraph 实现的 Barabasi-Albert 模型生成图形:

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

如何确定生成的有向图是无环的？是否存在暗示这一点的基本属性？

我找到了 here这是关于有问题的模型:

“然而，该模型缺少万维网的几个属性:• 如果我们将模型视为生成有向网络，那么它生成的非循环图不能很好地表示 Web。”

但我如何确定 igraph 生成的图形的属性？

Answer 1

该算法生成随机无标度网络。

这是来自 wikipedia 的关于它如何工作的描述:

The network begins with an initial network of m0 nodes. [...] New nodes are added to the network one at a time. Each new node is connected to m existing nodes with a probability that is proportional to the number of links that the existing nodes already have.

这意味着如果我们从一个小型非循环网络开始并添加具有有向边的新节点，它们将始终指向现有节点。不可能以这种方式完成一个循环，因为这需要一个现有节点指向一个新节点。

当每个新节点只连接到一个其他节点时，很容易看出生成的图将是非循环的，如维基百科页面上的图所示。该图是用 m = 1 生成的。

但是，当添加的边是定向的时，此属性也适用于较大的 m 值。

注意:这里假设种子图是非循环的。如果我们在小种子图中有一个循环，这个循环当然会随着新节点的生成和图形的增长而保留。