基于复杂网络的区域水上交通关键船舶识别方法*

文元桥 黄玉宇 周春辉1，，3 隋忠义 张 帆，4

（1. 武汉理工大学国家水运安全工程技术研究中心 武汉430063；2. 武汉理工大学航运学院 武汉430063；3. 武汉理工大学智能交通系统研究中心 武汉430063；4. 武汉理工大学内河航运技术湖北省重点实验室 武汉430063）

0 引 言

船舶是水上交通的行为主体，对其行为的研究是识别水上交通风险、实施水上交通组织和管控的重要基础性研究[1]。船舶行为一般是指船舶在驾驶人员的操纵下以航行和避让为目的所采取的行为方式及其规律。从国内外的研究现状来看，对船舶行为的研究主要包括以下几个方面。

船舶行为特征方面，主要对船舶行为特征进行宏观分析和微观分析。宏观行为分析研究船舶群体在全局尺度下所呈现的运动规律，通常通过轨迹聚类等方法分析大尺度下的船舶行为特征，胡智辉[2]通过对船舶轨迹进行聚类，得到了船舶的典型运动轨迹；潘家财等[3]、朱飞翔等[4]分别通过AIS 数据挖掘船舶轨迹特征并模拟船舶行为特征的空间分布。宏观分析主要针对船舶的运动规律，难以描述船舶行为内在的演化机制，不能实时表达船舶行为的当前状态。微观分析描述的是船舶个体在局部尺度下呈现的船舶行为；王立林等[5]、K.Patroumpas 等[6]通过不同的方法对船舶行为进行识别，但是，其没有考虑具体场景下的船舶行为、规则中的船舶行为以及多船行为；因此学者们进行进一步深入的研究。He 等[7]给出了国际海上避碰规则的量化解析模型，明确定义了船舶的各个会遇局面和会遇阶段。Lei[8]提出了1 个名为MT-MAD 的框架并在该框架中定义了船舶活动空间、行为顺序和行为特征，提出了基于船舶子轨迹评估的异常检测算法。

在行为传播研究方面，Damon[9]于2010年发表了关于行为传播的研究成果，引起人们对行为传播研究的关注。王新华等[10]基于SIRS信息传播模型提出了1种矿工不安全行为传播的SIRS模型，分析了不安全行为在矿工之间的传播机制。刘映森[11]基于弓形虫传染病模型建立了车辆异常行为传播模型，分析了传播过程的主要影响因素如环境因素、扩散能力等。陶琳玲[12]通过对复杂网络及个体行为决策等理论，构建了动态社会网络中行为扩散机制演化模型，探讨了不同影响因素对社会网络中行为扩散的影响。

在关键点识别研究中，航空、道路等交通领域也有很多相关研究。刘飞等[13]通过建立飞行冲突行为分析网络，采用复杂网络节点中心性算法结合AHP 方法对网络中节点的冲突等级进行评估，并有效地识别冲突关键点的位置；王斌等[14]将节点信任度引入PageRank 算法中，构建了1 种关键节点识别算法，有效的识别网络的关键节点；袁银国[15]通过构建区域网络，使用基于OD 熵的区域重要性评估方法以及节点网络中心性度量指标对每1 个区域进行重要性评估从而找出排名较高的区域路网节点；陈思等[16]结合PageRank 与Warshall 方法建立基于节点随机失效下的各阶段关键节点识别算法对运输网络的关键节点进行识别，得到了较好的识别效果。

目前船舶行为的研究大多只行有关行为特征行为规律方面的研究分析，如异常行为检测、船舶典型行为如转向等识别以及通过历史轨迹进行预测以及航路推荐等；而在关键节点识别方面，只对航空网络、道路交通网络进行网络关键节点识别的研究分析，对水域中的关键船舶识别的研究较少，且多数节点重要度评估指标为节点度中心性，对其他节点中心性指标评估方法研究较少。鉴于此，针对船舶航行过程中船舶行为所产生的行为交互影响现象，基于复杂网络理论，将船舶作为节点映射到网络中，构建面向船舶行为分析的复杂网络模型（简称船舶行为分析网络），将船舶间的交互关系作为节点连边对节点间的连接关系，通过AHP（analytic hierarchy process）方法构造关键点综合重要性评价指标，通过节点综合重要度排序结果，识别船舶航行过程中对区域水上交通具有潜在威胁的关键船舶。

1 面向船舶行为分析的复杂网络的构建

1.1 行为分析网络构建

