基于图神经网络的机会网络节点重要度评估方法

刘琳岚 谭镇阳 舒 坚

1(南昌航空大学信息工程学院 南昌 330063)

2(南昌航空大学软件学院 南昌 330063)

(liulinlan@nchu.edu.cn)

机会网络(opportunistic network, ON)[1]是一种不需要通信双方的节点之间存在完整链路,利用节点移动带来的间歇性连通机会实现通信的自组织动态网络.机会网络的部分概念源于早期的延迟容忍网络(delay tolerant network, DTN)研究,其主要的目标之一就是为了支持那些具有间歇性的连通、延时量大、错误率较高等特点的异构网络之间的互联与相关,如车载自组织网、移动数据分流、信息分享、移动计算等.机会网络拓展了网络通信的使用范围,将成为未来泛在通信的重要组成部分[2].

机会网络利用机会式的通信方式实现智能设备间的内容、资源和服务的共享.正是这种机会式的通信方式导致了机会网络具有明显的动态性与时变性.因此,如何选择最理想的转发目标以及最理想的转发时机成为机会网络中数据传输机制关注的核心问题[3].对节点重要度的评估能够辅助上层路由协议选取最佳转发目标,从而提高整网的消息投递率.

一个具有多个移动节点的机会网络中,源节点A向目标节点B传递消息的过程如图1所示.由于机会网络节点间通信的频繁连接和断开,且移动节点的电池能量、内存等资源相对受限,为了使源节点A的时效性消息能够有效地投递至目标节点B,应选择重要度(即消息传播能力)高的节点作为转发目标,从而提高消息的投递成功率.

针对机会网络中通信节点位置的不确定性以及节点对连接的周期性导致其网络结构随时间频繁变化的特点,本文采用动态网络嵌入方法将随时间变化的动态网络拓扑信息压缩到特征空间中,以获取网络动态属性特征,利用图神经网络(graph neural network, GNN)建立网络动态属性特征与节点重要度的映射关系,实现对节点重要度的评估.本文的主要贡献有3个方面：

1) 利用节点间的交互信息,通过聚合图模型对机会网络进行建模.针对机会网络动态性与时变性的特点,将时序上连续的机会网络按照时间片切分为离散的机会网络单元,在机会网络单元上建立聚合图模型,确定图模型中连边的权重以构建网络属性矩阵,表征机会网络的拓扑结构信息.

2) 提出一种适用于机会网络的动态网络嵌入方法.采用类增量学习的方式,根据输入的网络属性矩阵生成节点的嵌入表示.提取机会网络的拓扑结构信息与时序变化信息,将其压缩表示为由节点动态属性嵌入向量组成的网络动态属性特征矩阵.

3) 提出基于图神经网络的机会网络节点重要度评估模型.通过节点之间相互关系对节点动态属性嵌入向量进行更新,实现节点邻域信息的融合,建立节点动态属性嵌入向量与节点重要度之间的映射关系,评估机会网络节点的重要度.

1 相关研究

近年来,评估节点重要度的方法可分为3类:基于局部指标的评估、基于全局指标的评估和基于混合指标的评估.

1.1 基于局部结构的评估方法

网络的拓扑结构在很大程度上能够决定一个节点在网络中的重要度.因此,依据网络的拓扑结构设计节点的重要度排序指标,是一类对网络节点重要度进行评估的重要方法.节点的重要度也称为“中心性”,即网络中节点的重要程度取决于该节点与其他节点的连接使其具有的显著性[4].度中心性[4](degree centrality, DC)的基本思想可描述为网络中节点的邻居数量决定其节点本身的影响力大小.文献[5]采用路径流的方式对时序网络建模,提出时序度中心性,将静态网络中的度中心性指标拓展到时序网络,考虑了节点度随时间变化的波动,能够有效评估动态网络中的节点重要度.为进一步提高节点重要度评估的准确性,Ren等人[4]提出一种利用节点在网络中半局部信息的节点重要度评估指标,简称半局部中心性(semi-local centrality, SLC),该指标通过计算网络中节点的2层邻居数量来表征节点的重要度,在损耗较少计算时间的前提下得到了较好的评估效果.度中心性与半局部中心性利用节点在网络拓扑中的领域信息对节点的重要度进行评估,认为邻域内节点数目相同的节点其重要程度也相同.

1.2 基于全局结构的评估方法

在现实世界中的诸多网络中,存在着一些邻居数目很少但重要程度却不容小觑的节点,这类节点的重要性往往不能采用传统的局部结构评估方法度量.因此,基于全局结构的评估方法应运而生.接近中心性(closeness centrality, CC)[4]指标通过计算节点与网络中其他所有节点的平均距离来衡量该节点在网络全局结构上的影响力,从而消除特殊位置对的节点重要度评估的干扰.

