基于信息传播节点集的CTDN 节点分类算法

黄 鑫，李 赟，熊瑾煜

（1.中国人民解放军战略支援部队信息工程大学信息系统工程学院，郑州 450001；2.盲信号处理国家级重点实验室，成都 610041）

0 概述

复杂网络是对现实世界中复杂系统的抽象表示，复杂系统的各组成部分及其相互之间的关联关系分别用节点和节点之间的边来表示。对复杂网络中的节点开展分类问题研究，有利于加深对复杂系统内部组成的理解。传统网络节点分类主要针对静态网络，即不考虑网络随时间发生演变，网络节点和节点之间的边始终保持不变。在实际情况中，网络的动态特征明显，节点和节点之间的边可能随时间发生变化。为使研究更贴近实际情况，在静态网络的基础上充分考虑时间要素，研究人员提出动态网络概念并进一步开展网络相关研究。本文基于经典的网络节点分类方法，在考虑时间要素的前提下，根据连续时间动态网络（Continuous-Time Dynamic Network，CTDN）的信息传播特征，结合网络表示学习方法进行网络节点分类研究，提出基于信息传播节点集的连续时间动态网络节点分类算法CTDNN-IPNS。

1 相关工作

基于网络表示学习的节点分类方法是研究网络节点分类问题的一类重要方法［1-3］。这类方法将网络节点表示为低维空间向量，通过对向量的分类实现节点的分类。结合网络表示学习方法，在分类过程中根据是否考虑节点或连边随时间变化的情况，形成静态网络节点分类和动态网络节点分类方法。

根据网络表示学习模型的使用情况，静态网络节点分类方法［4］大致可分为基于矩阵分解［5-6］、随机游走［7-8］和深度神经网络［9-10］三类。基于随机游走的网络表示学习方法将随机游走与自然语言处理领域的Skip-Gram 词向量生成模型相结合，形成节点采样+Skip-Gram 的网络表示学习框架，将网络节点和通过在网络节点之间随机游走采样获取的节点序列分别视作自然语言中的词和语句，对节点序列加以处理后实现网络节点的向量表示，并利用经典分类算法实现网络节点的最终分类。DeepWalk［7］算法是经典的基于随机游走的网络表示学习算法，具有网络表示能力强和计算复杂度低的特点。在此基础上，通过改进节点序列采样策略，衍生出Node2 Vec［8］、Walklets［11］、Metapath2Vec［12］等 众多网络表示学习算法。这类算法针对静态网络展开研究，未能对网络中的时间信息加以利用，即未考虑节点或连边随时间的变化情况对网络表示学习结果的影响，不适用于动态网络节点分类。

在动态网络节点分类方面，文献［13-14］利用LSTM、AutoEncoder 等深度学习模型对网络快照进行处理，较好地表示出网络节点类别随时间的演化过程，但是如果节点在不同的快照中表现出不同的类别，则这类方法不能给出节点的全局类别属性。文献［15-17］以改进节点序列采样策略为突破口，分别设计出基于随机游走的动态网络表示学习算法CTDNE、STWalk 和RWR-STNE，其 中，STWalk 和RWR-STNE 算法在静态网络的基础上增加时间要素，在不同时刻网络快照上构造节点时空图，进而在其上完成随机游走并实现节点采样，但是上述算法存在时间粒度过大、时间信息利用不充分的问题。CTDNE 算法针对连续时间动态网络，严格依照事件发生的时间顺序进行节点采样，但容易受噪声影响，导致网络表示学习结果与现实情况存在较大偏差，分类结果精度也会随之降低。

2 相关定义

定义1（连续时间动态网络）连续时间动态网络［15，18-19］表示为 图G=(V,ET,T)，其 中，V为节点 集，ET⊆V×V×R+为任意两个节点间具有时间戳的连边集，T：ET→R+为边的时间戳值到正实数集的映射。ei=(u,v,t)∊ET表示网络中的边，其中，u为源节点，v为目的节点，t为连边发生的时间戳。在最小时间粒度情况下，每条边可能具有互不相同的时间戳值。

