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 20, 2025
Science
0
140
データマイニング - グラフ構造の諸指標
1. グラフの大きさ
2. 密度
3. 連結性
4. 次数の分布
Y. Yamamoto
PRO
June 20, 2025
Tweet
Share
More Decks by Y. Yamamoto
See All by Y. Yamamoto
データベース15: ビッグデータ時代のデータベース
trycycle
PRO
0
270
データベース14: B+木 & ハッシュ索引
trycycle
PRO
0
360
データマイニング - グラフ埋め込み入門
trycycle
PRO
0
46
データマイニング - ウェブとグラフ
trycycle
PRO
0
130
データベース12: 正規化(2/2) - データ従属性に基づく正規化
trycycle
PRO
0
840
データマイニング - コミュニティ発見
trycycle
PRO
0
120
データベース11: 正規化(1/2) - 望ましくない関係スキーマ
trycycle
PRO
0
820
データマイニング - ノードの中心性
trycycle
PRO
0
230
データベース10: 拡張実体関連モデル
trycycle
PRO
0
860
Other Decks in Science
See All in Science
オンプレミス環境にKubernetesを構築する
koukimiura
0
290
システム数理と応用分野の未来を切り拓くロードマップ・エンターテインメント(スポーツ)への応用 / Applied mathematics for sports entertainment
konakalab
1
350
baseballrによるMLBデータの抽出と階層ベイズモデルによる打率の推定 / TokyoR118
dropout009
1
520
Transport information Geometry: Current and Future II
lwc2017
0
170
生成AI による論文執筆サポートの手引き(ワークショップ) / A guide to supporting dissertation writing with generative AI (workshop)
ks91
PRO
0
510
[第62回 CV勉強会@関東] Long-CLIP: Unlocking the Long-Text Capability of CLIP / kantoCV 62th ECCV 2024
lychee1223
1
960
白金鉱業Meetup Vol.16_数理最適化案件のはじめかた・すすめかた
brainpadpr
4
1.8k
高校生就活へのDA導入の提案
shunyanoda
0
1.9k
動的トリートメント・レジームを推定するDynTxRegimeパッケージ
saltcooky12
0
160
統計学入門講座 第3回スライド
techmathproject
0
110
モンテカルロDCF法による事業価値の算出(モンテカルロ法とベイズモデリング) / Business Valuation Using Monte Carlo DCF Method (Monte Carlo Simulation and Bayesian Modeling)
ikuma_w
0
210
CV_5_3dVision
hachama
0
140
Featured
See All Featured
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.8k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
229
22k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
Statistics for Hackers
jakevdp
799
220k
The World Runs on Bad Software
bkeepers
PRO
70
11k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
760
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
138
34k
A designer walks into a library…
pauljervisheath
207
24k
4 Signs Your Business is Dying
shpigford
184
22k
Building Applications with DynamoDB
mza
95
6.5k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Transcript
グラフ構造の諸指標 ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科
[email protected]
第10回 データマイニング (グラフ分析入門) ⼭本祐輔
クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
グラフを「把握したい」ケース グラフを把握したい ノード 単体 グラフの 部分構造 グラフ 全体
グラフを「把握したい」ケース グラフを把握したい ノード 単体 グラフの 部分構造 グラフ 全体 ノードの 重要度評価
コミュニティや 特徴的な経路の発⾒ 局所的特徴 ⼤局的特徴
グラフを「把握したい」ケース グラフを把握したい グラフ 全体 ノードの 重要度評価 コミュニティや 特徴的な経路の発⾒ 局所的特徴 ⼤局的特徴
はじめにグラフ全体の特徴を理解することは重要 ノード 単体 グラフの 部分構造
グラフの⼤きさを⽰す指標: ノード数 グラフに含まれるノードの数 1 0 2 3 4 5 |
V | = 6 # NetworkXを使う場合 V = G.nodes() len(V) # 以下でもOK G.number_of_nodes()
グラフの⼤きさを⽰す指標: 直径 (diameter) グラフに属するノード間の距離の最大値 1 0 2 3 4 5
(最も離れているノード同⼠の距離) 1 0 4 2 3 5 d = 3 d = 1
グラフの⼤きさを⽰す指標: 直径 (diameter) d = ? グラフに属するノード間の距離の最大値 (最も離れているノード同⼠の距離) 1 0
4 2 3 5
グラフの⼤きさを⽰す指標: 直径 (diameter) d = 3 グラフに属するノード間の距離の最大値 (最も離れているノード同⼠の距離) 1 0
4 2 3 5 # NetworkXを使う場合 nx.diameter(G)
余談: 離⼼数 (eccentricity) 注目ノードから他ノードへの距離の最大値 1 0 2 3 4 5
ノード0の離⼼数 = 3 1 0 2 3 4 5 ノード2の離⼼数 = 2 グラフの直径とは「グラフ中のノード離心数の最大値」
グラフの⼤きさを⽰す指標: 半径 (radius) グラフに属するノードの離心数の最小値 1 0 2 3 4 5
1 0 4 2 3 5 半径r = 2 r = 1 (直径d = 3) (直径d = 1)
グラフの⼤きさを⽰す指標: 半径 (radius) r = ? 1 0 4 2
3 5 グラフに属するノードの離心数の最小値
グラフの⼤きさを⽰す指標: 半径 (radius) r = 3 グラフに属するノードの離心数の最小値 1 0 4
2 3 5 # NetworkXを使う場合 nx.radius(G)
グラフの密度 (density) グラフ中のノード間に張ることのできる すべての辺に対する、実際の辺の数の割合 1 0 2 3 4 5
ノード集合をV、 エッジ集合をEとすると = | E | | V | C2 密度 密度 = ! "#$ nx.density(G) # NetworkXを使う場合
グラフの密度 (density) グラフ中のノード間に張ることのできる すべての辺に対する、実際の辺の数の割合 密度 = ! !"# = 0.4
1 0 4 2 3 5 1 0 4 2 3 5 密度 = 1
完全グラフ(complete graph) グラフ中の全ノード間にエッジが張られている グラフを完全グラフと呼ぶ 1 0 4 2 3 5
密度 = 1
連結性 グラフ中の任意のノード間に経路が存在する とき、そのグラフは「連結グラフ」という 1 0 4 2 3 5 連結グラフ
1 0 4 2 3 5 ⾮連結グラフ
連結性 グラフ中の任意のノード間に経路が存在する とき、そのグラフは「連結グラフ」という 1 0 4 2 3 5 連結グラフ
nx.is_connected(G) # NetworkXを使う場合 # 左のグラフにはTrueを返す
強連結 有向グラフ中の任意のノード間に有向経路が 存在するとき、そのグラフは「強連結」である 1 0 4 2 3 5 強連結である
1 0 4 2 3 5 強連結でない
強連結 有向グラフ中の任意のノード間に有向経路が 存在するとき、そのグラフは「強連結」である 1 0 4 2 3 5 強連結である
nx.is_strongly_connected(G) # NetworkXを使う場合 # 左のグラフにはTrueを返す
次数分布 次数 (degree) ノードに接続しているエッジの数 次数分布 § グラフに属するノードの次数の分布 § ⼤きさや密度が同じでも次数分布が異なることもある 1
0 2 3 4 ノード2の次数 = 3 ノード4の次数 = 1
次数分布 次数 (degree) ノードに接続しているエッジの数 次数分布 § グラフに属するノードの次数の分布 § ⼤きさや密度が同じでも次数分布が異なることもある 1
0 2 3 4 G.degree[2] # NetworkXを使う場合 # ノード2の次数(=3)を返す
同じノード数,密度を持つのに次数分布が異なるグラフの例
Hands-on タイム 以下のURLにアクセスして, 第10回のクイズを解いてみよう https://graphnote.hontolab.org/ 23
回 実施日 トピック 9 06/13 グラフデータ 10 06/20 グラフ構造の諸指標 11
06/27 ノードの中心性 12 07/04 コミュニティ発見 13 07/11 ウェブグラフ 14 07/18 グラフ埋め込み 15 07/25 総合演習 – 社会ネットワーク分析 授業計画 24