グラフ理論だけでは不十分です。

頂点（ドット）とエッジ（それらを接続する線）などのネットワークに通常依存する接続について話すための数学的言語は、少なくとも18世紀以来、現実世界の現象をモデル化するための非常に貴重な方法でした。 しかし、数十年前、巨大なデータセットの出現により、研究者はツールボックスを拡張することを余儀なくされ、同時に、新しい数学的洞察を適用するための広大なサンドボックスを提供しました。 それ以来、言った ジョシュ・グロチョウコロラド大学ボルダー校のコンピューター科学者である、研究者がビッグデータのノイズの中で複雑な構造や信号を見つけることができる新しい種類のネットワークモデルを開発したため、急速な成長の刺激的な時期がありました。

Grochowは、ビッグデータのつながりを見つけることになると、グラフ理論には限界があると指摘する研究者の増加する合唱のXNUMXつです。 グラフは、すべての関係をダイアドまたはペアワイズ相互作用として表します。 ただし、多くの複雑なシステムは、バイナリ接続だけで表すことはできません。 この分野における最近の進歩は、前進する方法を示しています。

子育てのネットワークモデルを構築することを検討してください。 明らかに、各親には子とのつながりがありますが、グラフ理論がモデル化する可​​能性があるため、子育ての関係はXNUMXつのリンクの合計だけではありません。 仲間からの圧力のような現象をモデル化しようとする場合も同じです。

「直感的なモデルはたくさんあります。 社会的ダイナミクスに対する仲間からの圧力の影響は、データにすでにグループが含まれている場合にのみキャプチャされます」と述べています。 レオニー・ノイハウザー ドイツのRWTHアーヘン大学の。 ただし、バイナリネットワークはグループの影響をキャプチャしません。

数学者やコンピューター科学者は、「高次の相互作用」という用語を使用して、バイナリリンクではなくグループダイナミクスが個々の行動に影響を与える可能性があるこれらの複雑な方法を説明します。 これらの数学的現象は、量子力学におけるエンタングルメント相互作用から、集団全体に広がる病気の軌跡まで、あらゆるものに現れます。 薬理学者がモデル化したい場合 薬物相互作用たとえば、グラフ理論は、XNUMXつの薬が互いにどのように反応するかを示しているかもしれませんが、XNUMXつはどうでしょうか。 またはXNUMXつ？

これらの相互作用を調査するためのツールは新しいものではありませんが、高次元のデータセットが発見のエンジンになり、数学者やネットワーク理論家に新しいアイデアを提供するようになったのは近年のことです。 これらの努力は、グラフの限界とスケールアップの可能性について興味深い結果をもたらしました。

「今では、ネットワークが物事の影にすぎないことがわかりました」とGrochow氏は述べています。 データセットの基礎となる構造が複雑な場合、それをグラフとしてモデル化すると、ストーリー全体の限られた投影しか明らかにならない場合があります。

「私たちが物事を研究するために使用したデータ構造は、数学的な観点から、私たちがデータに見ているものに完全には適合していないことに気づきました」と数学者は言いました。 エミリー・パーバイン パシフィックノースウェスト国立研究所の。

そのため、数学者、コンピューターサイエンティスト、その他の研究者は、グラフ理論を一般化する方法にますます焦点を当てており、その多くの形で、高次の現象を探索しています。 過去数年間は、これらの相互作用を特徴づけ、高次元データセットでそれらを数学的に検証するための提案された方法の急流をもたらしました。

Purvineにとって、高次の相互作用の数学的探索は、新しい次元のマッピングのようなものです。 「土地のXNUMX次元プロットの基礎としてグラフについて考えてください」と彼女は言いました。 上に乗ることができるXNUMX次元の建物は、大幅に異なる可能性があります。 「地上にいるときは同じように見えますが、上に構築するものは異なります。」

ハイパーグラフを入力してください

