重要なものを失わずに高次ネットワークを圧縮する方法 多くの現実のシステムは単にペアワイズリンクだけでできているわけではありません。グループチャット、共著論文、教室、または生化学複合施設とは、3つ、4つ、あるいはそれ以上の存在が同時に参加するグループ相互作用のことです。ハイパーグラフはこれをモデル化する自然な方法です。エンティティ用のノードと各グループごとに「ハイパーエッジ」を配置し、ペア用にレイヤー、トリプル用、クアドラプル用にレイヤーを分けます。ただし、これらの高次のモデルはすぐに巨大化し、計算が難しく、解釈も難しくなります。重要な問いは、その高次の構造のうちどれだけが本当に新しい情報であり、どれだけが低次の情報と重複しているのか、ということです。 アレック・カークリー、ヘルシオ・フェリッペ、フェデリコ・バティストンは、ハイパーグラフの構造的還元性という情報理論的概念を用いてこれに取り組んでいます。非常に高価なデータリンクを使って、より高次のネットワーク全体を送ろうとするようなことを想像してください。一つの選択肢は「ナイーブ」で、すべてのレイヤー(ペア、トリプル、4組タプルなど)を独立して送る方法です。彼らの代替案は賢く、少数の「代表的」レイヤーだけを送信し、残りのレイヤーは違いのみを使ってノイズの多いコピーとして記述します。順序間の構造が重なり合うほど(例えば、すべての2体・3体相互作用が5体相互作用によってすでに暗示されている場合)、より多く圧縮できます。 これを0(圧縮性なし)から1(完全入れ子で完全還元可能)の間の正規化されたスコアη、冗長でない相互作用サイズのみを保持する明示的な縮小モデルに変換します。論文の図は、4層ハイパーグラフを最適に2層にまで縮小しつつ、本質的な高次の組織を捉えることができる簡単な例を示しています。 その後、合成データと実際のデータでストレステストを行います。制御された「ネスト型」トイハイパーグラフでは、ランダム性を注入するにつれてηが滑らかに減少し、「完璧構造」から「完全ランダム」へダイヤルのように振る舞います。実際のシステム(共著者、連絡ネットワーク、メールスレッド、タグ付けシステムなど)では、多くのものが驚くほど圧縮可能であることがわかります。複数のハイパーエッジオーダーを削り、レイヤーの一部だけを保持できますが、グローバルな接続性、コミュニティ構造、さらにはネットワーク上での高次の有権者モデルの挙動まで維持できます。 要するに、複雑なシステムを研究するのに、複雑で扱いにくい高次の記述は必ずしも必要ないことが多いです。適切な情報理論的視点があれば、どのグループサイズが本当に新しい構造を加え、はるかに小さなハイパーグラフを構築しつつ、あなたが関心を持つ集団的なパターンやダイナミクスを忠実に捉えているかを特定できます。 論文: