networkx完全指南
- 2020 年 4 月 29 日
- AI
雖然很慢，但是作為圖演算法領域的菜鳥來說，networkx可以幫助快速建立起對圖數據的感知，並且其實對於中小型數據集，network是非常好上手的。當然工業級的還得用neo4j搭配graphx，畢竟動輒就是上億個節點幾十億條邊的巨量數據。
networkx主要包含了五個模組：
1、圖對象的類；
2、創建標準圖的生成器；
3、 在現有數據集中讀取的IO介面（比如從csv中讀取邊和節點的數據）；
4、經典的傳統圖演算法（不包含圖神經網路系列演算法）；
5、一些方便的畫圖函數
networkx支援創建四種圖類型：
1、Graph 無向圖，允許節點與自身形成閉環；
2、DiGraph 有向圖；
3、MultiGraph 多重無向圖， 一種靈活的圖類，允許節點對之間有多個無向邊。 額外的靈活性導致性能的一些下降，不過通常不顯著；
4、MultiDiGraph 多重有向圖
不同類型的圖的定義如下：
import networkx as nx
>>> G = nx.Graph()
>>> G = nx.DiGraph()
>>> G = nx.MultiGraph()
>>> G = nx.MultiDiGraph()所有圖類都允許任何哈希對象作為節點。 哈希對象包括字元串、元組、整數或是另一個圖結構等等。
圖內部數據結構基於鄰接列表表示，並使用Python字典數據結構實現。
圖鄰接結構使用 Python的dict來實現；外部字典由節點鍵控到本身是字典的值，由相鄰節點鍵控到 與該邊緣相關聯的邊緣屬性。 這種「dict-of-dict」結構允許快速添加、刪除和查找大圖中的節點和鄰居。 底層數據結構通過類定義中的方法(編程介面「API」)直接訪問。
下面介紹使用networkx構建圖的流程，首先：
1.2 Graphs
使用Network X時要做的第一選擇是使用什麼類型的圖形對象。 圖（網路）是節點的集合，以及作為節點對的邊的集合。 屬性 通常與節點和/或邊相關聯。networkx支援四種類型的圖的構建上面提到過了：
其次：
1.2.1 Nodes and Edges
指定完圖類型之後，下一步是指定節點和邊的類型， 如果用戶關心的是網路的拓撲結構，那麼使用整數或字元串作為節點是有意義的，不需要考慮邊數據。 如果已經有了描述節點的數據結構，可以簡單地使用該結構作為節點，只要它是hashable的。 如果不可散列，則可以使用唯一標識符來表示節點，並將數據分配為節點屬性。
邊通常有與它們相關的數據。 任意數據可以作為邊屬性與邊相關聯。 如果數據是數字的，其意圖是表示加權圖，則使用「weight」 作為其屬性的關鍵字。 一些圖形演算法，如Dijkstra的最短路徑演算法，默認情況下使用這個屬性名（「weight」）來獲得每個邊緣的權重。
屬性可以通過在添加邊時使用key/value 對來分配給邊。 可以使用任何關鍵字來命名屬性，然後可以使用該屬性關鍵字查詢邊數據。
通過上述的兩個流程，我們就定義完畢一張完整的圖了。下面介紹實際的程式碼實現。
1.3 Graph Creation
networkX圖對象可以以下三種方式之一創建：
1、 圖形生成器 Graph generators -創建網路拓撲的標準方法；
2、 從預先存在的（通常是文件）來源導入數據；
3、 顯式添加邊緣和節點；
顯式添加和刪除節點/邊緣是最容易描述的。 每個圖形對象提供操作圖形的方法。 例如：
>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge(1, 2) # default edge data=1
>>> G.add_edge(2, 3, weight=0.9) # specify edge dataadd_edge的過程中，默認自動生成對應的節點，例如G.add_edge(1, 2)自動生成型的節點1和2，而G.add_edge(2, 3, weight=0.9)則自動生成節點3，因為節點2上一步已經生成過程，並且這裡是增加了帶權的邊，權重為0.9
邊屬性可以是任何hashable的對象：
>>> import math
>>> G.add_edge('y', 'x', function=math.cos)
>>> G.add_node(math.cos) # any hashable can be a node你可以同時添加很多邊：
>>> elist = [(1, 2), (2, 3), (1, 4), (4, 2)]
>>> G.add_edges_from(elist)
>>> elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
>>> G.add_weighted_edges_from(elist)上述是添加無權邊和帶權邊的兩種方式，無權邊的默認權重是1.0；
1.4 Graph Reporting
類視圖提供節點，鄰居，邊和度的基本報告. 這些視圖提供了屬性的迭代以及成員查詢和數據屬性查找的方法。 視圖是指圖形數據結構，因此對圖形的更改反映在視圖中。這類似於Python3中的字典視圖。 如果您想在迭代時更改圖形，則需要使用例如。 (for e in list(G.edges):)的方法來處理， 視圖提供類似集合的操作，例如。 聯合與交叉，以及類似dict的數據屬性的查找和迭代，G.edges[u, v][‘color’] and for e, datadict in G.edges.items()，方法G.edges.items()和G.edges.values()是熟悉的pythonDicts api的形式。
邊的基本圖形關係可以通過兩種方式得到.：尋找節點的鄰居，也可以尋找邊， 我們開玩笑地定義：關注節點/鄰居的人是以節點為中心的，關注邊緣的人是以邊緣為中心的， networkX的設計者傾向於以節點為中心，並將邊視為節點之間的關係。 可以通過選擇查找符號來看到這一點，例如G[u]提供鄰居（鄰接），而邊查找是G.edges[u，v]。稀疏圖的大多數數據結構本質上是鄰接列表（adjacency lists），因此符合這一觀點。 最後，當然，用哪種方式檢查圖表並不重要。 G.edges 重複表示無向邊（無向邊等價於雙向邊，通過這種方式來統一兩種便類型），而neighbor reporting 顯示節點的兩個方向的所有領節點。
任何比邊、鄰居和度更複雜的屬性都是由函數提供的，例如 nx.triangles(G, n)，返回在圖G上，n節點所在的三角關係的數量。這些函數都統一在networkx的algorithms模組。
1.5 Algorithms
一些圖演算法提供了網路X。 其中包括最短路徑、廣度優先搜索（參見遍歷）、聚類和同構演算法等。 例如，使用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'))
['a', 'c', 'd']1.6 Drawing
基本繪圖函數基本上使用通過字典提供的位置將節點放置在散點圖上，或者使用布局函數計算位置。使用的是graphiz和pydot來進行建議畫圖，至於畫圖的拓展，可以藉助外部軟體。
>>> import matplotlib.pyplot as plt
>>> G = nx.cubical_graph()
>>> plt.subplot(121)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw(G) # default spring_layout
>>> plt.subplot(122)
<matplotlib.axes._subplots.AxesSubplot object at ...>
>>> nx.draw(G, pos=nx.circular_layout(G), node_color='r', edge_color='b')
1.7 Data Structure
networkx使用 字典-字典-字典。。。這樣的符合結構來作為構建圖的基礎數據結構， 這允許快速查找，並對大型稀疏網路進行合理的存儲。 鍵是節點，因此G[u]返回一個鄰接字典，該鄰接字典由邊緣屬性字典的鄰居鍵。
鍵是節點，因此G[u]返回u的鄰節點，以領接字典的形式展現，通過list( G.adj.items())可以很直觀的看到整個圖的領接情況。
表達式G[u][v]返回邊屬性字典本身。優勢：
下面是一個例子：
>>> G = nx.Graph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> print(G.adj)
{'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}}
這裡介紹了另外兩種圖類型的實現機制。
圖提供了邊數據屬性的兩個介面：adjacency and edges。 因此，G[u][v][『wid h』]與G.edges[u，v][『width』]作用是相同的。
>>> G = nx.Graph()
>>> G.add_edge(1, 2, color='red', weight=0.84, size=300)
>>> print(G[1][2]['size'])
300
>>> print(G.edges[1, 2]['color'])
red
NetworkX提供了用於存儲圖形的數據結構和方法。
所有NetworkX圖形類都允許（可哈希）Python對象作為節點，並且任何Python對象都可以設定為邊屬性。圖類的選擇取決於您要表示的圖的結構。
見名知意。
2.2 Basic graph types
2.2.1 Graph—Undirected graphs with self loops
class Graph(incoming_graph_data=None, **attr) 源碼文檔
Base class for undirected graphs.
A Graph stores nodes and edges with optional data, or attributes.
Graphs hold undirected edges. Self loops are allowed but multiple (parallel) edges are not.
Nodes can be arbitrary (hashable) Python objects with optional key/value attributes. By convention None is not used as a node.
Edges are represented as links between nodes with optional key/value attributes.
Parameters
• incoming_graph_data (input graph (optional, default: None)) – Data to initialize graph. If None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists,
NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
• attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.
See also:
DiGraph, MultiGraph, MultiDiGraph, OrderedGraph
下面是一些簡單的示例：
屬性圖:
每個圖，節點和邊都可以在關聯的屬性字典中保存鍵/值屬性對（鍵必須是可哈希的）。 默認情況下，這些為空，但可以使用add_edge，add_node或直接操作分別名為graph，node和edge的屬性字典進行添加或更改。
networkx和neo4j一樣使用的是屬性圖。基本的nodes和edges構成graph，並且nodes，edges，graph都以字典的形式存儲其屬性。
下面是一些示例：
Shortcuts:
Many common graph features allow python syntax to speed reporting.
通常，遍歷圖形所有邊的最佳方法是通過鄰居。 The neighbors are reported as an adjacency-dict G.adj or G.adjacency() ，也就是通過Graph的領結矩陣的方式便利最快捷方便：
>>> for n, nbrsdict in G.adjacency():
... for nbr, eattr in nbrsdict.items():
... if 'weight' in eattr:
... # Do something useful with the edges
... passBut the edges() method is often more convenient:
>>> for u, v, weight in G.edges.data('weight'):
... if weight is not None:
... # Do something useful with the edges
... pass算了，隨緣翻譯吧