これらの高次元構造の検索は、数学が特に曖昧になり、興味深いものになる場所です。 たとえば、グラフの高次の類似物はハイパーグラフと呼ばれ、エッジの代わりに「ハイパーエッジ」があります。 これらは複数のノードを接続できます。つまり、多方向（または多重線形）関係を表すことができます。 線の代わりに、ハイパーエッジは、XNUMXか所以上に杭打ちされた防水シートのような表面として表示される場合があります。

これは問題ありませんが、これらの構造が従来の構造とどのように関連しているかについては、まだ多くのことがわかりません。 数学者は現在、グラフ理論のどの規則が高次の相互作用にも適用されるかを学習しており、新しい探索領域を示唆しています。

ハイパーグラフがビッグデータセットから引き出すことができる（通常のグラフではできない）種類の関係を説明するために、Purvineは、科学出版の世界である自宅に近い簡単な例を示しています。 最大XNUMX人の数学者が共同執筆した論文をそれぞれ含むXNUMXつのデータセットを想像してみてください。 簡単にするために、A、B、Cという名前を付けましょう。XNUMXつのデータセットにはXNUMXつの論文が含まれ、XNUMXつの異なるペア（AB、AC、BC）のそれぞれにXNUMXつの論文があります。 もうXNUMXつには、合計XNUMXつの論文しか含まれておらず、それぞれがXNUMX人の数学者（ABC）全員によって共同執筆されています。

いずれかのデータセットから取得した共著のグラフ表現は、三角形のように見える場合があり、各数学者（XNUMXつのノード）が他のXNUMXつ（XNUMXつのリンク）と共同作業を行ったことを示しています。 誰が誰と協力したかが唯一の質問であれば、ハイパーグラフは必要ないだろうとパーバイン氏は語った。

ただし、ハイパーグラフがある場合は、あまり目立たない構造に関する質問に答えることもできます。 たとえば、最初のセット（XNUMXつの論文を含む）のハイパーグラフには、各数学者がXNUMXつの論文に貢献したことを示すハイパーエッジを含めることができます。 XNUMXつのセットのハイパーグラフを比較すると、最初のセットでは論文の著者が異なっていたが、XNUMX番目のセットでは同じであったことがわかります。

野生のハイパーグラフ

このような高次の方法は、1990年代にイエローストーン国立公園にオオカミが再導入されたことが生物多様性や食物連鎖の構造にどのように変化をもたらしたかを生態学者が示したときなど、応用研究ですでに有用であることが証明されています。 そして最近のXNUMXつで 紙、Purvineと彼女の同僚は、ハイパーグラフを使用してウイルス感染に対する生物学的反応のデータベースを分析し、関与する最も重要な遺伝子を特定しました。 彼らはまた、グラフ理論によって提供される通常のペアワイズ分析では、これらの相互作用がどのように見落とされていたかを示しました。

「それは、グラフを超えて、ハイパーグラフから見ている種類の力です」とパーバイン氏は述べています。

ただし、グラフからハイパーグラフへの一般化はすぐに複雑になります。 これを説明するXNUMXつの方法は、グラフ理論からの標準的なカット問題を検討することです。グラフ上にXNUMXつの異なるノードがある場合、XNUMXつの間のすべての接続を完全に切断するためにカットできるエッジの最小数はいくつですか。 多くのアルゴリズムは、特定のグラフに最適なカット数を簡単に見つけることができます。

しかし、ハイパーグラフをカットするのはどうですか？ 「このカットの概念をハイパーグラフに一般化する方法はたくさんあります」と述べています。 オースティンベンソン、コーネル大学の数学者。 しかし、ハイパーエッジはさまざまな方法で切断され、ノードの新しいグループが作成される可能性があるため、明確な解決策はXNUMXつではないと彼は言いました。

XNUMX人の同僚と一緒に、ベンソン 最近試された ハイパーグラフを分割するさまざまな方法をすべて形式化する。 彼らが見つけたものは、さまざまな計算の複雑さを示唆していました。状況によっては、問題は多項式時間で簡単に解決されました。つまり、基本的に、コンピューターは妥当な時間で解を処理できます。 しかし、他の人にとっては、問題は基本的に解決できませんでした—解決策がまったく存在するかどうかを確実に知ることは不可能でした。