船舶行为在广义上包括船舶的一般航行行为和船舶的避碰行为，在狭义上一般指船舶在驾驶人员的操纵下以航行和避让为目的所采取的行为方式及其规律[17]。所谓船舶行为，指的是船舶在时空间活动过程描述，是指船舶受驾驶员潜在意图的支配而表现出来的活动，是识别水上交通态势[18]的关键。船舶行为包含着十分丰富的船舶航行状态信息，在水上交通系统中扮演着“显影剂”的角色，能够从客观上反映出当前水上交通的实时状态[19]。在进行行为建模时，船舶行为通常被抽象为船舶在航行时所产生的时空轨迹，从中提取出行为的数据模型。从行为认知的角度，船舶行为可被视为人类对轨迹的1 种思维上的理解，这种思维除了会关注轨迹本身的运动特征之外，也会综合考虑航行环境对船舶的影响，对行为进行认知。船舶在运动过程中与其行驶在其周围的其他船舶容易产生行为交互影响，构成1 个动态复杂网络；而如何通过这一动态复杂网络描述船舶间行为交互影响对水上交通状态造成的影响，是水上交通监管需要重点关注的问题之一。

构建船舶行为分析网络，是将船舶作为节点映射到网络中，同时，船舶节点间的连边关系不是单一的根据船舶间距离远近或者是船舶间的运动关系判断，而是结合船舶间的距离以及舶间形成的相互关系判断船舶节点间是否存在连边关系，船舶间的复杂度[20]作为连边的权重。船舶在航行过程中需要1个隐私空间来保证自身船舶航行安全的需求，本文将其看作船舶的船舶领域[21]。多船船舶领域模型见图1。

图1 多船船舶领域模型Fig. 1 Multi-vessel ship domain model

船舶间距离的计算方法见式（1）。

式中:a ，b 为船舶领域的长半轴长与短半轴长。

由式（1）可知，当dij＜1时，船舶j 位于船舶i 的船舶领域内；当1 ＜dij＜ 2 时，船舶j 可能位于船舶i 的船舶领域内，也有可能位于船舶i 的船舶领域外，但此时船舶j 的位置距离船舶i 的船舶领域边界很近；当dij＞ 2 时，船舶j 位于船舶i 的船舶领域外。当船舶间的位置距离越近，船舶间的行为交互影响的概率也就越高。

船舶运动趋势示例见图2，图2（a）中的船舶形成汇聚的运动趋势，图2（b）中的船舶运动趋势为相离的趋势。判断船舶运动趋势的方法见式（2）。

其中:Dij与vij= vi- vj分别为船舶i 与船舶j 之间的相对距离矢量和相对速度矢量，通过‖ Dij‖的变化量来描述船舶间的运动趋势。当dDijdt ＜0 时，2船间相对距离逐渐减小，形成汇聚趋势；当dDijdt ＞0时，2 船相对距离增大，形成汇聚趋势；当dDijdt = 0时，2 船间相对距离达到最小值即最小会遇距离（DCPA）。

图2 船舶运动趋势示例Fig. 2 Examples of ship movement trends

根据船舶间的距离及2 船间形成的运动趋势，当2船为汇聚趋势，且船舶间的距离dij＜ 2 时或者是2船呈相离趋势而此时船舶间距离dij＜1时，船舶间存在连边关系。基于船舶间存在行为交互连边规则的判定，抽象出图1 所示水域内船舶行为分析网络模型，见图3。

图3 图1场景对应的行为分析网络Fig. 3 Behavior analysis network corresponding to the scene of Fig. 1

将行为分析网络的邻接矩阵表示为A ，aij表示船舶i 与船舶j 之间的连边，当船舶i 与船舶j 之间的行为交互关系满足上述连边规则判定时，表示船舶i 与船舶j 之间存在连边，有aij= 1 ，否则aij= 0 ，则图3所示的网络邻接矩阵可表示见式（3）。

1.2 关键节点识别方法

网络中的关键节点是指对网络结构变化影响较大的节点，这些节点状态发生变化的时候对网络结构产生较大的影响[22]。同理，在船舶行为分析网络中，当某一船舶的航行状态发生改变对网络演变产生较大影响时，该船舶即为船舶行为分析网络中的关键节点。对于船舶交通监管而言，合理调配这些关键节点的船舶能够保证水上交通安全有序的进行，保证船舶航行的安全。接下来主要是介绍找出这些关键节点的参数指标与方法。

1.2.1 节点重要性指标

节点重要性本文选取节点的度中心性、介数中心性，以及紧密中心性3 个指标来研究船舶行为分析网络中节点的直接影响力、间接影响力，以及节点衔接性，节点重要性指标定义如下。

1） 度中心性。度中心性DCi是衡量某一节点i在整个网络中的地位。节点的度越大，说明该节点与其他节点的直接关联能力越大。在船舶行为分析网络中，节点度中心性就是某船舶在网络中与其他的船舶存在较多的连边，其行为改变对网络所产生的影响越大。节点度为ki的度中心性计算方式见式（4）～式（5）。

式中:N 为网络的节点总数；aij为船舶i 与船舶j之间的连边。

