使用圖對網絡魯棒性的有效評估的製作方法

2023-08-02 03:41:11 1

使用圖對網絡魯棒性的有效評估的製作方法
【專利摘要】可能的斷開或系統級影響產生的網絡中流量參數中的減速，可以通過對於表示網絡的圖的邊使用權重標註表示網絡的圖來識別。權重可以是，與影響的嚴重性的逆線性地或者非線性地成比例的，和/或與斷開的可能性的逆線性地或者非線性地成比例的。需要用於生成網絡中斷開的最小割集基於邊上的權重從經標註的網絡被識別。模擬期間，每一個最小割集的子集被生成並且被評估。子集可以對應於網絡的幾乎孤立的場景。通過選擇應用權重的最小割集，可以減小模擬的範圍。
【專利說明】使用圖對網絡魯棒性的有效評估

【技術領域】
[0001] 本公開涉及一種針對魯棒性（robustness)使用圖評估網絡的方法，以及實施相 冋功能的系統。

【背景技術】
[0002] 在網絡足夠健壯以抵禦破壞性事件的條件下，在網絡上監控、建模及模擬流量參 數（flow parameters)的能力在規劃、構建和維護網絡中是至關重要的。監控、建模及模擬 大型城市和都市區域道路上的交通狀況，對於運輸部門和涉及向市民提供服務（比如警察 局、消防局或時間敏感的派送公司）以及在邁向智慧城市的過程中規劃更健壯的基礎設施 的其他組織，已經變得越來越重要。由於惡劣天氣事件的愈加頻繁，城市必須處理緊急狀 況，在此期間某些區域可能經歷艱難的路況或者變得徹底無法通行。當對交通進行建模和 模擬時，識別道路網絡的可能的斷開（意味著給定集合的道路的不可用性，其導致城市的 某個部分被孤立）並且確定它們對交通狀況的影響是城市規劃者和基礎設施管理者需要 考慮的重要因素，使得可以提前規劃替代的緩解措施或者為了避免這種情況而確定投資。
[0003] 進一步地，經銷商的供應鏈網絡或者需要很多組件的產品的裝配線容易受到破 壞。例如，當某些組件因為任何原因，包括地緣政治的衝突以及自然災害，不能及時交付時， 汽車裝配線或者飛機裝配線的生產量可以急劇下降。
[0004] 然而，對大型網絡執行模擬可能是既耗費時間又耗費資源的，因為網絡通常包括 擁有超過數以萬計的節點和邊的大型的數學圖（此後稱為"圖"）。用於模擬網絡中的斷開 的當前已知的方法採用邊斷開的組合的檢查。然而，對n邊圖考慮k邊斷開的情況，在nk階 上產生斷開的場景，即n的k次冪。隨著數字n增加，斷開的數量可以輕易地變成即使現代 計算機也無法處理的天文數字。


【發明內容】

