第五節 算例與討論

本書提出的相對連通系數作為一種全新的網絡節點重要性指標，需要與已有的成熟指標性能進行對比。對于相同的算例，此指標得出的評價結果應該與已有的成熟指標相吻合，并且具備已有指標所不具備的特點，能夠解決以前解決不了的問題，只有這樣才能說明提出此指標的合理性和必要性。為此，本節將相對連通系數與常用的一些網絡節點重要性指標進行算例對比。

圖3-5為節點重要性文獻中經常引用的一個經典案例，呈現了40個艾滋病患者的性關系網絡，Poulin、Boily、Madsse、Stephenson、Zelen、Freeman、Bonacich、李鵬翔、席酉民等都用該網絡進行過核心性指標的計算和比較工作。

在此需要說明，雖然相對連通系數在本書中主要應用于道路網絡節點重要性的評價，但從前文其建立的過程中可以看出，此指標是在已有的成熟網絡節點重要性指標基礎之上改進得到的，其適用范圍并不只局限于道路網絡；而圖3-5所呈現的經典案例中，蘊含了進行網絡節點重要性評價時可能遇到的各種情況，較之一般道路網絡數據，更能測試出網絡節點重要性指標在極限情況下的性能。因此，為對比相對連通系數與其他常用指標的性能特點和適用范圍，本節以此網絡為例來計算其相對連通系數，并與其他常用指標進行對照。

一 求單目標節點的相對連通系數

1．首先將圖3-5中網絡以所選目標節點為根、按寬度優先搜索的順序展開成一棵樹，下面以17號節點為例展開（如圖3-6所示）。

值得注意的是圖中形成圈的地方會有共同的子樹，例如28號節點和34號節點的情形，這時只需在第一次遇到時展開一次，然后在以后的節點中保存指向該子樹根節點的指針即可。

2．遞歸估算網絡節點相對所選目標節點的單點相對連通系數，在相對連通性系數近似定義中，表征節點對應子樹形狀的特征向量的計算具有遞歸嵌套的特點，由此可用子樹中下一級節點已有的特征向量來計算上一級節點對應的特征向量。以17號節點為例的求解過程如表3-1所示。

二 求多目標節點的相對連通系數

1．利用前述方法求得網絡中所有節點相對任一節點的相對連通系數，具體情況如表3-2所示。

2．選取目標節點集，構造目標節點集相對連通系數矩陣。例如這里選取節點17、26、33作為目標節點集，然后從上一步求得的單點相對連通系數中選取這三個節點對應的 RCC 形成矩陣，具體情況如表3-6所示。

3．調用Matlab對上面矩陣做主成分分析，得到圖3-5所示網絡中節點17、26、33相對連通系數矩陣主成分對應的奇異值和主成分向量，具體情況如表3-7、表3-8所示。

4．利用公式（3.20）求得針對節點17、26、33的多目標節點相對連通系數，如表3-9所示。

由于現有指標都是針對整個網絡的，為與已有指標作一對比，這里利用上述方法求得節點相對整個網絡的多目標節點相對連通系數（即RCC［1…40］），從這里也可以看出：針對整個網絡的相對連通系數只是針對節點集的相對連通系數在節點集為網絡中所有節點時的一個特例，將其與Poulin、Boily和Madsse等就此網絡的計算結果對照列于表3-10中。

表3-10中，Rank表示根據節點指標數值排出的名次；CDeg、CCS、Cinf和CBon分別表示核心性的度指標、接近度指標、信息核心性指標和Bonacich的特征向量指標，CCN和CCN′是Poulin等提出的累計提名指標。CR是李鵬翔、席酉民等在文獻提出的CR指標，RCC為本書提出的基于節點刪除的重要性指標。節點編號和對應每個指標的計算結果列在表中。

從指標的分布模式來看，相對連通系數與度指標的相關性較強，但與度指標相比，它既考慮網絡的局部連接特性也考慮與之相關聯的網絡整體特性，這又與李鵬翔、席酉民等提出的CR指標相似，這三種指標的模式分布情況如圖3-7所示。

不同的指標是從不同的角度來探討同一問題的，每個指標都有自己的優缺點和適用范圍。接近度指標反映節點的居中程度，中介性指標反映節點對其他節點間溝通的控制能力，特征向量指標和累計提名指標反映的是節點的名望和地位特性，而相對連通系數指標則反映的是節點對保持整個網絡的連通所起的作用。因此，當目標節點集是整個網絡時，相對連通系數與前述指標相比并無明顯優勢，但當目標節點集動態變化時，相對連通系數就顯示出其他指標所不具備的優越性，其能夠根據所選目標節點集按需提取與之最相關的部分子網。例如，選取節點17、26、33作為目標節點集，利用前面計算所得的結果，濾掉RCC值為0的冗余節點，可得到與目標節點集密切相關的部分（如圖3-8所示）。

這其中包含了與節點17、26、33相關的大部分路徑，還有一些重要的關節點，這些都是有可能在路徑搜索中用到的。

進一步將濾取閾值提高到10，得到與目標節點集更相關的部分（如圖3-9所示）。

這時隨著閾值的提高，周邊的關節點和一些不重要的路徑如20-19-28-26也被濾掉，保留的都是與目標節點集最相關的路徑和節點。

在這里雖然網絡規模較小，偶然因素造成的誤差干擾較大，但結果已十分精確。這是因為在求相對連通系數的時候，不同的子樹形狀之間的差異是以指數的級別進行放大的，因此能夠有效地把冗余節點、非關鍵節點、關鍵節點按梯級分開。如果應用在大規模的網絡上，放大效果更加明顯，篩選結果就更加精確。

從上面的算例討論可以看出，利用相對連通系數指標可以根據所選目標節點集有效地提取網絡中與目標節點集最相關的部分，獲取與之相關的路徑解空間信息。

這一點對于應急物流配送車輛導航尤其重要。在應急物流配送車輛導航路徑搜索時，使用者并不需要了解節點對于整個網絡的重要性，其關心的只是與出救任務行車目標密切相關的那一部分路網，其他的冗余部分只會分散駕駛員的注意力，消耗車載設備上有限的計算資源，因此需要根據所選目標節點集按需生成應急物流配送導航地圖。但已有的節點重要性指標并未說明其重要性是針對哪些目標節點的，其重要性往往被默認是相對于整個網絡來說的，如果要求相對于特定節點（集）的重要性指標，就得對指標做復雜的分解，再合成。這時相對連通系數就顯示出其獨有的優勢：前述相對連通系數的求解過程，本身就是從單目標點過渡到多目標節點集的，因此我們可以很自然地根據選定的目標節點集提取相對于應急物流配送行車目標重要的部分。這就克服了已有指標的不足，對現有網絡節點重要性理論是一種補充和完善。