algorithm - igraph 优先附件有向图是无环的吗？

Question

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

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

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

我在这里找到了有关该模型的信息：

“然而，这个模型缺乏万维网的几个属性： • 如果我们认为该模型产生了一个有向网络，那么它会生成无环图，这是对 Web 的不良表示。”

但是我如何确定 igraph 生成的图表上的这些属性？

Answer 1

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

以下是wikipedia中对其工作原理的描述：

该网络以 m0 个节点的初始网络开始。[...] 一次将一个新节点添加到网络中。每个新节点连接到 m 个现有节点的概率与现有节点已经拥有的链接数量成正比。

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

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

但是这个属性也适用于更大的值，m当添加的边被定向时。

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