2） 介数中心性。介数中心性BCi由网络所有的最短路径中经过节点i 的最短路径的数目来衡量节点在网络中作为连接桥梁的中间衔接性的大小。在船舶行为分析网络中，某船舶节点的介数中心性越大，表示越多的船舶会通过该船舶对其他船舶产生行为交互影响，该船舶在网络中的中枢功能越明显，对行为传播的影响越大。节点度为ki的船舶的介数中心性计算方式为

式中:Lxy为船舶x 和船舶y 之间的最短路径个数；Lxy( i )为船舶x 和船舶y 之间的最短路径中经过船舶i 的个数。

3） 紧密中心性。紧密中心性CCi根据节点与网络中其他所有节点的最短距离，可以判断该节点在网络中的位置。行为分析网络中船舶节点的紧密中心性越大，表明该船舶在行为分析网络中所处的位置越靠近中心位置，对网络结构演变的影响越大。节点度为ki的紧密中心性计算方式为

式中:lij为以节点i 为起点，节点j 为终点的最短路径所含边的数量；N 为网络的节点总数。

1.2.2 基于AHP的节点综合重要度评估

考虑不同指标从不同的角度体现节点在网络中的重要程度，本文引入基于AHP方法构造节点综合重要度评估模型进行节点综合重要度评估。节点度中心性相对于其他2个指标能较好的反映节点在网络中的重要程度，其次是介数中心性，最后是紧密中心性；结果见表1。

可得节点中心性指标的判断矩阵M 。

表1 各指标比较结果Tab. 1 Comparison of indicators

计算矩阵M 的最大特征根λmax所相应的特征向量ω ，并进行归一化处理，得该特征向量的权重向量W =[W1W2W3] =[0 .637 0.258 0.105] 。

为消除所选3个节点中心性指标之间的数量级差异，选取最大最小归一化方法进行处理，如对度中心性处理见式（9）。

同理，对其余指标采取相同的方法进行归一化处理，最终得到节点综合重要度评价结果Pi为Pi= 0.637Dc′i+ 0.258Bc′i+ 0.105Cc′i。

2 关键点识别流程

基于上述对行为分析网络的构建以及关键节点判断指标与识别方法的介绍，可以了解到通过节点综合重要度评价指标能够识别出水域内的关键船舶，具体识别流程见图4。

船舶行为分析网络关键节点即水上交通关键船舶识别主要分为以下3个步骤。

1） 数据获取。收集当前水域内所有船舶的航行数据，如船舶位置，航速，航向，等等。

图4 关键节点识别流程图Fig. 4 Flow chart of Key node identification

2） 行为分析网络构建。根据获取的船舶航行数据，结合船舶领域与船舶运动趋势判定船舶行为交互关系，确定节点间的连接关系与连边权重，构建行为分析网络。

3） 关键节点识别。通过结合节点度中心性、介数中心性以及紧密中心性所构建的节点综合重要度指标，对行为分析网络中的节点进行重要度评估，根据评估结果确定网络关键节点，进而识别水上交通关键船舶。

3 实验分析

针对上文介绍的关键节点识别方法，设置了仿真实验与实证分析，以验证上述方法是否能够有效识别区域水上交通关键船舶。

3.1 仿真实验

假设某一水域范围内分布着不同数目船舶（船舶数目设置为10，20，30，50），船舶位置分布服从正态分布，分析观察水域中不同船舶数目情况下相应船舶行为分析网络中关键节点的分布情况，分析网络节点数目对网络关键节点识别结果的影响。网络关键节点识别结果见图5,其中，黑色圆点为船舶节点，带有白色五角星图案为关键节点。

由图5可见，当网络节点数较小时，网络中节点的连接较为分散；随着节点数目的增加，节点之间的相互连接增多，逐渐形成复杂的网络，但网络也没有形成完全连接。同时可以发现，不论网络节点数目大小，网络中关键节点的位置基本上保持在网络的中心位置，网络中节点连接越复杂的位置，关键节点越多。当船舶数量发生变化时，行为分析网络的关键节点位置分布会发生变化；在船舶运动过程中，随着船舶位置的变化，船舶间的行为交互关系网络的关键节点也在不断变化，使得网络结构也随之发生变化，网络的关键节点分布也会发生变化。

图5 不同节点数的网络关键节点识别Fig. 5 Identification of network key nodes with different number of nodes

3.2 实证分析

为验证关键节点识别方法是否适用于实际场景，截取镇江大港水域中某一时间段内船舶航行过程来进行实验分析，实验开始时刻船舶航行状态图及所构成的行为分析网络见图6。结合图6（a），可知使用船舶mmsi作为节点标签时，容易出现行为分析网络中节点标签重叠的情况，因此对所采用的实验数据中出现的船舶进行重新编号，见图6（b）。

图6 船舶航行状态图与船舶行为分析网络图Fig. 6 Ship navigation status diagram and ship behavior analysis network diagram