Katz中心性[4]指标在接近中心性的基础上进行改进,不仅考虑了节点对之间的最短路径,还考虑了它们之间的其他非最短路径.介数中心性(between-ness centrality, BC)[4]刻画了节点对在网络中沿最短路径传输的网络流的控制力.文献[6]基于静态网络中的CC以及BC,提出了时效介数(temporal betweenness, TB)中心性指标评估时效网络中节点重要程度,TB不仅考虑了经过节点的最短路径的数目,还考虑了最短路径上节点对于消息的保持时间,从而综合计算得到时序介数中心性的值,对节点重要度进行评估.

针对局部性指标仅仅只考察节点的局部特性而忽略节点在网络中位置的问题,Kitsak等人[7]提出k-壳分解法(k-shell decomposition),该方法首先利用节点位于网络中的位置,将外层节点层层剥去,认为处于内层的节点其重要程度也越高.针对k-壳粒度粗的问题,学者们提出了一系列关于k-壳分解法的改进方法,如将节点进行预分类的层次k-壳分解法(hierarchicalk-shell decomposition)[8]、使用迭代因子进一步细化分解粒度的迭代因子k-壳分解法(k-shell iteration factor)[9]等.基于全局结构的评估方法能够考虑网络的结构信息,对网络中的节点重要性评判更加准确,但基于全局结构的方法时间复杂度较高,在大型网络和动态网络中的应用受到限制.

1.3 基于混合结构的评估方法

研究人员结合前2类指标的优点提出了基于混合指标的节点重要度评估方法.Zareie等人[10]结合节点的邻居信息、影响力范围以及范围内的影响力强度提出了多样性强度中心性(diversity strength centrality, DSC)指标对节点的重要度做出评估.文献[11]综合考虑节点的拓扑结构、动力学特征,采用时序游走得到节点的路径信息,并定义了传播中心性和接收沟通性指标.文献[12]对传统的h-index指标进行改进,考虑了传统h-index未考虑的全局性信息,提出了扩展的h-index(extended h-index, EH)指标.文献[13]提出一种快速的混合指标评估方法,通过计算网络中节点的简单指标(DC、聚类系数、k-shell)与复杂指标(CC、BC、网络效率)构建知识库,利用层次分析法将复杂指标进行融合得到重要度指标,再通过最小二乘支持向量机找到简单指标与重要度指标的映射关系.文献[14]采用4种传统的中心性指标对多层网络中不同网络层节点的中心性和权威性进行量化,得到一个4维张量,通过张量计算将网络中所有节点和层的信息结合起来,得到张量奇异向量中心性指标评估多层网络中节点的重要性.

近年来,研究人员从数据挖掘的角度,利用机器学习算法对网络中的节点重要度进行评估.文献[15]利用网络嵌入技术提取电力网络的网络信息,结合节点本身的属性信息,利用支持向量回归机对电力网络的节点重要度进行评估.

上述研究为解决机会网络节点重要度评估问题提供了丰富的思路和解决方案,但多数方法是针对拓扑结构变化缓慢的社交网络所设计[16-21],无法直接应用于机会网络.本文针对机会网络的动态性与时变性特点,对机会网络进行切片处理,将切片后的网络快照表示为机会网络单元,通过对机会网络单元建立图模型,确定图模型中节点间连边的权值构建网络属性矩阵,表征网络拓扑信息;采用基于自编码器结构的动态网络嵌入方法,将网络属性矩阵作为输入,从网络的时序变化信息以及拓扑结构信息2个方面获取机会网络的网络动态属性特征;引入图神经网络构建节点重要度评估模型,实现节点间邻域信息的融合,从而建立网络动态属性特征与节点重要度的映射关系,对机会网络节点的重要度进行评估.

2 网络拓扑信息的表征

本文将连续的机会网络数据按照时间切片划分为离散的机会网络单元,建立机会网络单元对应的图模型以构建机会网络单元的带权邻接矩阵(本文称网络属性矩阵),将多个网络属性矩阵组成的张量作为动态网络嵌入模型的输入,以进一步提取网络信息.

2.1 机会网络数据的转化

本文主要研究机会网络中的便携设备交换网络(pocket switched network, PSN),其数据集的数据格式如图2所示：

Fig. 1 Schematic diagram of opportunistic network communication图1 机会网络通信示意图

Fig. 2 Data format图2 数据格式

Fig. 3 Evolution process of opportunistic network topology图3 机会网络拓扑的演化过程

Fig. 4 The effective records in each opportunistic network unit of MIT under different slice time length图4 不同切片时长下MIT各机会网络单元内有效记录

Fig. 5 The effective records in each opportunistic network unit of Haggle under different slice time length图5 不同切片时长下Haggle各机会网络单元内有效记录

Fig. 6 The effective records in each opportunistic network unit of Asturias-er under different slice time length图6 不同切片时长下Asturias-er各机会网络单元内有效记录

Fig. 8 Node importance evaluation model based on GNN图8 基于GNN的节点重要度评估模型