[0005] 可能的斷開或系統級影響產生的網絡中流量參數中的減速，可以通過對於表示網 絡的圖的邊使用權重標註表示網絡的圖來識別。權重可以是，與影響的嚴重性的逆線性地 或者非線性地成比例的，和/或與斷開的可能性的逆線性地或者非線性地成比例的。需要 用於生成網絡中斷開的最小割集基於邊上的權重從經標註的網絡被識別。最小割集可以按 照單調改變從邊的各自權重計算而來的權重參數的順序被列舉。模擬期間，每一個最小割 集的子集被生成並且被評估。子集可以對應於網絡的幾乎孤立的場景。可以減小模擬的範 圍，因為局部模擬可以針對每一個孤立的場景運行並且可以考慮對於流量參數具有最大影 響的斷開的更小集合。
[0006] 根據本公開的一個方面，提供了以網絡的至少一個流量參數模擬的一種方法。該 方法包括：生成表示將被模擬的網絡的圖；基於可用數據通過對圖的邊分配權重從該圖生 成經標註的圖，其中權重從表示網絡操作期間相應的邊被連接的可能性的似然權重、衡量 了一旦相應的邊斷開對於網絡的至少一個流量參數的影響的程度的影響權重、以及似然權 重和影響權重的組合中選擇；從所標註的圖生成最小割集；選擇少於所生成的最小割集的 全部的最小割集的集合；通過從每一個最小割集刪除至少一個割，從集合中的最小割集生 成幾乎孤立的場景；以及對於幾乎孤立的場景關於至少一個流量參數運行模擬，其中圖的 生成、經標註的圖的生成、最小割集的生成、集合的選擇、幾乎孤立的場景的生成、模擬的運 行中的至少一個步驟使用被配置為運行自動化程序的一個或多個處理器來執行。
[0007] 根據本公開的另一方面，提供了通過模擬修改網絡的一種方法。該方法包括：生成 表示將被模擬的網絡的圖；基於可用數據通過對圖的邊分配權重從該圖生成經標註的圖， 其中權重從表示網絡操作期間相應的邊被連接的可能性的似然權重、衡量了 一旦相應的邊 斷開對於網絡的至少一個流量參數的影響的程度的影響權重、以及似然權重和影響權重的 組合中選擇；從經標註的圖生成最小割集；選擇少於所生成的最小割集的全部的最小割集 的集合；通過從每一個最小割集刪除至少一個割，從集合中的最小割集生成幾乎孤立的場 景；對於幾乎孤立的場景關於至少一個流量參數運行模擬；從模擬識別至少一個系統級影 響產生的場景；並且修改網絡以減輕所識別的至少一個系統級影響產生的場景下的系統級 影響，其中圖的生成、經標註的圖的生成、最小割集的生成、集合的選擇、幾乎孤立的場景的 生成、模擬的運行、至少一個系統級影響產生的場景的識別以及網絡的修改中的至少一個 步驟使用被配置為運行自動化程序的一個或多個處理器來執行。
[0008] 根據本公開的又一方面，提供了以網絡的至少一個流量參數模擬的一種系統。該 系統包括一個或多個處理單元，被配置為執行以下的步驟：生成表示將被模擬的網絡的圖； 基於可用數據通過對圖的邊分配權重從該圖生成經標註的圖，其中權重從表示網絡操作期 間相應的邊被連接的可能性的似然權重、衡量了一旦相應的邊斷開對於網絡的至少一個流 量參數的影響的程度的影響權重、以及似然權重和影響權重的組合中選擇；從經標註的圖 生成最小割集；選擇少於所生成的最小割集的全部的最小割集的集合；通過從每一個最小 割集刪除至少一個割，從集合中的最小割集生成幾乎孤立的場景；以及對於幾乎孤立的場 景關於至少一個流量參數運行模擬。
[0009] 根據本公開的再一方面，提供了通過模擬修改網絡的一種系統。該系統包括一個 或多個處理單元，被配置為執行以下的步驟：基於可用數據通過對圖的邊分配權重從該圖 生成經標註的圖，其中權重從表示網絡操作期間相應的邊被連接的可能性的似然權重、衡 量了一旦相應的邊斷開對於網絡的至少一個流量參數的影響的程度的影響權重、以及似然 權重和影響權重的組合中選擇；從經標註的圖生成最小割集；選擇少於所生成的最小割集 的全部的最小割集的集合；通過從每一個最小割集刪除至少一個割，從集合中的最小割集 生成幾乎孤立的場景；對於幾乎孤立的場景關於至少一個流量參數運行模擬；從模擬識別 至少一個系統級影響產生的場景；並且修改網絡以減輕所識別的至少一個系統級影響產生 的場景下的系統級影響。

【專利附圖】

【附圖說明】
[0010] 圖1是圖示了根據本公開的一個實施例的，識別由圖所表示的網絡的幾乎孤立的 場景並且有選擇地對於幾乎孤立的場景執行模擬的方法的流程圖。
[0011] 圖2是根據本公開的一個實施例的示範性的圖。
[0012] 圖3是圖示了根據本公開的一個實施例的從包含最小割集的圖中生成表示幾乎 孤立的場景的子圖的方法的示意圖。
[0013] 圖4圖示了用於實現本公開的方法的示範性的系統。