表2 与表3 分别给出了船舶运动过程开始时刻与结束时刻下水域中所形成的行为分析网络中所有节点的度中心性、介数中心性和紧密中心性以及节点综合评价指标的评价结果。对比2个节点综合评价结果表，可以看出节点度中心性相较其他2 个节点中心性指标的评价结果更加稳定，能够反映出该指标在船舶行为分析网络中具有较好的评估效果。但节点度中心性指标主要考虑节点间的连接关系，同时也缺乏了对节点间连接的紧密程度以及节点在网络中的位置方面的考虑，因此还需要根据节点的综合评价指标对关键节点进行节点综合重要度的最终判断。

表2 开始时刻的节点综合重要度评价Tab. 2 Evaluation of the comprehensive importance of nodes at the star time

行为分析网络的关键船舶识别结果见图7，其中黑色圆点为船舶节点，黑色五角星节点为关键船舶。 从图7（a）中可以看出，节点7（mmsi 为413778336）的综合评价是所有节点评估结果中最高的，可以看到其周围船舶数量较多，所处的位置交通状态最为复杂，需要重点关注。同样，从图7（b）中可以看出节点综合评价指标最高的船舶节点28（mmsi为413882404）周围还分布着2个距其较近的网络关键节点，且该节点周围船舶较为聚集，对整个船舶行为分析网络中船舶的航行安全威胁较高。

本文选择将排名前5位的船舶节点识别为行为分析网络的关键节点。这些关键节点位置的船舶对水域中船舶航行安全的威胁程度较高。此外，可以将这些关键船舶作为重点监管对象，能够保证水上交通安全有序的进行。这些关键船舶往往位于船舶行为分析网络的核心部位，同时与其周围多艘船舶之间存在关联。所以交通监管人员需要对该位置的船舶进行重点关注。通过船舶行为分析网络的构建，避免了对水域内所有船舶进行重复判断，降低了交通监管人员或者船舶驾驶员进行水域内交通安全态势判断的复杂程度。特别是对关键船舶节点的识别，能够提供更精确的交通安全态势信息，协助监管人员和驾驶员针对不同的情况作出合理的行为响应。

表3 结束时刻的节点综合重要度评价Tab. 3 Evaluation of comprehensive importance of nodes at the end time

图7 不同时刻关键节点标识Fig. 7 Key node identification at different moments

将开始时刻下节点度中心性节点重要性评价结果与节点综合重要度评价结果进行对比分析，对比结果见表4。可以看出，2种方法的排序结果基本一致，仅个别节点的排序结果出现差异。根据上文以排序结果前5 的节点作为关键节点的假设，将排序结果每5个节点为1组进行对比，可以看出其中重要度等级排序结果出现较大差异的节点分别为6，11，12，31，产生该差异的原因主要是由于本文所采用的研究方法不仅考虑了节点的节点度，同时也考虑了节点在网络中所处的位置与其与网络中各节点间的连接关系，较为全面地考虑了节点在网络中的重要性。除去排序结果差异较大的节点，2种方法的分析结果中排序结果相同的节点数占节点总数的比例达到77.8%。对比出现差异的节点可以发现，通过节点综合重要度来识别关键船舶节点，比单纯使用节点度死别的方法考虑因素更多，更为全面的考虑了周围航行环境在船舶航行过程中的不同影响。例如，对比节点6与节点11，虽然二者节点度中心性指标相同，但由于节点6 在网络中所处的位置是网络中2 个社团（网络中节点之间相互连接较为紧密的小团体）中间，即处于连接2个社团的位置，故节点6在整个船舶行为分析网络中应承担着更为重要的网络连接功能。因此，节点6 的重要度等级应高于节点11的重要度等级。

而对比相同排序级别的节点，本文所采用的方法得出的结果更为细致，即根据节点综合重要度，可以在同一重要度等级中识别出更为关键的节点。综上，本文所采用方法得出的结果，相对而言能较全面地说明节点在行为分析网络中的重要性，且所得数据更为精确。

4 结束语

本文对区域水上交通关键船舶识别进行了研究，基于复杂网络分析和AHP方法分别建立了船舶行为分析网络和节点综合重要度评估方法，对网络中的节点进行节点重要度评估，找出网络中的关键节点。经过仿真实验与实证分析证明，该方法能够将综合节点性质指标识别网络的关键节点，并能够对船舶行为分析网络的关键船舶进行识别。同时对比分析结果验证，与单一节点度指标进行节点重要度评价相比，节点综合重要度综合考虑节点的各项指标，其评价结果更为全面。但研究并未考虑水域中其他因素对网络的影响，在后续的研究中可以考虑水域中其他因素对关键船舶识别的影响。

表4 开始时刻2 种分析结果比较Tab. 4 Comparison between two analytical results at the start time