Fig. 9 Influence of Δt on NDCG@10 of MIT图9 MIT数据集上Δt对NDCG@10的影响

Fig. 10 Influence of Δt on NDCG@10 of Haggle图10 Haggle数据集上Δt对NDCG@10的影响

Fig. 11 Influence of Δt on NDCG@10 of Asturias-er图11 Asturias-er数据集上Δt对NDCG@10的影响

Fig. 12 Comparison of network message propagation rate图12 网络消息传播速率对比

Fig. 13 Comparison of network message coverage图13 网络消息覆盖范围对比

Fig. 14 Comparison of different methods top1～5 under MIT图14 MIT下不同方法top1～5对比

Fig. 15 Comparison of different methods top1～5 under Haggle图15 Haggle下不同方法top1～5对比

Fig. 16 Comparison of different methods top1～5 under Asturias-er图16 Asturias-er下不同方法top1～5对比

利用原始数据中节点对的连接情况,计算节点对之间的连接持续时长以及连接次数.具体地,节点对[1,3]在第1秒连接类型为“up”,在第3秒的连接类型为“down”,则连接时长为3-1=2 s,节点对[1,3]在整个原始数据中的up,down状态成对存在的次数为12次,则节点对[1,3]的连接次数为12次.

2.2 机会网络单元的切分

根据机会网络的动态性与时变性,将连续的原始数据集按照时间片切分为离散的机会网络单元.原始的机会网络表示为G,按照时间片进行切分可将连续的机会网络表示为由一系列机会网络单元组成的有序集合G={G1,G2,…,GN}.其中,N=T/Δt为机会网络单元的数量,T为整个机会网络数据集持续时长,Δt为机会网络单元切片时长,G1表示初始机会网络单元,G2表示间隔一个切片时长的机会网络单元,依此类推,GN为最后一个机会网络单元,以MIT数据集为例,将其网络拓扑结构可视化后,其演化过程如图3所示.对机会网络单元建立对应的聚合图模型,使用Gt={Vt,Et,Wt}表示第t(t=1,2,…,N)个机会网络单元的聚合图,Vt表示在第t个机会网络单元上的节点集合,Et表示在第t个机会网络单元上边的集合,Wt表示第t个机会网络单元上对应边上的权值的集合.

机会网络单元切片时长Δt的长短直接关系到网络拓扑信息的表征能力.针对该问题,文献[22]对具有代表性的机会网络数据集进行统计分析,从机会网络的持续性与周期性2个角度,提出了基于邻接相关系数、聚类系数和节点平均度确定切片时长的方法.借鉴该方法,一方面考虑到切片时长Δt太短导致机会网络单元拓扑图过于稀疏,无法准确描述机会网络中节点间的连接情况,另一方面考虑切片时长Δt太长导致机会网络单元内拓扑图过于密集、节点间连接频繁,导致无法准确区分节点重要度的情况.本文对所使用的3个数据集按照不同切片时长进行切片得到机会网络单元,分别统计每个机会网络单元内有效记录的次数,其结果如图4～6所示.

按照Δt∈{0.5 d,1 d,10 d,30 d}对MIT数据集进行切片,分别统计每个机会网络单元内的有效记录情况.由图4可知,当Δt=0.5 d和Δt=1 d时,有效记录次数呈现明显的波动性,大多数机会网络单元内的有效记录次数非常少,导致网络拓扑结构过于稀疏,节点大多处于未连接状态,因此无法获取有效的拓扑信息.当Δt=30 d时,有效记录次数均大于20 000条,大部分节点间都发生频繁的连接,导致网络拓扑过于密集,无法通过拓扑结构信息区分节点的重要度.因此,采用Δt=10 d作为MIT数据集的候选切片时长,通过实验确定最终切片时长.

按照Δt∈{0.5 h,1 h,4 h,8 h}对Haggle数据集进行切分统计各机会网络单元内的有效记录情况.由图5可知,当切片时长Δt=0.5 h与Δt=1 h时,有效记录数呈明显的波动性,且大多数机会网络单元内不存在有效的连接,导致机会网络单元形成的网络拓扑中绝大部分节点处于孤立状态,网络拓扑极为稀疏,无法通过网络的拓扑连接情况对节点的重要度进行评估.当切片时长为Δt=8 h时,有效连接数量的均值大于25 000条,大部分节点频繁连接,导致网络拓扑过于密集,无法通过拓扑结构信息对不同节点的重要度做出评估.因此,将有效记录数量过于稀疏或密集的时间切片长度剔除,采用Δt=4 h作为Haggle的候选切片时长,通过实验确定最终切片时长.

