IT

ITの世界は「グラフ」でできている

Y.Yoshi

• 3 min read
ITの世界は「グラフ」でできている

― インターネット・Google・SNS・サイバー攻撃を支える数学 ―

ITの世界では、多くのシステムが「グラフ」という数学的なモデルで説明できます。

実は次のようなものはすべて グラフ構造です。

  • インターネット
  • Google検索
  • SNS
  • サイバー攻撃の経路
  • AIの分析

本記事では、IT分野でグラフ理論がどのように使われているのかをわかりやすく解説します。

グラフ理論とは何か

まず、グラフ理論とは何かを簡単に説明します。

グラフとは

ノード（点） + エッジ（線）

で構成される構造です。

例：

A  ─  B
 \    /
   C

ここでは

  • A, B, C → ノード
  • 線 → エッジ

になります。

この構造は

「もの同士の関係」

を表すのに非常に便利です。

インターネットは巨大なグラフ

インターネットの構造は、まさに巨大なグラフです。

要素 グラフ
ルータ ノード
通信リンク エッジ

例えば次のようなネットワークを考えます。

RouterA ─ RouterB ─ RouterD
     \           　/
       \         /
         RouterC

ここで重要になるのが

どの経路で通信するのが一番効率的か

という問題です。

このとき使われるのが

最短経路アルゴリズム

です。

代表例は

ダイクストラ法（Dijkstra algorithm）

です。

このアルゴリズムは

  • OSPF
  • IS-IS

といった実際のルーティングプロトコルでも使われています。

つまり

インターネットは常にグラフ計算をしながら通信している

と言えます。

Google検索はグラフ理論が使われている

Webの世界もグラフ構造です。

要素 グラフ
Webページ ノード
リンク エッジ

Googleの初期検索アルゴリズム

PageRank

は、このグラフ構造を利用しています。

考え方はシンプルです。

「重要なページからリンクされているページは重要」

つまり

A → B
C → B
D → B

多くのページからリンクされている Bは重要なページと判断されます。

さらに、

重要なページからのリンクはより価値が高い

という考えも加わります。

ちなみに

PageRankのPageはWebページではなく
Google創業者 Larry Page の名前です。

SNSは巨大なソーシャルグラフ

SNSも典型的なグラフです。

要素 グラフ
ユーザー ノード
友達関係 エッジ

例えば

あなた
  |
友達A
  |
友達B

この場合

友達Bはあなたの「友達の友達」

になります。

SNSではこの関係を利用して

  • 知り合いかもしれません
  • フォローおすすめ
  • コミュニティ分析

などが行われています。

このような分析は

ソーシャルネットワーク分析

と呼ばれます。

サイバー攻撃もグラフで分析できる

セキュリティの世界でもグラフ理論は重要です。

例えば企業ネットワークを考えます。

PC → Active Directory → File Server → Database

攻撃者は

  • どの経路で侵入できるか
  • どの経路で権限昇格できるか

を探します。

これは

攻撃グラフ（Attack Graph）

と呼ばれます。

実際のツールとして

BloodHound

があります。

このツールは

Active Directoryの権限関係をグラフ化し、

どのユーザーから
どの管理者権限へ
最短で到達できるか

を可視化します。

つまり

サイバー攻撃の分析もグラフ探索問題

を含んでいると言えます。

AIの世界でもグラフが注目されている

最近のAI研究では

Graph Neural Network（GNN）

という技術が注目されています。

これは

グラフ構造を直接学習するAI

です。

例えば

分子構造

原子 ─ 原子
 |      |
原子 ─ 原子

ここでは

  • 原子 → ノード
  • 結合 → エッジ

になります。

この構造を学習することで

  • 新薬開発
  • 材料研究

などが進められています。

ITエンジニアが知っておきたいグラフアルゴリズム

IT分野で特によく使われるアルゴリズムは次の通りです。

アルゴリズム 用途
ダイクストラ法 最短経路
BFS（幅優先探索） ネットワーク探索
DFS（深さ優先探索） 経路探索
PageRank 検索順位
最小全域木 ネットワーク設計

これらは

  • ネットワーク
  • 検索エンジン
  • セキュリティ
  • AI

など多くの分野で使われています。

ダイクストラ法のわかりやすい動画
https://www.youtube.com/watch?v=X1AsMlJdiok

BFS・DFSのわかりやすい動画
https://www.youtube.com/watch?v=0_9heBS7Flg

最小全域木のわかりやすい動画（応用広い)
https://www.youtube.com/watch?v=qFvhC5ym3H4

まとめ

グラフ理論は、一見すると抽象的な数学ですが、

実際には

  • インターネット
  • Google検索
  • SNS
  • サイバー攻撃
  • AI

など、現代のITシステムの多くを支えています。

つまり

ITの世界は「関係性」の世界であり、
その関係性を表す最も自然なモデルがグラフなのです。

グラフ理論を理解すると、
普段使っているシステムの仕組みが、少し違って見えてくるかもしれません。