基于Spark的PageRank算法优化及其军事应用研究

刘振宇，李钦富，曾 操,李 鹏

(1.西安电子科技大学，陕西 西安 710071；2.中国电子科技集团公司电子科学研究院，北京 100041)

0 引 言

在现代军事战争中，军事通信网络模型规模庞大且复杂多样，各种电子通信加密手段使得获取的通信信息有很大的虚假性和隐蔽性，同时各种新型作战模式使得重要作战目标很难被发现，所以从复杂的军事网络中找到核心的军事目标是本文的目的和初衷。军事通信网络也是一种网络模式，所以寻找重要目标的核心就是从军事网络图谱中寻找重要度较高的节点，而PageRank算法就是一种用于度量互联网络网页重要性的网络图谱节点重要度排名算法。2009年Sayyadi等人提出了FutureRank算法，考虑到了时间和已有PageRank值[1]，但是虚假消息对FutureRank的影响较大，预测排名相关度较低。刘大有等人提出了不需要当前PageRank值的权威网络，但是权威网络要求消息真实可靠，不适用于具有隐蔽消息的场景[2]。为了增强运算速率，刘记云等人提出了运用MapReduce进行PageRank值的计算[3]，但是MapReduce分布式并行计算本身不适合具有联系性的数据进行迭代运算。PageRank算法被广泛运用于社交、搜索引擎排名等方面[4]，虽然李政等人通过添加中心度来分析节点对于军事电子通信信息传播的影响[5]，但是只增强了通信站等通信中介的重要性，没有考虑通信节点在图谱中的真实性和可靠性。基于以上不足，本文提出了一种综合时间、目标位移、权威等因素，针对军事通信网络中虚假性和隐蔽性目标的改进加权的MilitaryRank算法。

1 军事通信网络及目标重要度评估

军事通信网络和互联网络一样，都可以表示为节点间的链接网络，包含了点与边之间的联系，由于军事目标的指挥层次和功能区分不尽相同，各种新型的分布式作战模式和网络战等作战方式层出不穷，所以节点在不同网络图谱中或同一网络图谱的不同位置具有不同重要性[5]，对敌方关键节点的打击具有重要意义，如何综合考虑时间、通信数量和权威性影响从而从军事通信网络中排除虚假节点的干扰找到核心节点，成为军事通信中的重要问题。

不同军事网络模型具有不同的拓扑结构，复杂的网络拓扑中存在着不同分工的节点，对关键节点的打击能有效的破坏通信网络[6]。PageRank值的引入可以体现出在电子通信系统中节点的重要性，要在作战时间内找出权威性最高的节点，同时由于敌方大量的通信的欺骗，所以我们给出几项假设进行验证：

(1)时间上越新的消息重要性越大，发出新消息的节点可能对战场的影响力越大。

(2)无论是新消息还是老消息，消息引起的军事目标的位置变化越大，那么这个消息就越重要，发出这个消息的节点的权威性就越高。

(3)通信目标在一定时间内并非发出消息越多就越重要，消息数量符合一定的幂率分布，不符合分布的数量过大消息的节点应予以限制。

(4)消息的内容无法获得，但可以知道消息的加密情况，加密度越高的消息那么重要性也随之增加。

(5)接收消息的单位，接收到的消息数量越少，位置变化快，那么这个单位的机动性就越高，威胁性也随之增高，更需要引起关注。

2 改进的PageRank重要军事目标排序算法

2.1 军事通信网络通信权威性

本文中引用链接网络中含有两类节点即通信单位节点以及通信消息节点，由于虚假通信的干扰，虚假信号源可能会发布大量的虚假信号来进行迷惑敌方，通信节点的权威不能通过发送消息的多少来表示，所以需要根据指挥单位发出的通信消息的结果来判断通信节点权威性，即根据接收单位接收到消息后的行为来判别发送方的权威性，虚假信号源的消息对接收单位的行为不会有影响，但是真正指挥者即便真假消息混合发送也会有一部分信息对接受方产生影响，此时虚假消息对发送方的权威性影响不大。我们定义权威矩阵之前需要先定义影响力。

(1)

(2)

(3)

(4)

由此我们可以定义出发送单位的权威性公式R=diag(Map×Mpa×Mad)和消息单位的权威公式R′=diag(Mpa×Mad)，为了防止出现某些点权威性过大，我们使用相对权威性，通信节点Pi和消息节点Pj的相对权威性分别是Ri/R和Rj/R′

2.2 军事通信时间权重

在军事通信中时间要素是一项很重要的要素，越靠近当前作战时间的消息就越有价值，越晚收到的消息在时间上就比之前收到的消息重要，因此给通信消息加上时间权重，使得时间越近的消息权重就越高。

w(Pi)=PRlast(Pi)*Ti

(6)

式(6)中

式(7)中ts是固定值，Tn是当前迭代次数。获得每个网页的时间反馈权值之后，针对同一个网页，我们可以计算出各个入链的相对时间反馈权值。

