NetworkxでKautzグラフを構築する。

igraph経由で行うと楽です。

pythonパッケージ↓

import igraph as ig

# m = the size of the alphabet minus one
# n = the length of the strings minus one
# total nodes = (m+1)m^n
# degree = m
G = ig.Graph.Kautz(3, 1)
nx_G = G.to_networkx()  # convert from igraph to networkx

igraphでは他には次のグラフ生成が可能です。

• Kautz graphs Graph.Kautz()

  • A Kautz graphはラベル付けされたグラフで、m+1の文字を持つアルファベット上での長さn+1の文字列で頂点がラベル付けされています。ただし、文字列内の連続する2つの文字は異なる必要があります。頂点vから頂点wへの有向辺が存在するのは、vの文字列の最初の文字を取り除き、文字を追加することでwの文字列に変換できる場合です。

• De Bruijn graphs Graph.De_Bruijn()

  • A de Bruijn graphは文字列間の関係を表しています。m個の文字からなるアルファベットが使用され、長さnの文字列が考慮されます。各頂点は可能な文字列に対応しており、頂点vから頂点wへの有向辺が存在します。これは、vの文字列の最初の文字を取り除き、文字を追加することでwの文字列に変換できる場合に当てはまります。

• LCF表記からのグラフ Graph.LCF()

  • LCF Notation -- from Wolfram MathWorld
  • LCF は Lederberg-Coxeter-Frucht の略で、3 つの正則ハミルトニアン グラフの簡潔な表記法です。これは、グラフ内の頂点の数、サイクル バックボーンに追加のエッジを与えるシフトのリスト、およびシフトを実行する回数を示す別の整数の 3 つのパラメーターで構成されます。

• 任意の「同型クラス」の小さなグラフ Graph.Isoclass()

• 指定された次数シーケンスを持つグラフ Graph.Realize_Degree_Sequence()

---

余談ですが、gravis+jupyter notebookを使うとグラフインタラクティブに表示できていいですね。

import igraph as ig
import gravis as gv

G = ig.Graph.Kautz(2, 1)
gv.d3(G)