Loading article…
計算生物学において、パワーグラフ解析は複雑なネットワークの解析と表現のための手法です。パワーグラフ解析とは、グラフ（ネットワーク）からパワーグラフを計算、解析、視覚的に表現することです。
パワーグラフ解析は、グラフのロスレス圧縮アルゴリズムと考えることができます。 [ 1 ]クリーク、バイクリーク、スターの表現でグラフ構文を拡張します。複雑な生物学的ネットワークでは、最大95%の圧縮率が得られています。
ハイパーグラフは、エッジが単なるノードのペアではなく、任意のnタプルであるグラフの一般化です。パワーグラフは、グラフの別の一般化ではなく、むしろ「ノードとエッジ」という言語から、クリーク、バイクリーク、スターを基本要素として使用する言語への移行を提案する、グラフの新しい表現です。
グラフは、ノードを表す円または点と、ノードのペアを結ぶエッジを表す線で描画されます。パワーグラフは、ノードまたは他のパワーノードを囲む円として描画されるパワーノードと、パワーノード間の線であるパワーエッジによって、グラフの構文を拡張します。
二分枝とは、2つのノードの集合から成り、一方の集合のすべての要素と他方の集合のすべての要素との間にエッジが存在するものです。べきグラフでは、二分枝は2つのべきノード間のエッジとして表されます。
クリークとは、すべてのノード間にエッジが存在するノードの集合です。パワーグラフでは、クリークはループを持つパワーノードで表されます。
スターとは、集合内のすべてのノードと、その集合外にある単一のノードとの間にエッジが存在するノードの集合です。パワーグラフでは、スターは通常のノードとパワーノードとの間のパワーエッジによって表されます。
グラフが与えられた場合どこはノードの集合であり、エッジの集合、べきグラフは冪集合上に定義されたグラフである。電力エッジによって互いに接続された電力ノードの:したがって、べきグラフは、グラフのノードのべき集合とエッジのべき集合の両方で定義されます。。
パワーグラフの意味論は以下のとおりです。2つのパワーノードがパワーエッジで接続されている場合、これは最初のパワーノードのすべてのノードが2番目のパワーノードのすべてのノードに接続されていることを意味します。同様に、パワーノードがパワーエッジで自身に接続されている場合、これはパワーノード内のすべてのノードがエッジで相互に接続されていることを意味します。
以下の2つの条件を満たす必要があります。
関数のフーリエ解析は、関数を調和関数で書き換えたものと見なすことができる。 ペア。この変換により、視点が時間領域から周波数領域 に変わり、信号解析、データ圧縮、フィルタリングで多くの興味深いアプリケーションが可能になります。同様に、パワーグラフ解析は、バイクリーク、クリーク、スターを基本要素として使用してネットワークを書き換えたり分解したりします（フーリエ解析の調和関数と同様）。ネットワークの解析、圧縮、フィルタリングに使用できます。ただし、いくつかの重要な違いがあります。まず、フーリエ解析では、2 つの空間（時間領域と周波数領域）は同じ関数空間ですが、厳密に言えば、パワーグラフはグラフではありません。次に、与えられたグラフを表す一意のパワーグラフはありません。しかし、非常に興味深いクラスのパワーグラフは、与えられたグラフを表すために必要な最小限のパワーエッジとパワーノードを持つ最小パワーグラフです。
一般に、与えられたグラフに対して唯一の最小べきグラフは存在しません。この例（右）では、4つのノードと5つのエッジを持つグラフに対して、それぞれ2つのべきエッジを持つ2つの最小べきグラフが存在します。これら2つの最小べきグラフの主な違いは、2番目のべきグラフのネストレベルが高いことと、基となるグラフに対する対称性が失われていることです。対称性の喪失は、複雑なネットワークがそもそもそのような対称性を示すことは稀であるため、小さな例でのみ問題となります。さらに、ネストレベルを最小化することは可能ですが、それでも一般に、最小ネストレベルの最小べきグラフは存在しません。
パワーグラフの貪欲アルゴリズムは、分解を実行するために2つの簡単なステップに依存しています。
最初のステップでは、ネットワーク内のノードを、隣接ノードとの類似性に基づいて階層的にクラスタリングすることで、候補となる電力ノードを特定します。2つの隣接ノード群の類似性は 、それらの群のジャッカード係数として表されます。
第２のステップでは、候補となる電力ノード間の電力エッジを貪欲に探索します。元のネットワークで最も多くのエッジを抽象化した電力エッジが、最初に電力グラフに追加されます。このようにして、バイクリーク、クリーク、スターは、残りのすべての単一エッジが追加されるまで、電力エッジに順次置き換えられます。電力エッジの終点ではない候補電力ノードは無視されます。
モジュラー分解は、モジュラー分解の強いモジュールを使用してパワーグラフを計算するために使用できます。モジュラー分解におけるモジュールは、グラフ内で同一の隣接ノードを持つノードのグループです。強いモジュールは、他のモジュールと重複しないモジュールです。しかし、複雑なネットワークでは、強いモジュールは例外であり、規則ではありません。したがって、モジュラー分解によって得られるパワーグラフは、最小性とは程遠いものです。モジュラー分解とパワーグラフ分析の主な違いは、パワーグラフ分析では、ノードのモジュールだけでなく、エッジのモジュール（クリーク、バイクリーク）も使用してグラフを分解することに重点を置いている点です。実際、パワーグラフ分析は、ノードとエッジの両方の損失のない同時クラスタリングと見なすことができます。
パワーグラフ解析は、タンパク質間相互作用ネットワーク[ 2 ] 、ドメイン-ペプチド結合モチーフ、遺伝子制御ネットワーク[ 3 ]、相同性/パラロジーネットワークなど、いくつかのタイプの生物学的ネットワークの解析に有用であることが示されています。また、重要な疾患-形質ペアのネットワーク[ 4 ]も最近、パワーグラフを用いて可視化および解析されました。
パワーグラフから派生した新しい尺度であるネットワーク圧縮は、タンパク質相互作用ネットワークの品質尺度として提案されている。[ 5 ]
パワーグラフは、薬剤の再配置のための薬剤-標的-疾患ネットワークの分析にも適用されている[ 6 ]。
パワーグラフは、ソーシャルネットワークの大規模データに適用され、コミュニティマイニング[ 7 ]や著者タイプのモデリング[ 8 ]に用いられてきた。
