Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
データマイニング - グラフ構造の諸指標
Search
Y. Yamamoto
PRO
June 20, 2025
Science
570
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
データマイニング - グラフ構造の諸指標
1. グラフの大きさ
2. 密度
3. 連結性
4. 次数の分布
Y. Yamamoto
PRO
June 20, 2025
Transcript
25 slides
グラフ構造の諸指標 ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科
[email protected]
第10回 データマイニング (グラフ分析入門) ⼭本祐輔
クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
講義資料 https://b.hontolab.org/graph-analysis
グラフを「把握したい」ケース グラフを把握したい ノード 単体 グラフの 部分構造 グラフ 全体
グラフを「把握したい」ケース グラフを把握したい ノード 単体 グラフの 部分構造 グラフ 全体 ノードの 重要度評価
コミュニティや 特徴的な経路の発⾒ 局所的特徴 ⼤局的特徴
グラフを「把握したい」ケース グラフを把握したい グラフ 全体 ノードの 重要度評価 コミュニティや 特徴的な経路の発⾒ 局所的特徴 ⼤局的特徴
はじめにグラフ全体の特徴を理解することは重要 ノード 単体 グラフの 部分構造
グラフの⼤きさを⽰す指標: ノード数 グラフに含まれるノードの数 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/ 24
授業計画 25 回 トピック 9 グラフデータ 10 グラフ構造の諸指標 11 ノードの中心性
12 コミュニティ発見 13 ウェブとグラフ 14 グラフ埋め込み 15 総合演習 – 社会ネットワーク分析
More Decks by Y. Yamamoto
See All by Y. Yamamoto
データベース15: ビッグデータ時代のデータベース
trycycle
PRO
1
620
データベース14: B+木 & ハッシュ索引
trycycle
PRO
0
1k
データベース12: 正規化(2/2) - データ従属性に基づく正規化
trycycle
PRO
0
1.9k
データベース11: 正規化(1/2) - 望ましくない関係スキーマ
trycycle
PRO
0
1.8k
データベース10: 拡張実体関連モデル
trycycle
PRO
0
1.6k
データベース09: 実体関連モデル上の一貫性制約
trycycle
PRO
0
1.9k
機械学習 - ニューラルネットワーク入門
trycycle
PRO
0
1.4k
データベース08: 実体関連モデルとは?
trycycle
PRO
0
1.7k
機械学習 - SVM
trycycle
PRO
2
1.3k
Other Decks in Science
See All in Science
プレイがつなぐ研究と社会:市⺠‧クリエイター‧SF作家による実践を通じて
hayataka88
1
140
20260820_アウトカムが二値のデータに対するCausal Impact@LINEヤフー Data Science Share #2 / Causal Impact for Binary Outcomes
brainpadpr
3
1.6k
人工知能のための哲学塾 ニューロフィロソフィ篇 第一夜 「無著、世親と唯識のはじまり、ニューラルネットワークのはじまり」
miyayou
0
150
20260722【JAWS-UG東京 ランチタイムLT会 #37④】AWS Well-Architectedフレームワークに沿った回答をするAIエージェントを作ってみた
nozakijcom
1
170
JPA2026_NetworkSymposium_Overview
junkashihara
0
130
Conwayの法則を"ちゃんと"使うために — 原典でConwayは何を言っていたのか
bonotake
10
7.9k
生成AI時代のインタラクションサイエンス(招待講演)/interaction-science
okana2ki
0
130
サンプル対応のない複数遺伝子発現プロファイルに対するテンソル分解型統合解析の要約
tagtag
PRO
0
300
[Relay webinaire eBIS actu n°16] Sélection pour la vitalité des jeunes bovins allaitants et laitiers
institutdelelevage
PRO
0
370
Toward Causal Scientific Discovery with AI
sshimizu2006
0
250
J-STAGE全文XML登載必須化について
xspa2012
0
1.7k
AlgorithAlgorihms for Decision Making
mickey_kubo
0
200
Featured
See All Featured
Taking LLMs out of the black box: A practical guide to human-in-the-loop distillation
inesmontani
PRO
3
2.5k
The Organizational Zoo: Understanding Human Behavior Agility Through Metaphoric Constructive Conversations (based on the works of Arthur Shelley, Ph.D)
kimpetersen
PRO
0
540
Impact Scores and Hybrid Strategies: The future of link building
tamaranovitovic
0
490
The World Runs on Bad Software
bkeepers
PRO
72
12k
The Cost Of JavaScript in 2023
addyosmani
56
10k
Believing is Seeing
oripsolob
1
280
A Guide to Academic Writing Using Generative AI - A Workshop
ks91
PRO
1
570
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Practical Orchestrator
shlominoach
192
12k
Leo the Paperboy
mayatellez
11
2.5k
Chasing Engaging Ingredients in Design
codingconduct
0
400
SEO Brein meetup: CTRL+C is not how to scale international SEO
lindahogenes
2
3k