基于有向圖相似的應急響應程序模塊化問題研究

鄧 婕，池 宏，許保光

(1.中國科學院科技政策與管理科學研究所，北京 100190;2.江南大學商學院，江蘇 無錫 214122; 3.中國科學院大學公共政策與管理學院，北京 100049)

?

基于有向圖相似的應急響應程序模塊化問題研究

鄧 婕1,2，池 宏1,3，許保光1,3

(1.中國科學院科技政策與管理科學研究所，北京 100190;2.江南大學商學院，江蘇 無錫 214122; 3.中國科學院大學公共政策與管理學院，北京 100049)

對于發生頻率低，影響力大的突發事件，組織與個人的應急經驗將影響判斷與決策。應急響應程序在突發事件的響應過程中起著指導作用，通過對多個應急預案中響應程序分析發現，一些行動措施經常按照固定次序重復出現，如果將這種組合關系規范化，并固定成為模塊，響應時間將會縮短，應急機構與人員之間的協調將會改善，模塊的產生為應急預案的快速調整以及應急培訓提供參考方案。本文的主要目的是從多個應急響應程序中提取具有通用性與特殊性的模塊，首先對多個應急響應程序疊加起來的有向總圖進行了分割，通過定義的有向圖相似性判斷候選模塊的代表性，最后以復原應急響應程序的差異性之和與模塊接口之和為目標，建立數學規劃模型，并設計啟發式算法求解，將有向總圖所有的邊分配到響應程序模塊。通過案例計算分析，驗證所提方法可以獲得所需模塊，并為實現應急響應程序快速重構與功能組合提供了方法基礎。

應急管理；有向圖相似；響應程序模塊；模塊化

1 引言

隨著我國突發事件的頻繁發生，政府與社會也越來越重視應急預案的建設和管理工作。應急預案跟法律法規一樣以文本形式存在，它包含了應急方針、組織機構與職責、風險分析、能力評估、應急響應程序和支持附件等，作為應急響應第一處置行動的主要依據[1]，當前的應急響應程序通常用流程圖的形式表示。由于突發事件具有突發性、蔓延性、不確定性等特點，響應的即時性與準確性可以最大程度挽救生命與財產損失，因此響應過程中不斷出現的征兆或者搜集的信息對應急響應程序的編制提出了快速調整的要求。在制造業中存在全球化、多樣性帶來的小批量大批次的新制造需求，而可重構制造系統通過靈活的模塊快速安排制造系統成功的解決了這個問題，通過制造業的啟示，對同一類型的應急響應程序研究發現，在相同場景下，總是重復出現一些相同且邏輯關系固定若干措施(行動)集合，這些行動集合可以用來實現一定的功能，如果將這些行動集合定義為模塊，當處置需求發生變動時，可以通過模塊的修改、替代、增加、刪除等操作活動，實現模塊的快速重組。有學者已經意識到應急響應程序模塊化可以解決應急響應的結構化管理和動態調整問題，并在文章中提到了模塊化的思想與重要性[2-3]。