按照Δt∈{6 h,24 h,48 h,96 h}对Asturias-er数据集进行切片,分别统计每个机会网络单元内的有效记录情况.由图6可知,当Δt=6 h和Δt=24 h时,得到的有效记录次数呈现明显的波动性,机会网络单元内大多数机会网络单元网络拓扑结构过于稀疏,节点大多属于未连接状态,因此无法获取有效的拓扑信息.当Δt=96 h,机会网络单元内的有效记录次数均大于60 000条,节点间连接频繁,无法通过拓扑结构信息区分节点的重要度.因此,采用Δt=48 h作为Asturias-er数据集的候选切片时长,通过实验确定最终切片时长.

2.3 网络属性矩阵的构建

按照切片时长将连续的机会网络切分为离散的机会网络单元并建立相应的图模型.考虑到机会网络中的通信是以人携带智能手机、蓝牙通信设备进行数据交换,人具有社会性,相互通信的持续时长的频繁程度取决于通信双方的亲密程度.因此,为了准确描述机会网络中节点间的关系,本文采用节点间的连接次数以及连接持续时长表征节点间连边的权重.具体地,在机会网络单元Gt=(Vt,Et,Wt)中边的权值Wt可表示为该机会网络单元内存在连接的节点间的连接次数与连接持续时长之积

(1)

依据机会网络单元的拓扑状态来构建相应的带权邻接矩阵(本文称为网络属性矩阵)为

(2)

3 节点重要度评估

本文以网络属性矩阵作为动态网络嵌入模型的输入,利用动态网络嵌入方法将机会网络单元之间的时序变化信息以及拓扑结构信息压缩到特征空间中以获取网络动态属性特征,并以节点动态属性特征向量的形式表示.之后,利用图神经网络构建节点重要度评估模型,建立节点动态属性特征与节点重要度的映射关系,从而对节点重要度进行评估.

3.1 动态网络嵌入模型的构建

本文采用基于自编码器的动态网络嵌入模型提取网络动态属性特征.本节在介绍模型结构的基础上,从时序信息的提取和拓扑结构信息的提取阐述模型的实现.

3.1.1 模型结构

自编码器模型可以通过一系列非线性映射操作将网络的原始特征映射到一个低维的特征空间中。模型的目的是尽可能地使得原始特征和重构特征保持相似性,从而达到在降维和嵌入过程中降低网络信息的损失.基于此,本文采用基于自编码器的动态网络嵌入模型提取网络动态属性特征.将机会网络对应的多个网络属性矩阵作为输入,每个网络属性矩阵都要经过一系列的解码和编码操作,同时为了提取机会网络的时序变化信息以及拓扑结构信息,增加了编码阶段对原始特征整合的隐藏层和解码阶段对嵌入特征分解的隐藏层,最终得到由节点动态属性嵌入向量组成的网络动态属性嵌入矩阵作为模型的输出.动态网络嵌入模型的结构如图7所示.

模型包括编码与解码2部分：1)编码部分的作用是将原始特征向量映射到嵌入空间中;2)解码部分恢复嵌入向量到重构空间中.

在编码部分,xi代表节点的原始特征,即机会网络单元中节点i的属性向量mi,yi为编码器部分隐藏层的潜在特征,在嵌入空间中的编码结果表示为hi∈F(F为节点嵌入维数),这些变量之间的关系为

(3)

(4)

(5)

在解码部分,输入为动态属性嵌入向量hi∈F,输出为重构向量表示隐藏层的潜在特征,这些变量间的关系为

(6)

(7)

(8)

最终,将机会网络对应的多个网络属性矩阵M=(M1,M2,…,MN)作为自编码器输入,经过若干层的编码和解码操作,得到由节点动态属性嵌入向量组成的网络动态属性嵌入矩阵H=(h1,h2,…,hn)∈n×F作为模型的输出.

3.1.2 时序变化信息的提取

为了提取整个时序序列上机会网络单元间的时序变化信息,采用类增量学习式的策略,在训练的过程中充分利用历史的训练结果.让时刻τ网络单元对应的嵌入模型继承时刻τ-1网络单元训练好的参数,对第t个机会网络单元的网络信息进行迭代训练,得到新的模型参数θt.进一步地,在经过有限个该过程的迭代实现整个时序序列上时序信息的提取.采用该策略：其一加快了整个动态网络嵌入模型的训练收敛速度,使之更贴合机会网络的时变特性；其二确保最终得到的节点动态嵌入矩阵H=(h1,h2,…,hn)能够有效表征整个时序序列上网络的时序变化信息.

3.1.3 拓扑结构信息的提取

为了使节点动态属性嵌入向量更准确地表征网络拓扑结构信息,构建相应的损失函数.通过不断最小化机会网络中节点的属性向量与重构向量之间的编码损失,使得节点动态嵌入向量能够从局部结构以及全局结构上表征节点在网络中的拓扑信息.

(9)

(10)

加入L1正则项,辅助模型产生稀疏矩阵,得到:

(11)

得到模型的损失函数为

L=Lglob+αLloc+βL1.

(12)

3.2 节点重要度评估模型的构建

