グラフの差異を定量化するネットワーク階層エントロピー

ネットワークの小さな違いが重要な理由

ソーシャルメディアの友人関係や航空路線、タンパク質の立体構造に至るまで、多くのシステムはノードとリンクのネットワークとして表現できます。しかし、見た目が似ているネットワーク同士が本質的に異なるかどうかを見分けるのは意外に難しいです。本論文は、ノード（点）だけでなくエッジ（辺）とそれらの相互作用に注目することで、二つのネットワークがどれほど異なるかを測る新しい方法を提案します。ネットワーク階層エントロピーと呼ばれるこの手法は、他の手法が見落としがちな微妙な構造変化を検出でき、酵素タンパク質と非酵素を区別するのにも役立ちます。

層ごとに見るネットワークの視点

ネットワークを理解するために、著者らはまず各ノードがほかの各ノードからリンクをたどった何歩先にあるかを考えます。任意のノードを中心に、その周囲のノードは層ごとに分けられます：直接の近隣、近隣の近隣、といった具合です。このノード周りの「階層」は、影響や感染がネットワーク上でどのように外側に広がるかを記述します。ただし興味深いことに、非常に異なるネットワークが同じノードレベルの階層構造を共有することがあり、この視点だけでは区別できない場合があります。論文では、デザルグラフや十二面体グラフのような古典的な例が、内部の配線が異なるにもかかわらず同一のノード階層を持つことを示しています。

エッジに語らせる：ノード対の縮約

ノードレベルの視点が見落とす点を捉えるため、著者らはエッジ――ノード間の結びつき――と、それがネットワーク全体の距離に与える影響に注目します。彼らはシンプルだが強力な考えを導入します：「ノード対の縮約」です。ここでは、つながった二つのノードを一時的に一つの新しいノードに統合しつつ、それらの結合先は保持します。これにより、ほかのすべてのノードがそのペアに対してどれだけ近くなるかが、各端点単独の場合と比較して明らかになります。拡散の観点では、これは単一ノードからではなくリンクの両端を同時に感染させるような効果を模倣します。こうした層状の距離パターンから、ノードとエッジ双方についての「階層中心性」を定義し、それが実世界ネットワーク上のシミュレーション感染における拡散者としての有効性と強く相関することが示されます。

エントロピーで情報損失を測る

これらの中心性に基づき、著者らは二種類の階層エントロピーを定義します。エッジ階層エントロピーは、あるエッジの重要性をそれが結ぶ二つのノードの重要度を平均することで近似した場合にどれだけ情報を失うかを問います。ノード階層エントロピーは、ノードとその周囲のエッジについて逆の問いを立てます。両者ともネットワーク全体のサイズに依存しないよう正規化されています。これら二つの値は合わせてネットワークの二要素フィンガープリントを形成します。二つのネットワーク間の距離は、そのフィンガープリント間のユークリッド距離（幾何学的距離）として計算されます。この新たな距離尺度は距離の標準的な性質に従い、ネットワークが分断されるような変化にはより大きな罰則を与えるなど直感に合った挙動を示します。

より細かな構造と時間変化の可視化

著者らは人工ネットワークと実ネットワークの両方で手法を検証します。社会的・技術的システムを模した合成ベンチマークでは、新しい指標はモデルパラメータの変化に伴うネットワークの進化を追跡でき、コミュニティ構造が強いネットワークと弱いネットワークとを明確に区別します。他の手法が苦戦する場面でも優れていることが示されます。次数列や距離分布といった多くの共通統計量を保持するようにネットワークをシャッフルしても、階層エントロピー距離は他の一般的な指標が無視する差異を検出します。同一ネットワークのランダム化バージョンを正しくグループ化する能力にも優れ、単なるリンクやパスの数を超えた高次構造への感度が高いことを示します。

実世界での応用：移動とタンパク質

実用性の例として、著者らはCOVID-19の初期数か月における数百都市間の日次移動ネットワークにこの距離尺度を適用します。1月上旬を基準とすると、階層エントロピーは旧正月の移動ラッシュ、厳格な検疫の開始、徐々に回復する期間を通して移動パターンがどのように変化したかを明確に示し、政策変更や移動のコミュニティ構造とよく一致しました。別の応用では、タンパク質の構造を近傍にあるアミノ酸同士を結んだネットワークとして扱います。学習や手作りの特徴量を一切用いずに、この距離でタンパク質をクラスタリングすると、酵素と非酵素を分ける精度が約75%に達し、現代の教師ありニューラルネットワーク手法と競合する性能を示しました。

平易に言えば何を意味するか

要するに、本研究はノードとエッジが共同でネットワーク上の距離をどのように形作るかに注目することで、ノードのみを見るよりもはるかに鋭い「指紋」が得られることを示しています。エッジをその端点で置き換えたとき、あるいはノードをその周囲のエッジで置き換えたときにどれだけ情報が失われるかを定量化することで、提案する階層エントロピー距離は拡散、移動、生物学的機能に大きな影響を与える微妙な構造差を浮き彫りにします。あらゆる種類のネットワークデータを扱う研究者や分析者にとって、これは数学的に堅牢でありながら現実のプロセスの進行に密接に結びついた、実用的で汎用性の高い比較ツールを提供します。

引用: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

キーワード: ネットワーク類似度, 複雑ネットワーク, エントロピー測度, 感染拡大モデル, タンパク質構造ネットワーク