用語集

左側のキーワードの1つを選択…

日常生活のグラフ

読書の時間: ~5 min
このページは自動翻訳されているため、エラーが含まれている可能性があります。翻訳のレビューをご希望の場合はご連絡ください。

以前の章ではグラフ理論の多くの異なるアプリケーションを見てきましたが、それらのいくつかは少し工夫されていました。しかし、グラフは日常生活における多くのオブジェクト、概念、プロセスの基礎になっていることがわかります。

たとえば、インターネットは広大な仮想グラフです。すべての頂点は個別のWebページであり、すべてのエッジは2つのページ間にハイパーリンクがあることを意味します。このグラフがられるように、リンクが唯一、1つの道を行くことに注意してくださいこのグラフは_非常に、非常に、大きい_こと。

ウィキペディアやFacebookなどの一部のWebサイトには多数の受信リンクがありますが、多くの小さなWebサイトには受信リンクがほとんどない場合があります。これは、Googleが検索結果の並べ替えに使用する基本的な概念です。

着信リンクの多いWebサイトは品質が高くなる傾向があり、検索結果の上部に表示されます。たとえば、「ロンドン」を検索すると、ロンドンの小さなお店やロンドンに住んでいる人のブログの前に公式の観光情報サイトが表示されます。グラフ理論のこの単純なアイデアであるページランクアルゴリズムは 、Googleを他の初期の検索エンジンよりも大幅に優れたものにしました。

インターネットは人類がこれまでに作成した最大のネットワークです。この画像は、インターネットに接続されているすべてのサーバーのごく一部を示しています。

© LyonLabs, LLC and Barrett Lyon, 2014

ウェブサイトとハイパーリンクは_仮想_グラフを形成しますが、コンピューター、サーバー、ルーター、電話回線、ケーブルの_物理_ネットワークもあります。

ネットワークオペレーターは、電話をかけたりWebサイトを読み込んだりするたびに、個々のケーブルや接続の容量を超えずに、送信者と受信者を接続する方法を見つける必要があります。グラフの理論と確率により、たとえば特定の接続がビジーであるときに宛先変更を見つけることにより、信頼できるサービスを保証することが可能になります。

グラフは、輸送やナビゲーションにおいても重要な役割を果たします。すべてのフライト、電車、地下鉄のネットワークはグラフを形成し、効率的なスケジュールを作成するときに使用できます。最もわかりやすいグラフの1つはロンドン地下鉄マップです。

すべての道路と高速道路も大きなネットワークを形成しており、これはGoogleマップなどのナビゲーションサービスで、指定された2点間の最短ルートを求めるときに使用されます。

将来的には、 Intelligent Transportation Systemsは、スマートフォンや自動運転車から収集された位置データを使用して、より効率的に車をルーティングすることにより、渋滞や事故を減らします。これにより、毎年何百万時間もの道路での損失を節約し、汚染を大幅に削減し、緊急サービスをより速く移動させることができます。

この画像は、北ヨーロッパを横断する民間航空会社のフライトのネットワークを示しています。

科学、工学、日常生活には他にも無数のグラフがあります。

分子内の原子と結晶グリッド間のリンクがグラフを形成します。

病気や伝染病の蔓延は、ネットワークを使用してモデル化できます。

生物学では、種の祖先を示す進化の木がグラフを形成します。

電気回路とコンピューターチップのさまざまなコンポーネントがネットワークを形成しています。

言語の文法構造は、たとえば翻訳アルゴリズムを作成するために、グラフを使用してモデル化できます。

グラフは、 確率ゲーム理論金融数学においても多くの用途があります。

ソーシャルネットワーク

最後に、日常生活に存在するグラフの特に良い例、ソーシャルメディアについて考えてみましょう。ここで、頂点は表しますとエッジは、友情、いいね、購読、フォロワーを表します。

ソーシャルメディアのグラフを描くと、同じ学校に行ったり同じ都市に住んだりしている、相互の友人の特定のクラスターが表示される場合があります。また、頂点がどれほど適切に接続されているかに依存し、ソーシャルメディアでの個人の人気の尺度となる可能性がある、人々の中心性を判断することもできます。

2014年のFacebookのアクティブユーザーは14億人で、合計で2,000億人を超える友情がありました。 Facebookユーザーの半数には200人を超える友達がいて、ほとんどの友達は同数の友達を持っているため、簡単に何万人もの友達ができます

エキサイティングな質問は次のようになります。ランダムなFacebookユーザーを2人選んだ場合、一方から他方に移動するためにいくつの「友情のエッジ」に従う必要があるでしょうか。たとえば、友達同士の距離は 、友達同士の距離はなどです。

Facebookは2016年に、ユーザー同士のつながり方を調査しました。彼らは、平均して、あなたはFacebook上の_他の誰か_と最大で3.57人の人々を通じてつながっていることを発見した。そして、これには有名人、政治家、さらには王族さえ含まれます!

言い換えれば、世界中の何十億ものFacebookユーザーのいずれかを選択した場合、おそらく友達の友達を知っている友達の友達がいることになります。 3.57 度の分離があると言います。

Geographic visualisation of all Facebook friendships in 2010.

1929年にハンガリーの作家Frigyes Karinthyが最初に「6度の分離」のアイデアを提案したとき、インターネットやソーシャルメディアはありませんでしたが、世界はすでにより相互につながり始めていました。

1967年、 スタンリーミルグラムは最初の実証実験を行いました。ネブラスカとカンザスに住む296人の参加者は、マサチューセッツ州ボストンに住む特定の人に手紙を送るように求められました。彼らは全員、手紙を送る友人を選ばなければならず、その友人が別の友人を選んだ。すべての段階で、手紙はボストンに近づきました。ミルグラムは、平均して5.2人の中間の友人しかいないことを発見しました。分離度は5.2度です。

今日、私たち一人ひとりが、数え切れないほどの目に見えないグラフの一部になっています。このグラフは、私たちの社会的相互作用、旅行、インターネットとテクノロジー、科学などの根底にあります。

Archie