利用GNN对图数据强大的特征自动化提取能力,避免传统方法人工构建网络中节点重要度特征.通过动态网络嵌入模型得到的节点动态属性嵌入向量组成的网络动态属性特征矩阵作为重要度评估模型的输入,以构建节点动态属性嵌入向量与节点重要度之间的映射关系.节点重要度评估模型如图8所示：

3.2.1 图神经网络的确定

考虑到机会网络相邻节点间的重要度存在相互影响的情况,且节点间通信次数与通信时长会直接影响到节点间重要度的传递.为了有效地提取节点间重要度的相互影响关系,构建图神经网络将节点的动态属性嵌入向量按照节点间关系进行加权聚合,实现节点间邻域信息的融合.文献[24]提出了一种基于图数据的自注意力方法实现了一种根据节点间的关联关系对相邻节点进行卷积操作的图注意力网络(graph attention network, GAT).引入该方法中所提出的GAT构建节点重要度评估模型.

3.2.2 注意力因子的构造

根据文献[24]所提出的图注意力网络,首先将节点动态属性嵌入矩阵H=(h1,h2,…,hn)作为图注意力网络的输入,其中,hi∈F,n为节点总数,F为节点动态属性嵌入向量的维数.使用F′表示经过图注意力网络的输出,F′为更新后的节点动态属性嵌入向量维数.对于节点动态属性嵌入向量hi,首先通过一个节点共享的特征转换矩阵W∈F×F′进行线性变换,再通过注意力机制a∈2F′计算节点间的注意力系数,此后通过softmax函数对节点与其邻居的注意力系数进行归一化操作得到节点间的注意力因子,最后利用注意力因子对节点的动态属性嵌入向量进行加权求和,得到融合了领域信息的新的节点动态属性嵌入矩阵具体地,相邻节点对(i,j)之间的注意力系数为

eij=a(Whi,Whj),

(13)

其中,a为单层前馈神经网络实现的注意力函数,通过a计算相邻节点间的注意力系数eij,该系数表征了节点j与节点i的动态属性嵌入向量之间关联关系.

进一步地,为了方便计算节点i与其邻居节点之间的注意力系数,利用softmax函数对其进行归一化,得到相邻节点对(i,j)之间的注意力因子:

(14)

其中,Ni表示节点i的邻居节点集合,即机会网络中与节点i存在通信关系的节点集合.通过αij计算节点对(i,j)的动态属性嵌入向量的线性组合,从而对节点i的动态属性嵌入向量进行更新:

(15)

为了提高模型的性能,引入多头注意力机制:

(16)

本文实验采用LeakyReLU(leak系数设置为0.01)作为注意力机制的非线性激活函数.根据文献[24],多头注意力机制的头数设置为4.

3.2.3 损失函数

构建基于均方误差(mean squared error, MSE)的监督损失函数：

(17)

其中,N为样本总数,sn为节点n通过模型得到节点重要度分数评估值,gn为节点n的重要度分数真实值.MSE越小,模型的评估值与真实值的差异越小,对节点重要度评估越准确.

4 实验结果及分析

4.1 实验数据

本文实验在CRAWDAD[25]提供的稀疏型机会网络、密集型机会网络以及大型机会网络的真实数据集上进行.3个数据集的主要信息如表1所示：

Table 1 Trace Data Information表1 Trace数据信息

1) MIT reality数据集.记录了100个携带Nokia 6600手机的用户自2004-10—2005-05共246 d,利用蓝牙接口相遇的数据(300 s采集1次).

2) Haggle项目数据集.收集了Infocom2006年会98位参会人员3 d携带蓝牙接口相遇的数据(120 s采集1次).

3) Asturias-er数据集.记录了229台车载无线通信设备或GPS设备在2011-10—2012-10期间生成的数据(30 s采集1次).

本文采用Pycharm对机会网络数据集进行分析、处理,将其转化为网络属性矩阵.采用Keras框架作为动态网络嵌入模型以及节点重要度评估模型的训练工具.利用Python图形库Matplotlib对实验数据以及实验结果进行可视化.采用Gephi网络分析工具对机会网络数据集进行统计分析与可视化.

4.2 评价方法

采用SI(susceptible infected)，SIR(susceptible infected recovered)传播模型评价和比较本文所提出的节点重要度评估方法;采用NDCG@10(nor-malized discounted cumulative gain)对节点重要度排序列表的质量进行评价.

1) 基于传播模型的评价

通常认为,机会网络这类以消息传递为主的网络中,节点的重要度体现于节点在网络中对消息的传播能力[26].因此采用基于信息传播模型的评价方法对节点在网络中信息传递的重要度进行评价.利用SI与SIR感染模型[26]中网络感染节点总数来衡量节点的重要度,SI感染模型将网络中的节点分为2种状态,分别为易感染态和感染态,其中易感染态表示节点还未被感染疾病,但由于节点间的接触会被其他节点感染,感染态表示已经感染疾病的节点,易感态节点在被感染节点感染后无法被恢复.SIR模型则多出一种状态为免疫态,感染节点以恢复率恢复为免疫态.假设初始时刻t0将总节点数为n的未感染网络中i0个节点设置为感染源,剩余n-i个节点为未感染节点,感染概率为p.那么在时刻i感染节点总数为