“模塊化”思想在應急管理領域已有少量研究涉及，下面將從應急流程、應急預案以及應急系統方面進行闡述。應急流程方面，田軍等[4]通過統一建模語言(UML)對應急任務之間的依賴關系進行描述，從任務之間的流依賴和資源依賴中的角色依賴、設備依賴和設施依賴的關系強度方面提出依賴量指標，建立了應急任務活動的聚類優化模型，獲得具有高內聚和松散連接的流程模塊。鄧婕等[5]為提高響應程序動態調整效率，通過定義緊密度與代表性，建立多目標數學規劃模型，并設計蟻群算法進行求解，通過算例分析發現可以為響應程序模塊化提供有效合理的方案。姜艷萍等[6]提出了一種風險決策方法，以應急效果與實踐作為評價指標，可以實現應急決策方案動態調整問題，從而獲得最優方案，同理，王劍和羅東[7]也是為了解決應急決策問題，建立了貝葉斯決策網絡agent應急決策模型，從而來選擇決策方案，二者的方案均為場景下的處置措施集合，都可以視為模塊。應急預案方面，榮莉莉和楊永俊[8]針對預案應急響應流程WBS分解定義了核心任務，每個核心任務包含著一些具體問題，每個問題由一個應急處置措施來回答，其提出核心任務在一定程度上可以等同于本文中去掉邏輯關系的模塊。Liu Lei等[9]提出了基于預案模塊化，通過功能與需求相匹配原則重構生成新預案的思路，并建立了預案重構的框架。Girard等[10]提出了對當地應急響應計劃的事前評估來告知決策者可能失效的環節，以便有機會對脆弱環節加強，其中應急響應計劃是由模塊按順序組成，評估方法為故障樹方法。Turoff等[11]使用動態情景模型來應對潛在的突發事件，模型中要考慮一系列的因素以及必要事件，此必要事件等同與本文的模塊。應急系統方面，Mendonc等[12]在文中指出在應急管理需要一些靈活的模塊來保證安全、有效的應急響應，這些模塊可以處理不確定性與挑戰性情景，以及幫助計劃進行調整。Yoon等[13]也是主要研究交通輔助決策系統評價方法的有效性，文中系統是由計劃、資源、信息、交流四個大模塊組成，每個大模塊下具有小模塊，通過抽取小模塊作為組成新計劃。以上所有的文章，應急流程類文章沒有提供模塊接口，并且丟失了模塊內活動間銜接關系；應急預案只是介紹了模塊的概念以及使用情況，應急系統類文章的重點在評估方法的有效性，并未給出模塊的來源以及依據；因此模塊的啟用場景以及接口可插性是本文的一個創新點。

有向圖的相似性在數據挖掘中有較多的應用，目前使用的相似性方法大致可以分為以下三類[14]:基于圖同構的方法[15-16]、基于特征的方法[17]、基于迭代的方法[18]。SimRank算法為迭代算法中較為成功的算法，最開始應用在計算圖的自相似性上，通過對矩陣A2(A為鄰接矩陣)迭代計算一個圖中任意兩個節點的相似性，當相似分數收斂時算法結束。Blondel等[19]通過兩個有向圖的鄰接矩陣計算將這個方法擴充用到兩個有向圖的相似性比較中，其方法關注的是節點的相似性；Zager和Verghese[20]提出了圖相似與匹配的一種遞歸方法，這種方法引入了有向的邊與節點的相似分數的觀點來計算兩個有向圖的相似性。Bayati等[21]用信息傳遞算法提出了兩種稀疏圖匹配算法，即將尋找給定兩個圖節點的關系問題表達為整數二次規劃問題，然后用belief propagation(BP)算法來求解。雖然以上的相似性計算方法與匹配方法給了本文啟示，但是本文需要計算有向圖的相似性，且有向圖中節點具有唯一標示，不需要計算不同標識節點之間的相似性，因此前面介紹的方法需要經過改進來適應本文的需求。

為了提取網絡圖表達的應急響應程序中具有代表性與通用性的模塊化，本文希望通過定義有向圖相似性，建立應急響應程序模塊化模型，通過場景約束與圖分割方法獲得候選模塊，并設計啟發式算法對候選模塊進行調整，達到模塊化目的，產生一些好的初始方案，以供應急專家在應急決策支持中快速調用。

2 問題描述和數學模型

本文的問題來源于航空公司的應急預案重構需求，由于應急機構的不同，模塊的規模可大可小，從政府層面，一個應急機構可以算是一個大模塊，從企業層面，一個部門的功能模塊。本文通過分析自然災害與事故災難類突發事件，將突發事件劃分為若干個階段，每個階段具有一定的場景與處置目標，模塊在這樣的情況下進行使用。本文將需要模塊化的多個應急響應程序重疊起來形成有向圖，該圖中具有節點、邊、場景等屬性，在定義了有向圖相似性與場景約束條件下，建立數學模型對有向圖進行分割。

2.1 相關知識介紹

定義1 源節點矩陣、目標矩陣、出度、入度