连续时间动态网络的定义在传统静态网络的基础上充分考虑了动态网络中边的时序信息，同时克服了以网络快照形式表示动态网络过程中时间信息损失的问题。针对连续时间动态网络进行节点分类的3 个主要步骤如图1 所示。首先，按照定义1，利用实际数据构造连续时间动态网络；其次，使用网络表示学习方法，将连续时间动态网络中的节点映射至低维空间，采用保有节点原始关系的向量加以表示；最后，利用分类算法，通过对低维空间节点向量的分类，实现连续时间动态网络的节点分类。鉴于分类算法已经相对成熟，本文将网络表示学习环节作为研究重点，开展连续时间动态网络节点分类研究。

图1 连续时间动态网络节点分类流程Fig.1 Procedure of node classification for CTDN

定义2（连续时间动态网络表示学习）在连续时间动态网络中，学习得到的映射函数f：V→Rd，使得网络中的节点vi∊V被映射为低维向量mi∊Rd，其中，d表示向量维度且满足d<<|V|。

在通常情况下，映射函数f的目标是保留节点在原始网络结构上的内在相似性和时间上的平滑性。

3 CTDNN-IPNS 算法

在网络信息传播动力学研究中，DALEY 等人［20］提出了经典的DK 谣言传播模型。该模型将网络内节点分为与谣言传播无关者、传播谣言者和知道谣言但不继续传播者、谣言通过传播者之间的直接接触进行传播三类。在谣言传播过程中，节点间因接触范围不同，形成谣言传播群组，群组内因节点传播能力的不同，会产生不同的传播模式。

在实际网络信息传播过程中，信息通过节点间通联在不同类型节点之间传播。因此，在DK 谣言传播模型的基础上，本文结合实际通信网络数据特点及其时间维度属性，得出连续时间动态网络具有以下特点：

1）信息传播流程多数在一定时间内完成，传播范围在大小不等的节点集内。

2）信息传播包括一对一、一对多和多对多等多种模式。

3）类别相同或相似节点之间存在一定的周期性关联关系。

电话通信网络是典型的连续时间动态网络。表1 是某电话通信网络的部分通话记录，在时间戳值为316 999 s～317 344 s 的345 s 时间内，其中方括号标注的用户171、180、186、188 共同完成一次信息传播，而其他用户与其没有任何通联。图2 为信息传播过程示例，其中连边上的数字表示通联发生的时间顺序。

表1 某电话通信网络部分通话记录Table 1 Partial call records of a telephone communication network

图2 用户171、180、186 和188 之间的信息传播过程Fig.2 Information dissemination process among users 171，180，186 and 188

由此可以推测，对于连续时间动态网络的节点分类，若在网络表示学习环节的节点序列采样过程中对上述特征加以利用，其网络表示学习结果将更好地保留节点在原始网络结构上的内在相似性，在此基础上得到的分类结果精度也将大幅提高。具体而言：一是将节点采样范围、时间范围加以限制，提高节点集内成员共现概率；二是增加采样过程的灵活性，从逐个节点顺序采样转变为从节点集内成员发起的随机采样；三是信息传播周期性的存在，使得同类节点共现概率会在一定范围内随采样次数的提高而增加。

定义3（信息传播节点集）给定连续时间动态网络G，在时间范围Δt内，在信息I从节点vi传播至节点vj的过程中，所有参与此次信息传播的节点记为M={vi,…,vk,…,vj}，vp∊V，p∊{i,…,k,…,j}，这 些节点共同组成信息I的传播节点集。

基于上述分析，本文提出针对连续时间动态网络节点分类的CTDNN-IPNS 算法，该算法基于信息传播节点集的概念，对网络表示学习环节的节点序列采样策略进行改进，形成突显节点之间关联关系的节点向量表示，在此基础上进行类别划分，最终实现对连续时间动态网络节点的分类。

3.1 节点序列采样

节点序列采样的具体步骤如下：

步骤1构造连续时间动态网络G=(V,ET,T)，分别初始化信息传播节点集M、备选边集Ec和节点采样序列L为Ø，设置信息传播时间范围Δt、节点序列长度（即随机游走步长）l及采样次数（即随机游走次数）n。

步骤2从G中随机选择一条边作为初始边，其时间戳t作为本轮采样的基准时间，而其两端节点则作为初始节点加入信息传播节点集M。

