第二節 基于節點刪除的連通性度量指標——相對連通系數

為了尋找合適的連通性度量指標，以提取出對應急物流配送路徑分析最重要的元素，需要對路徑搜索的過程進行分析，以了解網絡中的元素在搜索中所起的作用。

路徑搜索的過程可看作由許多節點間的轉移組成的，因此只需考察其中某一個單步轉移的過程即可。為方便分析，這里所說的單步轉移不是指只通過一條邊的節點間跳轉，而是更廣泛的通過網絡中某條路徑的跳轉，此路徑可能由多條邊組成。

在導航程序進行單步跳轉時，由于搜索應用程序事先并沒有關于路徑優劣的先驗知識，因此只能認為下一步轉移的路徑選擇是隨機的，與當前節點相連的任何一條路徑都有相同的概率被選中進入結果路徑。

現在面臨的問題是如何最小化網絡中元素的減少對搜索過程的影響。很明顯應該盡量保留搜索時可能會選中的路徑，從而使網絡分解前后搜索程序所面對的路徑選擇變化最小。但哪些路徑是搜索時會用到的呢？路徑分析必然有目標節點，有時是一個目標節點集，將搜索的起點也看作目標節點集的一員，所有以這些目標節點為終點的路徑都是搜索時必然會涉及的；另外，假設有一條路徑在搜索時被選中，那么由它出發的搜索步驟必然也會到達某一目標節點。將這兩步搜索合并，形成的路徑仍是一條以某目標節點為終點的路徑，即上述搜索過程等價于選擇經由一條以目標節點為終點的路徑的單步跳轉。綜合以上兩方面可知，以目標節點為終點的路徑集合蘊涵了搜索時所有可能的選擇，即為所求搜索時會用到的路徑集合。

進一步來看，與目標元素相關的連通關系到任一元素上的投影可用經由元素以目標節點（集）為終點的路徑組成的集合來量化，其基數大小即表征了網絡中任一元素對目標節點（集）在路徑分析求解方面影響的大小。

由此可見，經由某一元素以目標節點（集）為終點的路徑條數，直接表征了該元素在路徑搜索時對路徑選擇的影響，描述了其對目標節點（集）在路徑分析方面的重要性，能夠恰當地量化元素之間的連通關系，是一個符合需要的合適的指標。

直接求經由某一元素以目標節點（集）為終點的路徑條數比較困難，關鍵在于“經由某一元素”這一條件驗證起來比較復雜，需要耗費大量的計算時間。因此，本書引入節點刪除的方法，通過統計指定節點刪除前后網絡中以目標節點（集）為終點的路徑數的差異來求得該節點對目標節點（集）連通路徑數的影響。這也符合突發事件中道路網絡節點常常因次生衍生災害損毀無法通行、應急物流配送路網道路節點常常動態變化這一實際情況。

為簡單起見，先考慮單目標節點的情況：假設元素a為所關心的目標點，考慮元素i對其連通性的影響。設從圖中任何一個元素出發，可引Rj條路徑到達a點，N0為圖中所有元素到元素a連通路徑的集合，那么圖中所有元素到元素a連通路徑的總條數為：

現在從圖中刪去元素i，設N1為此時圖中所有元素到元素a連通路徑的集合，再求圖中所有元素到元素a連通路徑的總條數為：

設Ni為從圖中刪去元素i后圖中所有元素到元素a減少的連通路徑的集合，綜合前兩個算式可以得到由于從圖中刪去元素i造成的到達a點的連通路徑的減少數為：

由于｜Ni｜通常是一個很大的數，為了方便應用，只需取其數量級即可，由此可引入以下元素i對元素a連通性影響的度量指標的定義，稱之為相對連通系數（Relative Connectivity Coefficient）：