如圖1，在一個有m個節點，n條邊的圖GA中，讓oA(i)代表邊i的源節點(開始節點)，tA(i)代表邊i的目標節點(結束節點)，通過m*n的矩陣可以表達GA的鄰接結構，那么源節點矩陣AO和目標節點矩陣AT定義為以下公式：

(1)

(2)

圖1 源節點矩陣、目標矩陣

定義2 圖匹配

給定兩個圖GA=(VA,EA),|VA|=nA和GB=(VB,EB),|VB|=nB，這兩個圖的匹配是一個從圖GA節點到圖GB節點的一對一映射M。映射M可以用節點對集合表示，每一節點對為(a,b),a∈VA,b∈VB。通常用一個nA×nB的映射矩陣M表示，矩陣中每一個元素M(a,b),a∈VA,b∈VB定義為:

兩個圖的匹配問題可以用著名的二分圖匹配算法解決。這個二分圖由兩個圖的節點構成，二分圖邊上的權值是圖節點間的相似值。在我們的問題中，GA與GB均有相同的大小(nA=nB=n)，因而可以直接采用解決指派問題的匈牙利算法。問題可以定義為：用VA中的n個節點對應VB中的n節點，VA中每個節點只能與VB中的一個節點相對應，并且使得對應上的節點間的相似值總和最大。令Xij表示VA中的節點i與VB中的節點j對應關系，Xij=1，節點i、j對應，否則Xij=0；Sij表示VA中的節點i與VB中的節點j間的相似值，問題的數學模型為：

滿足以下約束條件：

Xij∈{0,1},?i,j=1,…,n

2.2 相似性定義

本文的思路，根據圖分割后獲得的模塊，給定代表性閾值，模塊可以會存在的各種子結構，如果應急響應程序包含子結構，即子結構可以在應急響應程序中找到，那么說明模塊與應急響應程序相似。下面將定義有向圖的相似性，首先介紹一下節點相似性。

(一)節點相似性

(3)

(二)有向圖相似性

計算兩個有向圖GA和GB的相似性有以下三步：(1)計算標識相同的節點相似性；(2)無向圖將用上一步計算出的節點相似性構造一個二分圖，再在該二分圖上找到一個最大權值匹配，但是對于表達應急響應程序的有向圖而言，標識不同的節點就是兩個不同的行動，沒法進行匹配，因此只需要對標識相同的節點進行權值匹配；(3)所有匹配節點間相似性的總和并歸一化后，即為兩個圖之間的相似性。

根據前面介紹的步驟與應急響應程序的節點標識特殊性，GA與GB的相似性可以定義為匹配節點間的相似值求和，并用GA與GB節點數之積的平方根進行標準化。

(4)

2.3 模塊化的目標

從應急響應指揮者角度出發，希望應急響應開展過程中的管理是從粗到細的過程，即每層或者每個階段(模塊)具有管理者，這樣的分工將有利于應急任務的對接與管理。行動作為應急響應程序的最小組成單元，在進行統一標準化后，即明確行動為響應突發事件的過程中具體的某人或者某類相同性質的人組成的小團隊承擔的單一性質的工作，應急響應程序可以抽象為網絡計劃圖，對多個應急響應程序網絡計劃圖分析發現，由多個行動銜接組成的工作流(模塊)重復出現在多個應急響應程序中且可以實現一定功能。如果將這些相似且有序的行動組合用模塊替換的話，應急響應程序網絡計劃圖就會變得的簡潔明了，從管理角度出發，此措施可以方便以后的指揮管理、培訓、能力評估以及進行資源準備。為了達成指揮者形成模塊的需求，可以利用以下兩個目標獲得質量較高的模塊。

目標1：差異性之和最小化

從全局出發，盡量將同場景下出現頻率高且具有相同功能的多個相似網絡計劃圖提取作為模塊，那么在復原應急響應程序的時候，可以調用模塊快速組成應急響應程序，因此模塊的合理性體現在被應急響應程序調用時復原應急響應程序的復原程度，如果模塊復原的應急響應程序與原應急響應程序相比差異較少，即冗余與缺失的行動與邊較少，則復原程度好，模塊設置合理，否則設置不太合理，因此差異性之和最小化可以作為目標來獲得質量較優的解。

