比較不同尺寸圖形的好方法？

對不起，如果這是一個基本問題，但我想知道是否有人能幫我找出這個具體問題屬於哪類問題。我正在尋找任何可用於比較不同大小和連通性圖形的標準指標。具體而言，考慮下面的例子：比較不同尺寸圖形的好方法？

 G1        G2 
     2        D 
     |       /\ 
4 --- 1 --- 3     C -- A1 - A2 -- E 
     | 
     5

我所感興趣的是捕捉到穩定的一個概念圖（內部穩定性）和相對於其他圖（穩定性間）內。例如，

內部穩定性：

在G1，在我假想的指標，2,3,4,5都具有相同的效果是他們從圖中可以去除。在G2,C,E會有相同的效果，但D會有更多的影響。但是，A1,A2將被刪除更多的影響。我在這裏尋找的是圖的穩定性的概念。我猜測我可以使用每個節點的程度來捕獲特定節點的影響，但不知道如何爲整個圖表計算它。

跨穩定性：

我們可以說在相對意義上關於G1和G2東西即類似，因爲G1具有穩定性度量X和G2有Y因爲X < Y，我們得出的結論G1不太穩定比G2？穩定本身的定義是保持開放的，但我試圖捕捉圖的不可靠性，或者如何依賴於一個節點。

有人能指出我在正確的方向，以便能夠量化這個或至少是什麼這個問題被稱爲？

來源

2011-07-19 Legend

您能說清楚您的穩定性是什麼意思嗎？看起來你的意思是說，如果刪除一些節點對它的影響較小，則圖更穩定。你能以某種方式量化這個「效應」是什麼意思嗎？或者告訴我們你想用什麼來達到這個目的，所以我們可以一起提出一些定量的定義？ – Szabolcs

@Szabolcs：謝謝你幫助我。我目前的理解是這樣的：節點的度數清楚地表明瞭它對整個圖表的影響。例如，一個概念可以說'G1'不像'G2'那樣穩定，因爲1似乎是'G1'中的一個關鍵節點，如果失敗了，整個圖形就會崩潰。然而，在'G2'中，即使'A2'失敗，該圖在某種程度上仍然有效。但是，穩定本身的實際定義本身就像目前一樣是開放的。總之，我試圖用一個單一的度量來捕獲一個圖表如何輕鬆取下。 – Legend

在我看來，目前還不清楚您需要什麼，以及「拆除網絡」的含義。這篇評論文章可能很有用：http：//www.barabasilab.com/pubs/CCNR-ALB_Publications/200201-30_RevModernPhys-StatisticalMech/200201-30_RevModernPhys-StatisticalMech.pdf請看第九節「錯誤和攻擊容忍度」。他們隨機地或通過針對「重要」節點刪除節點，並查看需要刪除多少網絡才能分解成單獨的組件。這與@蘭迪的答案有關，但採用更實用的方法。 – Szabolcs

在圖論中，一個cut或cut集似乎描述了你最大的不穩定性描述。

作爲一種度量標準，您可能會在談論'連接性'

來源

2011-07-19 02:13:22 Randy

+1謝謝您的建議。我會看到如何在這裏使用cut-set並返回。 – Legend

比較不同尺寸圖形的好方法？

回答

相關問題