2023.11.22 2025.01.14

人やモノがつながる仕組みとは？ネットワークとグラフ理論の基礎

リプリパ編集部

「ネットワーク」と聞くと、インターネットや通信回線、交通網を思い浮かべる方が多いと思います。しかし、これらに限らず、身の回りには多種多様なネットワークが存在し、その特性を理解することで新しい規則性や関係性を発見できます。この記事では、ネットワークの基本概念から、グラフ理論の起源、さらに現代社会への応用まで幅広く紹介します。

ネットワークとは？基本をおさえよう

ネットワークとは、つながりを持つ要素の集まりを指します。友達同士のつながりや、コンピューター間の情報交換もネットワークの一例です。

ネットワークを構成する2つの要素：ノードとエッジ

ネットワークを理解する上で重要な要素が「ノード」」と「エッジ」です。ノードとはネットワーク内の個々のものや人を指していて、前述の例だと、友達やコンピューターがそれぞれノードに該当します。一方エッジとは、ノード同士を結ぶ線やつながりを指していて、友達同士のつながりや、コンピューター同士のつながりのことです。

ノード (Node)：ネットワーク内の個々の要素
エッジ (Edge)：ノード同士を結ぶつながり

ネットワークとは、一つのノードであるコンピューターから、エッジを通じて、別のノードであるコンピューターへ、情報やメッセージが伝わる様子として表現されます。また、SNSで友達同士がつながり、友達というノードを辿るエッジによって、さらに友達がつながったり、写真やメッセージを共有するのもネットワークの一例です。

ネットワークの基礎を築いた「グラフ理論」

ネットワーク科学の土台となる「グラフ理論」は、1735年にレオンハルト・オイラーによって提唱されました。さまざまな分野で何かの理論の起源を調べてみると、「諸説あり」というという言葉が散見されることが珍しくありません。しかし、ネットワーク科学の土台であるグラフ理論は、はっきりとその起源が分かっています。それが、「ケーニヒスベルクの7つの橋」問題です。

どうやったら、効率的に7つの橋を渡れるか？

1735年の東プロシアの首都で、商業で栄えたケーニスベルクという都市がありました。この都市は、中央を流れるプレーゲル川によって、クナイホフ（クナイ島）と呼ぶ中洲の島を含む4つの地区に分割されていました。

市の行政局は、それぞれの地区が行き来できるように、町を取り囲む川に7本の橋を架けました。このうち5本はクナイ島と本土を結び、2本は川の支流を跨ぐように架けられました。ケーニスベルクの4つの陸地と7本の橋の関係は以下の通りです。

18世紀の都市ケーニスベルクの概略図 — 18世紀の都市ケーニヒスベルクの概略図

この独特な構図から、『同じ橋を2回渡らずに、7つすべての橋を渡れるのか？』という難問が生まれました。この難問に対する解答は、数学者レオンハルト・オイラーによってもたらされました。オイラーは、それぞれが土地の区画と一致する4つのノードと、それぞれがその間の橋と一致する7つのエッジからなるネットワークを構成していることを示しました。そして、同じ橋を2回渡らずに7つの橋を渡る、ひと続きの経路が存在しないことも、数学的な方法で明らかにしました。

このオイラーの証明からグラフ理論が生まれ、ネットワークが科学へと発展していきました。リープリーパーには、数学的な土台であるグラフ理論の記事もあるので併せてご覧ください。

組織図やSNS、マッチング関係も！数学的に可視化するグラフ構造グラフ理論で描くグラフ構造は、関係や強弱を示したり、経路の判定・最適化などに使われる数学的概念です。組織図やソーシャルメディアのつながり、マッチングアプリのスコア評価など、実は身近なところで使われている様子を見てみましょう。

スモールワールド性と「6次の隔たり」

皆さんは、『知り合いの知り合いを6人辿れば、世界中の誰とでもつながる』という話を聞いたことがありますか？これは「6次の隔たり」とも呼ばれ、アメリカの心理学者のスタンレー・ミルグラムとジェフリー・トラバースによる、1967年の実験に由来しています。

6次の隔たりを示す手紙の転送実験

ミルグラムらは、カンザス州とネブラスカ州に住む、ランダムに選ばれた数十人の市民へ向けて手紙を送り、「マサチューセッツ州に住む株式仲買人へ手紙を転送するように」依頼しました。ただし、送り先の住所は教えず、目標の人物を知らない場合は、近しい人に転送するように勧めました。また、手紙の経路を辿れるように、「手紙を転送する時は、もう1通の手紙をミルグラム宛に送るように」指示しました。

その結果、最初に用意した手紙のうち1/3が目標の人物に届けられました。10回以上転送された手紙は1通もなく、平均の転送回数は6回でした。

この実験結果は、ネットワークの内の任意の2つのノード間の距離が、意外と短いことを意味しています。この性質は「スモールワールド性」と呼ばれ、ネットワークを理解する上で重要な性質です。

ネットワークの脆弱性：連鎖破綻とは？

現在、私たちはSNSを通じて世界中の人とつながることができ、膨大な情報を得られる恩恵を受けています。またリアルの世界でも、人とのつながりが多ければ多いほど、新しい出会いやビジネスチャンスが生まれます。これだけ聞くと、たくさんのつながりを持つことはいいことのように思えます。しかし、つながりすぎることで思わぬ悲劇を生むこともあります。

下の写真は、2003年8月14日にアメリカ北東部で発生した大規模停電の衛星写真です。左が停電前夜8月13日で、右が停電後の翌14日の衛星写真です。停電の主な原因は、送電管理システムがダウンしたことを発端に連鎖的に送電システムがダウンし、大規模な停電につながったとされています。

電力網のある変電所で局所的な停電が起きると、隣接する変電所の負荷が増えます。その追加負荷が取るに足らない程度であれば、その負荷を吸収できるため、停電が広がることはありません。しかし、負荷が隣接する変電所にとって過大な場合は、その変電所からそのまた隣の変電所へと、次々に追加負荷の影響が広がっていきます。このような現象は「連鎖破綻」と呼ばれています。