一种时序网络建模方法及重要节点识别方法

摘要

本发明公开了一种基于层间耦合关系强度衰减的时序网络建模方法，包括：划分网络的层数，定义多层图时序网络模型的层内关系和层间关系；基于局部相似性指标计算两个时间层网络中对应节点层间耦合关系；计算层间耦合强度的衰减因子，计算层间耦合关系；计算多个时间层网络对应的邻接矩阵，表示层内连接关系；使用层间耦合关系表示层间连接关系；通过层内连接关系和层间连接关系得到层间耦合强度衰减的超邻接矩阵，通过得到的层间耦合强度衰减的超邻接矩阵对时序网络进行建模。该方法能够适用于不同结构的时序网络，在计算复杂度低于全局方法的同时，能够更有效的识别时序网络中的重要节点，在时序网络的重要节点识别研究领域有显著应用价值。

说明书

技术领域

本发明涉及一种时序网络中节点的重要性识别方法，尤其是涉及一种基于层间耦合关系强度衰减的时序网络建模方法，并基于特征向量中心性指标来反映节点的重要性。

背景技术

在线社交网络在人们生活中扮演着重要的角色。人们可以通过社交网络表达想法、分享信息，并相互影响。识别网络中的重要节点在广告投放、舆情监督及推荐系统等方面有着重要的应用。

经检索国内外文献发现，目前关于重要节点识别的方法大多数都基于静态网络展开研究，但是现实生活中的许多网络并不能被简单建模为静态网络，因为网络中的节点可能只在某个时间段内存在联系，即节点之间的连边会随时间间断性的消失或出现。所以本发明涉及的是时序网络中的重要节点识别方法。

文献“Eigenvector-Based Centrality Measures for Temporal Networks[J].MultiscaleModeling&Simulation,2017,15(1):537-574.”利用多层耦合网络分析的方法，将时序网络按层间关系和层内关系建立超邻接矩阵(Supra-adjacency Matrix,SAM)，并定义了基于特征向量的中心性指标来反映节点的重要性。该方法用固定参数表示层间关系的强弱，导致研究需要谈论参数的变化对结果的影响，增加了问题的复杂度，且固定参数不能反映层间关系的差异性。

文献“基于层间相似性的时序网络节点重要性研究[J].物理学报,2018,67(04):279-286.”使用邻居拓扑重叠系数表示节点的层间连接关系，并提出基于节点相似性的超邻接矩阵(similarity-based supra-adjacencymatrix,SSAM)时序网络构建方法，同时利用特征向量中心性指标,获取节点在各个时间层上的重要性排序，最终可以得到节点重要性随时间变化的轨迹。同时，该研究证实当使用固定参数0.5(参数较小时)表示节点的层间连接关系，会弱化了持续出现且节点层间邻居相似度高的节点的重要程度，而当参数较大时，会强化孤立节点的重要程度。

发明内容

1、本发明的目的

针对现有复杂网络中重要节点识别方法准确性的不足，本发明提供一种基于层间耦合关系强度衰减的时序网络建模方法及重要节点识别方法，该方法能够适用于不同结构的时序网络，在实际使用时没有可调参数，在计算复杂度低于全局方法的同时，能够更有效的识别时序网络中的重要节点，在时序网络的重要节点识别研究领域有显著应用价值。

2、本发明所采用的技术方案

一种基于层间耦合关系强度衰减的时序网络建模方法，包括以下步骤：

S01：划分网络的层数，定义多层图时序网络模型的层内关系和层间关系；

S02：基于局部相似性指标计算两个时间层网络中对应节点层间耦合关系；

S03：计算层间耦合强度的衰减因子，计算层间耦合关系；

S04：计算多个时间层网络对应的邻接矩阵，表示层内连接关系；通过所述步骤S03计算得到的层间耦合关系，表示层间连接关系；通过层内连接关系和层间连接关系得到层间耦合强度衰减的超邻接矩阵，通过得到的层间耦合强度衰减的超邻接矩阵对时序网络进行建模。