步骤3与M中节点相连的所有边，若其时间戳在时间t±Δt内，则将其置入备选边集Ec。

步骤4若Ec≠Ø，则从Ec中随机选择一条边作为下一步采样的起始边，之后操作与步骤2 类似，但需合并M中的相同节点，并将新增节点添加至L。

步骤5若Ec=Ø，则在时间t+Δt内随机调整基准时间t，重复步骤3～步骤5。

步骤6重复步骤2～步骤5，当|M|≥l或t±Δt超出G的时间范围时，输出节点采样序列L。

步骤7重复步骤2～步骤6 共c次，输出n个节点序列L1,L2,…,Ln。

算法1CTDNN-IPNS 算法

在算法1 中，输入参数l控制每次节点序列采样的最大长度，n表示最终形成的节点序列个数，Δt表示一次信息传播的时间范围。

3.2 网络表示学习

定义4（节点邻居序列）对于网络中的节点u，在以采样策略S进行一次采样形成的序列中，与其同时被采集到的节点构成节点u的节点邻居序列［7］，记为NS(v)⊂V。

基于节点采样+Skip-Gram 的网络表示学习框架，可将网络表示学习问题转化为使V中所有节点v∊V在嵌入结果为f(v)的条件下，节点邻居序列中的节点共同出现的对数条件概率之和最大的优化问题，计算公式为：

为简化计算过程进行以下假设：

1）假设不同节点之间的采样过程相互独立，则如式（1）所示的条件概率可表示为NS(v)内各节点的条件概率之积，计算公式为：

2）假设同一条边的两端节点彼此作用对称，利用softmax 函数表示式（2）中的条件概率，计算公式为：

基于上述假设，式（1）可简化为：

由上述公式可知，网络表示学习的目标函数求解的关键为构造Ns(v)，即采样策略S的设计。利用节点采样+Skip-Gram 的网络表示学习框架，通过负采样方法［21］和Skip-Gram 模型即可求解式（4）描述的目标函数，从而生成网络节点的d维向量表示，其中d值由人为设定。需要说明的是，若要生成网络节点d维向量表示，则需从节点序列中截取其子序列作为Skip-Gram模型输入，而截取考察范围w同样由人为设定，该参数表示在截取节点序列的子序列时，针对节点vi截取的节点子序列为{vi-w,…,vi,…,vi+w}。

3.3 节点向量分类

CTDNN-IPNS 算法采 用LogicRegression 分类器对网络表示学习环节生成的节点向量进行分类，并依据F1_macro 和F1_micro 值量化评价分类结果。F1_macro 和F1_micro 的求解过程为：设数据集中的数据共分为n类，类别集合为C={c1,c2,…,cn}。对于类别ci，i=1,2,…,n，数据分类结果中的正确分类样本、错误分类样本和非ci类错误分类样本数量可分别表示为TTP、FFP、FFN，则F1_macro 可根据式（5）～式（8）进行求解，反映了分类结果在各个类别中样本分类的综合性能，F1_micro 可根据式（9）～式（11）进行求解，反映了分类结果在所有样本上的综合分类性能。

4 实验与结果分析

4.1 实验数据集与环境

本文选用网络表示学习研究领域常用的DBLP和AMiner 论文合作数据集，以及根据实际电话通联记录自制的Reality-Call 数据集，从连续时间动态网络的二维可视化展示效果及其节点分类结果两方面，对CTDNN-IPNS 算法的性能进行实验验证，数据集信息如表2 所示。DBLP 和AMiner 数据集中的网络节点是文章作者，若两位作者共同发表过论文，则两者之间存在一条连边，边的时间戳为论文发表年份，节点类别是论文作者的所属研究领域。类似地，Reality-Call 数据集中的用户号码被视为网络节点，若两位用户有过通话，则其对应的节点之间存在一条连边，边的时间戳为通话发起时间，节点类别为号码所属部门。实验环境设置如表3 所示。

表2 实验数据集Table 2 Experimental dataset

表3 实验环境Table 3 Experiment environment

4.2 参数设置

CTDNN-IPNS 算法涉及参数较多，具体设置如下：

1）网络节点向量表示维度d：可根据实际需要选择任意维度，在本文实验中设置为128。

