1 NetworkX概述

1.1 網路與NetworkX

網路的研究是運籌學的一個經典而重要的分支，是很多領域研究的基礎工具，在交通運輸、經濟管理和工業工程等都有廣泛的應用[1]。從廣義上講，我們都生活在一個由網路組成的世界裡，各種網路組成了我們現下複雜的生活環境。故而要分析身邊各個領域的規律，就需要對其組成基礎——網路的特性進行分析。

「工欲善其事，必先利其器」，一個優秀的工具能幫助我們更專註於網路本身，而非費心去選擇某種語言去實現演算法、繪製圖形。NetworkX作為Python的一個開源包，便於用戶對複雜網路進行創建、操作和學習。利用networkx可以以標準化和非標準化的數據格式存儲網路、生成多種隨機網路和經典網路、分析網路結構、建立網路模型、設計新的網路演算法、進行網路繪製等[2]。

1.2 NetWorkx基礎

1.2.1 圖與圖的生成

(1) 圖的定義

圖在現實世界中隨處可見，如交通運輸圖、旅遊圖、流程圖等。此處我們只考慮由點和線所組成的圖。利用圖可以描述現實生活中的許多事物，如用點可以表示交叉口，點之間的連線表示路徑，這樣就可以輕而易舉的描繪出一個交通運輸網路，如圖1所示。圖的定義可表述為：圖是用點和線來刻畫離散事物集合中的每對事物間以某種方式相聯繫的數學模型[3]。網路作為圖的一個重要領域，包含的概念與定義更多，如有向圖網路（Directed Graphs and Networks）、無向圖網路（Undirected ~）等概念，據體可參閱相關著作[4]。

(2) 模塊的載入

在Python中，用下列語句導入Networkx模塊：

import networkx as nx

如果導入失敗，則說明未安裝networkx模塊，為了方便載入模塊，筆者建議使用Anaconda集成環境，官方環境下載緩慢，建議從清華大學開源軟體鏡像站下載。

安裝Anaconda後，可在附帶的Anaconda Prompt輸入以下命令下載該庫，如圖2所示：

pip install networkx

鍵入命令回車後會自動下載安裝，若集成環境已安裝該庫，則會出現上圖所示的提示。

(3) 圖的生成

在NetworkX中，有以下4種基本的圖類型：

Graph：指無向圖（undirected Graph），即忽略了兩節點間邊的方向。

DiGraph：指有向圖（directed Graph），即考慮了邊的有向性。

MultiGraph：指多重無向圖，即兩個結點之間的邊數多於一條，又允許頂點通過同一條邊和自己關聯。

MultiDiGraph：多重圖的有向版本。實例如下圖3所示。

可通過以下代碼創建上述四種圖類型的空對象（默認已導入模塊），當然圖的類型不僅如此，這僅是4種基本圖類型。

G = nx.Graph() # 創建無向圖G = nx.DiGraph() # 創建有向圖G = nx.MultiGraph() # 創建多重無向圖G = nx.MultiDigraph() # 創建多重有向圖

在創建了相關對象後，並不會有圖像出現。一是因為這只是一個空對象，並沒有具體實際的數據（有點類似C#中類的概念）；二是因為Networkx庫設計的初衷也並非為了繪製網路圖，創建了對象後不會自動繪製其圖像，通常需要藉助matplotlib庫加以實現。下面舉例說明圖的生成過程。

import matplotlib.pyplot as plt # 導入模塊函數G = nx.cubical_graph() # 生成一個正則圖（3-regular Platonic Cubical graph）plt.subplot(121) # 繪製子圖nx.draw(G)plt.subplot(122) nx.draw(G,pos=nx.circular_layout(G),nodecolor=r,edge_color=b)

上述代碼，第一行使用import導入matplotlib庫中的pyplot函數，此函數類似與MATLAB中plot函數，導入其的目的是為了繪製子圖；第二行代碼創建了一個圖類型，其形狀將在第四行代碼中展現；第三行和第五行代碼用以創造子圖，其含義分別是3創建一個1行2列的圖形，並選取第1行第1列的子圖作為繪圖背景，5選取第1行第2列的子圖作為繪圖背景，繪製效果如下圖4所示；

