Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
データマイニング - グラフデータと経路
Search
Y. Yamamoto
PRO
June 13, 2025
Science
1
180
データマイニング - グラフデータと経路
1. グラフとは
2. 経路
Y. Yamamoto
PRO
June 13, 2025
Tweet
Share
More Decks by Y. Yamamoto
See All by Y. Yamamoto
データベース14: B+木 & ハッシュ索引
trycycle
PRO
0
340
データマイニング - グラフ埋め込み入門
trycycle
PRO
0
38
データマイニング - ウェブとグラフ
trycycle
PRO
0
110
データベース12: 正規化(2/2) - データ従属性に基づく正規化
trycycle
PRO
0
790
データマイニング - コミュニティ発見
trycycle
PRO
0
110
データベース11: 正規化(1/2) - 望ましくない関係スキーマ
trycycle
PRO
0
760
データマイニング - ノードの中心性
trycycle
PRO
0
210
データベース10: 拡張実体関連モデル
trycycle
PRO
0
810
データマイニング - グラフ構造の諸指標
trycycle
PRO
0
130
Other Decks in Science
See All in Science
オンプレミス環境にKubernetesを構築する
koukimiura
0
290
動的トリートメント・レジームを推定するDynTxRegimeパッケージ
saltcooky12
0
160
KH Coderチュートリアル(スライド版)
koichih
1
43k
Transport information Geometry: Current and Future II
lwc2017
0
160
SpatialBiologyWestCoastUS2024
lcolladotor
0
140
生成AIと学ぶPythonデータ分析再入門-Pythonによるクラスタリング・可視化をサクサク実施-
datascientistsociety
PRO
4
1.6k
地表面抽出の方法であるSMRFについて紹介
kentaitakura
1
770
02_西村訓弘_プログラムディレクター_人口減少を機にひらく未来社会.pdf
sip3ristex
0
520
LayerXにおける業務の完全自動運転化に向けたAI技術活用事例 / layerx-ai-jsai2025
shimacos
2
1.3k
03_草原和博_広島大学大学院人間社会科学研究科教授_デジタル_シティズンシップシティで_新たな_学び__をつくる.pdf
sip3ristex
0
510
地質研究者が苦労しながら運用する情報公開システムの実例
naito2000
0
220
CV_3_Keypoints
hachama
0
190
Featured
See All Featured
Facilitating Awesome Meetings
lara
54
6.5k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
126
53k
How STYLIGHT went responsive
nonsquared
100
5.6k
Gamification - CAS2011
davidbonilla
81
5.4k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Building Flexible Design Systems
yeseniaperezcruz
328
39k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.4k
The Cost Of JavaScript in 2023
addyosmani
51
8.6k
Navigating Team Friction
lara
187
15k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
50
5.5k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Transcript
グラフデータ ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科
[email protected]
第9回 データマイニング (グラフ分析入門) ⼭本祐輔
クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
クエスチョン Q. 「グラフ」と聞いて 思い浮かべるものは?
グラフと⾔えば グラフ グラフ チャート データ構造 CS/DSに学んだ人で「右」のグラフが頭によぎらないのはマズい…
「データ構造」としてのグラフ § “点”と “ つながり”によって表されるデータ § 事物間の関係性を抽象化する強⼒なデータ構造 § “ネットワーク”と呼ぶことも
グラフデータの例(1/5)- ウェブページのリンク
グラフデータの例(1/5)- ウェブページのリンク
グラフデータの例(2/5)- ⼈物関係 画像出典: https://ebookjapan.yahoo.co.jp/content/author/243/ Aさん Bさん Cさん Dさん Eさん 友⼈関係
グラフデータの例(2/5)- ⼈物関係 画像出典: https://ebookjapan.yahoo.co.jp/content/author/243/ Aさん Bさん Cさん Dさん Eさん M
F O A L D 対⽴ 恋 恋 恋 友 婚姻 C A B E D
グラフデータの例(3/5) - 路線図 画像出典: https://www.kotsu.city.nagoya.jp/jp/pc/subway/routemap.html
グラフデータの例(4/5) - 購買・出版 ユーザA ユーザB い ろ は に ほ
出版社X 出版社Y 出版社Z 出版 出版 出版 購⼊ 購⼊ 購⼊
グラフデータの例(5/5) 画像出典2: https://www.researchgate.net/ 画像出典1: https://commons.wikimedia.org/ 分⼦構造 化学反応
関係性を表すデータはグラフとして抽象化できる ウェブ構造 分⼦構造・化学反応 経路情報 購買・製造情報 グラフ化 グラフ化 抽象化の目を養えば,グラフデータは身近にあることが分かる!!
グラフデータに抽象化するとできること グラフの中での点の重要度を評価できる グラフ中の特徴的なグループを発見できる グラフ中の点同士の関係性を評価・予測できる グラフの構造を定量的に分析できる 橋渡し役の点,多くの点と繋がっている点の発⾒etc. コミュニティの発⾒,分極している点群の発⾒etc. 点同⼠をつなぐ最短経路の発⾒,点と点がつながる可能性の予測etc. グラフ全体の特徴の評価,頻出する関係(つながり)の発⾒etc.
グラフの定義 1 Definition of Graph
グラフ § 事物間の関係性を抽象化する強⼒なデータ構造 § “点”と “ つながり”によって表されるデータ ノード エッジ
グラフの数学的定義 グラフを構成する要素 ノード (頂点; vertex) ノード間の連結関係 エッジ (枝; edge) グラフ(graph)
ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
グラフの数学的定義 グラフを構成する要素 ノード (頂点; vertex) ノード間の連結関係 エッジ (枝; edge) グラフ(graph)
ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
グラフの数学的定義 グラフを構成する要素 ノード (頂点; vertex) ノード間の連結関係 エッジ (枝; edge) グラフ(graph)
ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
グラフの数学的な定義の例 G = (V, E) V = {1, 2, 3,
4, 5, 6} E = {(1, 2), (2, 3), (4, 3), (3, 5), (4, 6), (5, 6)} ノード集合→ エッジ集合→ 2 3 4 1 5 6
有向グラフと無向グラフ 2 3 4 1 5 6 有向グラフ エッジに⽅向性がある 2
3 4 1 5 6 無向グラフ エッジに⽅向性がない (双⽅向に関係があるとも⾔える)
重み付きグラフ 名古屋 京都 ⼤阪 ⾦沢 東京 40分 90分 150分 100分
25分 グラフはエッジに重みを設定することが可能 例: 移動コスト, 関係の強さ 本講義では断りがない限り,枝の重みは考えない
NetworkX グラフの処理のためのPythonライブラリ NetworkX ⾏列計算の 効率化 汎⽤機械学習 汎⽤機械学習 グラフ深層学習
例題1 以下の有向グラフをNetworkXで定義してみよう 2 4 3 1 0
グラフの定義 on NetworkX import networkx as nx コード中で頻繁にnetworkxライブラリを参照 するので,短い名前でアクセスできるように 略称を付けておく
2 4 3 1 0
グラフの定義 on NetworkX import networkx as nx V = [0,
1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] ← ノードの定義 ← エッジの定義 2 4 3 1 0
グラフの定義 on NetworkX import networkx as nx V = [0,
1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.DiGraph() G.add_nodes_from(V) G.add_edges_from(E) ← 空の有向グラフを⽤意 ← ノード, エッジの追加 2 4 3 1 0
グラフの定義 on NetworkX import networkx as nx V = [0,
1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.DiGraph() G.add_nodes_from(V) G.add_edges_from(E) nx.draw(G) ← グラフの可視化 2 4 3 1 0
例題2 以下の無向グラフをNetworkXで定義してみよう 2 4 3 1 0
無向グラフの定義 on NetworkX import networkx as nx V = [0,
1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.Graph() G.add_nodes_from(V) G.add_edges_from(E) nx.draw(G) 2 4 3 1 0 ← 無向グラフはDiGraphではなくGraph
ノード,エッジの確認 on NetworkX V = G.nodes() 2 4 3 1
0 ← グラフGのノード集合にアクセス E = G.edges() ← グラフGのノード集合にアクセス for e in E: print(e) ← エッジ集合をひとつずつ確認
隣接⾏列 (Adjacency Matrix ) (1/4) § グラフにおけるノードの接続関係を⽰す⾏列 § N個のノードを持つグラフの隣接⾏列のサイズは(N, N)
隣接⾏列は正⽅⾏列!! 2 4 3 1 0 𝐴 = 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0
隣接⾏列 (Adjacency Matrix ) (2/4) 2 4 3 1 0
𝐴 = 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 重みなしグラフの場合 隣接⾏列のa⾏b列の要素が1 → a番⽬のノードからb番⽬の要素へのエッジが存在する 隣接⾏列のa⾏b列の要素が0 → a番⽬のノードからb番⽬の要素へのエッジが存在しない 0⾏⽬ 1列⽬ ノード0から ノード1へのエッジが存在
隣接⾏列 (Adjacency Matrix ) (3/4) 2 4 3 1 0
𝐴 = 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 重みなしグラフの場合 隣接⾏列のa⾏b列の要素が1 → a番⽬のノードからb番⽬の要素へのエッジが存在する 隣接⾏列のa⾏b列の要素が0 → a番⽬のノードからb番⽬の要素へのエッジが存在しない 無向グラフの場合,隣接行列は対称行列になる
隣接⾏列 (Adjacency Matrix ) (4/4) 𝐴 = 0 1 0
0 0 1 0 3 0 0 0 0 0 0 0.5 0 8 0 0 0 0 0 2 0.5 0 重み付きグラフの場合 a番⽬のノードからb番⽬の要素へのエッジが存在する場合 → 隣接⾏列のa⾏b列の要素の値は重みの値 a番⽬のノードからb番⽬の要素へのエッジが存在しない場合 → 隣接⾏列のa⾏b列の要素の値はゼロ 2 4 3 1 0 1 3 0.5 0.5 2 8
隣接⾏列の取得 on NetworkX 2 4 3 1 0 import networkx
as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 2), (2, 4), (3, 1), (4, 3)] G = nx.Graph() G.add_nodes_from(V) G.add_edges_from(E) A = nx.adjacency_matrix(G).toarray() NumPy形式に変換 neighbors_from_1 = list(G.neighbors(1)) ノード1の隣接ノード
Hands-on タイム 以下のURLにアクセスして, 第9回のクイズQ1を解いてみよう https://graphnote.hontolab.org/ 36
経路 2 Path
経路 2 4 3 1 0 § グラフ上のエッジをたどって,あるノードから 別ノードに移動する際に通るノードの系列 §
ノード間の経路が複数ある場合もある ノード4からノード2への経路 (4, 2) (4, 3, 1, 2) …
到達可能性 ノード nx からノード ny への経路が存在するとき nx から ny へ到達可能という
ノード0からノード3へは 到達可能 ノード3からノード0へは 到達不可能 2 4 3 1 0
隣接⾏列と到達可能性(1/4) 2 4 3 1 0 𝐴 = 0 1
0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 重みなし行列の場合,隣接行列のべき乗を 計算することで到達可能性を調べられる
隣接⾏列と到達可能性(2/4) 2 4 3 1 0 𝐴2 = 0 1
0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 ノード0が接続しているノード ノード2に 接続しているノード
隣接⾏列と到達可能性(3/4) 2 4 3 1 0 𝐴2 = 0 0
1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 ノード0から2ホップで 到達できるノード
隣接⾏列と到達可能性(4/4) 2 4 3 1 0 𝐴3 = 0 0
0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 2 1 0 ノード4から3ホップで 到達できるノード ノード4からノード2へは 経路が2つあることを意味
Hands-on タイム 以下のURLにアクセスして, 第9回のクイズQ2を解いてみよう https://graphnote.hontolab.org/ 44
距離 ノード nx からノード ny への最短経路の長さ (or エッジの重み合計)を距離と呼ぶ 2 4
3 1 0 ノード4からノード2へは 最短経路は(4, 2) ノード4からノード2への 距離は1
距離⾏列 グラフに属する全ノード間の距離を表記した行列 2 4 3 1 0 𝐷 = 0
1 2 4 3 ∞ 0 1 3 2 ∞ 3 0 2 1 ∞ 1 2 0 3 ∞ 2 1 1 0 たどり着けない ノードの距離は∞ ノード1から ノード3への距離は3
[参考] 最短経路発⾒や距離計算のための効率的なアルゴリム 幅優先探索 重みなしグラフ限定で効率的 ダイクストラ法 指定したノードから他の全ノードへの最短経路を⾼速に探索 ワーシャルフロイド法 グラフに属する全ノード間の最短経路を⾼速に探索 行列のべき乗計算はグラフが大きくなるとコストが大きい…
最短経路アルゴリズム on NetworkX shortest_paths = dict( nx.single_source_all_shortest_paths(G, 3) ) all_shortest_paths
= dict( nx.all_pairs_shortest_paths(G) ) D = nx.floyd_warshall_numpy(G) # ワーシャルフロイド法で距離⾏列を計算 # ダイクストラ法で全ノード間の最短経路を取得 # ダイクストラ法でノード3から他ノードへの最短経路を取得
Hands-on タイム 以下のURLにアクセスして, 第9回のクイズQ3を解いてみよう https://graphnote.hontolab.org/ 49
回 実施日 トピック 9 06/13 グラフデータ 10 06/20 グラフ構造の諸指標 11
06/27 ノードの中心性 12 07/04 コミュニティ発見 13 07/11 ウェブグラフ 14 07/18 グラフ埋め込み 15 07/25 総合演習 – 社会ネットワーク分析 授業計画 50