目標2：模塊之間接口之和最小化

接口一詞普遍出現在計算機領域中，它的含義是信息交換的共享邊界。對于響應程序模塊而言，其特點是功能明確，接口較少，這樣工作交接需要協調的部門少，方便了責任追究與管理。響應程序模塊是從應急響應程序總圖中分割出來，根據點分割的思想希望模塊間的通信，即模塊間的切點的重復數量最少，因此無論是模塊本身以及圖分割，模塊之間接口之和最小化應該作為一個目標。

2.4 圖模塊化問題描述

決策問題是從G(V,E)的所有分割集合為Θ中找到一種合理分割模式來滿足應急響應程序復原后差異性之和最小與模塊間接口之和最小的需求，并獲得若干子圖(g1,g2,…，gc)形成程序模塊，其中gc是第c個模塊，C是模塊的總數。設決策變量為xgci,xgci=1,?i∈G(V),gc∈{g1,g2,…，gc}表示將i納入程序模塊gc，即i∈gc，否則xgci=0；假設gc執行的場景為d，響應程序k有多個場景，其中場景d對應的子圖用gc(k)表示，用Sgcgc(k)表示程序模塊gc與響應程序子圖gc(k)的相似性，ξ表示相似性閾值，若存在Sgcgc(k)≥ξ，則接受gc為一個模塊，并可以在復原應急響應程序k時使用，表示為zkgc=1,?gc∈{g1,g2,…，gc}；否則，不接受表示為zkgc=0,?gc∈{g1,g2,…，gc}。

2.5 數學模型

符號說明

k 應急響應程序下標(k∈K)

c模塊下標(c∈{1,…，C})

(i,j)表示E(G)中的一條邊

gc為第c個程序模塊

gc(k)表示在與gc相同場景下響應程序k對應的子圖

ξ為相似性閾值

決策變量

則數學模型為

(5)

(6)

(7)

xgcixgcj=ygcij?gc∈{g1,g2,…，gc},

i∈V(G),j∈V(G),i≠j,(i,j)∈A(G)

(8)

xgcixgcj-Dij≤0，?gc∈{g1,g2,…，gc},

i∈V(G),j∈V(G),i≠j,(i,j)∈A(G)

(9)

(10)

xgci∈{0,1},?gc∈{g1,g2,…，gc},i∈V(G)

(11)

ygcij∈{0,1},?gc∈{g1,g2,…，gc},(i,j)∈A(G),i≠j

(12)

zkgc∈{0,1},?k∈K,gc∈{g1,g2,…，gc}

(13)

其中式(5)為目標1差異之和，它一共由四部分組成：第一部分為與原應急響應程序相比缺失的邊，第二部分為與原應急響應程序相比冗余的邊，第三部分為與原應急響應程序相比缺失的點，第四部分為與原應急響應程序相比冗余的點；式(6)為目標2模塊接口之和；式(7)是保證總圖的邊被分配給一個模塊，且每條邊且被分配一次；式(8)是保證分配到同一個模塊的兩個節點，連接二者的邊也被分配給此模塊，若兩個節點分到不同模塊，二者之間不存在連邊；式(9)保證一個模塊內的行動是同一個場景；由于本文采用點分割的模式對有向圖進行分割，因此式(10)為確定切分點；式(11)-(13)為決策變量。

3 啟發式算法

本文將在多個應急響應程序網絡計劃圖映射的總圖G，對G圖中所有的邊采用圖分割的方式分配到子圖中來獲得模塊。由于事先不確定G需要劃分的模塊數量C，因此本文是先根據場景數量獲得候選模塊，然后對候選模塊中不滿足約束條件的節點不斷剪枝來獲得新的候選模塊，當候選模塊的改進不能影響目標增量加權或者相似性增量之和時，算法結束。本文中的啟發式算法主要采用剪枝原理，實際屬于窮舉法，最后形成了C個模塊，那么進行了C-1次剪枝，剪枝后比較兩個圖的相似性，那么其計算復雜度為O(2(C-1))，因此該算法可以適用規模較大的數據。

