📂グラフ理論

数学におけるグラフのレイアウト

概要

数学において、グラフまたはネットワークのレイアウトとは、2Dまたは3Dで視覚化する際に、具体的に頂点とエッジをどのように配置するかについてのアルゴリズムと要約できる。

コード

便宜上、すべてのコードはGitHubに公開されているJuliaを基に書かれている¹。例として使ったグラフは、バラバシ-アルバートモデルで生成した。

julia> G = barabasi_albert(50, 2)
{50, 96} undirected simple Int64 graph

julia> coordinates = random_layout(G)
([0.5010198458212828, 0.3452510059580436, 0.23056277180207596, 0.9451881326291259, 0.449381314574683, 0.4542317082538514, 0.599934409205972, 0.30717602583409154, 0.49093984675628266, 0.2715011111637651  …  0.681936012233088, 0.5814119530837815, 0.4207410774873547, 0.9727858272079993, 0.8552495989245602, 0.01141962455772294, 0.2899567788836197, 0.3666521897515005, 0.3711803454000888, 0.9162070908084106], [0.6301320613076998, 0.08213345094706803, 0.8807313434091223, 0.3037072145751386, 0.2696238790669454, 0.6634585165568677, 0.5096441313648647, 0.9252054034990449, 0.7087281373799236, 0.2122981806086709  …  0.5749195632507926, 0.7426568432084615, 0.42337991561728805, 0.7403457672559728, 0.09122908201258395, 0.06875442916534202, 0.5150784327498186, 0.0052746330721339385, 0.49087546999990384, 0.9942182342312704])

_layout系の関数は、そのアルゴリズムで計算される座標を返す。視覚化において、これらの座標を直接得られることは非常に大きな利点である。

spring layout

random layout

circular layout

shell_layoutという関数もあるが、明らかに実装はcircular_layoutと異なるが、視覚的には差がないため省略した。

stressmajorize layout

spectral layout

全体のコード

using Graphs, GraphPlot, Plots, Random, GraphRecipes
G = barabasi_albert(50, 2)
coordinates = random_layout(G)

gplot(G, layout = spring_layout)
gplot(G, layout = random_layout)
gplot(G, layout = circular_layout)
gplot(G, layout = shell_layout)
gplot(G, layout = stressmajorize_layout)
gplot(G, layout = spectral_layout)

環境

• OS: Windows
• julia: v1.10.0