2）随机游走步长l：选择大于网络平均路径长度的数值，在本文实验中设置为10。

3）节点子序列截取考查范围w：在本文实验环境及数据集条件下设置为5。

4）信息传播时间范围Δt：根据网络信息传播特点设置该参数。通过对实验数据集的分析，在论文合作网络中，作者与其合作对象的合作时间一般约为3 年，在电话通信网络中，一次信息传播的时间范围约为25 min，因此在本文实验中以3年和25 min设置该参数。

5）训练数据使用率γ：通常按照3∶1 的比例将数据集划分为训练集和测试集，在本文实验中设置为0.75。

6）总游走次数：由于CTDNN-IPNS 和CTDNE算法采用从随机选取的节点出发且依据指定规则进行随机游走的采样策略，而STWalk 算法采取以网络快照内的每个节点为起点且依次开始随机游走的策略，为便于比较，在实验中将总游走次数设置为网络节点数的整数倍。

在实验中以总游走次数为变量开展算法性能测试，其中随机游走步长l、节点子序列截取考查范围w和传播时间范围Δt的敏感性见下文分析，而网络节点向量表示维度d和训练数据使用率γ的取值则采用经验值。

4.3 CTDNN-IPNS 算法性能测试

为横向验证CTDNN-IPNS 算法的性能，基于相同测试数据集，本文将CTDNN-IPNS 算法与STWalk［16］和CTDNE［15］算法进行比较，对比算法采用清华大学发布的OpenNE 框架内的相关函数进行实现。在测试过程中，网络节点向量表示维度d=128，节点子序列截取考察范围w=5，随机游走步长l=10，随机游走次数n=30 000，训练数据使用率γ=0.75。

以DBLP 数据集为例，CTDNN-IPNS、STWalk 和CTDNE 算法的动态网络表示学习结果经t-SNE 算法［22］降维后的二维可视化效果如图3 所示。可以看出，与STWalk 和CTDNE 算法相比，基于本文提出的节点采样策略，CTDNN-IPNS 算法生成的动态网络表示学习结果能够更好地保持原有网络节点之间的内在相似性，数据集的6 个类别在二维空间中的分布更集中，数量较少的黑色类别数据的聚集效果也更明显且各个类别的界限清晰，能够更好地支持后续节点的分类任务。

图3 3 种算法的二维可视化效果Fig.3 2D visualized effect of three algorithms

在总游走次数下，CTDNN-IPNS、CTDNE和STWalk算法对不同数据集的分类结果评价指标值（F1_micro和F1_macro）如表4～表6 所示。上述分类结果评价指标值对应的曲线如图4～图6 所示。根据上述分类结果的评价指标值可知，针对DBLP、AMiner 和Reality-Call数据集，CTDNN-IPNS 算法整体上优于STWalk 和CTDNE 算法。具体而言，在3 组实验中，CTDNE 算法分类结果的F1_micro 和F1_macro 值随节点采样次数的增加而呈现出上升趋势，但上升速度较慢。在对DBLP数据集和Aminer数据集进行节点分类时，CTDNN-IPNS算法分类结果的F1_micro 和F1_macro 值均为最高值，且在总游走次数较少时，其优势更为明显。在对Reality-Call数据集进行分类时，3 种算法均在总游走次数达到750 以上时获得较好的分类效果，但CTDNN-IPNS 算法的分类效果更佳，且在总游走次数低于750 时，CTDNN-IPNS 算法具有更好的分类性能，其F1_micro和F1_macro 值更高且增速更快。

图6 3 种算法对Reality-Call 数据集的分类结果评价曲线Fig.6 The evaluation curves of classification results on the Reality-Call dataset by three algorithms

表4 CTDNN-IPNS、STWalk 和CTDNE 算法对DBLP数据集的分类结果评价指标值Table 4 The evaluation index values of classification results on the DBLP dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

表5 CTDNN-IPNS、STWalk 和CTDNE 算法对AMiner 数据集的分类结果评价指标值Table 5 The evaluation index values of classification results on the AMiner dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

表6 CTDNN-IPNS、STWalk 和CTDNE 算法对Reality-Call 数据集的分类结果评价指标值Table 6 The evaluation index values of classification results on the Reality-Call dataset by CTDNN-IPNS，STWalk，CTDNE algorithm

