三、小世界圖
譯者：飛龍
協(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 圖，它是一個小世界圖的模型。我將復(fù)制 Watts 和 Strogatz 所做的實(shí)驗(yàn)，并解釋它打算展示的東西。
這個過程中，我們將看到兩種新的圖算法：廣度優(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）的幾個隨機(jī)選擇的人發(fā)送了包裹，帶有一個指示，要求他們向馬薩諸塞州沙龍（Sharon, Massachusetts）的目標(biāo)人員發(fā)送一封附帶的信（在我長大的地方，波士頓附近），目標(biāo)人員通過名字和職業(yè)確定。受訪者被告知，只有當(dāng)他親自認(rèn)識目標(biāo)人員時，才可以將該信直接郵寄給目標(biāo)；否則他們按照指示，將信和同一個指示發(fā)送給他們認(rèn)為的，更有可能認(rèn)識目標(biāo)人員的親戚或朋友。
許多信件從來沒有發(fā)出過，但是對于發(fā)出的信件，平均路徑長度（信件轉(zhuǎn)發(fā)次數(shù)）的大約為 6。這個結(jié)果用于確認(rèn)以前的觀察（和猜測），社交網(wǎng)絡(luò)中任何兩個人之間的通常距離是“六度分隔”。
這個結(jié)論令人驚訝，因?yàn)榇蠖鄶?shù)人都希望社交網(wǎng)絡(luò)本地化 - 人們往往會靠近他們的朋友 - 而且在一個具有本地連接的圖中，路徑長度往往會與地理距離成比例增加。例如，我的大多數(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ī)連接。在正則圖中，每個節(jié)點(diǎn)具有相同數(shù)量的鄰居。他們考慮這些圖的兩個屬性，群聚性和路徑長度：
群聚是圖表的“集團(tuán)性”（cliquishness）的度量。在圖中，集團(tuán)是所有節(jié)點(diǎn)的子集，它們彼此連接；在一個社交網(wǎng)絡(luò)中，集團(tuán)是一群人，彼此都是朋友。Watts 和 Strogatz 定義了一個群聚系數(shù)，用于量化兩個節(jié)點(diǎn)彼此連接，并同時連接到同一個節(jié)點(diǎn)的可能性。
路徑長度是兩個節(jié)點(diǎn)之間的平均距離的度量，對應(yīng)于社交網(wǎng)絡(luò)中的分離度。
Watts 和 Strogatz 表明，正則圖具有高群聚性和長路徑長度，而大小相同的隨機(jī)圖通常具有群聚性和短路徑長度。所以這些都不是一個很好的社交網(wǎng)絡(luò)模型，它是高群聚性與短路徑長度的組合。
他們的目標(biāo)是創(chuàng)造一個社交網(wǎng)絡(luò)的生成模型。生成模型通過為構(gòu)建或?qū)е卢F(xiàn)象的過程建模，試圖解釋現(xiàn)象。Watts 和 Strogatz 提出了用于構(gòu)建小世界圖的過程：
從一個正則圖開始，節(jié)點(diǎn)為
n，每個節(jié)點(diǎn)連接k個鄰居。選擇邊的子集，并將它們替換為隨機(jī)的邊來“重新布線”。
邊的重新布線的概率是參數(shù)p，它控制圖的隨機(jī)性。當(dāng)p = 0時，該圖是正則的；p = 1是隨機(jī)的。
Watts 和 Strogatz 發(fā)現(xiàn)，較小的p值產(chǎn)生高群聚性的圖，如正則圖，短路徑長度的圖，如隨機(jī)圖。
在本章中，我將按以下步驟復(fù)制 Watts 和 Strogatz 實(shí)驗(yàn)：
- 我們將從構(gòu)建一個環(huán)格（ring lattice）開始，這是一種正則圖。
- 然后我們和 Watts 和 Strogatz 一樣重新布線。
- 我們將編寫一個函數(shù)來測量群聚度，并使用 NetworkX 函數(shù)來計(jì)算路徑長度。
- 然后，我們?yōu)榉秶鷥?nèi)的
p值計(jì)算群聚度和路徑長度。 - 最后，我將介紹一種用于計(jì)算最短路徑的高效算法，Dijkstra 算法。
3.3 環(huán)格
圖 3.1
n=10，k=4的環(huán)格
正則圖是每個節(jié)點(diǎn)具有相同數(shù)量的鄰居的圖；鄰居的數(shù)量也稱為節(jié)點(diǎn)的度。
環(huán)格是一種正則圖，Watts 和 Strogatz 將其用作模型的基礎(chǔ)。 在具有n個節(jié)點(diǎn)的環(huán)格中，節(jié)點(diǎn)可以排列成圓形，每個節(jié)點(diǎn)連接k個最近鄰居。
例如，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的一半。它是一個生成器函數(shù)，一次產(chǎn)生一個邊。它使用模運(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)在還不錯。
我們可以像這樣測試函數(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）圖，我們從一個環(huán)格開始，并為一些邊“重新布線”。 在他們的論文中，Watts 和 Strogatz 以特定順序考慮邊，并用概率p重新布置每個邊。 如果邊被重新布置，則它們使第一個節(jié)點(diǎn)保持不變，并隨機(jī)選擇第二個節(jié)點(diǎn)。它們不允許自環(huán)或多邊；也就是說，節(jié)點(diǎn)不能擁有到它自身的邊，并且兩個節(jié)點(diǎn)之間不能擁有多個邊。
這是我的這個過程的實(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的邊，我們必須選擇一個節(jié)點(diǎn)來替換v，稱為new_v。為了計(jì)算可能的選擇，我們從節(jié)點(diǎn)集開始，它是一個集合，并且移除u和它的鄰居，這避免了自環(huán)和多邊。
然后我們從選項(xiàng)中選擇new_v，將u到v的現(xiàn)有刪除，并從添加一個u到new_v的新邊。
另外，表達(dá)式G[u]返回一個字典，他的鍵是包含u的鄰居。在這種情況下，它比使用G.neighbors更快一點(diǎn)。
這個函數(shù)不按照 Watts 和 Strogatz 指定的順序考慮邊緣，但它似乎不會影響結(jié)果。
圖（？）展示了n = 20，k = 4和范圍內(nèi)p值的 WS 圖。當(dāng)p = 0時，該圖是環(huán)格。 當(dāng)p = 1時，它是完全隨機(jī)的。我們將看到，有趣的事情發(fā)生在兩者之間。
3.5 群聚性
下一步是計(jì)算群聚系數(shù)，它量化了節(jié)點(diǎn)形成集團(tuán)的趨勢。 集團(tuán)是一組完全連接的節(jié)點(diǎn)；也就是說，在集團(tuán)中的所有節(jié)點(diǎn)對之間都存在邊。
假設(shè)一個特定的節(jié)點(diǎn)u具有k個鄰居。如果所有的鄰居都相互連接，則會有k(k-1)/2個邊。 實(shí)際存在的這些邊的比例是u的局部群聚系數(shù)，表示為Cu。它被稱為“系數(shù)”，因?yàn)樗偸窃?0 和 1 之間。
如果我們計(jì)算所有節(jié)點(diǎn)上的Cu平均值，我們得到“網(wǎng)絡(luò)平均群聚系數(shù)”，表示為C。
這是一個計(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]，它返回一個字典，鍵是節(jié)點(diǎn)的鄰居。如果節(jié)點(diǎn)的鄰居少于兩個，則群聚系數(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)格中，每個節(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 是個 NumPy 函數(shù)，計(jì)算列表或數(shù)組中元素的均值。
然后我們可以像這樣測試：
>>> clustering_coefficient(lattice)
0.5
這個圖中，所有節(jié)點(diǎn)的局部群聚系數(shù)是 0.5，所以節(jié)點(diǎn)的平均值是 0.5。當(dāng)然，我們期望這個值和 WS 圖不同。
3.6 最短路徑長度
下一步是計(jì)算特征路徑長度L，它是每對節(jié)點(diǎn)之間最短路徑的平均長度。 為了計(jì)算它，我將從 NetworkX 提供的函數(shù)開始，shortest_path_length。 我會用它來復(fù)制 Watts 和 Strogatz 實(shí)驗(yàn)，然后我將解釋它的工作原理。
這是一個函數(shù)，它接受圖并返回最短路徑長度列表，每對節(jié)點(diǎn)一個。
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的返回值是字典的字典。外層字典每個節(jié)點(diǎn)u到內(nèi)層字典的映射，內(nèi)層字典是每個節(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
這個例子中，所有三個節(jié)點(diǎn)都互相連接，所以平均長度為 1。
3.7 WS 實(shí)驗(yàn)
圖 3.3：WS 圖的群聚系數(shù)
C和特征路徑長度L，其中n=1000, k=10，p是一個范圍。
現(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在我的電腦上需要大約一秒鐘；大部分時間用于計(jì)算平均路徑長度。
現(xiàn)在我們需要為范圍內(nèi)的p計(jì)算這些值。我將再次使用 NumPy 函數(shù)logspace來計(jì)算ps：
ps = np.logspace(-4, 0, 9)
對于每個p的值，我生成了 3 個隨機(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é)果是個字典，將每個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)時，我們?nèi)〉靡粋€p值和一個(mpl, cc)偶對的列表。 我們使用zip來提取兩個列表，mpls和ccs，然后計(jì)算它們的均值并將它們添加到L和C，這是路徑長度和群聚系數(shù)的列表。
為了在相同的軸上繪制L和C，我們通過除以第一個元素，將它們標(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 能有什么解釋？
如果你問我，為什么行星軌道是橢圓形的，我最開始會為一個行星和一個恒星建模；我將在 http://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation 上查找萬有引力定律，并用它為行星的運(yùn)動寫出一個微分方程。之后我會擴(kuò)展軌道方程式，或者更有可能在 http://en.wikipedia.org/wiki/Orbit_equation 上查找。通過一個小的代數(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)生一個橢圓軌道，但是我們不能證明這個模型與實(shí)際的行星有關(guān)（實(shí)際上它不是）。
- 這些模型可以做什么工作：它們是預(yù)測性的還是說明性的，還是都有？
- 這些模型的解釋，是否比基于更傳統(tǒng)模型的解釋更不滿意？為什么？
- 我們應(yīng)該如何刻畫這些和更傳統(tǒng)的模型之間的差異？他們在種類還是程度上不同？
在這本書中，我將提供我對這些問題的回答，但它們是暫時性的，有時是投機(jī)性的。我鼓勵你懷疑地思考他們，并得出你自己的結(jié)論。
3.9 廣度優(yōu)先搜索
當(dāng)我們計(jì)算最短路徑時，我們使用了 NetworkX 提供的一個函數(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)時沒有這么說，但它執(zhí)行深度優(yōu)先搜索（DFS）。現(xiàn)在我們將修改它來執(zhí)行廣度優(yōu)先搜索（BFS）。
為了了解區(qū)別，想象一下你正在探索一座城堡。你最開始在一個房間里，帶有三個門，標(biāo)記為 A，B 和 C 。你打開門 C 并發(fā)現(xiàn)另一個房間，它的門被標(biāo)記為 D ，E 和 F。
下面你打開哪個門呢？如果你打算冒險(xiǎn)，你可能想更深入城堡，選擇 D，E 或 F。這是一個深度優(yōu)先搜索。
但是，如果你想更系統(tǒng)化，你可以在 D，E 和 F 之前回去探索 A 和 B，這將是一個廣度優(yōu)先搜索。
在reachable_nodes中，我們使用list.pop選擇下一個節(jié)點(diǎn)來“探索”。默認(rèn)情況下，pop返回列表的最后一個元素，這是我們添加的最后一個元素。在這個例子中，這是門 F。
如果我們要執(zhí)行 BFS，最簡單的解決方案是將第一個元素從棧中彈出：
node = stack.pop(0)
這有效，但速度很慢。在 Python 中，彈出列表的最后一個元素需要常數(shù)時間，但是彈出第一個元素線性于列表的長度。在最壞的情況下，就是堆棧的長度O(n)，這使得 BFS 的O(nm)的實(shí)現(xiàn)比O(n + m)差得多。
我們可以用雙向隊(duì)列（也稱為deque）來解決這個問題。deque的一個重要特征就是，你可以在開頭和末尾添加和刪除元素。要了解如何實(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ì)列的最左邊的元素，這是第一個添加的元素。
這個版本恢復(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)到圖中每個其他節(jié)點(diǎn)（或至少每個連接節(jié)點(diǎn)）的最小距離。
我們最開始考慮算法的簡化版本，所有邊的長度相同。更一般的版本適用于任何非負(fù)的邊的長度。
簡化版本類似于第一節(jié)中的廣度優(yōu)先搜索 除了我們用稱為dist的字典替換集合seen，該字典將每個節(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ì)列包含單個元素
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。 - 對于每個鄰居，我們向
dist添加一個條目，然后將鄰居添加到隊(duì)列中。
只有在我們使用 BFS 而不是 DFS 時，這個算法才有效。為什么？
第一次循環(huán)中，node是start，new_dist為1。所以start的鄰居距離為 1，并且進(jìn)入了隊(duì)列。
當(dāng)我們處理start的鄰居時，他們的所有鄰居距離為2。我們知道，他們中沒有一個距離為1，因?yàn)槿绻械脑挘覀儠诘谝淮蔚邪l(fā)現(xiàn)它們。
類似地，當(dāng)我們處理距離為 2 的節(jié)點(diǎn)時，我們將他們的鄰居的距離設(shè)為3。我們知道它們中沒有一個的距離為1或2，因?yàn)槿绻械脑挘覀儗⒃谥暗牡邪l(fā)現(xiàn)它們。
等等。如果你熟悉歸納證明，你可以看到這是怎么回事。
但是，在我們開始處理距離為2的節(jié)點(diǎn)之前，只有我們處理了距離為1的所有節(jié)點(diǎn)，這個論證才有效，依此類推。這正是 BFS 所做的。
在本章末尾的練習(xí)中，你將使用 DFS 編寫 Dijkstra 算法的一個版本，以便你有機(jī)會看到出現(xiàn)什么問題。
3.11 練習(xí)
練習(xí) 1：
在一個環(huán)格中，每個節(jié)點(diǎn)的鄰居數(shù)量相同。鄰居的數(shù)量稱為節(jié)點(diǎn)的度，所有節(jié)點(diǎn)的度相同的圖稱為正則圖。
所有環(huán)格都是正則的，但不是所有的正則圖都是環(huán)格。特別地，如果k是奇數(shù)，則不能構(gòu)造環(huán)格，但是我們可以構(gòu)建一個正則圖。
編寫一個名為make_regular_graph的函數(shù)，該函數(shù)接受n和k，并返回包含n個節(jié)點(diǎn)的正則圖，其中每個節(jié)點(diǎn)都有k個鄰居。如果不可能使用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 提供了一個簡單，快速的 BFS 實(shí)現(xiàn)，可從 GitHub 上的 NetworkX 倉庫獲取，網(wǎng)址為 https://github.com/networkx/networkx/blob/master/networkx/algorithms/components/connected.py。
這里是我修改的一個版本，返回一組節(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
將這個函數(shù)與reachable_nodes_bfs相比，看看哪個更快。之后看看你是否可以修改這個函數(shù)來實(shí)現(xiàn)更快的shortest_path_dijkstra版本。
練習(xí) 3：
下面的 BFS 實(shí)現(xiàn)包含兩個性能錯誤。它們是什么？這個算法的實(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 算法不能工作。編寫一個shortest_path_dijkstra的版本，它使用 DFS，并使用一些例子測試它，看看哪里不對。
練習(xí) 5：
Watts 和 Strogatz 的論文的一個自然問題是，小世界現(xiàn)象是否特定于它的生成模型，或者其他類似模型是否產(chǎn)生相同的定性結(jié)果（高群聚和短路徑長度）。
為了回答這個問題，選擇 WS 模型的一個變體并重復(fù)實(shí)驗(yàn)。 你可能會考慮兩種變體：
- 不從常規(guī)圖開始，從另一個高群聚的圖開始。 例如，你可以將節(jié)點(diǎn)放置在二維空間中的隨機(jī)位置，并將每個節(jié)點(diǎn)連接到其最近的
k個鄰居。 - 嘗試不同種類的重新布線。
如果一系列類似的模型產(chǎn)生類似的行為，我們認(rèn)為論文的結(jié)果是可靠的。
練習(xí) 6：
Dijkstra 算法解決了“單源最短路徑”問題，但為了計(jì)算圖的特征路徑長度，我們其實(shí)需要解決“多源最短路徑”問題。
當(dāng)然，一個選擇是運(yùn)行 Dijkstra 算法n次，每個起始節(jié)點(diǎn)一次。 對于某些應(yīng)用，這可能夠好，但是有更有效的替代方案。
找到一個多源最短路徑的算法并實(shí)現(xiàn)它。請參閱 https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths。
將實(shí)現(xiàn)的運(yùn)行時間與運(yùn)行 Dijkstra 算法n次進(jìn)行比較。哪種算法在理論上更好？哪個在實(shí)踐中更好？NetworkX 使用了哪一個？