(18)

具体地,在实验中,通过本文方法得到所有节点的重要度,并按照重要度大小对节点进行排序,得到排序列表中重要度排名靠前的节点作为传播模型的感染源,利用SI和SIR感染模型比较在同一时间内感染节点的数量.采用SI模型评价本文方法的合理性,采用SIR比较本文方法和其他方法.

2) 基于相关性的评价

归一化折扣累计增益(normalized discounted cumulative gain,NDCG)常用于评价排序列表的质量.该指标的取值范围为[0,1],值越大,说明给定的排序列表与理想排序列表越接近,即说明节点重要度评估方法越优.给定一个按照节点重要度分数的排序列表,排序列表中排名前k位的折扣累计增益为

(19)

其中,ri为排序列表中位于第i位节点的重要度分数,考虑到理想排序列表(即按照节点真实重要度分数得到的排序列表)中前k位的理想折扣累计增益(IDCG@k),进行归一化操作得到归一化折扣累计增益为

(20)

4.3 实验参数设置

实验参数设置包括机会网络单元切片时长Δt的设置和动态网络嵌入模型中超参数的设置.

1) 机会网络单元切片时长Δt

考虑机会网络数据集持续性与周期性[27],确定MIT，Haggle，Asturias-er的候选切片时长分别为10 d,4 h,48 h.以候选切片时长为基准，按照Δt∈{8 d,9 d,10 d,11 d,12 d},在MIT数据集上,根据Δt对排序质量NDCG@10的影响,最终确定切片时长，实验结果如图9所示.其中Δt=11 d时NDCG@10取值最优.因此,本文选取机会网络单元切片时长Δt=11 d作为MIT的切片时长.

以候选切片时长Δt=2 h为基准,按照Δt∈{2 h,3 h,4 h,5 h,6 h},在Haggle数据集上,根据Δt对排序质量NDCG@10的影响,最终确定切片时长.实验结果如图10所示.其中Δt=3 h时NDCG@10取值最优.因此,本文选取Δt=3 h作为Haggle的切片时长.

以候选切片时长Δt=48 h为基准,按照Δt∈{36 h,42 h,48 h,54 h,60 h},在Asturias-er数据集上,根据Δt对排序质量NDCG@10的影响,最终确定切片时长.实验结果如图11所示.其中Δt=48 h时NDCG@10取值最优.因此,本文选取Δt=48 h为Asturias-er的切片时长.

2) 动态网络嵌入模型的超参数

在基于自编码器的动态网络嵌入模型中,超参数的具体配置为:网络嵌入的最佳网络嵌入维数与网络的规模和密度相关[27],考虑到所选机会网络数据集的规模(节点数目均小于300)以及机会网络的稀疏性(网络密度较小),将MIT，Haggle，Asturias-er的网络嵌入维数设置为F=32；考虑到网络中节点的全局结构相较于局部结构更能反映节点在网络中的重要程度[28]且正则项主要是辅助模型的训练,故设置式(12)中的α=10-5,β=10-4.采用Adam学习算法对自编码器进行训练,迭代次数设置为200,编码器与解码器隐藏层数量均为4,每层的神经元数量分别为n,84,64,32(n为网络节点数量),学习率参数设置为0.001.

4.4 实验结果

实验分为2个部分：1)通过信息传播模型评价节点在机会网络中的消息传播能力;2)通过相关性分析,利用NDCG@10衡量本文方法与其他方法所得到的节点重要度排序列表的质量.

1) 节点在机会网络中的消息传播能力

机会网络中节点的核心任务是消息的投递,网络中不同个体的社会属性决定了其在网络中对于消息的传播能力,而在网络中节点对消息的传播能力可分为对消息的传播速率和覆盖范围.本文提出的机会网络节点重要度评估方法,目的是找到并利用消息传播能力较高的节点以提高整个网络的消息传播效率.因此,本文通过实验1验证节点重要度高的节点对于消息的传播速率影响,通过实验2验证节点重要度高的节点对于消息覆盖范围的影响.