(1)剪枝原理

本文剪枝操作是從候選模塊gc與應急響應程序k在gc執行場景下對應的子圖gc(k)的相似性出發，通過設定相似性閾值ξ與相似性閾值下限θ將具有通用性與特殊性的模塊全部提取出來，θ的提出是為了提高相似性低模塊的剪枝速度。如果gc與gc(k)大部分相似，但又都不滿足相似性閾值，即θ

對于剪出來的子圖也需要優化，即判斷這些新增的子圖是否可以合并成新的候選模塊，如果能合并，將其作為新的候選模塊gc，再對gc與gc(k)的相似性判斷是否需要剪枝。

(2)算法結束條件

在對候選模塊的優化過程中，候選模塊的數量會隨著剪枝操作而不斷增加，即有向圖的切點也會增加，那么f2的值就會增大，但是隨著模塊的規模變小，即模塊包含的節點與關系變少，調用其復原應急響應程序的質量也就越好，f1就會變小。為了解決本文中相互矛盾的雙目標，需要設定一個指標來平衡其關系，由于兩個目標值的數量級有可能不一致，本文將采用兩個目標增量加權Δfn的方式來解決這一問題的，表達見下式(14)，其中第一部分為目標1在第n次剪枝后的增量，第二部分為目標2在第n次剪枝后的增量，然后將兩個目標增量的加權Δfn作為此次算法終止的指標，當Δfn小于某個設定值ε，可以認為目標值沒有改進的空間，算法結束。

(14)

Δsimn=

(15)

4 算例

本文算例選取航空公司現有的起落架故障、空中顛簸、空中停車三個應急響應程序對其求解響應程序模塊，由于應急響應程序涉及的行動數量較多，因此用編號表示，圖2至圖4分別是這3個應急響應程序的網絡圖。

圖2 起落架故障應急響應程序

圖3 輪胎故障應急響應程序

圖4 爆炸物應急響應程序

本文將對三組應急響應程序進行模塊化，首先將三個應急響應程序合并形成圖5中應急響應程序總圖G，通過對航空公司應急工作的分析發現，基本存在以下幾個場景：接收信息S1、啟動預案S2、現場處置S3、關閉預案S4，由于存在跨場景的行動集合，因此這些行動集合需要單獨作為模塊。在場景約束下，圖5的最初模塊數量為6個，其中模塊(a)在場景S1下啟動的信息上傳下達，模塊(b)在場景S2下啟動的人員集結，模塊(c)、(d)在場景S3下啟動的非安全落地與安全落地下現場處置,模塊(e)為跨場景模塊媒體應對，其位于在場景S2與S4中，模塊(f)在場景S4下啟動的預案關閉，隨著剪枝過程模塊數量在原始數量基礎上增加。

本文在給定相似性閾值下限θ為0.3，相似性閾值ξ為0.75、終止條件閾值ε為0.01的情況下，經過算法計算獲得結果見表1，由于將圖5中的模塊與圖2-4分別計算相似性，發現圖5中(a)、(c)、(e)、(f)其它模塊與圖2-4應急響應程序中對應的子圖相似性都為1，不需要剪枝，即圖6中的模塊(A)、(E)、(G)、(K)，然而模塊(b)、(d)相似性低需要剪枝。第1次剪枝，模塊(b)被切分成3個模塊，其中2個為特殊性模塊(D)、(F)，其對應的功能為本公司判斷模塊、地面空中判斷模塊，不可繼續剪枝，剩下1個模塊(b’)。第2次剪枝，雖然模塊(d)可以在圖4的子圖中找到，但是如果繼續對其剪枝，分成模塊(H)、(I)、(J)，在提高模塊(d)與圖2-3對應子圖的相似性的同時，也會增加模塊(d)與所有子圖的相似性之和。第3次剪枝，對模塊(b’)進行再次剪枝，獲得模塊(B)、(C)，從而提高代表性之和，獲得具有通用性的模塊；當開始第4次剪枝時，發現每個候選模塊與其同場景下對應的子圖的相似性已經達到1，因此無法繼續進行剪枝，最后選擇方案3作為最優解f1=0，f2=34。

