基于角色关系网络的应急处置业务流程相似度计算

刘 静，郭文艳，鲁法明，李 昂，周长红，曾庆田,2

(1.山东科技大学 计算机科学与工程学院，山东 青岛 266590； 2.山东科技大学 电子信息工程学院，山东 青岛 266590)

近年来，突发事件频发，给人们的生命和财产安全造成了巨大威胁。突发事件应急处置需要相关组织和人员按照应急预案快速执行各项应急处置措施。突发事件应急处置流程是一个涉及多组织、多角色协同交互的复杂过程[1-2]。应急处置业务流程既规定了组织和角色的具体执行任务，还描述了不同组织和角色间的交互过程，是突发事件应急响应的基础与核心。实际上，不同突发事件的应急处置流程具有一定的相似性，基于已有的、相似的应急处置业务流程构建新的应急流程无疑能提高流程构建的效率和科学性。因此，本研究拟探讨应急处置业务流程的相似性度量问题。

流程模型相似度可以从多个不同的角度予以度量[3]。目前，流程相似度计算方法主要从流程模型的结构、行为出发度量相似性流程之间的相似度。结构相似是指流程模型的拓扑结构、模型中任务逻辑关系的相似性，即模型看起来很像，但结构相似，执行行为却不一定相似；而行为相似是指流程模型的执行语义相似，也就是流程模型执行序列集合相似，很多时候体现了流程执行功能相似。文献[4]利用Petri网作为业务流程的模型，将Petri网的行为序列拆分为非循环结构、有限循环结构和无限循环结构三种主变迁序列，通过计算每类主变迁序列集合的相似度度量标签Petri网流程模型之间的行为相似性；文献[5]基于节点标签文本的语法相似度和字符串编辑距离提出了一种简单的相似度度量方法；文献[6]忽略流程活动的文本标签，通过迭代策略来识别两个流程模型元素之间的对应关系，提出了一种基于流程内部结构的相似性度量方法；文献[7-8]综合考虑模型结构和日志行为给出综合的相似度计算方法，弥补了单一基于方法计算流程相似度时的不足；文献[9]分别对基于模型结构和行为的流程相似度计算方法进行改进，使得改进的两种方法对流程日志具有相同的支持程度；文献[10]基于应急处置流程中组织部门之间的协同模式分别建立任务逻辑关系视图、部门内部流程视图、部门间协同关系视图和多部门联动视图，给出了不同视图下应急处置流程的相似度计算方法；文献[11]为满足各组织隐私保护的个性化需求，从全局结构相似和多元结构相似两方面给出消息交互流程的相似度计算方法。

综上所述，现有业务流程相似度计算方法主要通过过程模型结构、行为或者标签文本进行相似性度量。但这两种相似都是从任务视角进行衡量，如果任务命名差异性大，则可能直接导致流程相似性不高；相反，如果任务命名差异性小，则可能导致流程差异性很低。实际上，任务执行角色和组织部门等信息也是业务流程的一个重要要素[12]，尤其是在应急处置业务流程中更是如此。在流程中，角色是任务的执行者。不同的应急处置业务流程，其角色和组织的结构、命名等可能存在较大差异。在这种情况下，使用已有的计算方法，从流程模型出发计算流程相似度是不全面的。从角色视角出发计算流程相似度，有利于应急处置业务流程中角色和组织的调整，从而提高效率，更高效地做出应急处置。为解决这一问题，本研究尝试从角色视角度量流程之间差异和相似性，给出一种基于角色关系网络的应急处置业务流程相似度计算方法。具体而言，从角色的任务交付和层次关系出发，构建角色关系网络，进而基于图编辑距离计算流程的相似度，并结合实例验证所提方法的有效性。

1 基本概念

本节介绍应急处置业务流程、角色和角色层次图的定义，并结合高速公路突发事件应急处置流程实例说明相关概念，为构建角色关系网络奠定基础。

1.1 应急处置业务流程

定义1(应急处置业务流程)应急处置业务流程定义为一个五元组Σ=(P,T;F,D,M0),其中：

1)P为库所集合，用以刻画应急处置流程的运行状态；

2)T为变迁集合，每个变迁表示一个应急处置任务；

3)F⊆P×T∪T×P为流关系集合，流程的初始任务无前驱，流程的结束任务无后继；

