根据节点交互模式对动态网络中的节点分类方法及系统

摘要

本发明公开了一种根据节点交互模式对动态网络中的节点分类方法及系统，将包含N个节点的动态网络解耦为N个自我中心网络；将每个自我中心网络建立起止时间段内的动态过程按照时间顺序平均离散为T个时刻；根据时间信息提取每个自我中心网络的点序列与边序列；将所述每个自我中心网络的点序列与边序列匹配为N个稀疏交互矩阵；将稀疏交互矩阵根据时间顺序压缩为N个离散交互矩阵；根据所述N个离散交互矩阵使用CNN提取每个自我中心网络的特征作为自我中心网络中心节点的特征进行节点分类该方法提出的拓扑数据组织方式与特征提取方式对于拓扑结构中的信息挖掘具有实际意义，在不增加信息量的同时，降低空间复杂度并且大大提高了节点分类的准确率。

说明书

技术领域

本发明属于动态网络的节点分类技术领域，具体为根据节点交互模式对动态网络中的节点分类方法及系统。

背景技术

动态网络应用于广泛的领域，包括社会网络分析、推荐系统和流行病学。将复杂网络表示为随时间变化的结构，使得网络模型不仅能够利用结构模式，还能够利用时间模式。然而，由于动态网络文献来源于不同的领域，并且使用了不一致的术语，因此导航具有挑战性。与此同时，近年来，图神经网络因其在链路预测和节点分类等一系列网络科学任务中表现出色而受到广泛关注。

节点分类是将图节点分类成不同类别的问题。节点分类问题的一个例子是根据社交网络用户的属性、联系和活动来预测他们的政治倾向。特别地，人们可能对在流式场景中进行这样的预测感兴趣，在流式场景中，分类分数随着新事件的发生或随着用户活动的观察而不断更新。节点分类通常在两种情况下进行研究:直推式和归纳式。在直推式方法(也称为半监督分类)中，给定几个节点的标签，我们希望预测图中其他节点的标签。在归纳设置中，标签是为在训练中没有看到的新节点预测的。在动态情况下，节点分类的问题变得具有挑战性，因为类标签的分布可能随着时间而改变。

当前在动态网络中的节点分类技术基本由静态网络中个的节点分类技术扩展而来。对于动态网络，先由静态网络中的节点分类技术通过不同时期的模糊集来聚合邻居节点的信息。结合RNN等时间序列模型，静态网络中的节点分类技术可以利用时间序列模型将静态网络中的节点分类技术提取的信息进行组合。然而，对于由交互模式主导的动态网络来说。静态网络中的节点分类技术无法描述它们复杂的相互作用。因此，设计其他方法来关注由交互模式而不是关系信息主导的图形仍然存在差距。

发明内容

本发明的目的在于提供一种根据节点交互模式对动态网络中的节点分类方法及系统；在多个动态网络中的节点分类任务中都具有较高的准确率，为提取动态网络中的特征提供一种新的思路。

为了实现上述目的，本发明采用的技术方案为：一种根据节点交互模式对动态网络中的节点分类方法，包括以下步骤：

将包含N个节点的动态网络解耦为N个自我中心网络；

将N个自我中心网络中每个自我中心网络建立起止时间段内的动态过程按照时间顺序平均离散为T个时刻；

根据时间信息提取每个自我中心网络的点序列与边序列；

将所述每个自我中心网络的点序列与边序列匹配为N个稀疏交互矩阵；

将稀疏交互矩阵根据时间顺序压缩为N个离散交互矩阵；

根据所述N个离散交互矩阵使用CNN提取每个自我中心网络的特征作为自我中心网络中心节点的特征进行节点分类。

将包含N个节点的动态网络解耦为N个自我中心网络的具体过程是：对原始网络中的每一个节点，提取其所有一跳邻居节点、所述节点与其一跳邻居节点之间的边，分别作为所述节点的自我中心网络的点集与边集；其中点集中的元素为：

node

边集中的元素为：