【具體實施方式】
[0014] 如上所述，本公開涉及一種針對魯棒性使用圖評估網絡的方法，以及實施相同功 能的系統，現在結合附圖對其詳細地描述。附圖並不一定按比例繪製。
[0015] 如在此所用，"流量參數"指衡量網絡功能的參數。例如，交通網絡可以有表示交通 流量的流量參數。供應網絡可以有表示貨物流動（運輸）的流量參數。電力網絡可以有表 示傳輸電量的流量參數。應當注意，網絡可以以多於一個流量參數為表徵。例如，交通網絡 可以由不同類型的車輛的交通流量代表，而供應網絡可以由不同類型的貨物（穀物、礦物 等）的流量代表。
[0016] 如在此所用，"圖"是節點（頂點）和連接節點的邊的集合，其用於對網絡建模。每 條邊具有節點集合中的兩個端點，並且被稱為連接或連結這兩端點。一條邊因此可以被定 義為兩個頂點的集合。節點（頂點）可以被簡單地畫作點。圖G的頂點集合通常由V(G) 表示。圖G的階指其頂點的數量，S卩|V(G)|。圖的大小為其邊的數量。
[0017] 如在此所用，如果兩個頂點之間存在邊，則它們是"相鄰的"。
[0018] 圖的"子圖"指這樣的圖，其頂點集合是G的頂點集合的子集，並且其相鄰關係是 被局限於該子集的、G的相鄰關係的子集。
[0019] 如在此所用，"割（cut)"指將圖的節點（頂點）分為兩個互斥子集（disjoint subset)的劃分。
[0020] 如在此所用，"割集（cut set)"指圖的邊的組合，當被集體刪除時，該組合導致了 由圖所表示的網絡的至少一個流量參數的破壞。每一個割集對應於組件失效的一個組合， 其可以導致網絡中的系統失效。割集是邊的集合，該邊的端點存在於由相應的割所導致的 劃分的不同子集中。
[0021] 如在此所用，當任何邊從割集被刪除時，如果該割集的剩餘部分不再是一個割集， 割集是"最小割集"。
[0022] 如在此所用，數量的"符號"指數量是正的還是負的，S卩，數量大於零或小於零。
[0023] 參考圖1，根據本公開的一個實施例的流程圖圖示了識別由圖所表示的網絡的幾 乎孤立的場景並且有選擇地對於幾乎孤立的場景執行模擬的方法。網絡的至少一個流量參 數可以通過使用流程圖的步驟來模擬。包括一個或多個處理單元的計算裝置可以被配置為 執行流程圖的各種步驟。
[0024] 參考步驟100,流程流可以開始於識別將要模擬的網絡。將要模擬的網絡可以是交 通網絡、供應鏈網絡、電力供應網絡或可以以表示了如本領域已知的可量化的變量的流的 至少一個流量參數為表徵的任何其他網絡。在一個非限制性的示例中，網絡可以是大型都 市區域的道路網絡。
[0025] 參考步驟120,表示網絡的圖使用本領域已知的方法生成。參考圖2,圖示了示範 性的圖，該圖包括由點表示的節點以及由實線表示的邊。在一個非限制性的示例中，城市規 劃者可以準備表示城市的道路網絡的圖以對於交通流量來被評估。
[0026] 參考步驟130,經標註的圖基於可用數據通過對圖的邊分配權重生成。可選地，圖 的邊之間的相關性可以針對每一對邊來分配。
[0027] 特別地，經標註的圖基於可用數據通過對圖的邊分配權重生成。權重包括似然權 重和影響權重中的至少一個。似然權重表示網絡操作期間對應的邊被連接的可能性。影響 權重衡量了一旦相應的邊斷開對於網絡的至少一個流量參數的影響的程度。
[0028] 參考圖2,示意性地圖示了對圖的邊分配權重的過程。對於第一條邊el，分配了第 一似然權重wl_l和第一影響權重wi_l。對於第二條邊e2,分配了第二似然權重wl_2和第 二影響權重wi_2。例如，通過對於大於2並且直至等於圖中所有邊的條數的整數的每一個 i所分配的第i似然權重wl_i和第i影響權重wi_i的分配，該過程對於第i條邊ei繼續。
[0029] 在一個實施例中，似然權重是與網絡操作期間特定的邊被連接的可能性相關的非 負實數。該似然權重可以正向地或逆向地相關於網絡操作期間特定的邊被連接的可能性。 在一個實施例中，似然權重可以是線性地、或非線性地與網絡操作期間特定的邊被連接的 可能性成比例。在一個實施例中，似然權重可以是網絡操作期間特定的邊被連接的可能性。 在一個實施例中，似然權重可以具有從〇到1並且包括〇和1的值。
[0030] 在一個實施例中，影響權重是與在網絡的至少一個流量參數上可量化的有害影響 相關的非負實數。該影響權重可以正向地或逆向地相關於在網絡的至少一個流量參數上可 量化的有害影響。在一個實施例中，影響權重可以是線性地、或非線性地與在網絡的至少一 個流量參數上可量化的有害影響成比例。在一個實施例中，影響權重可以是在網絡的至少 一個流量參數上歸一化的可量化的有害影響的逆。在一個實施例中，影響權重可以具有與 歸一化的可量化的有害影響成反比的值。
[0031] 在一個實施例中，至少一個似然權重和/或至少一個影響權重可以由系統的運行 者直接輸入，該系統運行顯示或者表示該圖的程序。在另一實施例中，至少一個似然權重和 /或至少一個影響權重可以在提供網絡時、生成圖時或者生成圖以後，由被輸入至系統的數 據決定。
[0032] 至少一個似然權重和/或至少一個影響權重可以由生成關於連接斷開的邊的信 息的模擬提供。在一個實施例中，至少一個似然權重和/或至少一個影響權重可以從事件 的歷史數據以及從相同或相似網絡上之前所執行的模擬，來推斷或者估計。如果圖從其生 成的網絡是交通網絡，至少一個似然權重和/或至少影響權重可以基於交通模擬數據和/ 或洪水模擬數據。
[0033] 在示範性的說明中，圖可以表示全部的城市道路網絡或者全部的城市道路網絡的 子集。每一條道路可以由一條邊表示，並且每一個交叉口可以由一個節點表示。至少一個 流量參數可以是交通流量，該交通流量可以由，例如，穿過對應於圖的一條邊的道路的中央 部分的車輛的數量來測量。
[0034] 在一個實施例中，每一個似然權重可以是網絡即城市道路網絡操作期間，道路具 有功能（functional)的可能性。感興趣的時間間隔可以是被選擇用於模擬目的的感興趣 的任何時間段。確定道路功能的標準可以由經驗因數提供。例如，用於確定道路功能的標 準可以是正常的交通水平的固定的倍數（例如，3、4或5)或者可以是由對於維持城市道路 網絡功能所必需的設計的交通水平所生成的數字。在一個實施例中，道路具有功能的可能 性可以由歷史數據確定。在此情況下，每一個似然權重可以是〇和1之間並且包括〇和1 的實數。在一個實施例中，用於生成經標註的圖的系統中的一個或多個處理單元可以被配 置為對於圖中的每一條邊分配所述似然權重的值，該值是從O到小於I. O的正數並且包括 0。對於似然權重小的值意味著相應的道路有可能被斷開，而對於似然權重大的值意味著相 應的道路不太可能被斷開，即在道路網絡操作期間可能保持連接。
[0035] 在一個實施例中，網絡是交通網絡，至少一個流量參數包括交通流量，以及似然權 重可以由對應於每一條邊的道路上每單位時間通過的車輛的總數確定。例如，似然權重可 以由Z/Nv給出，其中Z是歸一化常數，以及Nv是對應於圖的一條邊的道路上每單位時間通 過的車輛的總數。如果Nv為0,我們將對似然權重分配大的數。可替代地，似然權重可以由 Y/Nw給出，其中Y是歸一化常數，以及Nw是對應於圖的一條邊的道路上每單位長度的車輛 的總數。如果Nw為0,我們將對似然權重分配大的數。仍然可替代地，似然權重可以由（Z/ Nv)a和（Y/Nw)0的加權線性組合或乘積給出，即，Ax (Z/Nv) a+Bx (Y/Nw)0或Cx (Z/Nv) a X (Y/ Nw) 0 或者其組合，S卩，Dx(Z/Nvr+Ex(Y/Nw) e+Fx(Z/Nvrx(Y/Nw) 0 其中 a 和 0 是正實數， 以及A、B、C、D、E和F是非零實數。
[0036] 在一個實施例中，網絡是交通網絡，至少一個流量參數包括交通流量，以及似然權 重可以由表徵自然或人為災害的量級的參數確定。例如，似然權重可以由Z' /WL給出，其 中Z'是歸一化常數，以及WL是對應於圖的一條邊的道路上所模擬的洪水期間的水位。如 果WL是零，我們將對似然權重賦一個大的數。
[0037] 影響權重可以與對至少一個流量參數有量化的有害影響的逆線性地或者非線性 地成比例。對於一條邊的影響權重可以基於歷史數據，或者標識保持特定的邊連接以維持 網絡的至少一個流量參數在正常的範圍內的重要性的任何其他模擬來估計。
[0038] 如果基於歷史數據或其他模擬的影響權重的估計對於任何邊不可用，對於相應邊 的影響權重可以被設為預設值，該預設值可以是，例如，對於網絡的影響權重的所估計的平 均值。影響權重是非負實數，並且預定的範圍從〇到一個預定的數，並且包括〇。如果影響 權重被歸一化，影響權重可以有從〇到1的值，並且包括〇和1。
[0039] 在一個實施例中，邊的集合的斷開的相關性的數據可以被可選擇地添加到經標註 的圖。邊的集合的斷開的相關性的數據可以基於歷史數據、地圖數據或者地形數據。在此 情況下，經標註的圖的生成可以包括對圖的邊分配斷開相關性數據，以及基於斷開相關性 數據收縮（contracting)圖的鄰接的邊（以將鄰接的邊轉換為單條邊並消除中間節點）的 步驟。
[0040] 參考圖1的步驟140,最小割集從經標註的圖來生成。
[0041] 在一個實施例中，最小割集的生成可以受以下各項影響：（1)最小割集的最大數 目J，（2)通過迭代地刪除來自每一個割集的邊生成每一個割集的子集，以及（3)確定每一 個子集是否是割集。
[0042] 將要生成的最小割集的最大數目J可以依賴於對於至少一個流量參數的模擬的 水平以及可用於該模擬的計算時間的長短來選擇。在其中計算資源沒有受到嚴重限制的 "平時的（peacetime)"模擬中，最大數目J可以設置在相對大的值。在其中計算資源可能 受到限制的"緊急"模擬中，最大數目J可以設置在相對低的值。
[0043] 對於擁有N條邊的給定的網絡生成具有基數K的割集的方法是已知的，例如 在 Computer Science 中的 Lecture Notes, Vol. 623/1992, 1992 中的 Vazirani, V.，Ya nnakakis, M. , Suboptimal cuts:their enumeration, weight, and number 以及 Li-Pu Yeh,Biing-Feng Wang, Hsin-Hao Su,Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing Weights中。本公開的枚舉法可以被應用於無向圖 和有向圖兩者。在一個實施例中，用戶可以指定將被分離的兩個節點。在另一實施例中，用 戶不需要指定這樣的節點。
[0044] 對於具有基數K的每一個割集，S卩，將要斷開的邊的總數，識別割集的子集即最小 割集。最小割集的識別可以通過這種方式來執行，即通過迭代地刪除來自每一個割集的邊 生成具有基數K的每一個割集的子集，並且確定每一個子集是否是割集。
[0045] 迭代地刪除來自具有基數K的割集的邊的過程可以通過從割集生成具有基數 (K-I)的KCi (等於K)個第一子集來執行。第一子集被檢查以確定KCi個第一子集中的任何 一個是否為割集。如果KC1個第一子集中沒有一個是割集，那麼具有基數K的割集是最小割 集。如果KCi個第一子集中的任何一個是割集，那麼具有基數K的割集不是最小割集，具有 基數（K-2)的第二子集從W1 (等於K)個第一子集通過再刪除一條邊被生成。第二割集的 總數是KC2 (等於K (K-I) /2)。對於每一個所選擇的KCi個第一子集，如果具有比所選擇的第 一子集少一條邊的第二子集中沒有一個是割集，具有基數（K-I)的所選擇的第一割集是最 小割集。如果具有比所選擇的第一子集少一條邊的第二子集中的任何一個是割集，所選擇 的第一割集不是最小割集，即，是非最小割集。對於每一個大於1的整數P，具有基數（K-p) 的每一個非最小割集被選擇用於具有基數（K-p-1)的第（p+1)子集的生成。由所選擇的第 P子集生成的第（P+1)子集被檢查以確定具有比所選擇的第P子集少一條邊的第（P+1)子 集中的任何一個是否是割集。如果具有比所選擇的第P子集少一條邊的第（P+1)子集中沒 有一個是割集，具有基數（K-p)的所選擇的第p割集是最小割集。該處理隨著p值的增加 而繼續，直到為具有基數K的割集的子集的所有最小割集被識別。進一步地，該處理對於具 有基數K的每一個割集繼續。
[0046] -旦最小割集被生成，少於所生成的最小割集的全體的最小割集的集合被選擇。 最小割集的集合的選擇對應於其模擬將被隨後執行的最小割集。不包括在集合中的最小割 集被認為對於保證模擬不是足夠重要。因此，最小割集的集合的選擇確定了哪些割集將隨 後在模擬中被檢查以及哪些最小割集將不通過模擬來檢查。這樣，最小割集的集合的選擇 以包括相比未被選擇的最小割集更有可能失效的最小割集的方式，以包括一旦失效相比未 被選擇的最小割集對網絡的系統性能更不利的割集的方式，或者對於每一個最小割集的失 效的可能性和一旦失效對系統的不利程度的綜合考慮來執行。
[0047] 在一個實施例中，最小割集的集合的選擇可以通過以下步驟執行：（1)在所生成 的最小割集中一次一個地選擇每一個最小割集；(2)對於每一個所選擇的最小割集，分配 權重參數，該權重參數依賴於分配給所選擇的最小割集內的邊的權重的每一個值；以及 (3)應用權重參數的值以確定每一個最小割集是否被包括於集合內。
[0048] 對於因此被識別的所有最小割集的集合中的每一個最小割集，分配權重參數。權 重參數是給定的最小割集內的邊的所有權重的函數。權重參數可以是標量函數，即具有標 量的值的函數。標量可以是實數。在一個實施例中，權重參數中的改變對於所選擇的最小 割集內任何邊的權重的值的任何增量具有相同的符號。
[0049] 在一個實施例中，權重參數是隨著對應的最小割集內任何邊的似然權重的值的任 何改變而改變的值。權重參數中的改變對於對應的最小割集內任何邊的似然權重的值的任 何增量具有相同的符號（其為正或者負）。在一個實施例中，權重參數可以隨著逆向影響網 絡的至少一個流量參數的對應的最小割集內任何邊的似然權重的值的任何改變而減少。例 如，如果邊的似然權重的值代表由邊所代表的路徑（例如，道路）在網絡操作期間是具有功 能的可能性，該似然權重的值的減少代表逆向影響網絡的至少一個流量參數的改變，並且 因此，權重參數減少。
[0050] 在一個實施例中，似然權重被定義為使得似然權重的值對於逆向影響對於 圖中所有邊的網絡的至少一個流量參數的改變（例如，如邊具有功能的可能性）而 減少，並且權重參數可以被定義為隨著對應的最小割集中的似然權重的任何值的減 少而線性地或者非線性地減少的數。例如，如果最小割集包括eml、em2?emT，每一 個分別具有似然權重的值wl_ml、wl_m2…或wl_mT，對於最小割集的權重參數WP可