图4 3 种算法对DBLP 数据集的分类结果评价曲线Fig.4 The evaluation curves of classification results on the DBLP dataset by three algorithms

图5 3 种算法对AMiner 数据集的分类结果评价曲线Fig.5 The evaluation curves of classification results on the AMiner dataset by three algorithms

4.4 参数敏感性分析

随机游走步长l和节点子序列截取考查范围w及信息传播时间范围Δt是CTDNN-IPNS 算法中的重要参数，本节通过在DBLP 数据集上设定其他参数，分别改变l、w和Δt的取值大小来观察节点分类指标值（F1_micro 和F1_macro）的变化情况，对算法的参数敏感性进行分析。如图7 所示，随着l值的增加，F1_micro 和F1_macro 值先快速上升，再逐渐趋于平缓，曲线拐点在l=7 附近，接近于DBLP 数据集的平均路径长度值，且当l取值大于网络平均路径长度时，算法性能趋于平稳。这表明基于信息节点集的随机游走节点采样方式，能够较好地反映出网络的通联规律及其内在的结构属性。在本文实验中，为便于算法性能比较，将随机游走步长设定为3 个数据集的网络平均路径最大值，故取l=10。在图8中，随着w值的增加，F1_micro 和F1_macro 值逐步提高，当w≥5 时逐渐趋于平稳，因此在本文实验环境及数据集条件下取w=5。

图7 CTDNN-IPNS 算法分类性能随参数l 的变化曲线Fig.7 The change curves of classification performance of CTDNN-IPNS algorithm with parameter l

图8 CTDNN-IPNS 算法分类性能随参数w 的变化曲线Fig.8 The change curves of classification performance of CTDNN-IPNS algorithm with parameter w

如图9、图10 所示，在DBLP 数据集和Reality-Call数据集的节点分类实验中，当Δt分别取3 年和25 min时，算法分类性能较其他取值有小幅增长，这表明该参数的合理设置将直接影响算法的分类效果。

图9 CTDNN-IPNS 算法在DBLP 数据集上的分类性能随参数Δt 的变化曲线Fig.9 The change curves of classification performance of CTDNN-IPNS algorithm on the DBLP dataset with parameter Δt

图10 CTDNN-IPNS 算法在Reality-Call 数据集上的分类性能随参数Δt 的变化曲线Fig.10 The change curves of classification performance of CTDNN-IPNS algorithm on the Reality-Call dataset with parameter Δt

4.5 结果分析

实验结果表明，在随机游走次数较少时，CTDNE 算法因采用严格依照时间先后顺序的游走策略，在网络学习表示过程中受噪声影响较大，不能较好地捕捉到节点与同类别其他节点之间的关系，随着游走次数的增加，同类别节点的共现次数逐渐增加，其分类精度也随之提高。由于STWalk 算法和CTDNN-IPNS 算法在随机游走过程中，分别以节点历史邻居和信息传播集内节点为采样对象，因此在随机游走次数较少时表现出较好的分类性能，随着游走次数的增加，采集节点数逐渐增多，采样序列反而可能受到不同类别节点的干扰，导致分类性能略有下降，但总体表现基本平稳。

随着总游走次数的增加，CTDNE 和CTDNNIPNS 算法的性能曲线逐渐趋同，这表明在总游走次数足够大的情况下，不同的随机游走策略最终反映出的图信息基本趋于一致，且对网络的整体表示学习能力相近，而STWalk 算法侧重于关注单个网络快照上的节点，因此相比其他算法，整体分类性能相对较差。

5 结束语

本文提出一种新的连续时间动态网络节点分类算法，定义信息传播节点集，改进网络表示学习方法的节点序列采样策略，利用其生成的节点低维向量和LogicRegression 分类器实现对连续时间动态网络的节点分类。实验结果表明，针对论文合作网络的作者分类和电话通信网络的用户分类问题，相比CTDNE 和STWalk 算法，该算法的网络表示学习结果能够更好地保留节点在原始网络结构上的内在相似性，且最终分类结果也更优。后续将结合节点属性、连边权重等信息，研究针对连续时间动态网络的分类算法，进一步提升其分类效果和适用范围。