实验1.采用SI传播模型考察本文方法得到的节点重要度列表中排名不同的节点的消息传播速率,进而说明本文方法的有效性.为了直观地展示网络中不同节点的消息传播速率,选取节点重要度排序列表中间隔相同的5个节点分别单独作为消息源对比其消息传播速率.若排名靠前的节点在消息的传播速率(即图12中曲线下的覆盖面积)上要高于排名靠后的节点,则说明重要度高的节点能够更快地使消息传播到更多的节点上,进而验证本文方法对节点重要度的评估是有效的.具体地,根据经验值设定SI传播模型的传播概率,观察消息的传播速率.图12(a)为MIT数据集下,选取节点重要度排序列表中第1(即top节点)、第25、第50、第75以及最后1名(即bottom节点)的5个节点分别作为SI传播模型的传播源的消息传播速率情况.从实验结果可知,由于MIT数据集持续时间较长,且有效记录数较少,导致网络连接较为稀疏,将单一节点作为消息源时,消息能够覆盖全网85%左右,top节点的消息传播速度明显快于排名靠后的节点.从整体趋势来看,排名靠前的节点其消息传播速率上要快于排名靠后的节点,从逐个节点传播情况来看,top节点的消息传播速率明显快于bottom节点,且节点重要度排序越靠后其消息覆盖速率越低.图12(b)为Haggle数据集下,同样选取节点重要度排序列表中第1(top)、第25、第50、第75以及最后1名(bottom)的5个节点进行实验比较不同节点的消息传播速率.从实验结果可知,相比于MIT而言,Haggle持续时间短且有效记录数多,节点间连接较为密集,因此,消息能够迅速覆盖到整个网络.总体上来说,top节点的消息传播速率均快于其他节点,且排名越靠后其消息传播速率越慢,但由于Haggle数据集较MIT数据集更密集,使得网络中节点的传播速率总体上要更高,且top节点与bottom节点的差距较MIT也更小.图12(c)为Asturias-er数据集下,选取节点重要度排序列表中第1(top)、第60、第120、第180以及最后1名(bottom)节点作为实验对象考察其消息传播速率.从实验结果可知,由于Asturias-er节点数目多且持续时间长,不同节点间的消息传播能力存在明显差距.从整体上来说,排名越靠后的节点其在消息传播速率以及消息覆盖率上都明显低于排名靠前的节点,且排名越靠后其差距越大,从节点层面上来说,top节点与bottom节点间无论是在消息覆盖范围和消息传播速率上都有明显的差距,top节点的消息覆盖率能达到80%左右而bottom节点的消息覆盖率不足20%,且在传播过程中bottom消息传播速率也要显著慢于top节点.

综上所述,在MIT，Haggle，Asturias-er数据集上,实验结果表明按照本文方法得到的节点重要度由高向低将节点进行排序,等差选取5个节点单独作为SI模型的传播源时,排名靠前的节点消息传播速率高于排名靠后的节点.因此,本文方法得到的节点重要度能够准确地描述节点对于消息的传播速率,也说明了本文方法是有效的.

实验2.采用SIR模型比较本文方法和时效度(temporal degree, TD)方法[11]、时效介数(temporal betweenness, TB)方法[12]、时效PageRank(temporal PageRank, f-PageRank)方法[29]以及kshell-CN方法[30],验证模型的正确性.具体地,选取时TD，TB，f-PageRank，kshell-CN以及本文方法(以下简称GNN)得到的节点重要度排序列表中排名前5的节点作为重要节点集合S,分别将不同方法得到的top1，top2，top3，top4，top5，S作为SIR传播模型的传播源,比较不同方法的消息覆盖范围.相同的传播时间步下,消息覆盖节点数越多,则说明节点重要度评估方法越准确.

表2～4分别给出了在MIT，Haggle，Asturias-er机会网络数据集下由TD，TB，f-PageRank，kshell-CN，GNN节点重要度评估方法得到的排名top1～5节点以及由这些节点组成的重要节点集合S.

Table 2 MIT Node Importance Rank Table表2 MIT节点重要度排序表

Table 3 Haggle Node Importance Rank Table表3 Haggle节点重要度排序表

Table 4 Asturias-er Node Importance Rank Table表4 Asturias-er节点重要度排序表

首先,以S为传播源考察3个数据集下消息覆盖范围结果,图13为实验结果.从图13(a)中可以看出,由于MIT数据集属于稀疏型机会网络,节点间连接频率低,整体的消息覆盖节点数较少,本文方法得到的重要节点集合S作为消息源时,网络的消息覆盖节点数要明显高于TD，TB方法,略高于f-PageRank方法与kshell-CN方法.图13(b)为Haggle数据集网络消息覆盖范围结果,由于Haggle数据集属于密集型机会网络,节点连接频繁,即便在相同的传播条件下,4种方法所得到的消息覆盖范围更广.由本文方法得到的S作为消息源时,网络的消息覆盖率明显高于TD方法,略高于TB，kshell-CN，f-PageRank方法.图13(c)为Asturias-er数据集网络消息覆盖范围,Asturias-er数据集持续时间长,且随着时间的推移参与通信的节点数目也随之增加.总体来说,以本文方法得到的重要节点集合S作为消息源时网络的消息覆盖范围均高于其他方法.

其次,逐一考察由不同方法得到的top1～5节点在SIR传播模型下的消息覆盖范围.图14～16分别为MIT，Haggle，Asturias-er数据集下,不同方法top1～5节点在SIR传播模型下的消息覆盖范围对比图.

