複雜網路中邊的中心性（Edge Centrality）

來自專欄新交通人的技術閑談

一分鐘讀完全文

補充了OSMNX給的官方demo中的一些未描述清楚的地方。對複雜網路中的主要用到的兩種邊中心性betweenness centrality以及current-flow closeness centrality進行了科普性介紹。不涉及對點的centrality如degree的介紹。主要基於osmnx與networkx。開發環境為python 3.6。

參考文獻：Centrality - NetworkX 1.9 documentation

什麼是中心性

中心性在網路中的初衷是為了表示邊和點的重要度。但重要度也有很多不同的衡量模式，比方說，有些邊的連通性很好，你可以認為他重要；有的邊在最短路中出現的頻次高，他也可以被認為重要；而且，如何評價路徑最短也是不定的。因而，也催生出多種不同的Centrality。我們在networkx的官網下看到的Centrality就有（不限於以下幾種）：

其中，degree和closeness都是指的node，當然你也可以用來指邊。在OSMNX給的官方DEMO裡面就有計算edge的closeness。而實際上，從上圖來看，networkx裡面給了edge介面的只有betweenness。

什麼是betweenness

官方定義是：Betweenness centrality of an edge is the sum of the fraction of all-pairs shortest paths that pass through. 已經說得很直白了，就是計算所有網路間節點的最短路，然後對每條邊統計最短路經過的次數，並以每對節點間的最短路條數進行歸一：

如何計算這個Betweenness呢，很簡單。我這裡直接從osmnx上下載的路網，然後導入進去，就可以計算。

import networkx as nximport osmnx as oximport osG = ox.graph_from_place(Seattle, State of Washington,USA, network_type=drive)G_projected = ox.project_graph(G)edge_centrality = nx.edge_betweenness_centrality(G_projected)

什麼是current-flow betweenness

如果說Betweenness是理性出行的話，current-flow betweenness基本就是佛系出行了。官方定義為：Current-flow betweenness centrality uses an electrical current model for information spreading in contrast to betweenness centrality which uses shortest paths.又強調說：Current-flow betweenness centrality is also known as random-walk betweenness centrality。

值得注意的是，Current-flow betweenness centrality是不對directed graph進行計算的，因此，對於有向網路，需要先去除方向：

edge_current_flow = nx.edge_current_flow_betweenness_centrality(G_projected.to_undirected())

點的中心性指標可以用於邊上嗎

也是可以的。OSMNX就給出了這樣的demo: