3
申し訳ありませんが、これは基本的な質問ですが、誰かが問題のクラスを見つけるのを助けることができるかどうか疑問に思っていました。私は、さまざまなサイズと接続性のグラフを比較するために使用できる標準的なメトリックを探していました。具体的には、次の例を考えてみます。さまざまなサイズのグラフを比較する良い方法はありますか？
G1 G2
2 D
| /\
4 --- 1 --- 3 C -- A1 - A2 -- E
|
5
私は1つのグラフ（内安定性）と、別のグラフ（インター安定性）に対する内部の安定性の概念をキャプチャすることですに興味があります。例えば、
イントラ・安定性：G1で
、私の仮説的なメトリックでは、2,3,4,5すべてのは、彼らがグラフから削除する同じ効果を持っていました。 G2では、C,Eは同じ効果を持ちますが、Dはもっと効果があります。しかし、A1,A2は、削除するより効果があります。私がここで探しているのは、グラフの安定性の概念です。私は、各ノードの次数を使って特定のノードの効果を捕捉することはできますが、グラフ全体に対してどのように計算するかはわかりませんと推測しています。
間の安定性：
我々はすなわち相対的な意味では約G1とG2何かを言うことができますのようなものG1が安定メトリックXとG2はYを持っており、X < Yので持っているので、我々はG1を締結はあまり安定していますG2より？安定性自体の定義は開いたままですが、グラフがどれほど信頼できないか、または1つのノード上にどれほど依存しているかを把握しようとしています。
誰かが、この問題はと呼ばれるものを、少なくともこれを定量化するか、することができるようにするために、正しい方向に私を指すことができますか？グラフ理論における
安定性の意味を明確にすることはできますか？いくつかのノードを削除しても効果が少ない場合、グラフがより安定しているということになります。あなたは何とかこの "効果"によってあなたが意味するものを数量化することができますか、これを使用したいものを私たちに教えてください。そうすれば、いくつかの量的定義を一緒に考え出すことができますか？ – Szabolcs
@ザボルス：私を助けてくれてありがとう。私の現在の理解は次のようなものになります。ノードの度合いは、グラフ全体に与える影響を明確に示します。例えば、1つはG1がG1のクリティカルノードであると思われるため、G1がG2ほど安定でないと言うことができます。失敗した場合、グラフ全体が崩れます。しかし、 'G2'では、' A2'が失敗してもグラフはある程度機能しています。しかし、安定性自体の実際の定義自体は今のところ終わりのないものです。要するに、私はグラフをどれだけ簡単に取り除くことができるかを1つのメトリックで捕捉しようとしています。 – Legend
あなたに必要なものと、「ネットワークを奪う」ものはまだ分かりません。セクションIX、「エラーと攻撃寛容」を見てみましょうhttp://www.barabasilab.com/pubs/CCNR-ALB_Publications/200201-30_RevModernPhys-StatisticalMech/200201-30_RevModernPhys-StatisticalMech.pdf：このレビュー紙は便利かもしれません。ランダムに、または「重要な」ノードを対象にしてノードを削除し、ネットワークが別々のコンポーネントに分割されるために削除する必要がある数を調べました。これは@ Randyの答えに関連していますが、より実用的なアプローチです。 – Szabolcs