图14为MIT数据集下top1～5的对比结果.其中,图14(a)是不同方法top1节点的对比情况,根据表2结果选取89，56，28号节点单独作为SIR传播模型的传播源进行实验,从图14(a)中可知,89号节点优于56号节点与28号节点.类似地,图14(b)～(e)为按照表2结果分别比较top2～5不同方法得到的节点的消息覆盖范围.特别地,top4和top5节点集中在85和95号节点上,故图14(d)和图14(e)均为85号和95号节点的对比情况.从实验结果可知,本文方法在top1，top3，top4，top5的评估更为准确.

图15为Haggle数据集下top1～5的对比结果.其中,图15(a)是不同方法top1节点的对比情况,根据表3的结果选取77，86，44号节点单独作为SIR传播模型的传播源进行实验,从图15(a)中可知,77号节优于86与44号节点.类似地,图15(b)～(e)分别为top2～5不同方法得到的节点消息覆盖范围.从实验结果可知,本文方法在top1～5的评估更为准确.

图16为Asturias-er数据集下top1～5的对比结果.其中,图16(a)和图16(b)是不同方法top1与top2节点的对比情况,根据表4不同方法的评估结果中top1和top2的节点均是33号和158号节点,故选取33，158号节点单独作为SIR传播模型的传播源进行实验,从图16(a)中可知,33号节点与158号节点消息覆盖率基本一致,因此多种评估方法的top1与top2节点均是158号和33号节点.类似地,图15(c)(d)(e)分别为top3～5不同方法得到的节点消息覆盖范围.从实验结果可知,本文方法在top1，top2，top3，top4的评估更为准确.

综上所述,在MIT，Haggle，Asturias-er数据集上,本文方法得到的top1～5节点以及由它们组成的重要节点集合S,在SIR传播模型上的消息覆盖率均高于TD方法、TB方法、f-PageRank方法以及kshell-CN方法.这是由于本文方法综合考虑了节点的局部拓扑信息、全局拓扑信息、时序变化信息以及节点间重要度的相互影响关系,因此,能更加准确地识别出机会网络中的重要节点.

2) 节点重要度排序列表的质量

根据TD方法、TB方法、f-PageRank方法、kshell-CN方法及本文方法得到节点重要度的排序列表,将消息传播模型的结果作为标准排序.分别计算不同网络数据集中TD方法、TB方法、f-PageRank方法、kshell-CN方法以及本文方法的NDCG@10,排序质量如表5所示:

Table 5 NDCG@10 of Three Datasets表5 3个数据集上的NDCG@10值

由表5可知,由于MIT数据集持续时间长,且有效记录数较少,属于稀疏性机会网络,采用TD与TB方法对节点重要度评估时,导致网络的拓扑结构信息以及时序变化信息不能被充分利用,本文方法在排序质量上相较于TD方法与TB方法分别提高了22.2%与22.0%,相较于f-PageRank方法提高了7.1%.在Haggle数据集中,由于Haggle持续时间短,节点间通信频繁,属于密集型机会网络.随着节点间的有效通信路径增加,TB方法能够更好地刻画出节点对于网络中有效通信路径的控制力,因此,评估结果较TD更好.但相较本文方法,TB方法没有考虑节点间重要度的相互影响,故评估效果低于本文方法.在Asturias-er数据集中,由于Asturias-er节点规模相较于其他2个数据集更大且数据集持续时间长,因此能够获取的网络拓扑信息以及时序变化信息更加丰富,本文方法相较于其他方法能够更有效地利用这些信息进行节点重要度的评估,故评估效果均高于其他方法.基于以上分析,本文所提出的方法能够有效地对机会网络中的节点重要度进行评估,且实验结果表明本文方法在多个评价方法上优于现有其他方法.

5 总 结

本文方法针对机会网络的动态性与时变性,利用机会网络数据的历史连接信息有效地对机会网络中节点的重要度进行评估,从而识别出机会网络中消息传播能力强的节点.实验结果表明：本文方法能够准确识别出在机会网络中消息传播能力强的节点,将这些节点作为消息的传播源时,能提高消息覆盖率和传播速率.同时,在稀疏型机会网络场景、密集型机会网络场景以及大型机会网络场景下,本文提出的基于GNN的机会网络节点重要度评估方法,在SI，SIR和NDCG@10评价方法上优于TD，TB，f-PageRank，kshell-CN.未来研究将进一步确定机会网络单元的最佳切片时长以尝试改善评估的效果.

作者贡献声明：刘琳岚负责理论模型构建、实验方案设计和文章撰写；谭镇阳提出研究思路，负责实验数据整理与分析、实验结果可视化，撰写初稿；舒坚参与了论文想法的讨论，确定研究思路，对于实验方案提出指导意见，审阅和完善论文内容.