第4行和第6行代碼使用了networkx庫中為數不多的繪圖函數（調用了matplotlib庫），其中第4行不帶任何參數，第6行則展示了draw函數的可調整參數，draw函數的調用格式如下：

nx.draw(G, pos=None, ax=None, **kwds)

其中，G表示要繪製的網路圖，pos是一個可選項，默認為None，其用於建立布局，不同的*_layout有不同的美化效果，如下所示。ax和**kwds是可選項，其中參數很多，可參閱官方文檔，這裡的「nodecolor用以控制節點顏色，edge_color用於控制邊的顏色」。

circular_layout:將節點位置調整為圓形；

random_layout:將節點隨機的放在一個單位正方形內；

shell_layout:將節點放於多個同心圓內；

spring_layout:使用FR演算法來定位節點；

spectral_layout:利用圖拉普拉斯的特徵向量定位節點

1.2.2 演算法與存儲結構

(1) 演算法概述

NetworkX中為使用者提供了許多圖論演算法，包括最短路演算法、廣度優先搜索演算法、聚類演算法和同構演算法等，在後文中會詳述，在這裡僅舉一個調用迪傑斯特拉演算法（(Dijkstra）求解最短路的例子，代碼如下：

G = nx.Graph()e = [(a,b,0.3),(b,c,0.9),(a,c,0.5),(c,d,1.2)]G.add_weighted_edges_from(e)print(nx.dijkstra_path(G,a,d))

其中第2和3行代碼是為圖對象賦予權重，其中用到的函數我們在後文中會詳細講述，現在只需知道這是賦予圖邊權的一種是即可。運行結果如下圖5所示，最短路為a-c-d。

(2) 數據存儲結構

NetworkX存儲網路的相關數據時，使用了Python中的3層字典結構（字典Dictionary是Python中的基礎概念，詳見這裡），這有利於在存儲大規模稀疏網路時提高存取速度。

下面本文舉例說明其存儲方式：

G = nx.Graph()G.add_edge(A,B)G.add_edge(B,C)print(G.adj)

由圖6可得其存儲方式，由於我們為賦予邊權重，故權重處{ }沒有值，讀者可嘗試賦予權重，觀察結構如何變化。

又如想要得到某條邊的具體數據，可參見下例，運行結果如圖7所示。

G = nx.Graph()G.add_edge(1,2,color=red,weight=0.84,size=300)print(G[1][2]) # 獲取邊1-2的全部信息print(G[1][2][size]) # 獲取邊1-2的尺寸print(G[1][2][color]) #獲取邊的顏色

1.3 本章小結

本章對NetworkX做了一個基本的介紹，內容包括圖與網路的定義，NetworkX與網路的關係，NetworkX的基本操作，NetworkX中的圖論演算法及NetworkX中數據的存儲，並給出部分實例。

1.4 參考文獻

1. 謝金星, 邢文訓, 王振波. 網路優化[M]. 清華大學出版社, 2000.
2. Aric Hagberg, Dan Schult, Pieter Swart.NetworkX Reference[DB/OL].https://networkx.github.io/documentation/stable/_downloads/networkx_reference.pdf,2018-1-22.
3. 吳建軍，高自友，孫會君等. 城市交通系統複雜性[M]. 科學出版社, 2010.
4. Ahuja R K, Magnanti T L, Orlin J B. Network flows: theory, algorithms, and applications[M]. Prentice Hall, 1993.
5. 王航臣.基於級聯失效的航路網路中關鍵航路識別演算法[J].航空計算技術,2017,47(06):32-35.
6. 程朋,崔德光,吳澄.空中交通短期流量管理的動態網路流模型[J].清華大學學報(自然科學版),2000(11):114-118.

推薦閱讀：