式(8)中O(Pj)是网页Pi的入链集合，将Wt加入到PageRank算法中，那么Pi的入链Pj会根据Pi的时间权重为Pi分配PR值，即如果Pi是Pj出度中时间较新的节点，Pj就会分配给Pi较大的时间权威值。这样就可以有效的提升新通信节点的PR值，同时可以在消息节点与通信节点共存的网络图谱中凸显出通信节点的重要性。

2.3 抑制虚假军事通信节点

军事通信网络图谱不同于传统互联网网页关系图谱，通信节点之间有各种业务规则，不同的通信节点等级有不同的通讯消息数量级别，越重要的部门通信量也就会越多，所以某些通讯节点数量过多或者过少都属于不正常情况，有可能是敌方的虚假通信干扰。参谋单位或者通信卫星汇集各个分指挥中心的数据，进行分析后进行上报，并根据上级决策，对各个分域进行指挥，属于信息量交换最大的地方。各分域指挥中心负责本分域的情报处理和下达，属于信息交换次大的地方。下属各个师到单兵，虽然分工和只能不同导致通信消息数量不一致，但是随着人员数量的减少，信息交换的数量也属于一个可变范围，最后单兵信息的上传和接收远远小于各个上级部门。综合以上信息，虽然现在部队已经不是完全按照“三三制”原则，并且部队编制较为复杂，但是大规模节点下整体符合幂率分布特点[7]。

为了避免敌方的通信欺骗，将通信量远远多于该等级正常幂律分布下通讯量的节点定义为通信欺骗点。我们需要先定义通信节点的消息量，由于树形拓扑结构是一种分级的集中控制结构，是典型的传统军事通信网络的拓扑结构，这种拓扑结构与一般的指挥控制关系相一致，因此广泛存在于现有的军事通信网络中[6]。根据军事通信网络的树形拓扑结构，找到某点的最长入度链长度，找到最小消息单位即单兵设为基准消息量，进行回归分析，求出回归曲线。

y=k-bx

(9)

再对偏离最大最小阈值的通信消息量进行回归分析，判断该节点的通信量是否符合回归方程，越不符合回归方程，给予该节点的权重越小。

式(10)中μ是回归曲线的计算值，x是将通信节点消息数量带入回归方程所得值，比回归曲线大过多或者小过多的点都定义为无价值点，所以加权中给予较小权重，由于某一级作战单位的通讯量应当在一定范围内，可以求出各个作战级别的正态分布曲线，根据实际通信量和该点理论通信量差给予一定的权重限制，从而排除了过大通信量节点的欺骗信号和过小通信量的无用信号。

2.4 通信节点行动力加权

若调整余弦相似度小于阈值,本文阈值设为0.5，则判断为正常目标进行下一步行动力加权计算：

式(13)中行动力d即一定时间内的通信节点的位置变化量或网络IP位置变化，dmax是战场作战范围。

2.5 军事通信节点的重要程度

综合权威向量，时间权重，数量影响及行动力变化多方面考虑的MilitaryRank公式为：

适用于军事电子通信的PageRank优化算法，当观察者查看一个消息时，会根据出链节点的时间反馈值、通信量反馈值以及行动力变化，综合通信节点和消息节点的相对权威性来决定查看下一个通信单位。因此能有效避免某些虚假通信节点的干扰以及更大几率的找到通信较少但影响较大的隐蔽节点。

3 仿真试验分析

3.1 试验条件

3.1.1 试验环境及重要参数

本试验的环境：(1)大数据平台环境：三节点大数据平台CDH2.4，单节点256G内存，linux，CentOS7

(2)单机环境：单核，2G内存 ，Linux， CentOS7

试验参数：加权PageRank公式阻尼系数0.85，抑制虚假节点的线性回归曲线分析b=-1.9，k=6.4，迭代终止条件e=0.01，每个节点的初始PageRank值设为1。

图1 幂率分布的线性回归分析

3.1.2 仿真目标关系图谱

我们选用了社区发现中常用的LFR-benchmark仿真网络数据集按照幂律分布进行网络生成，并在网络中相连节点间添加消息节点，根据消息节点所在的社区在一定范围内随机生成时间和位置数据，同时根据已知网络模拟出军事通信网络节点名称形成仿真数据。图2为构造的军事通信网络图谱：

阀板开关柄设计：采用1m长的角钢（规格为40＊40＊5）作为阀板开关柄，开关柄与阀板主板通过焊接连在一起，在开关柄末端进行开孔，孔径为20mm，末端孔通过绑定尼龙绳并引至沉箱顶预留钢筋处。在沉箱进水控制时，只需要操作人员站在沉箱顶拉紧或放松尼龙绳，即可进行沉箱进水控制。

图2 LFR仿真网络通信节点图谱

3.2 试验流程

实验流程如图3所示：

图3 基于Hadoop平台的军事Military PageRank算法总体框架

(1)初始化阶段用LFR-benchmark方法构造仿真网络社区，并根据社区数据向网络中添加消息节点并随机生成时间等特征信息。

(2)军事网络节点重要度排序Military PageRank阶段首先初始化转移概率矩阵并设置PageRank初值和迭代终止值。然后根据每个节点周围节点的时间和位置等特征进行军事网络加权的PageRank计算，计算得出新的PageRank值。最后与原先的PageRank值进行比较判断收敛并输出结果。