圖5 應急響應程序總圖G以其初始模塊情況

剪枝次數1234模塊數量8101111f1281200f221323434Δfn—0．04760．93750Δsimn?—(0，0．2275，0，0，0，0，0，0)(0，0，0．2546，0，0，0，0，0，0，0)(0，0，0，0，0，0，0，0，0，0，0)

*中的一組值(0,0.2275,0,0,0,0,0,0)為第二次剪枝與第一次剪枝相似性的對比，由于在第二次剪枝過程中，其中有1個模塊被劃分成3個模塊，因此三個模塊的平均相似性與原來的模塊計算相似性之和增量。

第3次剪枝次數對應的模塊集合見圖6，分析圖中的模塊，沒有發現任何模塊違背模型中約束條件，即將同一條邊分給多個模塊，不同場景下的行動放在同一個模塊中；另外圖6中重復的節點為模塊的接口，例如，接口5被分配給5個模塊，接口6-11被分配給4個模塊，此措施增加了目標f2。由于算例最優解中已經獲得具有特殊性的模塊B、D、F、I、J，因此在復原3個應急響應程序的時候，起落架故障應急響應程序根據相似性與功能調用了模塊(A、B、C、G、H、K)，輪胎故障應急響應程序調用模塊(A、C、D、E、H、K)，爆炸應急響應程序調用了模塊(A、C、D、E、F、G、H、I、J、K)，根據3個應急響應程序調用模塊情況復原后差異性都為0，因此差異性之和也為0。通過算例可以得知基于有向圖相似性的模型與啟發式算法在提取通用性模塊與特殊性模塊的有效性，且算法的計算復雜度低，計算速度快，可以為大規模的應急響應程序模塊化服務。

圖6 第3次剪枝次數對應的模塊集合

5 結語

本文研究利用有向圖相似性的思路，通過對多個應急響應程序疊加的有向總圖進行分割，建立了多目標數學模型，并設計啟發式算法對候選模塊的從粗到細進行了優化，選取航空公司的作為算例，通過模塊化結果顯示，本文提出的數學模型與啟發式算法對多個應急響應程序的模塊化具有可行性，將具有通用性與特殊性的模塊都提取出來，并提供了模塊的接口。本文的貢獻在于，提出了應急響應程序模塊的有向圖相似性定義以及提取模塊的具體模型，形成了模塊，保留了模塊之間的接口，在一定程度上可以提高應急管理的組織效率與應急預案調整的速度，體現了模塊的即插即用性，可以為計算機輔助應急管理提供基礎。

[1] 袁宏永,蘇國鋒,李藐.論應急文本預案、數字預案與智能方案[ J] .中國應急管理, 2007,(4):20-23.

[2] 劉磊,池宏,邵雪焱,等.預案管理中的重構問題研究[C]. 第四屆國際應急管理論壇暨中國(雙法)應急管理專業委員會第五屆年會,北京,2009年12月12日-13日.

[3] 蔡冠華,黎偉.美國應急預案體系研究及對我國的標準化建議[J].質量與標準,2013,(7):42-45.

[4] 田軍,李莉芳,白劍,等.基于DSM的應急任務流程模塊化設計研究[J].中國管理科學,2014, 22(8):100- 107.

[5] 鄧婕,祁明亮,池宏,等.應急預案響應程序模塊化研究[J].運籌與管理, 2015, 24(5):132-143.

[6] 姜艷萍,樊治平,蘇明明.應急決策方案的動態調整方法研究[J].中國管理科學,2011,19(5):104-109.

[7] 王劍,羅東.基于BDN的突發事件多主體應急決策模型研究[J].中國管理科學,2015,23(S1):316-325.

[8] 榮莉莉,楊永俊.一種基于知識供需匹配的預案應急能力評價方法[J].管理學報,2009,6(12):1643-1647.