「そこにはまだ多くの未解決の質問があります」とベンソンは言いました。 「これらの不可能な結果のいくつかは、グラフに還元できない可能性があるため、興味深いものです。 そして理論的には、グラフで見つけられるようなものに縮小していなければ、そこに何か新しいものがあることを示しています。」

数学的サンドイッチ

 しかし、ハイパーグラフは、高次の相互作用を探索する唯一の方法ではありません。 トポロジ（オブジェクトをストレッチ、圧縮、または変換しても変化しない幾何学的プロパティの数学的研究）は、より視覚的なアプローチを提供します。 トポロジー学者がネットワークを研究するとき、彼らは形と表面と寸法を探します。 彼らは、XNUMXつのノードを接続するエッジがXNUMX次元であることに気づき、異なるネットワーク内のXNUMX次元オブジェクトのプロパティについて質問する場合があります。 または、XNUMXつのノードを接続して形成されたXNUMX次元の三角形の表面を見て、同様の質問をする場合もあります。

トポロジー学者はこれらの構造を呼びます 単体の複合体。 これらは、事実上、トポロジーのフレームワークを通して見たハイパーグラフです。 機械学習の一般的なカテゴリに分類されるニューラルネットワークは、わかりやすい例です。 それらは、私たちの脳のニューロンが情報を処理する方法を模倣するように設計されたアルゴリズムによって駆動されます。 物事間の接続をペアワイズ接続としてモデル化するグラフニューラルネットワーク（GNN）は、大規模なデータセットから欠落しているデータの推測に優れていますが、他のアプリケーションと同様に、XNUMXつ以上のグループからのみ発生する相互作用を見逃す可能性があります。 近年、コンピュータ科学者は開発しました 単純なニューラルネットワーク、これらの効果を見つけるためにGNNのアプローチを一般化するために高次の複合体を使用します。

複体はトポロジーをグラフ理論に結び付け、ハイパーグラフのように、将来の調査を推進する説得力のある数学的質問を提起します。 たとえば、トポロジーでは、複体の特殊な種類のサブセットもそれ自体が複体であるため、同じプロパティを持ちます。 同じことがハイパーグラフにも当てはまる場合、サブセットには、埋め込まれたすべての双方向エッジを含む、内のすべてのハイパーエッジが含まれます。

しかし、常にそうとは限りません。 「私たちが今目にしているのは、データがこの中間点に分類され、すべてのハイパーエッジ、すべての複雑な相互作用が他のすべての相互作用と同じサイズであるとは限らないということです」とパーバイン氏は述べています。 「スリーウェイインタラクションは可能ですが、ペアワイズインタラクションはできません。」 ビッグデータセットは、生物学的シグナル伝達ネットワークであろうと、仲間からの圧力のような社会的行動であろうと、グループの影響がしばしば個人の影響をはるかに上回っていることを明確に示しています。

Purvineは、データを一種の数学的サンドイッチの真ん中を埋め、トポロジーからのこれらのアイデアによって上にバインドされ、グラフの制限によって下にバインドされると説明しています。 ネットワーク理論家は現在、高次の相互作用のための新しいルールを見つけることに挑戦しています。 そして数学者にとって、彼女は「遊ぶ余地がある」と言った。

ランダムウォークとマトリックス

その創造的な「遊び」の感覚は、他のツールにも広がります。 グラフとデータを記述するための他のツールの間には、あらゆる種類の美しいつながりがあるとベンソン氏は述べています。 「しかし、高次の設定に移行するとすぐに、これらの接続を確立するのが難しくなります。」

マルコフ連鎖のより高次元のバージョンを検討しようとすると、それは特に明白だと彼は言った。 マルコフ連鎖は、次の段階が要素の現在の位置のみに依存する多段階プロセスを表します。 研究者はマルコフモデルを使用して、情報、エネルギー、さらにはお金などがシステムをどのように流れるかを説明しました。 おそらく、マルコフ連鎖の最もよく知られている例はランダムウォークです。これは、各ステップがその前のステップからランダムに決定されるパスを表します。 ランダムウォークも特定のグラフです。グラフに沿ったウォークは、リンクに沿ってノードからノードへと移動するシーケンスとして表示できます。

