二矫俺、圖
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
本書的前三章有關(guān)一些模型烹棉，它們描述了由組件和組件之間的連接組成的系統(tǒng)。例如忧陪，在生態(tài)食物網(wǎng)中扣泊，組件是物種近范，連接代表捕食者和獵物的關(guān)系。
在本章中延蟹，我介紹了 NetworkX评矩，一個用于構(gòu)建和研究這些模型的 Python 包。我們從 Erd?s-Rényi 模型開始阱飘，它具有一些有趣的數(shù)學(xué)屬性斥杜。在下一章中，我們將介紹更有用的沥匈，解釋現(xiàn)實系統(tǒng)的模型蔗喂。
本章的代碼在本書倉庫中的chap02.ipynb中。使用代碼的更多信息請參見第（高帖？）章缰儿。
2.1 圖是什么？
圖 2.1：表示社交網(wǎng)絡(luò)的有向圖
對于大多數(shù)人來說散址，圖是數(shù)據(jù)集的視覺表示返弹，如條形圖或股票價格對于時間的繪圖。這不是本章的內(nèi)容爪飘。
在本章中，圖是一個系統(tǒng)的表示拉背，它包含離散的互連元素师崎。元素由節(jié)點表示，互連由邊表示椅棺。
例如犁罩，你可以表示一個路線圖，每個城市都是一個節(jié)點两疚，每個城市之間的路線是一條邊床估。或者你可以表示一個社交網(wǎng)絡(luò)诱渤，每個人是節(jié)點丐巫，如果他們是朋友，兩個人之間有邊勺美，否則沒有递胧。
在某些圖中，邊具有長度赡茸，成本或權(quán)重等屬性缎脾。例如，在路線圖中占卧，邊的長度可能代表兩個城市之間的距離遗菠，或旅行時間联喘。在社交網(wǎng)絡(luò)中，可能會有不同的邊來表示不同種類的關(guān)系：朋友辙纬，商業(yè)伙伴等豁遭。
邊可以是有向或無向的，這取決于它們表示的關(guān)系是不對稱的還是對稱的牲平。在路線圖中堤框，你可能會使用有向邊表示單向街道，使用無向邊表示雙向街道纵柿。在某些社交網(wǎng)絡(luò)蜈抓，如 Facebook，好友是對稱的：如果 A 是 B 的朋友昂儒，那么 B 也是 A 的朋友沟使。但在 Twitter 上，“關(guān)注”關(guān)系并不對稱渊跋；如果 A 關(guān)注了 B腊嗡，這并不意味著 B 關(guān)注 A。因此拾酝，你可以使用無向邊來表示 Facebook 網(wǎng)絡(luò)燕少，并將有向邊用于 Twitter。
圖具有有趣的數(shù)學(xué)屬性蒿囤，并且有一個稱為圖論的數(shù)學(xué)分支客们，用于研究它們。
圖也很有用材诽，因為有許多現(xiàn)實世界的問題可以使用圖的算法來解決底挫。例如，Dijkstra 的最短路徑算法脸侥，是從圖中找到某個節(jié)點到所有其他節(jié)點的最短路徑的有效方式建邓。路徑是兩個節(jié)點之間的，帶有邊的節(jié)點序列睁枕。
圖的節(jié)點通常以圓形或方形繪制官边，邊通常以直線繪制。例如譬重，上面的有向圖中拒逮，節(jié)點可能代表在 Twitter 上彼此“關(guān)注”的三個人。線的較厚部分表示邊的方向臀规。在這個例子中滩援，愛麗絲和鮑勃相互關(guān)注，都關(guān)注查克塔嬉，但查克沒有關(guān)注任何人玩徊。
下面的無向圖展示了美國東北部的四個城市租悄；邊上的標(biāo)簽表示駕駛時間，以小時為單位恩袱。在這個例子中泣棋，節(jié)點的位置大致對應(yīng)于城市的地理位置，但是通常圖的布局是任意的畔塔。
2.2 NetworkX
圖 2.2：表示城市和高速公路的無向圖
為了表示圖潭辈，我們將使用一個名為 NetworkX 的包，它是 Python 中最常用的網(wǎng)絡(luò)庫澈吨。你可以在 https://networkx.github.io/ 上閱讀更多信息把敢，但是我們之后會解釋。
我們可以通過導(dǎo)入 NetworkX 和實例化nx.DiGraph來創(chuàng)建有向圖：
import networkx as nx
G = nx.DiGraph()
通常將 NetworkX 導(dǎo)入為nx谅辣。此時修赞，G是一個DiGraph對象，不包含節(jié)點和邊桑阶。我們可以使用add_node方法添加節(jié)點：
G.add_node('Alice')
G.add_node('Bob')
G.add_node('Chuck')
現(xiàn)在我們可以使用nodes方法獲取節(jié)點列表：
>>> G.nodes()
['Alice', 'Bob', 'Chuck']
添加邊的方式幾乎相同：
G.add_edge('Alice', 'Bob')
G.add_edge('Alice', 'Chuck')
G.add_edge('Bob', 'Alice')
G.add_edge('Bob', 'Chuck')
我們可以使用edges來獲取邊的列表：
>>> G.edges()
[('Alice', 'Bob'), ('Alice', 'Chuck'),
('Bob', 'Alice'), ('Bob', 'Chuck')]
NetworkX 提供了幾個繪圖的功能柏副；draw_circular將節(jié)點排列成一個圓，并使用邊將它們連接：
nx.draw_circular(G,
node_color=COLORS[0],
node_size=2000,
with_labels=True)
這就是我用來生成圖（蚣录？）的代碼割择。with_labels選項標(biāo)注了節(jié)點；在下一個例子中萎河，我們將看到如何標(biāo)注邊锨推。
為了產(chǎn)生圖（？）公壤，我們以一個字典開始，它將每個城市的名稱椎椰，映射為對應(yīng)的經(jīng)緯度：
pos = dict(Albany=(-74, 43),
Boston=(-71, 42),
NYC=(-74, 41),
Philly=(-75, 40))
因為這是個無向圖厦幅，我實例化了nx.Graph：
G = nx.Graph()
之后我可以使用add_nodes_from來迭代pos的鍵，并將它們添加為節(jié)點慨飘。
G.add_nodes_from(pos)
下面我會創(chuàng)建一個字典确憨，將每條邊映射為對應(yīng)的駕駛時間。
drive_times = {('Albany', 'Boston'): 3,
('Albany', 'NYC'): 4,
('Boston', 'NYC'): 4,
('NYC', 'Philly'): 2}
現(xiàn)在我可以使用add_edges_from瓤的，它迭代了drive_times的鍵休弃，并將它們添加為邊：
G.add_edges_from(drive_times)
現(xiàn)在我不使用draw_circular，它將節(jié)點排列成一個圓圈圈膏，而是使用draw塔猾，它接受pos作為第二個參數(shù)：
nx.draw(G, pos,
node_color=COLORS[1],
node_shape='s',
node_size=2500,
with_labels=True)
pos是一個字典，將每個城市映射為其坐標(biāo)稽坤；draw使用它來確定節(jié)點的位置丈甸。
要添加邊的標(biāo)簽糯俗，我們使用draw_networkx_edge_labels：
nx.draw_networkx_edge_labels(G, pos,
edge_labels=drive_times)
drive_times是一個字典，將每條邊映射為它們之間的駕駛距離睦擂，每條邊表示為城市名稱的偶對得湘。這就是我生成圖（？）的方式顿仇。
在這兩個例子中淘正，這些節(jié)點是字符串，但是通常它們可以是任何可哈希的類型臼闻。
2.3 隨機圖
隨機圖就像它的名字一樣：一個隨機生成的節(jié)點和邊的圖鸿吆。當(dāng)然，有許多隨機過程可以生成圖些阅，所以有許多種類的隨機圖伞剑。
其中一個更有趣的是 Erd?s-Rényi 模型，PaulErd?s 和 AlfrédRényi 在 20 世紀(jì) 60 年代研究過它市埋。
Erd?s-Rényi 圖（ER 圖）的特征在于兩個參數(shù)：n是節(jié)點的數(shù)量黎泣，p是任何兩個節(jié)點之間存在邊的概率。見 http://en.wikipedia.org/wiki/Erdos-Renyi_model缤谎。
Erd?s 和 Rényi 研究了這些隨機圖的屬性抒倚；其令人驚奇的結(jié)果之一就是，隨著隨機的邊被添加坷澡，隨機圖的屬性會突然變化托呕。
展示這類轉(zhuǎn)變的一個屬性是連通性。如果每個節(jié)點到每個其他節(jié)點都存在路徑频敛，那么無向圖是連通的项郊。
在 ER 圖中，當(dāng)p較小時斟赚，圖是連通圖的概率非常低着降，而p較大時接近1。在這兩種狀態(tài)之間拗军，在p的特定值處存在快速轉(zhuǎn)變任洞，表示為p*。
Erd?s 和 Rényi 表明发侵，這個臨界值是p* = lnn / n交掏，其中n是節(jié)點數(shù)。如果p < p*刃鳄，隨機圖G(n, p)不太可能連通盅弛，并且如果p > p*，則很可能連通。
為了測試這個說法熊尉，我們將開發(fā)算法來生成隨機圖罐柳，并檢查它們是否連通。
2.4 生成圖
我將首先生成一個完全圖狰住，這是一個圖张吉，其中每個節(jié)點都彼此連接。
這是一個生成器函數(shù)催植，它接收節(jié)點列表并枚舉所有不同的偶對肮蛹。如果你不熟悉生成器函數(shù)，你可能需要閱讀附錄创南？伦忠，然后回來。
def all_pairs(nodes):
for i, u in enumerate(nodes):
for j, v in enumerate(nodes):
if i>j:
yield u, v
你可以使用all_pairs來構(gòu)造一個完全圖稿辙。
def make_complete_graph(n):
G = nx.Graph()
nodes = range(n)
G.add_nodes_from(nodes)
G.add_edges_from(all_pairs(nodes))
return G
make_complete_graph接受節(jié)點數(shù)n昆码，并返回一個新的Graph，擁有n個節(jié)點邻储，所有節(jié)點之間都有邊赋咽。
以下代碼生成了一個包含 10 個節(jié)點的完全圖，并繪制出來吨娜。
complete = make_complete_graph(10)
nx.draw_circular(complete,
node_color=COLORS[2],
node_size=1000,
with_labels=True)
圖（脓匿？）顯示了結(jié)果。不久之后宦赠，我們將修改此代碼來生成 ER 圖陪毡，但首先我們將開發(fā)函數(shù)來檢查圖是否是連通的。
2.5 連通圖
如果每個節(jié)點到每個其他節(jié)點都存在路徑勾扭，這個圖就是連通圖毡琉。請見http://en.wikipedia.org/wiki/Connectivity_(graph_theory)。
對于許多涉及圖的應(yīng)用妙色，檢查圖是否連通是很有用的绊起。幸運的是，有一個簡單的算法燎斩。
你可以從任何節(jié)點起步，并檢查是否可以到達(dá)所有其他節(jié)點蜂绎。如果你可以到達(dá)一個節(jié)點v栅表，你可以到達(dá)v的任何一個鄰居，他們是v通過邊連接的任何節(jié)點师枣。
Graph類提供了一個稱為neighbors的方法怪瓶，返回給定節(jié)點的鄰居列表。例如践美，在上一節(jié)中我們生成的完全圖中：
>>> complete.neighbors(0)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
假設(shè)我們從節(jié)點s起步洗贰。我們可以將s標(biāo)記為“已訪問”找岖，然后我們可以標(biāo)記它的鄰居。然后我們標(biāo)記鄰居的鄰居敛滋，依此類推许布，直到你無法再到達(dá)任何節(jié)點。如果訪問了所有節(jié)點绎晃，則圖是連通圖蜜唾。
以下是 Python 中的樣子：
def reachable_nodes(G, start):
seen = set()
stack = [start]
while stack:
node = stack.pop()
if node not in seen:
seen.add(node)
stack.extend(G.neighbors(node))
return seen
reachable_nodes接受Graph和起始節(jié)點start，并返回可以從start到達(dá)的節(jié)點集合庶艾，他們袁余。
最初，已訪問的集合是空的咱揍，我們創(chuàng)建一個名為stack的列表颖榜，跟蹤我們發(fā)現(xiàn)但尚未處理的節(jié)點。最開始煤裙，棧包含單個節(jié)點start掩完。
現(xiàn)在，每次在循環(huán)中积暖，我們：
- 從棧中刪除一個節(jié)點藤为。
- 如果節(jié)點已在
seen中，我們返回到步驟 1夺刑。 - 否則缅疟，我們將節(jié)點添加到
seen，并將其鄰居添加到棧遍愿。
當(dāng)棧為空時存淫，我們無法再到達(dá)任何節(jié)點，所以我們終止了循環(huán)并返回沼填。
例如桅咆，我們可以找到從節(jié)點0可到達(dá)的，完全圖中的所有節(jié)點：
>>> reachable_nodes(complete, 0)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
最初坞笙，棧包含節(jié)點0岩饼，seen是空的。第一次循環(huán)中薛夜，節(jié)點0添加到了seen籍茧，所有其他節(jié)點添加到了棧中（因為它們都是節(jié)點0的鄰居）。
下一次循環(huán)中梯澜，pop返回棧中的最后一個元素寞冯，即節(jié)點9.因此，節(jié)點9被添加到seen，并且其鄰居被添加到棧吮龄。
請注意俭茧，同一個節(jié)點在棧中可能會出現(xiàn)多次；實際上漓帚，具有k個鄰居的節(jié)點將添加到棧k次母债。稍后我們將尋找方法，來使此算法更有效率胰默。
我們可以使用reachable_nodes來編寫is_connected：
def is_connected(G):
start = next(G.nodes_iter())
reachable = reachable_nodes(G, start)
return len(reachable) == len(G)
is_connected通過調(diào)用nodes_iter來選擇一個起始節(jié)點场斑，node_iter返回一個迭代器對象，并將結(jié)果傳遞給next牵署，返回第一個節(jié)點漏隐。
reachable獲取了一組節(jié)點，它們可以從start到達(dá)奴迅。如果這個集合的大小與圖的大小相同青责，那意味著我們可以訪問所有節(jié)點，也就是這個圖是連通的取具。
一個完全圖是連通的脖隶，毫不奇怪：
>>> is_connected(complete)
True
下一節(jié)中，我們會生成 ER 圖暇检，并檢查它們是否是連通的产阱。
2.6 生成 ER圖
圖 2.4：ER 圖，
n=10块仆，p=0.3
ER 圖G(n, p)包含n個節(jié)點构蹬，每對節(jié)點以概率為p的邊連接。生成 ER 圖類似于生成完全圖悔据。
以下生成器函數(shù)枚舉所有可能的邊庄敛，并使用輔助函數(shù)flip，來選擇哪些應(yīng)添加到圖中：
def random_pairs(nodes, p):
for i, u in enumerate(nodes):
for j, v in enumerate(nodes):
if i>j and flip(p):
yield u, v
flip以給定概率p返回True科汗，以互補的概率1-p返回False藻烤。
from numpy.random import random
def flip(p):
return random() < p
最后，make_random_graph生成并返回 ER 圖G(n, p)头滔。
def make_random_graph(n, p):
G = nx.Graph()
nodes = range(n)
G.add_nodes_from(nodes)
G.add_edges_from(random_pairs(nodes, p))
return G
make_random_graph幾乎和make_complete_graph怖亭，唯一的不同是它使用random_pairs而不是all_pairs。
這里是p=0.3的例子：
random_graph = make_random_graph(10, 0.3)
圖（坤检？）展示了結(jié)果兴猩。這個圖是連通圖；事實上缀蹄，大多數(shù)p=10并且p=3的 ER 圖都是連通圖。在下一節(jié)中，我們將看看有多少缺前。
2.7 連通性的概率
圖 2.5：連通性的概率蛀醉，
n=10，p是一個范圍衅码。豎直的線展示了預(yù)測的臨界值拯刁。
圖 2.6：連通性的概率立润，
n是多個值蓝谨，p是一個范圍。
對于n和p的給定值泽谨，我們想知道G(n, p)連通的概率奶躯。我們可以通過生成大量隨機圖帚桩，來計算有多少個來估計它。就是這樣：
def prob_connected(n, p, iters=100):
count = 0
for i in range(iters):
random_graph = make_random_graph(n, p)
if is_connected(random_graph):
count += 1
return count/iters
iters是我們生成的隨機圖的數(shù)量嘹黔。隨著我們增加iter账嚎，估計的概率就會更加準(zhǔn)確。
>>> prob_connected(10, 0.3, iters=10000)
0.6454
在具有這些參數(shù)的 10000 個 ER 圖中儡蔓，6498 個是連通的郭蕉，因此我們估計其中65％是連通的。所以 0.3 接近臨界值喂江，在這里連通概率從接近 0 變?yōu)榻咏?1召锈。根據(jù) Erd?s 和 Rényi，p* = lnn / n = 0.23获询。
我們可以通過估計一系列p值的連通概率涨岁，來更清楚地了解轉(zhuǎn)變：
import numpy as np
n = 10
ps = np.logspace(-2.5, 0, 11)
ys = [prob_connected(n, p) for p in ps]
這是我們看到的使用 NumPy 的第一個例子。按照慣例筐付，我將 NumPy 導(dǎo)入為np卵惦。函數(shù)logspace返回從10 ** -2.5到10 ** 0 = 1的 11 個元素的數(shù)組，在對數(shù)刻度上等間隔瓦戚。
為了計算y沮尿，我使用列表推導(dǎo)來迭代ps的元素，并計算出每個值為p的隨機圖的連通概率较解。
圖（畜疾？）展示了結(jié)果，豎直的線為p*印衔。從 0 到 1 的轉(zhuǎn)變發(fā)生在預(yù)測的臨界值附近啡捶。在對數(shù)刻度上，這個轉(zhuǎn)變大致對稱奸焙。
對于較大的n值瞎暑，圖（彤敛？）展示了類似的結(jié)果。隨著n的增加了赌，臨界值越來越小墨榄，轉(zhuǎn)變越來越突然。
這些實驗與 Erd?s 和 Rényi 在其論文中證明的結(jié)果一致勿她。
2.8 圖的算法分析
這一章中袄秩，我提出了一個檢查圖是否連通的算法；在接下來的幾章中逢并，我們將再次看到更多的圖的算法之剧。并且我們要分析這些算法的性能，了解它們的運行時間如何隨著圖大小的增加而增長砍聊。
如果你還不熟悉算法分析背稼，在你繼續(xù)之前，你應(yīng)該閱讀附錄一辩恼。
圖算法的增長級別通常表示為頂點數(shù)量n雇庙，以及邊數(shù)量m的函數(shù)。
作為一個例子灶伊，我們分析從前面的reachable_nodes：
def reachable_nodes(G, start):
seen = set()
stack = [start]
while stack:
node = stack.pop()
if node not in seen:
seen.add(node)
stack.extend(G.neighbors(node))
return seen
每次循環(huán)疆前，我們從棧中彈出一個節(jié)點；默認(rèn)情況下聘萨，pop刪除并返回列表的最后一個元素竹椒，這是一個常數(shù)時間的操作。
接下來我們檢查節(jié)點是否被已訪問米辐，這是一個集合胸完，所以檢查成員是常數(shù)時間。
如果節(jié)點還沒有訪問翘贮，我們添加它是常量時間赊窥，然后將鄰居添加到棧中，這相對于鄰居數(shù)量是線性的狸页。
為了使用n和m表達(dá)運行時間锨能，我們可以將每個節(jié)點添加到seen和stack的總次數(shù)加起來。
每個節(jié)點只添加一次芍耘，所以添加的總數(shù)為n址遇。
但是節(jié)點可能多次被添加到棧，具體取決于它們有多少鄰居斋竞。如果節(jié)點具有k個鄰居倔约，則它會被添加到棧k次。當(dāng)然坝初，如果它有k個鄰居浸剩，那意味著它擁有k個邊钾军。
所以添加到棧的總數(shù)是邊的數(shù)量m的兩倍，由于我們考慮每個邊兩次绢要。
因此巧颈，這個函數(shù)的增長級別為O(n + m)，我們可以說袖扛，即運行時間與n或m成正比，以較大者為準(zhǔn)十籍。
如果我們知道n和m之間的關(guān)系蛆封，我們可以簡化這個表達(dá)式。例如勾栗，在完全圖中惨篱，邊數(shù)是n(n-1)/ 2，它屬于O(n^2)围俘。所以對于一個完全圖砸讳，reachable_nodes是二次于n的。
2.9 練習(xí)
本章的代碼在chap02.ipynb中界牡，它是本書的倉庫中的 Jupyter 筆記本簿寂。使用此代碼的更多信息，請參閱第（宿亡？）節(jié)常遂。
練習(xí) 1：啟動chap02.ipynb并運行代碼。筆記本中嵌入了一些簡單的練習(xí)挽荠，你可能想嘗試一下克胳。
練習(xí) 2：我們分析了reachable_nodes的性能，并將其分類為O(n + m)圈匆，其中n是節(jié)點數(shù)漠另，m是邊數(shù)。繼續(xù)分析跃赚，is_connected的增長級別是什么笆搓？
def is_connected(G):
start = next(G.nodes_iter())
reachable = reachable_nodes(G, start)
return len(reachable) == len(G)
練習(xí) 3 ：在我實現(xiàn)reachable_nodes時，你可能很困惑来累，因為向棧中添加所有鄰居而不檢查它們是否已訪問砚作，明顯是低效的。編寫一個該函數(shù)的版本嘹锁，在將鄰居添加到棧之前檢查它們葫录。這個“優(yōu)化”是否改變了增長級別？它是否使函數(shù)更快领猾？
譯者注：在彈出節(jié)點時將其添加到
seen米同，在遍歷鄰居時檢查它們是否已訪問骇扇。
練習(xí) 4：
實際上有兩種 ER 圖。我們在本章中生成的一種面粮，G(n少孝，p)的特征是兩個參數(shù)，節(jié)點數(shù)量和節(jié)點之間的邊的概率熬苍。
一種替代定義表示為G(n稍走，m)，也以兩個參數(shù)為特征：節(jié)點數(shù)n和邊數(shù)m柴底。在這個定義中婿脸，邊數(shù)是固定的，但它們的位置是隨機的柄驻。
使用這個替代定義狐树，重復(fù)這一章的實驗。這里是幾個如何處理它的建議：
編寫一個名為
m_pairs的函數(shù)鸿脓，該函數(shù)接受節(jié)點列表和邊數(shù)m抑钟，并返回隨機選擇的m個邊。一個簡單的方法是野哭，生成所有可能的邊的列表在塔，并使用random.sample。編寫一個名為
make_m_graph的函數(shù)拨黔，接受n和m心俗，并返回n個節(jié)點和m個邊的隨機圖。創(chuàng)建一個
prob_connected的版本蓉驹，使用make_m_graph而不是make_random_graph城榛。計算一系列
m值的連通概率。
與第一類 ER 圖的結(jié)果相比态兴，該實驗的結(jié)果如何狠持？
