text: 在圖論中，介數中心性是基於最短路徑針對網路圖中心性的衡量標準之一。針對全連線網路圖，其中任意兩個節點均至少存在一個最短路徑，在無權重網路圖中該最短路徑是路徑包含邊的數量求和，加權網路圖中該最短路徑則是路徑包含邊的權重求和。每個節點的介數中心性即為這些最短路徑穿過該節點的次數。介數中心性在網路理論中有廣泛的應用：它代表了某節點與其他節點之間的互動程度。 例如，在通訊網路中，一個有更高介數中心性的節點在網路中有更強的控制能力，因為更多的資訊傳遞時將透過該節點。 介數中心性被用作為對中心性的一種常見測量方式: 它適用於解決網路理論中的許多問題，包括與社會網路、生物、運輸和科學合作等方面相關的問題。雖然早期的研究人員曾直觀地描述了介數的中心性，但Freeman在1977年給了第一個介數中心性的正式定義。定義.節點formula_1的介數中心性可表達為以下公式：formula_2其中formula_3是節點formula_4到節點formula_5的最短路徑之數量，而formula_6這些路徑經過formula_1的次數。可注意到一個節點的介數中心性與該網路圖中的節點個數相關。因此，可透過除以不包含formula_1的節點對數以將計算結果標準化，使得formula_9。其中有向圖需除以 formula_10 ，而無向圖需除以formula_11，其中 formula_12是網路圖中節點數量的集合。該比例代表的是最高可能計算值，即某節點與其他所有節點都透過單一的最短路徑相連線，不過以上情況通常不會發生。標準化的過程並不會使計算的精準度受到影響。formula_13可求解得：formula_14formula_15由公式可知，計算結果將始終是一個從較小範圍到更大範圍的比例，因此沒有精準度的損失。加權網路.在一個加權網路中，連線節點的邊不再被看作類似於二元的互相作用，而是根據其特徵、影響、頻率等賦予對應的權重，這在網路圖基於的網路拓撲結構之上增加了另一個異質性的維度。 在加權網路中，一個節點的強度為其鄰邊權重的代數和。formula_16其中formula_17和formula_18分別表示節點formula_19和formula_20之間的鄰接矩陣和權重矩陣。類似於在無標度網路中發現的冪律分佈，一個給定節點的強度也服從冪律分佈。formula_21一項研究表明，介數為 formula_22的節點其平均值formula_23可用以下公式來近似：formula_24滲流中心性.滲流中心性是加權介數中心性的一種特殊情況，它在計算其權重時考慮了每條最短路徑的源節點與目標節點的“狀態”。 在複雜網路中，許多情景都會發生“感染”並進行滲流。 例如，眾所周知，在接觸網路中細菌或病毒的感染可以在人群的社會網路中傳播。也可以將疾病的傳播抽象化，認為一個城鎮或人群聚集地是由公路、鐵路或航空的連線而構成的網路。計算機病毒可能透過計算機網路傳播。關於商業報價和交易的傳聞或新聞也可以經由人群的社交網路傳播。 在所有這些情景下，一個“感染”可在複雜網路中透過連線傳播，並伴隨著節點“狀態”的改變，如受到感染或感染後恢復到原狀態。例如，在一個流行病的情景下，個體在感染傳播時會將狀態由“易感染”變為“已感染”。 在上述例子中，各個節點在傳播時可能的狀態可以是二元的。 在所有這些情景中，常見的特徵是傳染病的傳播使網路中節點狀態發生變化。 以上這些有關滲流中心性(PC)的概念由Piraveenan et al.提出，這對具體地測量節點在網路滲透中的重要性很有幫助。滲流中心性的定義是：給定一個節點，在給定的時間內“滲透路徑”透過該節點的比例。“滲透路徑”指的一對節點之間的最短路徑，其中源節點產生滲透效果(例如傳播感染)，目標節點可以是處於已滲透、未滲透或部分滲透的狀態。formula_25其中 formula_26 是從節點formula_4到節點 formula_28最短路徑數之和，formula_29這些路徑中透過 formula_1的次數。 節點formula_19在時間 formula_5的滲流狀態由formula_33決定，其中有兩個臨界值，formula_34時表示在時間formula_5的時候沒有滲透狀態，formula_36時表示在時間 formula_5的時候為完全滲流狀態。0到1之間的值則表示部分滲透狀態。滲流路徑的權重取決於源節點的滲流水平，如果源節點的滲流水平越高，那麼來自該節點的路徑影響力更大。 因此在源節點為高滲透作用節點的最短路徑上的節點更有可能受到滲流影響。滲流中心性的定義還可以擴充套件到也包括目標節點的權重。 滲流中心性的計算可採用Brandes快速演算法有效實現，其時間複雜度為formula_38。如果計算需要考慮目標節點的權重，最壞情況的時間複雜度為 formula_39。演算法.中心性的概念也被擴充套件到評定一個團隊的級別。 團隊介數中心性表示透過一組節點連線非該組節點的測地線的比例。能計算所有節點介數中心性的布蘭德斯演算法被修改為計算一組具有相同漸近執行時間的節點的團隊介數中心性。相關概念.介數中心性與網路的連線度相關，介數高的節點如果在被移除以後有很大可能性使網路圖不完全連線。路由介數中心性使介數中心性適用於任何迴圈較少的簡單路徑定義方案而不侷限於最短路徑標準。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 介數中心性
metadata: https://zh.wikipedia.org/wiki?curid=6584639