【權利要求】
1. 一種模擬網絡的至少一個流量參數的方法，所述方法包括： 生成表示將被模擬的網絡的圖； 基於可用數據通過對所述圖的邊分配權重從所述圖生成經標註的圖，其中所述權重從 表示相應的邊在所述網絡操作期間被連接的可能性的似然權重、衡量了一旦所述相應的邊 斷開對於所述網絡的至少一個流量參數的影響的程度的影響權重、以及所述似然權重和所 述影響權重的組合中選擇； 從所述經標註的圖生成最小割集； 選擇少於生成的所述最小割集的全部的最小割集的集合； 通過從每一個所述最小割集刪除至少一個割，從所述集合中的所述最小割集生成幾乎 孤立的場景； 對於所述幾乎孤立的場景關於所述至少一個流量參數運行模擬， 其中所述圖的所述生成、所述經標註的圖的所述生成、所述最小割集的所述生成、所述 集合的所述選擇、所述幾乎孤立的場景的所述生成和所述模擬的所述運行中的至少一個步 驟使用被配置為應用自動化程序的一個或多個處理器被執行。
2. 根據權利要求1所述的方法，其中所述最小割集的所述生成包括： 從所述經標註的圖生成具有基數K的割集，所述基數K小於所述圖的邊的總數； 通過迭代地刪除來自每一個所述割集的邊生成每一個所述割集的子集；以及 確定每一個所述子集是否是割集。
3. 根據權利要求1所述的方法，其中最小割集的所述集合的所述選擇包括： 在生成的所述最小割集中一次一個地選擇每一個最小割集； 對於每一個選擇的最小割集，分配權重參數，所述權重參數依賴於分配給所述選擇的 最小割集內的邊的所述權重的每一個值；以及 應用所述權重參數的值以確定每一個最小割集是否被包括於所述集合內。
4. 根據權利要求3所述的方法，其中所述權重參數的所述值的所述應用包括： 將所有生成的所述最小割集以所述權重參數的單調地改變的順序排序；以及 從前N_mcs個排序的生成的所述最小割集或者從後N_mcs個排序的生成的所述最小割 集中，選擇預定數目N_mcs個生成的所述最小割集。
5. 根據權利要求3所述的方法，其中所述權重參數的所述值的所述應用包括，對於所 述集合，選擇具有大於或小於預定閥值的所述權重參數的所述值的每一個生成的所述最小 害集。
6. 根據權利要求3所述的方法，其中所述權重參數中的改變對於所述選擇的最小割集 內任何邊的所述權重的值的任何增量具有相同的符號。
7. 根據權利要求3所述的方法，所述權重至少包括所述似然權重。
8. 根據權利要求7所述的方法，其中所述權重參數中的改變對於所述選擇的最小割集 內任何邊的所述似然權重的值的任何增量具有相同的符號。
9. 根據權利要求7所述的方法，其中所述網絡是交通網絡，以及所述至少一個流量參 數包括交通流量。
10. 根據權利要求9所述的方法，其中所述似然權重由Z/Nv給出，其中Z是歸一化常 數，並且Nv是對應於所述圖的邊的道路上每單位時間通過的車輛的總數。
11. 根據權利要求9所述的方法，其中所述似然權重由Y/Nw給出，其中Y是歸一化常 數，並且Nw是對應於所述圖的邊的道路上每單位長度的車輛的總數。
12. 根據權利要求11所述的方法，其中所述似然權重由Z' /WL給出，其中Z'是歸一化 常數，並且WL是對應於所述圖的邊的道路上所模擬的洪水期間的水位。
13. 根據權利要求3所述的方法，其中所述權重包括所述影響權重。
14. 根據權利要求13所述的方法，其中所述權重參數中的改變對於所述選擇的最小割 集內任何邊的所述影響權重的值的任何增量具有相同的符號。
15. 根據權利要求3所述的方法，其中所述權重包括所述似然權重和所述影響權重的 所述組合。
16. 根據權利要求15所述的方法，其中所述權重參數中的改變對於所述選擇的最小割 集內任何邊的所述似然權重的值的任何增量以及對於所述選擇的最小割集內任何邊的所 述影響權重的值的任何增量具有相同的符號。
17. 根據權利要求1所述的方法，進一步包括，對所述圖中的至少一些邊分配在所述幾 乎孤立的場景下反映對於至少一個流量參數的影響的經更新的影響權重或者新的影響權 重。
18. -種通過模擬修改網絡的方法，所述方法包括： 生成表示將被模擬的網絡的圖； 基於可用數據通過對所述圖的邊分配權重從所述圖生成經標註的圖，其中所述權重從 表示相應的邊在所述網絡操作期間被連接的可能性的似然權重、衡量了一旦所述相應的邊 斷開對於所述網絡的至少一個流量參數的影響的程度的影響權重、以及所述似然權重和所 述影響權重的組合中選擇； 從所述經標註的圖生成最小割集； 選擇少於生成的所述最小割集的全部的最小割集的集合； 通過從每一個所述最小割集刪除至少一個割，從所述集合中的所述最小割集生成幾乎 孤立的場景； 對於所述幾乎孤立的場景關於所述至少一個流量參數運行模擬； 從所述模擬識別至少一個系統級影響產生的場景；以及 在識別的所述至少一個系統級影響產生的場景下修改所述網絡以減輕所述系統級影 響， 其中所述圖的所述生成、所述經標註的圖的所述生成、所述最小割集的所述生成、所述 集合的所述選擇、所述幾乎孤立的場景的所述生成、所述模擬的所述運行、所述至少一個系 統級影響產生的場景的所述識別以及所述網絡的所述修改中的至少一個步驟應用被配置 為運行自動化程序的一個或多個處理器被執行。
19. 根據權利要求18所述的方法，進一步包括，在所述網絡的所述修改之前對所述另 一個圖中的至少一些邊分配在所述幾乎孤立的場景下反映對於至少一個流量參數的影響 的經更新的影響權重或者新的影響權重。
20. 根據權利要求19所述的方法，進一步包括以下步驟： 生成表示所述最近所修改的網絡的另一個圖； 從所述另一圖生成另一個經標註的網絡； 從所述另一個經標註的圖生成額外的最小割集； 通過刪除來自每一個所述最小割集的至少一個割從每一個所述額外的最小割集生成 經更新的幾乎孤立的場景； 對於所述經更新的幾乎孤立的場景關於所述至少一個流量參數運行另一模擬； 從所述另一個模擬識別至少一個經更新的系統級影響產生的場景。
21. 根據權利要求19所述的方法，進一步包括至少一次地執行以下步驟： 更新權利要求19的所述最近所修改的網絡以減輕所述至少一個經更新的系統級影響 產生的場景的影響；以及 重複權利要求19的步驟。
22. 根據權利要求18所述的方法，其中所述最小割集的所述生成包括： 從所述經標註的圖生成具有基數K的割集，所述基數K小於所述圖的邊的總數； 通過迭代地刪除來自每一個所述割集的邊生成每一個所述割集的子集；以及 確定每一個所述子集是否是割集。
23. 根據權利要求18所述的方法，其中最小割集的所述集合的所述選擇包括： 在生成的所述最小割集中一次一個地選擇每一個最小割集； 對於每一個選擇的最小割集，分配權重參數，所述權重參數依賴於分配給所述選擇的 最小割集內的邊的所述權重的每一個值；以及 應用所述權重參數的值以確定每一個最小割集是否被包括於所述集合內。
24. 根據權利要求23所述的方法，其中所述權重參數的所述值的所述應用包括： 將所有生成的所述最小割集以所述權重參數的單調地改變的順序排序；以及 從前N_mcs個排序的所述生成的最小割集或者從後N_mcs個排序的生成的所述最小割 集中，選擇預定數目N_mcs個生成的所述最小割集。
【文檔編號】G06F7/544GK104335161SQ201380027263
【公開日】2015年2月4日 申請日期:2013年4月29日 優先權日:2012年6月18日
【發明者】M·迪亞斯德阿森考, B·D·弗拉赫, M·A·德克加蒂, R·R·哈裡普特拉, 今道貴司, M·A·斯特爾瑪內託 申請人:國際商業機器公司