グラフアルゴリズム

Pythonで学ぶネットワーク分析入門

Eric Ma

Data Carpentry instructor and author of nxviz package

経路の発見

  • 経路探索の用途
    • 最適化：例 最短輸送経路
    • モデリング：例 感染拡大・情報伝播
  • アルゴリズム：幅優先探索（BFS）
Pythonで学ぶネットワーク分析入門

幅優先探索（BFS）

  • 例：2ノード間の最短経路

十数個のノードを持つグラフ。間接的につながる2つのノードが強調表示されている。

Pythonで学ぶネットワーク分析入門

幅優先探索（BFS）

  • 例：2ノード間の最短経路

同じグラフ。強調ノードのうち一方の隣接ノードも強調されている。

Pythonで学ぶネットワーク分析入門

幅優先探索（BFS）

  • 例：2ノード間の最短経路

同じグラフ。すべての強調ノードの隣接ノードも強調されている。

Pythonで学ぶネットワーク分析入門

幅優先探索（BFS）

  • 例：2ノード間の最短経路

同じグラフ。既存の強調ノードのさらに隣接ノードも強調され、目的ノードに到達している。

Pythonで学ぶネットワーク分析入門

復習：隣接ノード

G

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

57

len(G.nodes())

20
Pythonで学ぶネットワーク分析入門

復習：隣接ノード

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]
Pythonで学ぶネットワーク分析入門

Let's practice!

Pythonで学ぶネットワーク分析入門

Preparing Video For Download...