三懊缺、小世界圖
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
現(xiàn)實(shí)世界中的許多網(wǎng)絡(luò)，包括社交網(wǎng)絡(luò)在內(nèi)培他，具有“小世界屬性”鹃两，即節(jié)點(diǎn)之間的平均距離，以最短路徑上的邊數(shù)來衡量俊扳，遠(yuǎn)遠(yuǎn)小于預(yù)期。
在本章中，我介紹了斯坦利·米拉格（Stanley Milgram）的著名的“小世界實(shí)驗(yàn)”涕刚，這是小世界屬性在真正的社交網(wǎng)絡(luò)中的第一次科學(xué)演示。之后我們將考慮 Watts-Strogatz 圖峡捡，它是一個(gè)小世界圖的模型。我將復(fù)制 Watts 和 Strogatz 所做的實(shí)驗(yàn)埂奈，并解釋它打算展示的東西拗引。
這個(gè)過程中楚里，我們將看到兩種新的圖算法：廣度優(yōu)先搜索（BFS）和 Dijkstra 算法，用于計(jì)算圖中節(jié)點(diǎn)之間的最短路徑满葛。
本章的代碼在本書倉庫的chap03.ipynb中玩般。使用代碼的更多信息請參見第（？）章核行。
3.1 Stanley Milgram
斯坦利·米拉格（Stanley Milgram）是美國社會心理學(xué)家杨刨，他進(jìn)行了兩項(xiàng)最著名的社會科學(xué)實(shí)驗(yàn)，即 Milgram 實(shí)驗(yàn)闯估，研究人們對權(quán)威的服從（http://en.wikipedia.org/wiki/Milgram_experiment）和小世界實(shí)驗(yàn)侠姑，研究了社交網(wǎng)絡(luò)的結(jié)構(gòu)（http://en.wikipedia.org/wiki/Small_world_phenomenon）安吁。
在小世界實(shí)驗(yàn)中，Milgram 向堪薩斯州威奇托（Wichita, Kansas）的幾個(gè)隨機(jī)選擇的人發(fā)送了包裹谊路，帶有一個(gè)指示萝究，要求他們向馬薩諸塞州沙龍（Sharon, Massachusetts）的目標(biāo)人員發(fā)送一封附帶的信（在我長大的地方免都，波士頓附近），目標(biāo)人員通過名字和職業(yè)確定帆竹。受訪者被告知绕娘，只有當(dāng)他親自認(rèn)識目標(biāo)人員時(shí)，才可以將該信直接郵寄給目標(biāo)栽连；否則他們按照指示险领，將信和同一個(gè)指示發(fā)送給他們認(rèn)為的，更有可能認(rèn)識目標(biāo)人員的親戚或朋友升酣。
許多信件從來沒有發(fā)出過舷暮，但是對于發(fā)出的信件，平均路徑長度（信件轉(zhuǎn)發(fā)次數(shù)）的大約為 6噩茄。這個(gè)結(jié)果用于確認(rèn)以前的觀察（和猜測）下面，社交網(wǎng)絡(luò)中任何兩個(gè)人之間的通常距離是“六度分隔”。
這個(gè)結(jié)論令人驚訝绩聘，因?yàn)榇蠖鄶?shù)人都希望社交網(wǎng)絡(luò)本地化 - 人們往往會靠近他們的朋友 - 而且在一個(gè)具有本地連接的圖中沥割，路徑長度往往會與地理距離成比例增加。例如凿菩，我的大多數(shù)朋友都住在附近机杜，所以我猜想社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的平均距離是大約 50 英里。威奇托距離波士頓約有 1600 英里衅谷，所以如果 Milgram 的信件穿過了社交網(wǎng)絡(luò)的典型環(huán)節(jié)椒拗，那么他們應(yīng)該有 32 跳，而不是 6 跳获黔。
3.2 Watts 和 Strogatz
1998年蚀苛，Duncan Watts 和 Steven Strogatz 在 Nature 雜志上發(fā)表了一篇“小世界網(wǎng)絡(luò)的集體動態(tài)”（Collective dynamics of ’small-world’ networks）論文，提出了小世界現(xiàn)象的解釋玷氏。 你可以從 http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html 下載堵未。
Watts 和 Strogatz 從兩種很好理解的圖開始：隨機(jī)圖和正則圖。在隨機(jī)圖中盏触，節(jié)點(diǎn)隨機(jī)連接渗蟹。在正則圖中块饺，每個(gè)節(jié)點(diǎn)具有相同數(shù)量的鄰居。他們考慮這些圖的兩個(gè)屬性雌芽，群聚性和路徑長度：
群聚是圖表的“集團(tuán)性”（cliquishness）的度量授艰。在圖中，集團(tuán)是所有節(jié)點(diǎn)的子集膘怕，它們彼此連接想诅；在一個(gè)社交網(wǎng)絡(luò)中召庞，集團(tuán)是一群人岛心，彼此都是朋友。Watts 和 Strogatz 定義了一個(gè)群聚系數(shù)篮灼，用于量化兩個(gè)節(jié)點(diǎn)彼此連接忘古，并同時(shí)連接到同一個(gè)節(jié)點(diǎn)的可能性。
路徑長度是兩個(gè)節(jié)點(diǎn)之間的平均距離的度量诅诱，對應(yīng)于社交網(wǎng)絡(luò)中的分離度髓堪。
Watts 和 Strogatz 表明，正則圖具有高群聚性和長路徑長度娘荡，而大小相同的隨機(jī)圖通常具有群聚性和短路徑長度干旁。所以這些都不是一個(gè)很好的社交網(wǎng)絡(luò)模型，它是高群聚性與短路徑長度的組合炮沐。
他們的目標(biāo)是創(chuàng)造一個(gè)社交網(wǎng)絡(luò)的生成模型争群。生成模型通過為構(gòu)建或?qū)е卢F(xiàn)象的過程建模，試圖解釋現(xiàn)象大年。Watts 和 Strogatz 提出了用于構(gòu)建小世界圖的過程：
從一個(gè)正則圖開始换薄，節(jié)點(diǎn)為
n，每個(gè)節(jié)點(diǎn)連接k個(gè)鄰居翔试。選擇邊的子集轻要，并將它們替換為隨機(jī)的邊來“重新布線”。
邊的重新布線的概率是參數(shù)p垦缅，它控制圖的隨機(jī)性冲泥。當(dāng)p = 0時(shí)，該圖是正則的壁涎；p = 1是隨機(jī)的凡恍。
Watts 和 Strogatz 發(fā)現(xiàn)，較小的p值產(chǎn)生高群聚性的圖粹庞，如正則圖咳焚，短路徑長度的圖，如隨機(jī)圖庞溜。
在本章中革半，我將按以下步驟復(fù)制 Watts 和 Strogatz 實(shí)驗(yàn)：
- 我們將從構(gòu)建一個(gè)環(huán)格（ring lattice）開始碑定，這是一種正則圖。
- 然后我們和 Watts 和 Strogatz 一樣重新布線又官。
- 我們將編寫一個(gè)函數(shù)來測量群聚度延刘，并使用 NetworkX 函數(shù)來計(jì)算路徑長度。
- 然后六敬，我們?yōu)榉秶鷥?nèi)的
p值計(jì)算群聚度和路徑長度碘赖。 - 最后，我將介紹一種用于計(jì)算最短路徑的高效算法外构，Dijkstra 算法普泡。
3.3 環(huán)格
圖 3.1
n=10，k=4的環(huán)格
正則圖是每個(gè)節(jié)點(diǎn)具有相同數(shù)量的鄰居的圖审编；鄰居的數(shù)量也稱為節(jié)點(diǎn)的度撼班。
環(huán)格是一種正則圖，Watts 和 Strogatz 將其用作模型的基礎(chǔ)垒酬。 在具有n個(gè)節(jié)點(diǎn)的環(huán)格中砰嘁，節(jié)點(diǎn)可以排列成圓形，每個(gè)節(jié)點(diǎn)連接k個(gè)最近鄰居勘究。
例如矮湘，n = 3和k = 2的環(huán)形網(wǎng)格將擁有以下邊：(0, 1), (1, 2), (2, 0)。 請注意口糕，邊從編號最高的節(jié)點(diǎn)“繞回”0缅阳。
更一般地，我們可以像這樣枚舉邊：
def adjacent_edges(nodes, halfk):
n = len(nodes)
for i, u in enumerate(nodes):
for j in range(i+1, i+halfk+1):
v = nodes[j % n]
yield u, v
adjacent_edges接受節(jié)點(diǎn)列表和參數(shù)halfk走净，它是k的一半券时。它是一個(gè)生成器函數(shù)，一次產(chǎn)生一個(gè)邊伏伯。它使用模運(yùn)算符%橘洞，從編號最高的節(jié)點(diǎn)繞回最低的節(jié)點(diǎn)。
我們可以這樣測試：
>>> nodes = range(3)
>>> for edge in adjacent_edges(nodes, 1):
... print(edge)
(0, 1)
(1, 2)
(2, 0)
現(xiàn)在我們可以使用adjacent_edges來生成環(huán)格说搅。
def make_ring_lattice(n, k):
G = nx.Graph()
nodes = range(n)
G.add_nodes_from(nodes)
G.add_edges_from(adjacent_edges(nodes, k//2))
return G
注意炸枣，make_ring_lattice使用地板除計(jì)算halfk，所以如果k是奇數(shù)弄唧，它將向下取整并產(chǎn)生具有度k-1的環(huán)格适肠。這可能不是我們想要的，但現(xiàn)在還不錯(cuò)候引。
我們可以像這樣測試函數(shù)：
lattice = make_ring_lattice(10, 4)
圖（侯养？）展示了結(jié)果。
3.4 WS 圖
圖 3.2 WS 圖澄干，
n=20逛揩，k=4柠傍，p=0（左邊），p=0.2（中間）辩稽，p=1（右邊）惧笛。
為了制作 Watts-Strogatz（WS）圖，我們從一個(gè)環(huán)格開始逞泄，并為一些邊“重新布線”患整。 在他們的論文中，Watts 和 Strogatz 以特定順序考慮邊喷众，并用概率p重新布置每個(gè)邊各谚。 如果邊被重新布置，則它們使第一個(gè)節(jié)點(diǎn)保持不變侮腹，并隨機(jī)選擇第二個(gè)節(jié)點(diǎn)嘲碧。它們不允許自環(huán)或多邊；也就是說父阻，節(jié)點(diǎn)不能擁有到它自身的邊，并且兩個(gè)節(jié)點(diǎn)之間不能擁有多個(gè)邊望抽。
這是我的這個(gè)過程的實(shí)現(xiàn)加矛。
def rewire(G, p):
nodes = set(G.nodes())
for edge in G.edges():
if flip(p):
u, v = edge
choices = nodes - {u} - set(G[u])
new_v = choice(tuple(choices))
G.remove_edge(u, v)
G.add_edge(u, new_v)
參數(shù)p是邊的重新布線的概率。for循環(huán)枚舉了邊煤篙，并使用flip斟览，它以概率p返回True，來選擇哪些被重新布置辑奈。
如果我們重新布置節(jié)點(diǎn)u到節(jié)點(diǎn)v的邊苛茂，我們必須選擇一個(gè)節(jié)點(diǎn)來替換v，稱為new_v鸠窗。為了計(jì)算可能的選擇妓羊，我們從節(jié)點(diǎn)集開始，它是一個(gè)集合稍计，并且移除u和它的鄰居躁绸，這避免了自環(huán)和多邊。
然后我們從選項(xiàng)中選擇new_v臣嚣，將u到v的現(xiàn)有刪除净刮，并從添加一個(gè)u到new_v的新邊。
另外硅则，表達(dá)式G[u]返回一個(gè)字典淹父，他的鍵是包含u的鄰居。在這種情況下怎虫，它比使用G.neighbors更快一點(diǎn)暑认。
這個(gè)函數(shù)不按照 Watts 和 Strogatz 指定的順序考慮邊緣督暂，但它似乎不會影響結(jié)果。
圖（穷吮？）展示了n = 20逻翁，k = 4和范圍內(nèi)p值的 WS 圖。當(dāng)p = 0時(shí)捡鱼，該圖是環(huán)格八回。 當(dāng)p = 1時(shí)，它是完全隨機(jī)的驾诈。我們將看到缠诅，有趣的事情發(fā)生在兩者之間。
3.5 群聚性
下一步是計(jì)算群聚系數(shù)乍迄，它量化了節(jié)點(diǎn)形成集團(tuán)的趨勢管引。 集團(tuán)是一組完全連接的節(jié)點(diǎn)；也就是說闯两，在集團(tuán)中的所有節(jié)點(diǎn)對之間都存在邊褥伴。
假設(shè)一個(gè)特定的節(jié)點(diǎn)u具有k個(gè)鄰居。如果所有的鄰居都相互連接漾狼，則會有k(k-1)/2個(gè)邊重慢。 實(shí)際存在的這些邊的比例是u的局部群聚系數(shù)，表示為Cu逊躁。它被稱為“系數(shù)”似踱，因?yàn)樗偸窃?0 和 1 之間。
如果我們計(jì)算所有節(jié)點(diǎn)上的Cu平均值稽煤，我們得到“網(wǎng)絡(luò)平均群聚系數(shù)”核芽，表示為C。
這是一個(gè)計(jì)算它的函數(shù)酵熙。
def node_clustering(G, u):
neighbors = G[u]
k = len(neighbors)
if k < 2:
return 0
total = k * (k-1) / 2
exist = 0
for v, w in all_pairs(neighbors):
if G.has_edge(v, w):
exist +=1
return exist / total
同樣轧简，我使用G [u]，它返回一個(gè)字典绿店，鍵是節(jié)點(diǎn)的鄰居吉懊。如果節(jié)點(diǎn)的鄰居少于兩個(gè)，則群聚系數(shù)未定義假勿，但為簡便起見借嗽，node_clustering返回 0。
否則转培，我們計(jì)算鄰居之間的可能的邊數(shù)量恶导，total，然后計(jì)算實(shí)際存在的邊數(shù)量浸须。結(jié)果是存在的所有邊的比例惨寿。
我們可以這樣測試函數(shù)：
>>> lattice = make_ring_lattice(10, 4)
>>> node_clustering(lattice, 1)
0.5
在k=4的環(huán)格中邦泄，每個(gè)節(jié)點(diǎn)的群聚系數(shù)是0.5（如果你不相信，可以看看圖（裂垦？））顺囊。
現(xiàn)在我們可以像這樣計(jì)算網(wǎng)絡(luò)平均群聚系數(shù)：
def clustering_coefficient(G):
cc = np.mean([node_clustering(G, node) for node in G])
return cc
np.mean 是個(gè) NumPy 函數(shù)，計(jì)算列表或數(shù)組中元素的均值蕉拢。
然后我們可以像這樣測試：
>>> clustering_coefficient(lattice)
0.5
這個(gè)圖中特碳，所有節(jié)點(diǎn)的局部群聚系數(shù)是 0.5，所以節(jié)點(diǎn)的平均值是 0.5晕换。當(dāng)然午乓，我們期望這個(gè)值和 WS 圖不同。
3.6 最短路徑長度
下一步是計(jì)算特征路徑長度L闸准，它是每對節(jié)點(diǎn)之間最短路徑的平均長度益愈。 為了計(jì)算它，我將從 NetworkX 提供的函數(shù)開始夷家，shortest_path_length蒸其。 我會用它來復(fù)制 Watts 和 Strogatz 實(shí)驗(yàn)，然后我將解釋它的工作原理瘾英。
這是一個(gè)函數(shù)枣接，它接受圖并返回最短路徑長度列表，每對節(jié)點(diǎn)一個(gè)缺谴。
def path_lengths(G):
length_map = nx.shortest_path_length(G)
lengths = [length_map[u][v] for u, v in all_pairs(G)]
return lengths
nx.shortest_path_length的返回值是字典的字典。外層字典每個(gè)節(jié)點(diǎn)u到內(nèi)層字典的映射耳鸯，內(nèi)層字典是每個(gè)節(jié)點(diǎn)v到u->v的最短路徑長度的映射湿蛔。
使用來自path_lengths的長度列表，我們可以像這樣計(jì)算L：
def characteristic_path_length(G):
return np.mean(path_lengths(G))
并且我們可以使用小型的環(huán)格來測試它县爬。
>>> lattice = make_ring_lattice(3, 2)
>>> characteristic_path_length(lattice)
1.0
這個(gè)例子中阳啥，所有三個(gè)節(jié)點(diǎn)都互相連接，所以平均長度為 1财喳。
3.7 WS 實(shí)驗(yàn)
圖 3.3：WS 圖的群聚系數(shù)
C和特征路徑長度L察迟，其中n=1000, k=10，p是一個(gè)范圍耳高。
現(xiàn)在我們準(zhǔn)備復(fù)制 WS 實(shí)驗(yàn)扎瓶，它表明對于一系列p值，WS 圖具有像正則圖像那樣的高群聚性泌枪，像隨機(jī)圖一樣的短路徑長度概荷。
我將從run_one_graph開始，它接受n碌燕，k和p误证；它生成具有給定參數(shù)的 WS圖继薛，并計(jì)算平均路徑長度mpl和群聚系數(shù)cc：
def run_one_graph(n, k, p):
ws = make_ws_graph(n, k, p)
mpl = characteristic_path_length(ws)
cc = clustering_coefficient(ws)
print(mpl, cc)
return mpl, cc
Watts 和 Strogatz 用n = 1000和k = 10進(jìn)行實(shí)驗(yàn)。使用這些參數(shù)愈捅，run_one_graph在我的電腦上需要大約一秒鐘遏考；大部分時(shí)間用于計(jì)算平均路徑長度。
現(xiàn)在我們需要為范圍內(nèi)的p計(jì)算這些值蓝谨。我將再次使用 NumPy 函數(shù)logspace來計(jì)算ps：
ps = np.logspace(-4, 0, 9)
對于每個(gè)p的值灌具，我生成了 3 個(gè)隨機(jī)圖，并且我們將結(jié)果平均像棘。這里是運(yùn)行實(shí)驗(yàn)的函數(shù)：
def run_experiment(ps, n=1000, k=10, iters=3):
res = {}
for p in ps:
print(p)
res[p] = []
for _ in range(iters):
res[p].append(run_one_graph(n, k, p))
return res
結(jié)果是個(gè)字典稽亏，將每個(gè)p值映射為(mpl, cc)偶對的列表。
最后一步就是聚合結(jié)果：
L = []
C = []
for p, t in sorted(res.items()):
mpls, ccs = zip(*t)
mpl = np.mean(mpls)
cc = np.mean(ccs)
L.append(mpl)
C.append(cc)
每次循環(huán)時(shí)缕题，我們?nèi)〉靡粋€(gè)p值和一個(gè)(mpl, cc)偶對的列表截歉。 我們使用zip來提取兩個(gè)列表，mpls和ccs烟零，然后計(jì)算它們的均值并將它們添加到L和C瘪松，這是路徑長度和群聚系數(shù)的列表。
為了在相同的軸上繪制L和C锨阿，我們通過除以第一個(gè)元素宵睦，將它們標(biāo)準(zhǔn)化：
L = np.array(L) / L[0]
C = np.array(C) / C[0]
圖（？）展示了結(jié)果墅诡。 隨著p的增加壳嚎，平均路徑長度迅速下降，因?yàn)榧词股倭侩S機(jī)重新布線的邊末早，也提供了圖區(qū)域之間的捷徑烟馅，它們在格中相距很遠(yuǎn)。另一方面然磷，刪除局部鏈接降低了群聚系數(shù)郑趁，但是要慢得多。
因此姿搜，存在較寬范圍的p寡润，其中 WS 圖具有小世界圖的性質(zhì)，高群聚度和短路徑長度舅柜。
這就是為什么 Watts 和 Strogatz 提出了 WS 圖梭纹，作為展示小世界現(xiàn)象的，現(xiàn)實(shí)世界網(wǎng)絡(luò)的模型业踢。
3.8 能有什么解釋栗柒？
如果你問我，為什么行星軌道是橢圓形的，我最開始會為一個(gè)行星和一個(gè)恒星建模瞬沦；我將在 http://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation 上查找萬有引力定律太伊，并用它為行星的運(yùn)動寫出一個(gè)微分方程。之后我會擴(kuò)展軌道方程式逛钻，或者更有可能在 http://en.wikipedia.org/wiki/Orbit_equation 上查找僚焦。通過一個(gè)小的代數(shù)運(yùn)算，我可以得出產(chǎn)生橢圓軌道的條件曙痘。之后我會證明我們看做行星的物體滿足這些條件芳悲。
人們，或至少是科學(xué)家边坤，一般對這種解釋感到滿意名扛。它有吸引力的原因之一是，模型中的假設(shè)和近似值似乎是合理的茧痒。行星和恒星不是真正的質(zhì)點(diǎn)肮韧，但它們之間的距離是如此之大，以至于它們的實(shí)際尺寸可以忽略不計(jì)旺订。同一太陽系中的行星可以影響彼此的軌道弄企，但效果通常較小。而且我們忽視相對論的影響区拳，再次假定它們很小拘领。
這也因?yàn)樗腔诜匠淌降摹Ｎ覀兛梢杂瞄]式表達(dá)軌道方程樱调，這意味著我們可以有效地計(jì)算軌道约素。這也意味著我們可以得出軌道速度，軌道周期和其他數(shù)量的一般表達(dá)式笆凌。
最后业汰，我認(rèn)為這是因?yàn)樗哂袛?shù)學(xué)證明的形式。它從一組公理開始菩颖，通過邏輯和分析得出結(jié)果。但重要的是要記住为障，證明屬于模型晦闰，而不是現(xiàn)實(shí)世界。也就是說鳍怨，我們可以證明呻右，行星的理想模型產(chǎn)生一個(gè)橢圓軌道，但是我們不能證明這個(gè)模型與實(shí)際的行星有關(guān)（實(shí)際上它不是）鞋喇。
- 這些模型可以做什么工作：它們是預(yù)測性的還是說明性的声滥，還是都有？
- 這些模型的解釋，是否比基于更傳統(tǒng)模型的解釋更不滿意落塑？為什么纽疟？
- 我們應(yīng)該如何刻畫這些和更傳統(tǒng)的模型之間的差異？他們在種類還是程度上不同憾赁？
在這本書中污朽，我將提供我對這些問題的回答，但它們是暫時(shí)性的龙考，有時(shí)是投機(jī)性的蟆肆。我鼓勵你懷疑地思考他們，并得出你自己的結(jié)論晦款。
3.9 廣度優(yōu)先搜索
當(dāng)我們計(jì)算最短路徑時(shí)炎功，我們使用了 NetworkX 提供的一個(gè)函數(shù)，但是我沒有解釋它是如何工作的缓溅。為此蛇损，我將從廣度優(yōu)先搜索開始，這是用于計(jì)算最短路徑的 Dijkstra 算法的基礎(chǔ)。
在第（讨衣？）節(jié)森篷，我提出了reachable_nodes，它尋找從給定的起始節(jié)點(diǎn)可以到達(dá)的所有節(jié)點(diǎn)：
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
我當(dāng)時(shí)沒有這么說床玻，但它執(zhí)行深度優(yōu)先搜索（DFS）。現(xiàn)在我們將修改它來執(zhí)行廣度優(yōu)先搜索（BFS）沉帮。
為了了解區(qū)別锈死，想象一下你正在探索一座城堡。你最開始在一個(gè)房間里穆壕，帶有三個(gè)門待牵，標(biāo)記為 A，B 和 C 喇勋。你打開門 C 并發(fā)現(xiàn)另一個(gè)房間缨该，它的門被標(biāo)記為 D ，E 和 F川背。
下面你打開哪個(gè)門呢贰拿？如果你打算冒險(xiǎn)，你可能想更深入城堡熄云，選擇 D膨更，E 或 F。這是一個(gè)深度優(yōu)先搜索缴允。
但是荚守，如果你想更系統(tǒng)化，你可以在 D，E 和 F 之前回去探索 A 和 B矗漾，這將是一個(gè)廣度優(yōu)先搜索锈候。
在reachable_nodes中，我們使用list.pop選擇下一個(gè)節(jié)點(diǎn)來“探索”缩功。默認(rèn)情況下晴及，pop返回列表的最后一個(gè)元素，這是我們添加的最后一個(gè)元素嫡锌。在這個(gè)例子中虑稼，這是門 F。
如果我們要執(zhí)行 BFS势木，最簡單的解決方案是將第一個(gè)元素從棧中彈出：
node = stack.pop(0)
這有效蛛倦，但速度很慢。在 Python 中啦桌，彈出列表的最后一個(gè)元素需要常數(shù)時(shí)間溯壶，但是彈出第一個(gè)元素線性于列表的長度。在最壞的情況下甫男，就是堆棧的長度O(n)且改，這使得 BFS 的O(nm)的實(shí)現(xiàn)比O(n + m)差得多。
我們可以用雙向隊(duì)列（也稱為deque）來解決這個(gè)問題板驳。deque的一個(gè)重要特征就是又跛，你可以在開頭和末尾添加和刪除元素。要了解如何實(shí)現(xiàn)若治，請參閱 https://en.wikipedia.org/wiki/Double-ended_queue慨蓝。
Python 在collections模塊中提供了deque，所以我們可以像這樣導(dǎo)入它：
from collections import deque
我們可以使用它來編寫高效的 BFS：
def reachable_nodes_bfs(G, start):
seen = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in seen:
seen.add(node)
queue.extend(G.neighbors(node))
return seen
差異在于：
- 我用名為
queue的deque替換了名為stack的列表端幼。 - 我用
popleft替換pop礼烈，它刪除并返回隊(duì)列的最左邊的元素，這是第一個(gè)添加的元素婆跑。
這個(gè)版本恢復(fù)為O(n + m)〈税荆現(xiàn)在我們做好了尋找最短路徑的準(zhǔn)備。
3.10 （簡化的）Dijkstra 算法
Edsger W. Dijkstra 是荷蘭計(jì)算機(jī)科學(xué)家滑进，發(fā)明了一種有效的最短路徑算法（參見 http://en.wikipedia.org/wiki/Dijkstra's_algorithm）摹迷。他還發(fā)明了信號量，它是一種數(shù)據(jù)結(jié)構(gòu)郊供，用于協(xié)調(diào)彼此通信的程序（參見 http://en.wikipedia.org/wiki/Semaphore_(programming）和 Downey，《The Little Book of Semaphores》）近哟。
作為一系列計(jì)算機(jī)科學(xué)論文的作者驮审，Dijkstra 是著名（臭名昭著）的。 有些比如“反對 GOTO 語句的案例”（A Case against the GO TO Statement），對編程實(shí)踐產(chǎn)生了深遠(yuǎn)的影響疯淫。其他比如“真正的計(jì)算機(jī)科學(xué)教學(xué)的殘酷”（On the Cruelty of Really Teaching Computing Science）的人地来，很有娛樂性，但效果卻不好熙掺。
Dijkstra 算法解決了“單源最短路徑問題”未斑，這意味著它尋找從給定的“源”節(jié)點(diǎn)到圖中每個(gè)其他節(jié)點(diǎn)（或至少每個(gè)連接節(jié)點(diǎn)）的最小距離。
我們最開始考慮算法的簡化版本币绩，所有邊的長度相同蜡秽。更一般的版本適用于任何非負(fù)的邊的長度。
簡化版本類似于第一節(jié)中的廣度優(yōu)先搜索 除了我們用稱為dist的字典替換集合seen缆镣，該字典將每個(gè)節(jié)點(diǎn)映射為與源的距離：
def shortest_path_dijkstra(G, start):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
new_dist = dist[node] + 1
neighbors = set(G[node]) - set(dist)
for n in neighbors:
dist[n] = new_dist
queue.extend(neighbors)
return dist
這是它的工作原理：
- 最初芽突，隊(duì)列包含單個(gè)元素
start，dist將start映射為距離 0（這是start到自身的距離）董瞻。 - 每次循環(huán)中寞蚌，我們使用
popleft獲取節(jié)點(diǎn)，按照添加到隊(duì)列的順序钠糊。 - 接下來挟秤，我們發(fā)現(xiàn)節(jié)點(diǎn)的所有鄰居都沒有在
dist中。 - 由于從起點(diǎn)到節(jié)點(diǎn)的距離是
dist [node]抄伍，到任何未訪問的鄰居的距離是dist [node] +1艘刚。 - 對于每個(gè)鄰居，我們向
dist添加一個(gè)條目逝慧，然后將鄰居添加到隊(duì)列中昔脯。
只有在我們使用 BFS 而不是 DFS 時(shí)，這個(gè)算法才有效笛臣。為什么云稚？
第一次循環(huán)中，node是start沈堡，new_dist為1静陈。所以start的鄰居距離為 1，并且進(jìn)入了隊(duì)列诞丽。
當(dāng)我們處理start的鄰居時(shí)鲸拥，他們的所有鄰居距離為2。我們知道僧免，他們中沒有一個(gè)距離為1刑赶，因?yàn)槿绻械脑挘覀儠诘谝淮蔚邪l(fā)現(xiàn)它們懂衩。
類似地撞叨，當(dāng)我們處理距離為 2 的節(jié)點(diǎn)時(shí)金踪，我們將他們的鄰居的距離設(shè)為3。我們知道它們中沒有一個(gè)的距離為1或2牵敷，因?yàn)槿绻械脑捄恚覀儗⒃谥暗牡邪l(fā)現(xiàn)它們。
等等枷餐。如果你熟悉歸納證明靶瘸，你可以看到這是怎么回事。
但是毛肋，在我們開始處理距離為2的節(jié)點(diǎn)之前怨咪，只有我們處理了距離為1的所有節(jié)點(diǎn)，這個(gè)論證才有效村生，依此類推惊暴。這正是 BFS 所做的。
在本章末尾的練習(xí)中趁桃，你將使用 DFS 編寫 Dijkstra 算法的一個(gè)版本辽话，以便你有機(jī)會看到出現(xiàn)什么問題。
3.11 練習(xí)
練習(xí) 1：
在一個(gè)環(huán)格中卫病，每個(gè)節(jié)點(diǎn)的鄰居數(shù)量相同油啤。鄰居的數(shù)量稱為節(jié)點(diǎn)的度，所有節(jié)點(diǎn)的度相同的圖稱為正則圖蟀苛。
所有環(huán)格都是正則的益咬，但不是所有的正則圖都是環(huán)格。特別地帜平，如果k是奇數(shù)幽告，則不能構(gòu)造環(huán)格，但是我們可以構(gòu)建一個(gè)正則圖裆甩。
編寫一個(gè)名為make_regular_graph的函數(shù)冗锁，該函數(shù)接受n和k，并返回包含n個(gè)節(jié)點(diǎn)的正則圖嗤栓，其中每個(gè)節(jié)點(diǎn)都有k個(gè)鄰居冻河。如果不可能使用n和k的給定值來制作正則圖，則該函數(shù)應(yīng)該拋出ValueError茉帅。
練習(xí) 2：
我的reachable_nodes_bfs實(shí)現(xiàn)是有效的叨叙，因?yàn)樗?code>O(n + m)的，但它產(chǎn)生了很多開銷堪澎，將節(jié)點(diǎn)添加到隊(duì)列中并將其刪除擂错。 NetworkX 提供了一個(gè)簡單，快速的 BFS 實(shí)現(xiàn)樱蛤，可從 GitHub 上的 NetworkX 倉庫獲取马昙，網(wǎng)址為 https://github.com/networkx/networkx/blob/master/networkx/algorithms/components/connected.py桃犬。
這里是我修改的一個(gè)版本，返回一組節(jié)點(diǎn)：
def _plain_bfs(G, source):
seen = set()
nextlevel = {source}
while nextlevel:
thislevel = nextlevel
nextlevel = set()
for v in thislevel:
if v not in seen:
seen.add(v)
nextlevel.update(G[v])
return seen
將這個(gè)函數(shù)與reachable_nodes_bfs相比行楞，看看哪個(gè)更快。之后看看你是否可以修改這個(gè)函數(shù)來實(shí)現(xiàn)更快的shortest_path_dijkstra版本土匀。
練習(xí) 3：
下面的 BFS 實(shí)現(xiàn)包含兩個(gè)性能錯(cuò)誤子房。它們是什么？這個(gè)算法的實(shí)際增長級別是什么就轧？
def bfs(top_node, visit):
"""Breadth-first search on a graph, starting at top_node."""
visited = set()
queue = [top_node]
while len(queue):
curr_node = queue.pop(0) # Dequeue
visit(curr_node) # Visit the node
visited.add(curr_node)
# Enqueue non-visited and non-enqueued children
queue.extend(c for c in curr_node.children
if c not in visited and c not in queue)
練習(xí) 4：在第（证杭？）節(jié)中，我說了除非使用 BFS妒御，Dijkstra 算法不能工作解愤。編寫一個(gè)shortest_path_dijkstra的版本，它使用 DFS乎莉，并使用一些例子測試它送讲，看看哪里不對。
練習(xí) 5：
Watts 和 Strogatz 的論文的一個(gè)自然問題是惋啃，小世界現(xiàn)象是否特定于它的生成模型哼鬓，或者其他類似模型是否產(chǎn)生相同的定性結(jié)果（高群聚和短路徑長度）。
為了回答這個(gè)問題边灭，選擇 WS 模型的一個(gè)變體并重復(fù)實(shí)驗(yàn)异希。 你可能會考慮兩種變體：
- 不從常規(guī)圖開始，從另一個(gè)高群聚的圖開始绒瘦。 例如称簿，你可以將節(jié)點(diǎn)放置在二維空間中的隨機(jī)位置，并將每個(gè)節(jié)點(diǎn)連接到其最近的
k個(gè)鄰居惰帽。 - 嘗試不同種類的重新布線憨降。
如果一系列類似的模型產(chǎn)生類似的行為，我們認(rèn)為論文的結(jié)果是可靠的善茎。
練習(xí) 6：
Dijkstra 算法解決了“單源最短路徑”問題券册，但為了計(jì)算圖的特征路徑長度，我們其實(shí)需要解決“多源最短路徑”問題垂涯。
當(dāng)然烁焙，一個(gè)選擇是運(yùn)行 Dijkstra 算法n次，每個(gè)起始節(jié)點(diǎn)一次耕赘。 對于某些應(yīng)用骄蝇，這可能夠好，但是有更有效的替代方案操骡。
找到一個(gè)多源最短路徑的算法并實(shí)現(xiàn)它九火。請參閱 https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths赚窃。
將實(shí)現(xiàn)的運(yùn)行時(shí)間與運(yùn)行 Dijkstra 算法n次進(jìn)行比較。哪種算法在理論上更好岔激？哪個(gè)在實(shí)踐中更好勒极？NetworkX 使用了哪一個(gè)？
