人やモノのつながる仕組みはコレだ！ネットワークとグラフ理論

「ネットワーク」と聞くと、インターネットや通信回線などを思い浮かべる方が多いと思います。実はこれらだけでなく、身の回りにはたくさんのネットワークがたくさんあり、ネットワークの特性を理解することで、物事の新しい規則性を発見できます。今回の記事では、ネットワークの例をいくつか見ながら、皆さんと一緒にネットワークの理解を深めようと思います。

そもそも「ネットワーク」って？

ネットワークとは、つながりのある要素の集まりです。例えば、友達と友達、コンピューターとコンピューターが互いに情報をやりとりするのも、ネットワークの例です。

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

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

ネットワークの土台は数学？

さまざまな分野で何かの理論の起源を調べてみると、「諸説あり」という言葉 が散見されることが珍しくありません。しかし、ネットワーク科学の土台である「グラフ理論」は、はっきりとその起源が分かっています。

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

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

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

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

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

イッツ ア スモール ワールド！6人とつながれば、世界中のみんなと友達！？

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

彼らは、ランダムに選ばれたアメリカのカンザス州とネブラスカ州に住む、数十人の市民へ向けて手紙を送りました。手紙の中で、マサチューセッツ州に住む株式仲買人へ手紙を転送するように依頼しました。その際、目標の人物の住所は教えませんでした。もし目標の人物を知らない場合は、目標の人物と近しい人に転送するように勧めました。また、手紙の経路を辿れるように、『手紙を転送する時は、もう1通の手紙をミルグラム宛に送らなければならない』としました。その結果、最初に用意した手紙のうち1/3が目標の人物に届けられました。途中で10回より多く転送されたものは1通もなく、転送の回数の平均が6回でした。

6次の隔たりは、ネットワークの内の任意の2つのノード間の距離は、思いもよらないほど小さいということを意味しています。 この性質は、「スモールワールド性」と呼ばれ、ネットワークを理解する上で重要な性質です。

つながりすぎるのは諸刃の剣？

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

下の写真は、2003年8月14日にアメリカ北東部で発生した大規模停電の衛星写真です。左が停電前夜8月13日で、右が停電後8月14日の衛星写真です。停電の主な原因は、送電管理システムがダウンしたことを発端に連鎖的に送電システムがダウンし、大規模な停電につながったとされています。電力網のある変電所で局所的な停電が起きると、隣接する変電所の負荷が増えます。その追加負荷が取るに足らない程度であれば、その負荷を吸収できるため、停電が広がることはありません。しかし、負荷が隣接する変電所にとって過大な場合は、その変電所からそのまた隣の変電所へと、次々に追加負荷の影響が広がっていきます。このような現象は「連鎖破綻」と呼ばれています。

外部リンク

2003年北アメリカ、世界の大停電

2003年8月14日、アメリカ北東部とカナダ南東部で大停電が発生し、交通機関が麻痺したニューヨークでは多くの帰宅者がブル...

URLhttps://natgeo.nikkeibp.co.jp/nng/article/news/14/6682/

この連鎖破綻を避けるには、次の3つのことが重要です。

• 連鎖破綻を起こすネットワーク構造を理解する
• ネットワーク上で起きる動的なプロセスをモデル化する
• ネットワークの構造とダイナミクスの相互作用の影響を明らかにする

つながり合うことは便利なことですが、その反面ネットワークには脆弱性も持ち合わせています。このような脆弱性を理解し抑制するためにも、ネットワーク科学の発展は非常に重要です。

身の回りのアレもコレも、実はネットワーク！

今回の記事では、ネットワークの基本的な概念や起源、ネットワークに関する実験と事件について紹介しました。これ以外にも、実は日常にはネットワークが隠れています。世界のいろいろなことをネットワークの視点から捉え、その特性を理解することで、新しい規則性を発見できます。皆さんも、身の回りのネットワークを探してみてはいかがでしょうか。

福田 慎一郎

ワイン大好き社会人

2021年BlueMemeに新卒で入社。2023年10月からネットワークの統計解析に関する研究開発業務に携わっています。2024年4月から九州大学大学院システム生命科学府に社会人博士学生として入学。科学とアートが好きで、休みの日は美術館や博物館によく行きます。入社してからワインにはまりました。
福田 慎一郎の記事一覧