4)D:T→O为任务执行组织函数，其中O表示参与应急处置的组织部门集合；

图1为一个高速公路突发事件的应急处置流程。其中，矩形表示任务，圆圈表示库所，有向弧表示流关系，t1,t11,t17,t24,t30为初始任务，t10为结束任务。假设事件场景为高速公路危化品运输车辆发生追尾，进而导致车体起火、危化品泄露，随时有爆炸危险。该应急处置流程涉及6个组织部门和36个应急处置任务，流程模型中涉及的具体组织信息见表1，任务信息见表2。

表1 某高速公路危化品运输车辆追尾事故应急处置业务流程涉及的组织信息表

图1 某高速公路危化品运输车辆追尾事故应急处置业务流程

表2 某高速公路危化品运输车辆追尾事故应急处置业务流程涉及的任务信息表

1.2 角色

角色可以理解为某一类对象结构、性质、行为和职能等方面所共有的特征集合，是目标、能力、责任等多方面本质特征的综合反映，能够作为事物分类的合理标准[12]。应急处置业务流程中的角色主要指任务执行者，是具有相同职能、相似行为的执行者的集合[13]。图1的应急处置业务流程涉及的角色信息见表3，共包含18个角色，角色任务信息表见表4。从角色的角度来说，应急处置业务流程可抽象为角色及其交付关系的集合，后文将基于此计算流程相似度。

表3 某高速公路危化品运输车辆追尾事故应急处置业务流程涉及的角色信息表

表4 某高速公路危化品运输车辆追尾事故应急处置业务流程涉及的角色任务信息表

1.3 角色层次图

应急处置业务流程中，角色之间通常存在上下级层次关系，从而形成一个树型的角色层次图。树的边表示流程中角色间的上下级关系，由上级指向下级。其形式化定义如下。

定义2(角色层次图)角色层次图是一个二元组CG=(NR,Es)，其中：

1)NR为角色节点集合,角色节点与角色间一一对应；

2)E⊆NR×NR表示角色节点之间的有向边集合，一条有向边表示边的起始角色与终止角色间存在直接的上下级关系。

对于角色层次图中的任意两个角色节点R,R′∈NR，若存在从R到R′的有向路，则R为R′的上级角色。

前述高速公路危化品运输车辆追尾事故应急处置业务流程对应的角色层次关系图见图2。途中每个圆表示一个角色，有向边表示直接上下级关系。例如R5是R3、R5、R10、R12和R16的直接上级，是R7和R8的间接上级。

图2 某高速公路危化品运输辆追尾事故应急处置业务流程对应的角色层次图

2 角色关系网络及其构建算法

流程模型由具有各种逻辑依赖关系的任务构成，而每个任务均关联到一个或多个角色。这些角色相互协作并最终达成流程的最终目标。因此，从角色的角度分析，应急处置业务流程可理解为角色及其交付关系的集合，从而可将流程视作一个多角色协同的业务过程[13-15]。本节给出角色关系网络的定义及其构建算法，并用角色关系网络刻画业务流程对应的角色之间的复杂协同关系。

2.1 角色关系网络

角色关系网络主要由角色对应的顶点以及角色交付关系对应的边构成。基于角色视角计算流程相似度时，上下级之间的任务交付与非上下级之间的任务交付关系具有明显差异，故根据存在交付关系的两个任务之间是否存在上下级关系，将边分为上下级之间的交付关系边、非上下级之间的交付关系边，共两类。

定义3(角色关系网络)将角色关系网络图表示为一个六元组RG=(NR,E,Es,Eu,λ,f)，其中：

1)NR为节点的集合，每个节点对应流程涉及的一个角色；

2)E⊆NR×NR为有向边的集合，假设流程模型中存在到任务的一个交付关系ti，且Ri为ti的一个执行角色，Rj为tj的一个执行角色，则(Ri,Rj)；

3)Es={(Ri,Rj∈E|Ri到Rj存在直接或者间接的上下级关系，对应上下级角色之间的任务交付关系}；不存在上下级关系的两个角色之间的任务交付关系记入集合Eu，即Eu=E-Es；

4)λ:NR→R表示角色的参与度函数(R表示实数集)，其定义如下：

其中，R∈NR为一个角色，T表示流程中全部任务的集合，TR表示角色R参与的任务的集合；