优选的技术方案中，所述步骤S02计算两个时间层网络中对应节点层间耦合关系的方法包括：在固定参数基础上，综合考虑两个时间层网络中对应节点的自身邻居和共同邻居对层间关系的影响，定义改进的相似性指标度量层间耦合关系，改进的相似性指标ESI为：

式中，N表示时序网络中节点总数，

式中，

优选的技术方案中，所述步骤S03中衰减因子表示设定两个时间层网络中对应节点i的层间相似性会随时间间隔Δt增加而变弱定义衰减因子为：

式中，Δt＝t

式中，1≤t

优选的技术方案中，所述步骤S04中层间耦合强度衰减的超邻接矩阵ASAM为：

式中，A

本发明还公开了一种基于层间耦合关系强度衰减的时序网络的重要节点识别方法，包括上述的基于层间耦合关系强度衰减的时序网络建模方法得到层间耦合强度衰减的超邻接矩阵；

对超邻接矩阵ASAM求主特征向量Y＝{y

使用向量Y的第N(t-1)+i个项表示节点i在第t个时间层上的特征向量中心性，将其记为N×T的矩阵X＝{x

本发明又公开了一种基于层间耦合关系强度衰减的时序网络建模系统，包括：

网络划分模块，划分网络的层数，定义多层图时序网络模型的层内关系和层间关系；

局部相似性指标计算模块，基于局部相似性指标计算两个时间层网络中对应节点层间耦合关系；

层间耦合关系计算模块，计算层间耦合强度的衰减因子，计算层间耦合关系；

层间耦合强度衰减的超邻接矩阵计算模块，计算多个时间层网络对应的邻接矩阵，表示层内连接关系；通过计算得到的层间耦合关系，表示层间连接关系；通过层内连接关系和层间连接关系得到层间耦合强度衰减的超邻接矩阵，通过得到的层间耦合强度衰减的超邻接矩阵对时序网络进行建模。

优选的技术方案中，所述局部相似性指标计算模块计算两个时间层网络中对应节点层间耦合关系的方法包括：在固定参数基础上，综合考虑两个时间层网络中对应节点的自身邻居和共同邻居对层间关系的影响，定义改进的相似性指标度量层间耦合关系，改进的相似性指标ESI为：

式中，N表示时序网络中节点总数，

式中，

优选的技术方案中，所述层间耦合关系计算模块中衰减因子表示设定两个时间层网络中对应节点i的层间相似性会随时间间隔Δt增加而变弱定义衰减因子为：

式中，Δt＝t

式中，1≤t

优选的技术方案中，所述层间耦合强度衰减的超邻接矩阵计算模块中层间耦合强度衰减的超邻接矩阵ASAM为：

式中，A

本发明又公开了一种基于层间耦合关系强度衰减的时序网络的重要节点识别系统，包括：

层间耦合强度衰减的超邻接矩阵计算模块，采用上述的基于层间耦合关系强度衰减的时序网络建模系统得到层间耦合强度衰减的超邻接矩阵；

重要节点识别模块，对超邻接矩阵ASAM求主特征向量Y＝{y

使用向量Y的第N(t-1)+i个项表示节点i在第t个时间层上的特征向量中心性，将其记为N×T的矩阵X＝{x

3、本发明所采用的有益效果

本发明首先使用每个时间层网络的邻接关系表示层内关系，并综合考虑两个时间层网络中对应节点的自身邻居合共同邻居来计算层间耦合关系，然后考虑到层间耦合关系会随着时间间隔的增大而发生衰减，随即引入衰减因子更准确的刻画层间耦合关系的差异性。最终，提出基于层间耦合强度衰减的超邻接矩阵时序网络建模方法，以研究时序网络的节点重要性。该方法能适用于不同结构、不同规模的网络，本发明实现简单，在实际使用时不用调节参数，且计算复杂度小于全局方法，可以快速准确的发现时序网络中的重要节点。最重要的是，该方法能够更真实地描述时序网络各个时间层中各个节点地差异性、准确性好。

附图说明

图1为本实施例基于层间耦合关系强度衰减的时序网络建模方法的流程图；

图2为本实施例基于层间耦合关系强度衰减的时序网络的重要节点识别方法的流程图；

图3为本实施例基于层间耦合关系强度衰减的时序网络建模系统的原理框图；

图4为本实施例基于层间耦合关系强度衰减的时序网络的重要节点识别系统的原理框图；

图5a-5l分别表示本发明与SAM、SSAM的重要节点排序结果通过删除top-σ节点后，在EmailDept3、Enrons、Highschool3及Workspace数据集的时序网络最大连通分量的对比图；

图6a-6l分别表示本发明与SAM、SSAM的重要节点排序结果通过删除top-σ节点后，在EmailDept3、Enrons、Highschool3及Workspace数据集的时序网络的性能变化的对比图。

具体实施方式

下面结合本发明实例中的附图，对本发明实例中的技术方案进行清楚、完整地描述。显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域技术人员在没有做创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。

下面将结合附图对本发明实例作进一步地详细描述。

实施例1

如图1所示，一种基于层间耦合关系强度衰减的时序网络建模方法，包括以下步骤：

S01：划分网络的层数，定义多层图时序网络模型的层内关系和层间关系；

S02：基于局部相似性指标计算两个时间层网络中对应节点层间耦合关系；

S03：计算层间耦合强度的衰减因子，计算层间耦合关系；

S04：计算多个时间层网络对应的邻接矩阵，表示层内连接关系；通过所述步骤S03计算得到的层间耦合关系，表示层间连接关系；通过层内连接关系和层间连接关系得到层间耦合强度衰减的超邻接矩阵，通过得到的层间耦合强度衰减的超邻接矩阵对时序网络进行建模。

步骤S01中，层内关系表示对应时间层网络中节点间的交互作用，而层间关系表示相邻时间层网络中对应节点间的关系

一较佳的实施例中，步骤S02计算两个时间层网络中对应节点层间耦合关系的方法包括：在固定参数基础上，即0.5，综合考虑两个时间层网络中对应节点的自身邻居和共同邻居对层间关系的影响，定义改进的相似性指标度量层间耦合关系，改进的相似性指标ESI为：

式中，N表示时序网络中节点总数，

式中，

一较佳的实施例中，步骤S03中衰减因子表示设定两个时间层网络中对应节点i的层间相似性会随时间间隔Δt增加而变弱定义衰减因子为：

式中，Δt＝t

层间耦合关系的度量公式如下：

式中，1≤t

因为当时间间隔等于5时，衰减因子

一较佳的实施例中，步骤S04中层间耦合强度衰减的超邻接矩阵ASAM为：

式中，A

另一实施例中，如图2所示，本发明还公开了一种基于层间耦合关系强度衰减的时序网络的重要节点识别方法，包括上述的基于层间耦合关系强度衰减的时序网络建模方法得到层间耦合强度衰减的超邻接矩阵；

对超邻接矩阵ASAM求主特征向量Y＝{y

使用向量Y的第N(t-1)+i个项表示节点i在第t个时间层上的特征向量中心性，将其记为N×T的矩阵X＝{x

另一实施例中，如图3所示，本发明又公开了一种基于层间耦合关系强度衰减的时序网络建模系统，包括：

网络划分模块10，划分网络的层数，定义多层图时序网络模型的层内关系和层间关系；

局部相似性指标计算模块20，基于局部相似性指标计算两个时间层网络中对应节点层间耦合关系；

层间耦合关系计算模块30，计算层间耦合强度的衰减因子，计算层间耦合关系；

层间耦合强度衰减的超邻接矩阵计算模块40，计算多个时间层网络对应的邻接矩阵，表示层内连接关系；通过计算得到的层间耦合关系，表示层间连接关系；通过层内连接关系和层间连接关系得到层间耦合强度衰减的超邻接矩阵，通过得到的层间耦合强度衰减的超邻接矩阵对时序网络进行建模。

下面详细描述该建模系统的工作流程：

步骤一、划分网络的层数，以基于多层图时序网络模型进行研究。

多层图时序网络模型由层内关系和层间关系定义：层内关系表示对应时间层网络中节点间的交互作用，而层间关系表示相邻时间层网络中对应节点间的关系；

首先定义一个网络G＝(V,E),其中V＝{v

步骤二、基于局部相似性指标度量层间耦合关系；

定义和计算两个时间层网络中对应节点层间耦合关系，在固定参数0.5的基础上，综合考虑两个窗图中对应节点的自身邻居和共同邻居对层间关系的影响，定义改进的相似性指标(ESI)来度量层间耦合关系，如下：

式中，N表示时序网络中节点总数，

式中,

步骤三、衰减因子；

设定定义：衰减因子，设定两个时间层网络中对应节点i的层间相似性会随时间间隔Δt增加而变弱。基于网络数据所呈现的不同分布函数中的相似部分，即指数，定义如下衰减因子：

式中，Δt＝t

最终，层间耦合关系的度量公式如下：

式中，1≤t

步骤四、基于层间耦合强度衰减的超邻接矩阵时序网络建模方法；

给定时序网络G＝(V,E,T)，定义层间耦合强度衰减的超邻接矩阵时序网络建模方法，即用特定时间层网络的邻接关系表示层内连接关系，用步骤三中的计算层间耦合关系的方法表示层间连接关系，其表现形式如下：

式中，ASAM是层间耦合强度衰减的超邻接矩阵，

另一实施例中，如图4所示，本发明又公开了一种基于层间耦合关系强度衰减的时序网络的重要节点识别系统，包括：

层间耦合强度衰减的超邻接矩阵计算模块，采用上述的基于层间耦合关系强度衰减的时序网络建模系统得到层间耦合强度衰减的超邻接矩阵；

重要节点识别模块50，计算特征向量中心性，完成节点重要性排序；

在构造ASAM超邻接矩阵后，通过计算特征向量中心性来表示节点的重要性。即根据超邻接矩阵ASAM求主特征向量Y＝{y

本实施例的有效性可以通过下面的仿真实验来进一步说明。

1)仿真条件：

操作系统Windows10,CPU:nter(R)Core(TM)i7-5500U@2.40GHz,内存8GB，硬盘500GB，编程环境Pycharm，软件Python3.7。

2)仿真内容：

用于仿真实验的数据集包括四个真实网络：Enrons2001、Highschool3、Emaildept3、Workspace网络。表1显示了四个真实网络的基本统计信息。其中N,C,T分别表示节点总数，节点之间交互的总次数，切分的时间层数。

表1数据集的基本特征

3)对比方法

SAM.作为一个基准比较方法，该方法将层间耦合关系用固定参数表示。

SSAM.考虑到固定参数不能表现层间耦合关系的差异性，该方法利用邻居拓扑重叠系数(节点在两个相邻时间层网络中的共同邻居数量所占的比例似性，邻居拓扑重叠系数可以描述节点持续出现度及节点邻居关系的层间相似性，该系数越大表示节点持续出现在两个相继时间层，且邻居关系保持稳定。

4)评价方法

为了验证本发明方法的效果，基于网络性能的变化来评价该方法。通过删除一定比例的节点后，观察时序网络的连通性的变化程度来评价各个方法。一般认为，删除节点后，网络的连通性变化较大，则被删除的节点在网络越重要，反之，节点的重要性相对较低。

网络的时序最大连通分量是衡量网络可达性的一个指标，是时序网络最大连通图中的节点数占整个网络所有节点的比例。其具体表现形式如下：

式中，

其次本文通过直接删除前σ比例的节点计算网络性能的变化。具体过程是首先按节点的识别方法对节点重要性排序，然后分别衡量节点未删除时的网络性能及节点删除后的网络性能，然后比较两者的差值。记累积删除σ比例节点后的时序网络性能为E(G\σ)，得到计算公式如下：

上式计算的值越大，说明删除的节点对网络性能的影响越大，说明节点越重要，识别方法越好。

5)仿真实验分析

参照图5a-5l，图6a-6l，首先通过SAM、SSAM及ASAM模型计算出节点在各个时间层网络的特征向量中心性。然后通过删除各个时间层网络的一定比例的节点，计算此时时序网络的时序最大连通分量；计算网络性能的变化。最后，进行结果分析。

图5a-5c表示EmailDept3数据集上依次删除前20、30、40的节点后时序最大连通分量变化情况；图5d-5f表示Enrons数据集上依次删除前25、35、45的节点后时序最大连通分量变化情况；图5g-5i表示Highschool3数据集上依次删除前20、40、60的节点后时序最大连通分量变化情况；图5j-5l分别表示Workspace数据集上依次删除前10、20、30的节点后时序最大连通分量变化情况。图6a-6l表示相应数据集上的网络性能变化情况。

从图5a-5l可以看出，删除用ASAM方法识别出的重要节点后，网络的时序最大连通分量值整体均小于用SAM及SSAM方法识别出的重要节点，其中ASAM方法的结果相比SAM方法，时序最大连通分量在EmailDept3、Enrons、Highschool3及workspace数据集上分别最高减少了2.84％、1.72％、1.27％及2.17％，相比SSAM方法，时序最大连通分量在EmailDept3、Enrons、Highschool3及workspace数据集上分别最高减少了2.84％、1.72％、1.20％及1.52％。说明ASAM方法识别出的重要节点对网络的连通性破坏程度更大，则删除的节点在整个网络中越重要。

但是我们发现在个别的时间层网络，例如EmailDept3数据集T＝4时；WorkSpace数据集T＝7时，删除用ASAM方法识别出的重要节点后，网络的时序最大连通分量大于用SAM及SSAM方法识别出的重要节点，这是由于实际数据的影响所造成的(将时序网络切分后，各个切片网络的结构是不同的)。

网络性能的变化是考察节点对网络结构的影响力的评价指标。从图6a-6l可以明显看出，删除SAM、SSAM及ASAM方法得到的top-σ节点后，ASAM方法识别出的节点删除后，网络的性能变化整体上大于SAM和SSAM方法识别出的重要节点，且对Highschool3数据集的结果尤为显著。其中ASAM方法的结果相比SAM方法，网络性能在EmailDept3、Enrons、Highschool3及workspace数据集上分别最高增加了41.87％、59.03％、45.24％及42.54％；相比SSAM方法，网络性能在EmailDept3、Enrons、Highschool3及workspace数据集上分别最高增加了41.87％、59.03％、42.86％及76.95％。说明用ASAM识别出的节点对网络性能的影响越大，同时也说明删除的节点越重要，ASAM方法的性能越好。

我们发现，在个别的时间层网络，例如EmailDept3数据集T＝4时、WorkSpace数据集T＝7时，ASAM方法的结果会比SAM和SSAM方法差，这是因为将时序网络按不同的时间间隔切分后，各个切片网络的结构是不同的。并且如何对时序网络切分一直以来都是一个困难的问题。

综上所述，从网络的时序最大连通分量和网络性能变化两个角度进行分析，ASAM方法均明显优于SAM和SSAM方法，即证实了本文提出ESI指标及衰减因子可以更准确的量化各个切片网络之间的层间耦合关系，同时说明本文提出的ASAM模型更能准确的计算节点在各个切片网络的重要性，则ASAM方法得到的节点重要性排序更准确。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。