[9] Liu lei, Chi Hong, Shao Xueyan, et al. A study on reconstruction problem in emergency plan management[C]// Proceedings of International Symposium on Emergency Management, Beijing, China,2009.

[10] GirardC,David P, PiatyszekE et al. Emergency response plan: Model-based assessment with multi-state degradation[J].Safety Science,2016，85:230-240.

[11] Turoffa M, Baulsb V, Plotnickc L,et al.A collaborative dynamic scenario model for the interaction of critical infrastructures[J]. Futures, 2016，84(Part A):23-42.

[12] Mendonc D, Beroggi G E G, van Gent D, et al. Designing gaming simulations for the assessment of group decision support systems in emergency response[J].Safety Science, 2006,44(6):523-535.

[13] Yoon S W,Velasquez J D,Partridge B K, et al.Transportation security decision support system for emergency response: A training prototype[J].Decision Support Systems,2008, 46(1):139-148.

[14] Koutra D, Parikh A,Parikh A,et al. Algorithms for graph similarity and subgraphmatching[R].Technical Report,2011.Carnegie Mellon University.

[15] Zelinka B. On a certain distance between isomorphism classes of graphs[J].Casopis Pest. Math.,100,(4): 371-373.

[16] Sobik F,Sommerfeld E. A graph theoretic approach to the characterization of classes of structured objects[J].Computers and Artificial Intelligence,1984,3: 235-247.

[17] Giugno R,Shasha D.Graphgrep: A fast and universal method for querying graphs[C]//Proceedings of International Cenferenee on Pattern Recognition,Quebec City,Canada,August 11-15,2002.

[18] Jeh G,Widom J. SimRank: A measure of structural-context similarity[C]// Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, Edmonton,Alberta,Canada,July 23-26,2002.

[19] Blondel V D, Gajardo A, Heymans M, et al. A measure of similarity between graph vertices: Applications to synonym extraction and web searching[J]. SIAM Review, 2004, 46(4), 647-666.

[20] Zager L A,Verghese G C. Graph similarity scoring and matching[J]. Applied Mathematics Letters, 2008.21(1):86-94.

[21] Bayati M,Gleich D F,Saberi A, et al. Message passing algorithms for sparse networkalignment[J]. 2013,7(11):1-31.

The Research on Emergency Response Procedures ModularityBased on the Similarity of Directed Graph

DENG Jie1,2, CHI Hong1,3, XU Bao-guang1,3

(1.Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100190,China;2.Jiangnan University, School of Business, Wuxi 214122,China;3.School of Public Policy and Management,UCAS,Beijing 100049,China)

In very low-frequency,high-consequence emergency events, a group or individual’s prior experience will influence judgments and decision. Emergency response procedures play a guiding role when emergency accidents happen. Through analyzing multiple emergency response procedures, it is found that some actions repeatedly work together with a sequence, if those actions can be normalizedand fixed as a module, reaction time will be reduced and coordination will be improved, the generation of emergency modular will provide a suggestion for the same type of emergency accident on adjusting and emergency training. The purpose of this paper is to extract the commonality and particularity module from multiple emergency response procedures, firstly partition the general directed graphwhich is formed by superimposing multiple emergency response procedures, and determine therepresentative of candidate module by defining the similarity of the directed graph. Finally, a mathematical programming model whose goal is to minimum the sum of procedures’ difference and module’s interface is built. Then, by designing the heuristic algorithm, all edges of general directed graph are distributed to response procedure modules. Through analyzing the case, it is verified that this method can obtain the module with demand, and it provides a methodological basis for rapidly reconstruction and functional combination on emergency response procedures.

emergency management; the similarity of directed graph; response procedure module; modularity

2015-07-20；

2017-01-09

池宏(1960-)，男(漢族)，福建人，中國科學院科技政策與管理科學研究所，研究員，研究方向：應急管理、安全管理、風險管理和項目管理，E-mail：chihong@casipm.ac.cn.

1003-207(2017)04-0115-09

10.16381/j.cnki.issn1003-207x.2017.04.014

C931.1; O221.4

A