5)f:E→R表示边的交付权值函数，其定义如下：

其中，freq(Ri,Rj)表示角色Ri交付给角色Rj的任务数量。

图3是前述高速公路危化品运输车辆追尾事故应急处置业务流程对应的角色关系网络。其中，每个圆圈表示一个角色，虚线有向边表示存在上下级关系之间的两个角色之间发生任务交付，实线有向边表示非上下级关系的两个角色之间发生任务交付关系，边上的权值表示交付权值。以R1到R2的有向边为例，该边存在是因为流程模型中存在任务t3到t5的交付关系，而R1为任务t3的执行角色之一，R2为任务t5的执行角色之一；该边为实边，因为R1和R2之间不存在直接或者间接的上下级关系；该边的权值为0.25，因为R1交付到R2的任务数量为1，而R1的全部交付任务数量为4，两者之商为0.25。角色关系网络的具体构造算法见下一节。

图3 某高速公路危化品运输车追尾事故应急处置业务流程对应的角色关系网络

2.2 角色关系网络的构建算法

算法1给出角色关系网络的构建过程。输入为含有角色信息的应急处置业务流程图和相关的角色层次图，输出为相应的角色关系网络图。遍历应急处置流程模型的所有任务，若两个角色之间存在交付任务，则两者在角色关系网络中存在有向边(Step1-3)；对于每一条边，若该边关联的两个角色在角色层次图中存在直接或者间接的上下级关系，则将该边标记为虚线边，归入Es，否则归入Eu(步骤4)；遍历角色集合中的所有角色，每个角色的参与度为该角色参与的任务数量与所有任务数量的比值(步骤 5～7)；遍历角色关系网络中的所有有向边，每条有向边的交互权值为该边的起始角色交付给终止角色的任务数量与该起始角色交付出的所有任务数量的比值(步骤8～11)。

算法1：构建角色关系网络

输入:含有角色信息的应急处置业务流程模型Σ，角色层次图CG

输出:角色关系网络图RG

步骤：

1Fort∈Tdo

2E←(t.role,((t·)·).role);∥流程模型中存在任务交付的角色对在RG中存在有向边

3Enddo

4Eu=EEs;∥计算角色关系网络中的非上下级关系

5ForeachR∈NRdo

6λR=|TR|/|T|;∥计算每一个角色的参与度

7Enddo

8Foreache∈Edo

9 ∥Rstart为边e的起始角色节点，Rend为边e的终止角色节点

11Enddo

12RG=(NR,E,Es,Eu,λ,f)

13ReturnRG

例如，以图1所示应急处置业务流程模型和图2中的角色层次关系为算法1输入，经过算法1的处理得到图3所示角色关系网络。

3 基于角色关系网络的流程相似度计算

为比较两个角色关系网络的相似度，给出一种基于图编辑距离的度量方法。两个图之间的图编辑距离是将一个图转换成另一个图的最小代价。首先，约定所允许的图的基本转换操作，包括节点的插入、删除、替换和边的插入、删除、替换；之后，设定每种基本转换操作的操作代价；最后，利用A-star算法[16]求出最小图编辑距离。两个图之间的编辑距离越小，则从一个图转化为另一个图所需要的操作代价越小，相似度越高。

3.1 角色关系网络的编辑操作

2)角色节点n∈NR，n可从RG中删除(或插入RG′中)，当且仅当n∉sn；同理可以定义从RG′中删除(或插入RG中)的节点,可插入删除节点的集合定义为idn；

4)有向边(n,m)∈E，该边可以从RG中删除(或插入RG′中)需满足以下两种条件之一：

a)不存在函数M使得(n,n′)∈M，(m,m′)∈M且(n′,m′)∈E′同时成立；

同理可以定义从RG′中删除(或插入RG中)的有向边。

3.2 角色关系网络图编辑距离

RGEDM(RG,RG′)=‖sn‖+‖idn‖+‖se‖+‖ide‖，

两个角色关系网络图RG和RG′的编辑距离定义为：

RGED(RG,RG′)=min RGEDM(RG,RG′)。

3.3 应急处置业务流程相似度计算

两个角色关系网络RG和RG′的相似度：

Sim(RG,RG′)=

