NetworkXで可視化 ２

 NetworkXで一枚可視化が出来たので、今度は少し深入りしてみようと思います。

Software for Complex Networks — NetworkX 3.3 documentation

Greedy Coloringというものがありました。１２面体ドデカヘドラのグラフです。

「greedy」という言葉の語源は、古英語の「grēdīg」に遡るそうです。この言葉は「欲しい」という意味の「grēd」から派生しており、もともとは「渇望している」「強く欲する」というニュアンスを持っており、現在の意味では「欲深い」「貪欲な」という意味だそうです。
Greedy alogorithmは貪欲法と呼ばれ、局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つだそうです。
Greedyな手法というと、最適化問題を解くためのアルゴリズムの一種で、各段階で局所的に最適な選択を行いながら全体の最適解に近づこうとする方法だそうです。具体的には、各ステップでその時点での最善の選択を行い、その選択が後のステップでも続いていく特徴があるそうです。

それでは、コードを見てみます。

# ライブラリーのインポート

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

import matplotlib.colors as mpl

1. numpyは、数値計算ライブラリ
2. networkxは、グラフ構造を操作するためのライブラリ
3. matplotlib.pyplotは、グラフを描画するためのライブラリ
4. matplotlib.colorsは、カラーマッピングに使用されるライブラリ

# グラフの生成

G = nx.dodecahedral_graph()

• nx.dodecahedral_graphで、ドデカヘドラ（12面体）グラフを生成します。

# グラフの色付け

graph_coloring = nx.greedy_color(G)

unique_colors = set(graph_coloring.values())

1. nx.greedy_color(G)で、貪欲法を用いてグラフのノードに色を割り当てます。この方法では、隣接するノードが異なる色を持つようにします。
2. unique_colorsで、割り当てられた色のユニークな集合を取得します。

# ノードの色の決定

graph_color_to_mpl_color = dict(zip(unique_colors, mpl.TABLEAU_COLORS))

node_colors = [graph_color_to_mpl_color[graph_coloring[n]] for n in G.nodes()]

1. graph_color_to_mpl_colorで、ユニークな色をMatplotlibのカラーマップにマッピングします。
2. node_colorsで、各ノードに対して、割り当てられた色をリストとして作成します。

# グラフの描画

pos = nx.spring_layout(G, seed=14)

nx.draw(

    G,

    pos,

    with_labels=True,

    node_size=500,

    node_color=node_colors,

    edge_color="grey",

    font_size=12,

    font_color="#333333",

    width=2,

)

1. nx.spring_layout(G, seed=14)で、グラフのノードの配置を計算します（ここでは力学的レイアウトを使用）。
2. nx.draw()で、グラフを描画します。ノードは色付けされ、エッジは灰色で描かれ、ラベルも表示されます。

# グラフの表示

plt.show()

• plt.show()で、グラフを画面に表示します。