# 三、小世界圖 > 原文：[Chapter 3 Small world graphs](http://greenteapress.com/complexity2/html/thinkcomplexity2004.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 現實世界中的許多網絡，包括社交網絡在內，具有“小世界屬性”，即節點之間的平均距離，以最短路徑上的邊數來衡量，遠遠小于預期。 在本章中，我介紹了斯坦利·米拉格（Stanley Milgram）的著名的“小世界實驗”，這是小世界屬性在真正的社交網絡中的第一次科學演示。之后我們將考慮 Watts-Strogatz 圖，它是一個小世界圖的模型。我將復制 Watts 和 Strogatz 所做的實驗，并解釋它打算展示的東西。 這個過程中，我們將看到兩種新的圖算法：廣度優先搜索（BFS）和 Dijkstra 算法，用于計算圖中節點之間的最短路徑。 本章的代碼在本書倉庫的`chap03.ipynb`中。使用代碼的更多信息請參見第（？）章。 ## 3.1 Stanley Milgram 斯坦利·米拉格（Stanley Milgram）是美國社會心理學家，他進行了兩項最著名的社會科學實驗，即 Milgram 實驗，研究人們對權威的服從（<http://en.wikipedia.org/wiki/Milgram_experiment>）和小世界實驗，研究了社交網絡的結構（<http://en.wikipedia.org/wiki/Small_world_phenomenon>）。 在小世界實驗中，Milgram 向堪薩斯州威奇托（Wichita, Kansas）的幾個隨機選擇的人發送了包裹，帶有一個指示，要求他們向馬薩諸塞州沙龍（Sharon, Massachusetts）的目標人員發送一封附帶的信（在我長大的地方，波士頓附近），目標人員通過名字和職業確定。受訪者被告知，只有當他親自認識目標人員時，才可以將該信直接郵寄給目標；否則他們按照指示，將信和同一個指示發送給他們認為的，更有可能認識目標人員的親戚或朋友。 許多信件從來沒有發出過，但是對于發出的信件，平均路徑長度（信件轉發次數）的大約為 6。這個結果用于確認以前的觀察（和猜測），社交網絡中任何兩個人之間的通常距離是“六度分隔”。 這個結論令人驚訝，因為大多數人都希望社交網絡本地化 - 人們往往會靠近他們的朋友 - 而且在一個具有本地連接的圖中，路徑長度往往會與地理距離成比例增加。例如，我的大多數朋友都住在附近，所以我猜想社交網絡中節點之間的平均距離是大約 50 英里。威奇托距離波士頓約有 1600 英里，所以如果 Milgram 的信件穿過了社交網絡的典型環節，那么他們應該有 32 跳，而不是 6 跳。 ## 3.2 Watts 和 Strogatz 1998年，Duncan Watts 和 Steven Strogatz 在 Nature 雜志上發表了一篇“小世界網絡的集體動態”（Collective dynamics of ’small-world’ networks）論文，提出了小世界現象的解釋。 你可以從 <http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html> 下載。 Watts 和 Strogatz 從兩種很好理解的圖開始：隨機圖和正則圖。在隨機圖中，節點隨機連接。在正則圖中，每個節點具有相同數量的鄰居。他們考慮這些圖的兩個屬性，群聚性和路徑長度： 群聚是圖表的“集團性”（cliquishness）的度量。在圖中，集團是所有節點的子集，它們彼此連接；在一個社交網絡中，集團是一群人，彼此都是朋友。Watts 和 Strogatz 定義了一個群聚系數，用于量化兩個節點彼此連接，并同時連接到同一個節點的可能性。 路徑長度是兩個節點之間的平均距離的度量，對應于社交網絡中的分離度。 Watts 和 Strogatz 表明，正則圖具有高群聚性和長路徑長度，而大小相同的隨機圖通常具有群聚性和短路徑長度。所以這些都不是一個很好的社交網絡模型，它是高群聚性與短路徑長度的組合。 他們的目標是創造一個社交網絡的生成模型。生成模型通過為構建或導致現象的過程建模，試圖解釋現象。Watts 和 Strogatz 提出了用于構建小世界圖的過程： 1. 從一個正則圖開始，節點為`n`，每個節點連接`k`個鄰居。 2. 選擇邊的子集，并將它們替換為隨機的邊來“重新布線”。 邊的重新布線的概率是參數`p`，它控制圖的隨機性。當`p = 0`時，該圖是正則的；`p = 1`是隨機的。 Watts 和 Strogatz 發現，較小的`p`值產生高群聚性的圖，如正則圖，短路徑長度的圖，如隨機圖。 在本章中，我將按以下步驟復制 Watts 和 Strogatz 實驗： + 我們將從構建一個環格（ring lattice）開始，這是一種正則圖。 + 然后我們和 Watts 和 Strogatz 一樣重新布線。 + 我們將編寫一個函數來測量群聚度，并使用 NetworkX 函數來計算路徑長度。 + 然后，我們為范圍內的`p`值計算群聚度和路徑長度。 + 最后，我將介紹一種用于計算最短路徑的高效算法，Dijkstra 算法。 ## 3.3 環格  > 圖 3.1 `n=10`，`k=4`的環格 正則圖是每個節點具有相同數量的鄰居的圖；鄰居的數量也稱為節點的度。 環格是一種正則圖，Watts 和 Strogatz 將其用作模型的基礎。 在具有`n`個節點的環格中，節點可以排列成圓形，每個節點連接`k`個最近鄰居。 例如，`n = 3`和`k = 2`的環形網格將擁有以下邊：`(0, 1), (1, 2), (2, 0)`。 請注意，邊從編號最高的節點“繞回”0。 更一般地，我們可以像這樣枚舉邊： ```py 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`接受節點列表和參數`halfk`，它是`k`的一半。它是一個生成器函數，一次產生一個邊。它使用模運算符`%`，從編號最高的節點繞回最低的節點。 我們可以這樣測試： ```py >>> nodes = range(3) >>> for edge in adjacent_edges(nodes, 1): ... print(edge) (0, 1) (1, 2) (2, 0) ``` 現在我們可以使用`adjacent_edges`來生成環格。 ```py 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`使用地板除計算`halfk`，所以如果`k`是奇數，它將向下取整并產生具有度`k-1`的環格。這可能不是我們想要的，但現在還不錯。 我們可以像這樣測試函數： ```py lattice = make_ring_lattice(10, 4) ``` 圖（？）展示了結果。 ## 3.4 WS 圖  > 圖 3.2 WS 圖，`n=20`，`k=4`，`p=0`（左邊），`p=0.2`（中間），`p=1`（右邊）。 為了制作 Watts-Strogatz（WS）圖，我們從一個環格開始，并為一些邊“重新布線”。 在他們的論文中，Watts 和 Strogatz 以特定順序考慮邊，并用概率`p`重新布置每個邊。 如果邊被重新布置，則它們使第一個節點保持不變，并隨機選擇第二個節點。它們不允許自環或多邊；也就是說，節點不能擁有到它自身的邊，并且兩個節點之間不能擁有多個邊。 這是我的這個過程的實現。 ```py 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) ``` 參數`p`是邊的重新布線的概率。`for`循環枚舉了邊，并使用`flip`，它以概率`p`返回`True`，來選擇哪些被重新布置。 如果我們重新布置節點`u`到節點`v`的邊，我們必須選擇一個節點來替換`v`，稱為`new_v`。為了計算可能的選擇，我們從節點集開始，它是一個集合，并且移除`u`和它的鄰居，這避免了自環和多邊。 然后我們從選項中選擇new_v，將`u`到`v`的現有刪除，并從添加一個`u`到`new_v`的新邊。 另外，表達式`G[u]`返回一個字典，他的鍵是包含`u`的鄰居。在這種情況下，它比使用`G.neighbors`更快一點。 這個函數不按照 Watts 和 Strogatz 指定的順序考慮邊緣，但它似乎不會影響結果。 圖（？）展示了`n = 20`，`k = 4`和范圍內`p`值的 WS 圖。當`p = 0`時，該圖是環格。 當`p = 1`時，它是完全隨機的。我們將看到，有趣的事情發生在兩者之間。 ## 3.5 群聚性 下一步是計算群聚系數，它量化了節點形成集團的趨勢。 集團是一組完全連接的節點；也就是說，在集團中的所有節點對之間都存在邊。 假設一個特定的節點`u`具有`k`個鄰居。如果所有的鄰居都相互連接，則會有`k(k-1)/2`個邊。 實際存在的這些邊的比例是`u`的局部群聚系數，表示為`Cu`。它被稱為“系數”，因為它總是在 0 和 1 之間。 如果我們計算所有節點上的`Cu`平均值，我們得到“網絡平均群聚系數”，表示為`C`。 這是一個計算它的函數。 ```py 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]`，它返回一個字典，鍵是節點的鄰居。如果節點的鄰居少于兩個，則群聚系數未定義，但為簡便起見，`node_clustering`返回 0。 否則，我們計算鄰居之間的可能的邊數量，`total`，然后計算實際存在的邊數量。結果是存在的所有邊的比例。 我們可以這樣測試函數： ```py >>> lattice = make_ring_lattice(10, 4) >>> node_clustering(lattice, 1) 0.5 ``` 在`k=4`的環格中，每個節點的群聚系數是`0.5`（如果你不相信，可以看看圖（？））。 現在我們可以像這樣計算網絡平均群聚系數： ```py def clustering_coefficient(G): cc = np.mean([node_clustering(G, node) for node in G]) return cc ``` `np.mean` 是個 NumPy 函數，計算列表或數組中元素的均值。 然后我們可以像這樣測試： ```py >>> clustering_coefficient(lattice) 0.5 ``` 這個圖中，所有節點的局部群聚系數是 0.5，所以節點的平均值是 0.5。當然，我們期望這個值和 WS 圖不同。 ## 3.6 最短路徑長度 下一步是計算特征路徑長度`L`，它是每對節點之間最短路徑的平均長度。 為了計算它，我將從 NetworkX 提供的函數開始，`shortest_path_length`。 我會用它來復制 Watts 和 Strogatz 實驗，然后我將解釋它的工作原理。 這是一個函數，它接受圖并返回最短路徑長度列表，每對節點一個。 ```py 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`的返回值是字典的字典。外層字典每個節點`u`到內層字典的映射，內層字典是每個節點`v`到`u->v`的最短路徑長度的映射。 使用來自`path_lengths`的長度列表，我們可以像這樣計算`L`： ```py def characteristic_path_length(G): return np.mean(path_lengths(G)) ``` 并且我們可以使用小型的環格來測試它。 ```py >>> lattice = make_ring_lattice(3, 2) >>> characteristic_path_length(lattice) 1.0 ``` 這個例子中，所有三個節點都互相連接，所以平均長度為 1。 ## 3.7 WS 實驗  > 圖 3.3：WS 圖的群聚系數`C`和特征路徑長度`L`，其中`n=1000, k=10`，`p`是一個范圍。 現在我們準備復制 WS 實驗，它表明對于一系列`p`值，WS 圖具有像正則圖像那樣的高群聚性，像隨機圖一樣的短路徑長度。 我將從`run_one_graph`開始，它接受`n`，`k`和`p`；它生成具有給定參數的 WS圖，并計算平均路徑長度`mpl`和群聚系數`cc`： ```py 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`進行實驗。使用這些參數，`run_one_graph`在我的電腦上需要大約一秒鐘；大部分時間用于計算平均路徑長度。 現在我們需要為范圍內的`p`計算這些值。我將再次使用 NumPy 函數`logspace`來計算`ps`： ```py ps = np.logspace(-4, 0, 9) ``` 對于每個`p`的值，我生成了 3 個隨機圖，并且我們將結果平均。這里是運行實驗的函數： ```py 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 ``` 結果是個字典，將每個`p`值映射為`(mpl, cc)`偶對的列表。 最后一步就是聚合結果： ```py 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) ``` 每次循環時，我們取得一個`p`值和一個`(mpl, cc)`偶對的列表。 我們使用`zip`來提取兩個列表，`mpls`和`ccs`，然后計算它們的均值并將它們添加到`L`和`C`，這是路徑長度和群聚系數的列表。 為了在相同的軸上繪制`L`和`C`，我們通過除以第一個元素，將它們標準化： ```py L = np.array(L) / L[0] C = np.array(C) / C[0] ``` 圖（？）展示了結果。 隨著`p`的增加，平均路徑長度迅速下降，因為即使少量隨機重新布線的邊，也提供了圖區域之間的捷徑，它們在格中相距很遠。另一方面，刪除局部鏈接降低了群聚系數，但是要慢得多。 因此，存在較寬范圍的`p`，其中 WS 圖具有小世界圖的性質，高群聚度和短路徑長度。 這就是為什么 Watts 和 Strogatz 提出了 WS 圖，作為展示小世界現象的，現實世界網絡的模型。 ## 3.8 能有什么解釋？ 如果你問我，為什么行星軌道是橢圓形的，我最開始會為一個行星和一個恒星建模；我將在 <http://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation> 上查找萬有引力定律，并用它為行星的運動寫出一個微分方程。之后我會擴展軌道方程式，或者更有可能在 <http://en.wikipedia.org/wiki/Orbit_equation> 上查找。通過一個小的代數運算，我可以得出產生橢圓軌道的條件。之后我會證明我們看做行星的物體滿足這些條件。 人們，或至少是科學家，一般對這種解釋感到滿意。它有吸引力的原因之一是，模型中的假設和近似值似乎是合理的。行星和恒星不是真正的質點，但它們之間的距離是如此之大，以至于它們的實際尺寸可以忽略不計。同一太陽系中的行星可以影響彼此的軌道，但效果通常較小。而且我們忽視相對論的影響，再次假定它們很小。 這也因為它是基于方程式的。我們可以用閉式表達軌道方程，這意味著我們可以有效地計算軌道。這也意味著我們可以得出軌道速度，軌道周期和其他數量的一般表達式。 最后，我認為這是因為它具有數學證明的形式。它從一組公理開始，通過邏輯和分析得出結果。但重要的是要記住，證明屬于模型，而不是現實世界。也就是說，我們可以證明，行星的理想模型產生一個橢圓軌道，但是我們不能證明這個模型與實際的行星有關（實際上它不是）。 + 這些模型可以做什么工作：它們是預測性的還是說明性的，還是都有？ + 這些模型的解釋，是否比基于更傳統模型的解釋更不滿意？為什么？ + 我們應該如何刻畫這些和更傳統的模型之間的差異？他們在種類還是程度上不同？ 在這本書中，我將提供我對這些問題的回答，但它們是暫時性的，有時是投機性的。我鼓勵你懷疑地思考他們，并得出你自己的結論。 ## 3.9 廣度優先搜索 當我們計算最短路徑時，我們使用了 NetworkX 提供的一個函數，但是我沒有解釋它是如何工作的。為此，我將從廣度優先搜索開始，這是用于計算最短路徑的 Dijkstra 算法的基礎。 在第（？）節，我提出了`reachable_nodes`，它尋找從給定的起始節點可以到達的所有節點： ```py 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 ``` 我當時沒有這么說，但它執行深度優先搜索（DFS）。現在我們將修改它來執行廣度優先搜索（BFS）。 為了了解區別，想象一下你正在探索一座城堡。你最開始在一個房間里，帶有三個門，標記為 A，B 和 C 。你打開門 C 并發現另一個房間，它的門被標記為 D ，E 和 F。 下面你打開哪個門呢？如果你打算冒險，你可能想更深入城堡，選擇 D，E 或 F。這是一個深度優先搜索。 但是，如果你想更系統化，你可以在 D，E 和 F 之前回去探索 A 和 B，這將是一個廣度優先搜索。 在`reachable_nodes`中，我們使用`list.pop`選擇下一個節點來“探索”。默認情況下，`pop`返回列表的最后一個元素，這是我們添加的最后一個元素。在這個例子中，這是門 F。 如果我們要執行 BFS，最簡單的解決方案是將第一個元素從棧中彈出： ```py node = stack.pop(0) ``` 這有效，但速度很慢。在 Python 中，彈出列表的最后一個元素需要常數時間，但是彈出第一個元素線性于列表的長度。在最壞的情況下，就是堆棧的長度`O(n)`，這使得 BFS 的`O(nm)`的實現比`O(n + m)`差得多。 我們可以用雙向隊列（也稱為`deque`）來解決這個問題。`deque`的一個重要特征就是，你可以在開頭和末尾添加和刪除元素。要了解如何實現，請參閱 <https://en.wikipedia.org/wiki/Double-ended_queue>。 Python 在`collections`模塊中提供了`deque`，所以我們可以像這樣導入它： ```py from collections import deque ``` 我們可以使用它來編寫高效的 BFS： ```py 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`，它刪除并返回隊列的最左邊的元素，這是第一個添加的元素。 這個版本恢復為`O(n + m)`。現在我們做好了尋找最短路徑的準備。 ## 3.10 （簡化的）Dijkstra 算法 Edsger W. Dijkstra 是荷蘭計算機科學家，發明了一種有效的最短路徑算法（參見 <http://en.wikipedia.org/wiki/Dijkstra's_algorithm>）。他還發明了信號量，它是一種數據結構，用于協調彼此通信的程序（參見 <http://en.wikipedia.org/wiki/Semaphore_(programming>）和 Downey，《The Little Book of Semaphores》）。 作為一系列計算機科學論文的作者，Dijkstra 是著名（臭名昭著）的。 有些比如“反對 GOTO 語句的案例”（A Case against the GO TO Statement），對編程實踐產生了深遠的影響。其他比如“真正的計算機科學教學的殘酷”（On the Cruelty of Really Teaching Computing Science），很有娛樂性，但效果卻不好。 Dijkstra 算法解決了“單源最短路徑問題”，這意味著它尋找從給定的“源”節點到圖中每個其他節點（或至少每個連接節點）的最小距離。 我們最開始考慮算法的簡化版本，所有邊的長度相同。更一般的版本適用于任何非負的邊的長度。 簡化版本類似于第一節中的廣度優先搜索 除了我們用稱為`dist`的字典替換集合`seen`，該字典將每個節點映射為與源的距離： ```py 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 ``` 這是它的工作原理： + 最初，隊列包含單個元素`start`，`dist`將`start`映射為距離 0（這是`start`到自身的距離）。 + 每次循環中，我們使用`popleft`獲取節點，按照添加到隊列的順序。 + 接下來，我們發現節點的所有鄰居都沒有在`dist`中。 + 由于從起點到節點的距離是`dist [node]`，到任何未訪問的鄰居的距離是`dist [node] +1`。 + 對于每個鄰居，我們向`dist`添加一個條目，然后將鄰居添加到隊列中。 只有在我們使用 BFS 而不是 DFS 時，這個算法才有效。為什么？ 第一次循環中，`node`是`start`，`new_dist`為`1`。所以`start`的鄰居距離為 1，并且進入了隊列。 當我們處理`start`的鄰居時，他們的所有鄰居距離為`2`。我們知道，他們中沒有一個距離為`1`，因為如果有的話，我們會在第一次迭代中發現它們。 類似地，當我們處理距離為 2 的節點時，我們將他們的鄰居的距離設為`3`。我們知道它們中沒有一個的距離為`1`或`2`，因為如果有的話，我們將在之前的迭代中發現它們。 等等。如果你熟悉歸納證明，你可以看到這是怎么回事。 但是，在我們開始處理距離為`2`的節點之前，只有我們處理了距離為`1`的所有節點，這個論證才有效，依此類推。這正是 BFS 所做的。 在本章末尾的練習中，你將使用 DFS 編寫 Dijkstra 算法的一個版本，以便你有機會看到出現什么問題。 ## 3.11 練習 練習 1： 在一個環格中，每個節點的鄰居數量相同。鄰居的數量稱為節點的度，所有節點的度相同的圖稱為正則圖。 所有環格都是正則的，但不是所有的正則圖都是環格。特別地，如果`k`是奇數，則不能構造環格，但是我們可以構建一個正則圖。 編寫一個名為`make_regular_graph`的函數，該函數接受`n`和`k`，并返回包含`n`個節點的正則圖，其中每個節點都有`k`個鄰居。如果不可能使用`n`和`k`的給定值來制作正則圖，則該函數應該拋出`ValueError`。 練習 2： 我的`reachable_nodes_bfs`實現是有效的，因為它是`O(n + m)`的，但它產生了很多開銷，將節點添加到隊列中并將其刪除。 NetworkX 提供了一個簡單，快速的 BFS 實現，可從 GitHub 上的 NetworkX 倉庫獲取，網址為 <https://github.com/networkx/networkx/blob/master/networkx/algorithms/components/connected.py>。 這里是我修改的一個版本，返回一組節點： ```py 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 ``` 將這個函數與`reachable_nodes_bfs`相比，看看哪個更快。之后看看你是否可以修改這個函數來實現更快的`shortest_path_dijkstra`版本。 練習 3： 下面的 BFS 實現包含兩個性能錯誤。它們是什么？這個算法的實際增長級別是什么？ ```py 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) ``` 練習 4：在第（？）節中，我說了除非使用 BFS，Dijkstra 算法不能工作。編寫一個`shortest_path_dijkstra `的版本，它使用 DFS，并使用一些例子測試它，看看哪里不對。 練習 5： Watts 和 Strogatz 的論文的一個自然問題是，小世界現象是否特定于它的生成模型，或者其他類似模型是否產生相同的定性結果（高群聚和短路徑長度）。 為了回答這個問題，選擇 WS 模型的一個變體并重復實驗。 你可能會考慮兩種變體： + 不從常規圖開始，從另一個高群聚的圖開始。 例如，你可以將節點放置在二維空間中的隨機位置，并將每個節點連接到其最近的`k`個鄰居。 + 嘗試不同種類的重新布線。 如果一系列類似的模型產生類似的行為，我們認為論文的結果是可靠的。 練習 6： Dijkstra 算法解決了“單源最短路徑”問題，但為了計算圖的特征路徑長度，我們其實需要解決“多源最短路徑”問題。 當然，一個選擇是運行 Dijkstra 算法`n`次，每個起始節點一次。 對于某些應用，這可能夠好，但是有更有效的替代方案。 找到一個多源最短路徑的算法并實現它。請參閱 <https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths>。 將實現的運行時間與運行 Dijkstra 算法`n`次進行比較。哪種算法在理論上更好？哪個在實踐中更好？NetworkX 使用了哪一個？