其中，wsn、widn、wse和wide为替换节点、插入删除节点、替换边和插入删除边的代价系数，取值范围为[0,1]，可根据实际需求设置。

4 实例分析

高速公路是突发事故的多发地，一旦发生重大事故，其应急处置需要交通、消防、医疗等多个组织部门进行跨组织协同合作，是典型的跨组织应急处置业务流程。本节结合高速公路突发事故应急联动处置场景下的流程实例，给出本研究提出的相似度计算方法的实例分析。

4.1 实例设计

某高速公路发生多车连续相撞重大交通事故，导致有车体起火，多人受伤。该应急处置过程与上文提到的危化品运输车追尾事故相似，但不涉及环境监测以及排爆等工作，其流程如图4所示，涉及4个组织和29个应急处置任务。

图4 某高速公路重大交通事故应急处置业务流程

组织与任务信息如表1和表2所示，角色信息如表5所示，共包含13个角色，角色任务表如表6所示。

表5 实例2某高速公路重大交通事故应急处置业务流程对应的角色信息表

表6 实例2某高速公路重大交通事故应急处置业务流程对应的角色任务信息表

某高速公路重大交通事故应急处置业务流程对应的角色层次关系如图5所示。由急处置业务流程(图4)和角色层次关系(图5)经过算法1可得相应的角色关系网络，如图6所示。

图5 某高速公路重大交通事故应急处置业务流程对应的角色层次图

图6 某高速公路重大交通事故应急处置业务流程对应的角色关系网络

4.2 实验结果

根据文献[10]对上文中关于某高速公路危化品运输车追尾事故和重大交通事故两个应急处置业务流程构建过程视图，得到面向过程视图的计算结果为0.83。对两个应急处置业务流程应用本方法，角色关系网络已得到，设图3所示角色关系网络为RG，图6为RG′利用A-star算法求得最小图编辑距离，对应的四种基本操作为：

2)插入删除节点集合idn: {R14,R15,R16,R17,R18}

3)可替换边集合se:

4)插入删除边集合ide:

R14→R5,R9→R17,R17→R18,R14→R15,R15→R15,R15→R16，R15→R5}

取wsn=widn=wse=wide=1，通过本文的方法计算得到两个应急处置业务流程的相似度为Sim(RG,RG′)=0.627。

4.3 实验结果分析

实验选取了两种方法对图1和图4所示的两个应急处置业务流程进行相似度度量，一是基于过程模型的计算方法，一是基于角色关系网络的计算方法。其中：

1)由于两个模型都是高速公路应急处置流程，其活动和执行过程都较为相似，活动的命名也基本一致，导致两个流程面向过程视图的相似性较高，无法体现二者的差异性。

2)对于本研究所述两个应急处置流程，其过程较为相似，但由于角色与活动的对应关系以及角色的层次结构之间的差异，因此面向角色关系的计算结果比面向过程视图的计算结果偏低，更能体现两者差异性。

3)执行角色不同，即使任务层面的流程模型非常相似，也可能因为执行角色的不同，导致两个流程的执行效率不同，但仅仅通过任务层面的结构或者行为相似却不能发现这种差异性。因此，在流程的角色信息完整，组织结构信息完整的情况下，可以采用本研究所述方法。从角色的角度出发进行流程相似度的计算，弥补了仅从过程模型出发进行计算的不全面性。从多个角度出发进行相似度的计算，可以更全面地把握流程之间的相似性和差异性。

4)如果两个应急处置业务流程在效率上存在差异，在对效率较低的流程进行调整的时候，由于面向角色关系的相似度计算结果偏低，可以着重调整流程中的角色、组织结构，进而对流程进行优化。

5 总结

本研究给出了一种面向角色视图的应急处置业务流程相似度计算方法，基于组织角色之间的任务参与度、任务交付关系和角色层次关系构建角色关系网络。当应急业务流程之间的活动差异性较大，但角色设置相似的场景下，可以从角色关系的角度发现流程的相似性；当业务流程之间活动设置较为相似，但角色设置有所差异的情况下，可以从角色关系的角度发现流程的差异性，进而调整角色结构，优化业务流程。本研究所述的相似度计算方法可以弥补仅从任务和流关系角度分析业务流程相似性的不足，同时，可以从多个维度对应急处置流程进行评估、调整和优化。