(3)数据可视化阶段将排序后的重要节点信息添加到图数据库中并进行可视化展现。

3.3 时间复杂度分析

军事通信中往往需要从大量的通信节点中找出关键目标，现代战争中电子通信复杂，各种干扰和隐蔽信号繁多，因此构成包含通讯单位和消息在内的超大规模图谱，传统的计算方式不能高效快速的分析出结果。我们使用大数据组件HDFS、Hbase进行数据存储，Spark进行调用数据计算，运用图数据库Neo4j进行部分可视化，Spark是基于内存的编程模型，它可以把中间的迭代过程不放在磁盘中，直接数据不落地在内存中执行，极大的提高了它的执行速度。试验中上万节点数据以及千万条边数据在单机环境下需要分钟级运行时间，在大数据平台环境下只需要秒级运算时间，符合军事上实时性的要求。

在迭代计算中，相比于传统MapReduce方式每次迭代都要与HDFS进行一次交换而言，Spark运用DAG编程模型将多个MapReduce简化为一个Spark作业。随后将作业切分成多个Stage并通过Shuffle进行数据传递，中间数据以RDD(Resilient Distributed Dataset)形式分布式存储在slave节点中，与HDFS之间只需要一次读写操作，运行时间节约60%以上。在不同数量节点下的PageRank运算时间如图4。

图4 相同节点下运算时间比较

3.4 目标重要度排名结果

针对军事领域电子通信的特殊性，将军事通信优化的PageRank算法结果与传统PageRank算法和进行比较，针对军事电子通信的虚假性和隐蔽性特点，不断修改时间、通信量和行动力的比重值，提高挖掘军事通信重要节点的准确率。最终从复杂网络图谱中求出不同权重下对隐蔽目标查找，虚假目标排除，以及重要信息节点排序的不同结果。

3.4.1 隐蔽目标查找

将传统的Pagerank算法与加权改进后(a=0.3,b=0.1,c=0.6)的Pagerank算法进行结果进行比对：

表1 传统PageRank算法结果

表2 隐蔽目标PR值查找结果

图5 隐蔽点的目标关系网络

从图5可以看出隐蔽目标的关系网络相较整个网络来说并不复杂，但是由于关系网络较为简单，出入度相对较少，所以传统PageRank方法获得的PR值会很低，经过对隐蔽目标加权迭代后隐蔽目标的MilitaryRank值会升高，从而发现隐蔽性高的机动目标，但同时会降低固定位置或固定IP位置单位的排名。

3.4.2 虚假目标抑制

从图5可以看出虚假目标的发送网络相对复杂，接收网络与真实信号源也有很大重叠，普通的PageRank方法无法分辨他的真实性，但是经过虚假目标抑制的迭代之后，能明显将其重要性降低。

表3 原始PageRank算法结果

表4 虚假目标排除结果

图6 虚假目标发送网络

3.4.3 重要链路排序

重要链路排序获取迭代结果中标签为消息的所有节点，并对其进行MilitaryRank排序，可以获得较为重要的消息节点，该消息节点处于的位置就是关键链路，可以通过对关键链路的打击来割裂目标集群之间的联系或者对己方关键军事链路进行保护。

表5 部分消息节点排序结果

3.5 结果分析

从试验中可以看出隐蔽目标的关系网络相较干扰点来说并不复杂，但是由于关系网络较为简单，出入度相对较少，所以传统PageRank方法获得的PR值会很低，经过对隐蔽目标加权的MilitaryRank算法使隐蔽目标的排名升高，从而发现隐蔽性高的机动目标，但同时会降低固定位置或固定IP位置单位的排名。同时由于虚假目标的发送网络十分复杂，接收网络与真实信号源也有很大重叠，普通的PageRank方法无法分辨该类目标的真实性，但是经过虚假目标抑制的迭代之后，能明显将其重要性降低。从排序后的结果中选中标签为消息类型的节点，并对其进行统计，可以获得较为重要的消息节点，说明该消息节点处于的位置是关键的消息链路，从而通过对关键链路的打击来割裂目标集群之间的联系或者对己方关键军事链路进行保护。

4 结 语

本文从军事目标网络的各项问题出发，在Pagerank算法的基础上对军事网络目标的重要程度进行了研究，将时间、空间/IP位置、目标权威性与加权Pagerank算法结合，提出了适合军事目标网络的的网络目标重要度评估算法。仿真结果表明，相比经典的Pagerank算法，该算法能从网络目标关系图谱中更好的找到隐蔽点和排出虚假点的影响，同时能合理的分析不同消息链路的重要程度。但是由于本方法的Pagerank值是由各方面加权迭代计算获得的，所以各部分的权重很难平衡，同时也不具备动态变化的功能。而且真正的军事目标位置复杂多变，并非能完全获得目标的位置变化，所以在未来的工作中将考虑如何在节点信息不全的情况下进行计算并且动态的调整构成Pagerank值的各项权重比例。