A＝(node

node

将N个自我中心网络中每个自我中心起止时间段内的动态过程按照时间顺序平均离散为T个时刻的具体过程是：以自我中心网络中的最早出现的边的时间作为起始时间，以自我中心网络中最晚出现的边的时间作为终止时间，将起止时间平均分为T个时间段，将T个时间段的点与边的信息有损压缩为T个快照，第T个快照中包含的点和边的信息为：

其中，V

根据时间信息提取每个自我中心的点序列与边序列的具体过程是：对于自我中心网络，假设中心节点自始至终都存在，对于中心节点的邻居节点，所述邻居节点与中心节点第一次建立边的时间将被视为所述邻居节点出现的时间，根据节点出现的时间将自我中心网络中的所有节点排列成有序的序列，即点序列：

S

其中node

S

其中A

点序列与边序列匹配为稀疏交互矩阵的具体过程是：根据点序列与边序列构造一个二维矩阵B，其中每一列对应于一个节点的信息，每一行对应于一个时刻的信息：

B[m，n]表示矩阵B的第m行，第n列元素的值，矩阵B包含原始网络中以一个node为中心建立的自我中心网络的时序信息。

将稀疏交互矩阵根据时间顺序压缩为离散交互矩阵的具体过程是：将稀疏交互矩阵中相邻且离散在同一时间段内的行求和，得到离散交互矩阵：

其中，B[m,n]代表稀疏交互矩阵中第m行第n列的元素，m用于表示其自我中心网络中边出现的顺序，n用于表示其自我中心网络中点出现的顺序；B[t,n]代表稀疏交互矩阵中第t行第n列的元素，t用于表示时间快照的顺序，l表示每两个相邻的时间快照的时间间隔，m∈(l*(t-1),l*t]第m个出现的边位于第(t-1)到第t个时间快照之间，将这些边求和。

使用CNN提取每个自我中心网络的特征作为自我中心网络中心节点的特征进行节点分类的具体过程是：基于N个离散交互矩阵生成N个一一对应的灰度图，采用基于计算机视觉的卷积神经网络，提取每个灰度图的特征并使用全连接神经网络进行分类，将灰度图的分类结果作为其生成所用的离散交互矩阵对应的点的分类结果。

一种根据节点交互模式对动态网络中节点分类的系统，包括解耦模块、离散模块、点序列与边序列提取模块、稀疏交互矩阵匹配模块、离散交互矩阵构建模块以及分类模块：解耦模块用于将包含N个节点的动态网络解耦为N个自我中心网络；

离散模块用于将N个自我中心网络中每个自我中心网络建立起止时间段内的动态过程按照时间顺序平均离散为T个时刻；

点序列与边序列提取模块用于根据时间信息提取每个自我中心网络的点序列与边序列；

稀疏交互矩阵匹配模块用于将所述每个自我中心网络的点序列与边序列匹配为N个稀疏交互矩阵；

离散交互矩阵构建模块用于将稀疏交互矩阵根据时间顺序压缩为N个离散交互矩阵；

分类模块用于根据所述N个离散交互矩阵使用CNN提取每个自我中心网络的特征作为自我中心网络中心节点的特征进行节点分类。

一种计算机设备，包括一个或多个处理器以及存储器，存储器用于存储计算机可执行程序，处理器从存储器中读取部分或全部所述计算机可执行程序并执行，处理器执行部分或全部计算可执行程序时能实现本发明所述根据节点交互模式对动态网络中的节点分类方法。

一种计算机可读存储介质，计算机可读存储介质中存储有计算机程序，所述计算机程序被处理器执行时，能实现本发明所述的节点交互模式对动态网络中的节点分类方法。

与现有技术相比，本发明具有以下有益的技术效果：

本发明对原始的动态网络进行解耦后进行计算，解耦操作极大的降低了全流程的空间复杂度，在仅使用拓扑结构数据的情况下，可以根据动态网络中的节点交互方式的差异对不同类型的节点分类，并且性能显著优于现有技术；本发明具有较低的空间复杂度，对显存的需求量小，使用基于卷积神经网络的计算方式大大降低了显存的需求，有利于对大型网络提取特征；本发明在由于对单个节点的计算无需整张网络的数据，极大的降低了预测单个个体类别的计算量，在不增加信息量的同时，降低空间复杂度并且大大提高了节点分类的准确率。

附图说明

图1为本发明实施例1中部分样本的灰度图。

图2为本发明方法的流程图。

具体实施方式

下面结合附图及具体实施方式对本发明做进一步详细描述：

参考图2，本发明提供了一种根据节点交互模式对动态网络中的节点分类方法，其过程是：

步骤1，对于原始动态网络中的每一个节点，提取其所有一跳邻居节点作为该节点所对应的自我中心网络的点集，点集中的元素为：

node

提取该节点与一跳邻居节点之间的边作为自我中心网络的边集，边集中的元素为：

A＝(node

node

步骤2，对于一个自我中心网络来说，将其第一条边建立的时间作为起始时间，将其最后一条边的建立时间作为终止时间。将自我中心网络的起止时间内的时间平均分为T段，每一段时间内的信息生成一个时间快照。生成方式为，该时间快照包含对应时间段内所有的点与边。若一个时间快照内存在重边，则将边的权重求和作为快照中边的权重。则第T个快照中包含的点和边的信息为：

其中，V

步骤3，对于每一个自我中心网络，先给定点集与边集中所有元素出现的时间。对于点集中的元素，默认中心节点是自然存在的，对于其他的节点，将其第一次与中心节点建立边的时间作为其在自我中心网络中的出现时间。对于边集的元素，使用动态网络边的建立时间作为其出现时间，则依据点出现的时间先后可以将点集排列为有序序列，即点序列

S

同理，边集也可以被排列为有序序列，即边序列：

S

步骤4，将所述点序列与边序列匹配为一个二维矩阵B作为稀疏交互矩阵，列数为点的数量，行数为边的数量，第m行第n列上的元素表示第m个出现的、中心节点与第n个出现的点建立的边的权重。稀疏交互矩阵可以被表示为：

B[m，n]表示矩阵B的第m行，第n列元素的值，矩阵B包含原始网络中以一个node为中心建立的自我中心网络的时序信息。

步骤5，对于稀疏交互矩阵根据时间信息进行有损压缩。将稀疏交互矩阵中属于同一时间段的行求和，将稀疏交互矩阵的行数由边数压缩为快照数T，得到离散交互矩阵：

其中，B[m,n]代表稀疏交互矩阵中第m行第n列的元素，m用于表示其自我中心网络中边出现的顺序，n用于表示其自我中心网络中点出现的顺序；B[t,n]代表稀疏交互矩阵中第t行第n列的元素，t用于表示时间快照的顺序，l表示每两个相邻的时间快照的时间间隔，m∈(l*(t-1),l*t]第m个出现的边位于第(t-1)到第t个时间快照之间，将这些边求和。

步骤6，根据步骤5所得到的N个离散交互矩阵生成N个灰度图，使用卷积神经网络提取每个灰度图的特征，并使用全连接神经网络对灰度图进行分类，将灰度图的分类结果作为其生成所用的离散交互矩阵对应的点的分类结果，参考图1。

本发明的具体实施例如下：

实现根据节点交互模式对动态网络中的节点分类，其具体过程如下：

步骤1，对于一个包含3012个节点的动态网络，先选取其中的一个节点作为节点0建立自我中心网络，该节点具有6个邻居节点，将6个邻居节点编号为1～6，则以0号节点为中心建立的自我中心网络的点集为：

{0,1,2,3,4,5,6}

0号节点与这6个邻居节点共建立了8条边，这八条边构成了自我中心网络的边集：

{(0,1,3),(0,2,2),(0,3,1),(0,2,7),(0,3,2),(0,4,3),(0,5,1),(0,6,4)}。

对于该动态网络中的所有节点都生成对应的点集与边集。

步骤2，步骤1中描述的自我中心网络中的第一条边(0,1,3)建立的时间0h作为起始时间，将自我中心网络最后一个边(0,6,4)的出现时间8h作为终止时间，将0～9h平均分成3段，0～2h，3～5h，6～8h。其中0～2h包含(0,1,3),(0,2,2)两条边，3～5h包含(0,3,1),(0,2,7),(0,3,2),(0,4,3)四条边，6～8h包含(0,5,1),(0,6,4)两条边。则0～2h的点集为{0,1,2}，边集为{(0,1,3),(0,2,2)}，3～5h的点集为{0,2,3,4}，边集为{(0,3,1),(0,2,7),(0,3,2),(0,4,3)}，6～8h的点集为{0,5,6}，边集为{(0,5,1),(0,6,4)}。对其余3011个自我中心网络重复此操作。

步骤3，对于步骤2所描述的自我中心网络，先给定点集与边集中所有元素出现的时间。0号节点是自然存在的，因此其出现在0h。该自我中心网络中边出现的顺序为：(0,1,3),(0,2,2),(0,3,1),(0,2,7),(0,3,2),(0,4,3),(0,5,1),(0,6,4)，将邻居节点第一次与0号节点建立边的时间作为其在自我中心网络中的出现时间，则所有邻居节点出现的时间顺序为：1,2,3,4,5,6。该自我中心网络的点序列为：

S

边序列为：

S

对其余3011个自我中心网络重复此操作，得到所有自我中心网络的点序列和边序列。

步骤4，将点序列与边序列匹配为一个二维矩阵B作为稀疏交互矩阵，列数为点的数量，行数为边的数量，第m行第n列上的元素表示第m个出现的、中心节点与第n个出现的点建立的边的权重。则步骤3所描述的自我中心网络的稀疏交互矩阵为：

对其余3011个自我中心网络重复此操作，得到所有自我中心网络的稀疏交互矩阵。

步骤5，对于步骤4所描述稀疏交互矩阵根据时间信息进行有损压缩。具体的，将稀疏交互矩阵中属于同一时间段的行求和，将行数由边数压缩为3行，得到离散交互矩阵：

对其余3011个自我中心网络重复此操作。

步骤6，根据步骤5所得到的3012个离散交互矩阵生成3012个灰度图，使用卷积神经网络提取每个灰度图的特征并使用全连接神经网络进行分类，将灰度图的分类结果作为其生成所用的离散交互矩阵对应的点的分类结果。

本实施例选取全量网络中的355个点作为正样本，355个点作为负样本做二分类。将步骤5生成的灰度图作为步骤6中卷积神经网络的输入，最终分类准确率为96.48％。

本发明在实现分类任务过程中仅使用了图的拓扑结构信息与时间信息，与现有技术所使用的信息一致的情况下实现了96.48％的节点分类准确率。

本发明对原始的动态网络解耦后进行计算，解耦操作极大的降低了全流程的空间复杂度。使用基于卷积神经网络的计算方式大大降低了显存的需求，有利于对大型网络提取特征。

本发明在由于对单个节点的计算无需整张网络的数据，仅需该节点的自我中心网络用语生成灰度图，极大的降低了预测单个个体类别的计算量。

本发明提供动态网络中节点分类的系统，包括：将包含N个节点的动态网络解耦为N个自我中心网络；

将每个自我中心起止时间段内的动态过程按照时间顺序平均离散为T个时刻。

将每个自我中心根据时间信息提取点序列与边序列。

将点序列与边序列匹配为稀疏交互矩阵。

将稀疏交互矩阵根据时间顺序压缩为离散交互矩阵。

根据离散交互矩阵使用CNN提取每个自我中心网络的特征作为自我中心网络中心节点的特征进行节点分类。

可选的，本发明还提供一种根据节点交互模式对动态网络中节点分类的设备，包括处理器以及存储器，存储器用于存储计算机可执行程序，处理器从存储器中读取部分或全部所述计算机可执行程序并执行，处理器执行部分或全部计算可执行程序时能实现本发明所述识别根据节点交互模式对动态网络中节点分类方法的部分步骤或所有步骤。

所述根据节点交互模式对动态网络中节点分类的设备可以是笔记本电脑、平板电脑、桌面型计算机或工作站。

处理器可以是中央处理器(CPU)、数字信号处理器(DSP)、专用集成电路(ASIC)或现成可编程门阵列(FPGA)。

对于本发明所述存储器，可以是笔记本电脑、平板电脑、桌面型计算机、手机或工作站的内部存储单元，如内存、硬盘；也可以采用外部存储单元，如移动硬盘、闪存卡。

计算机可读存储介质可以包括计算机存储介质和通信介质。计算机存储介质包括以用于存储诸如计算机可读指令、数据结构、程序模块或其他数据等信息的任何方法或技术实现的易失性和非易失性、可移动和不可移动介质。计算机可读存储介质可以包括：只读存储器(ROM，Read Only Memory)、随机存取记忆体(RAM，Random Access Memory)、固态硬盘(SSD，Solid State Drives)或光盘等。其中，随机存取记忆体可以包括电阻式随机存取记忆体(ReRAM,Resistance)。