igraphによって実装されたBarabasi-Albertモデルを使用してグラフを生成しています。
Graph.Barabasi(10,5,directed=True)
生成された有向グラフが非周期的であることをどのように確認できますか？それを暗示する基本的な性質はありますか？
私はここで問題のモデルについてこれを見つけました：
「しかし、このモデルには、ワールドワイドウェブのいくつかの特性が欠けています。•モデルを有向ネットワークを生成すると見なすと、ウェブの表現が不十分な非巡回グラフが生成されます。」
しかし、igraphによって生成されたグラフのそのプロパティをどのように確認できますか？
このアルゴリズムは、ランダムなスケールフリーネットワークを生成します。
ウィキペディアからの仕組みの説明は次のとおりです。
ネットワークは、m0ノードの初期ネットワークから始まります。[...]新しいノードが一度に1つずつネットワークに追加されます。新しい各ノードは、既存のノードがすでに持っているリンクの数に比例する確率で、m個の既存のノードに接続されます。
これは、小さな非巡回ネットワークから始めて、有向エッジを持つ新しいノードを追加する場合、それらは常に既存のノードを指すことを意味します。既存のノードが新しいノードを指す必要があるため、この方法でサイクルを完了する可能性はありません。
新しい各ノードが他の1つのノードにのみ接続している場合、ウィキペディアページの図に示すように、結果のグラフが非周期的であることが簡単にわかります。グラフはで生成されm = 1ます。
mただし、このプロパティは、追加されたエッジが方向付けられるときのより大きな値にも当てはまります。
注：ここでは、シードグラフが非巡回であると想定しています。小さなシードグラフにサイクルがあったとしたら、このサイクルはもちろん、新しいノードが生成されてグラフが大きくなるときに残ります。