しかし、散歩のように簡単なものをスケールアップするにはどうすればよいですか？ 研究者は、現在の位置だけに依存するのではなく、以前の状態の多くを考慮することができる高次のマルコフ連鎖に目を向けます。 このアプローチは、Webブラウジング動作や空港の交通流などのシステムのモデリングに役立つことが証明されました。 ベンソンはそれを拡張する他の方法についてのアイデアを持っています：彼と彼の同僚は最近 記載された 高次マルコフ連鎖をテンソルと呼ばれる別のツールと組み合わせた確率的またはランダムなプロセスの新しいモデル。 彼らはそれをニューヨーク市のタクシー乗車のデータセットに対してテストし、それが軌道をどれだけうまく予測できるかを確認しました。 結果はまちまちでした。彼らのモデルは、通常のマルコフ連鎖よりもキャブの動きを予測していましたが、どちらのモデルも非常に信頼性がありませんでした。

テンソル自体は、近年独自に登場した高次の相互作用を研究するためのさらに別のツールを表しています。 テンソルを理解するには、まず、データを行と列の配列に編成する行列について考えます。 ここで、行列で構成された行列、または行と列だけでなく、データの深さやその他の次元も含む行列を想像してみてください。 これらはテンソルです。 すべてのマトリックスが音楽のデュエットに対応している場合、テンソルには楽器のすべての可能な構成が含まれます。

テンソルは、たとえば粒子のさまざまな可能な量子状態を記述するために長い間使用してきた物理学者にとって目新しいものではありませんが、ネットワーク理論家はこのツールを採用して、高次元データセットの行列の力を拡張しました。 そして数学者はそれらを使って新しいクラスの問題を解き明かしています。 Grochowはテンソルを使用して研究します 同型問題、これは基本的に、XNUMXつのオブジェクトが何らかの方法で同じであるかどうかをどのように知るかを尋ねます。 YoumingQiaoとの彼の最近の仕事は 新しい方法 解決が困難または不可能な複雑な問題を特定するため。

責任を持ってハイパーグラフを作成する方法

ベンソンの決定的でないタクシーモデルは、広く行き渡っている質問を提起します：研究者が実際にハイパーグラフのようなツールを必要とするのはいつですか？ 多くの場合、適切な条件下で、ハイパーグラフはグラフとまったく同じタイプの予測と分析を提供します。 「何かがすでにネットワークにカプセル化されている場合、システムを[高次として]モデル化する必要が本当にありますか？」 尋ねた マイケル・シャウブ アーヘン工科大学の。

それはデータセットに依存すると彼は言った。 「グラフはソーシャルネットワークの優れた抽象化ですが、ソーシャルネットワークはそれだけではありません。 高次のシステムでは、モデル化する方法が増えます。」 グラフ理論は、たとえば、個人がどのように接続されているかを示す場合がありますが、ソーシャルメディア上の友人のクラスターが互いの行動に影響を与える方法をキャプチャしません。

同じ高次の相互作用がすべてのデータセットに現れるわけではないため、不思議なことに、新しい理論はデータによって推進されます。これは、最初にPurvineをフィールドに引き付けた根本的な論理的感覚に挑戦します。 「私が数学で気に入っているのは、それが論理に基づいていることです。正しい方向に従えば、正しい答えが得られます。 しかし、数学のまったく新しい領域を定義するとき、それを行う正しい方法が何であるかという主観性がある場合があります」と彼女は言います。 「そして、それを行う方法が複数あることに気付いていない場合は、コミュニティを間違った方向に動かす可能性があります。」

最終的に、Grochow氏は、これらのツールは一種の自由を表しており、研究者がデータをよりよく理解できるようにするだけでなく、数学者やコンピューター科学者が新しい可能性の世界を探求できるようにします。 「探求するものは無限にあります。 それは面白くて美しく、そしてたくさんの素晴らしい質問の源です。」