一种支持增量更新的时态网络模体计算方法及系统

摘要

本发明通过人工智能处理领域的方法，实现了一种支持增量更新的时态网络模体计算方法及系统。包括：获取时态图数据和用户指定的频度阈值k；将时态图处理为能高效使用的数据结构；根据频度阈值k计算整个时态图上所有符合定义的时态网络模体；时态图动态更新后，根据已有计算结果，增量更新时态网络模体计算结果。本发明提供的方法及系统用以解决现有时态网络模体计算方法涉及子图同构检查，计算复杂度较高，效率低下且模体大小受到限制的问题，并实现在不限制时态网络模体结构大小的情况下的一种计算复杂度低、能够实时更新的时态网络模体计算方法。

说明书

技术领域

本发明涉及动态网络、图数据库搜索技术领域，尤其涉及一种支持增量更新的时态网络模体计算方法及系统。

背景技术

现实世界大量领域可通过图(graph)来建模，如社交网络、计算机网络等，原因在于图即能够表达数据实体，又能表达数据之间联系，现已作为新型数据存储结构得到充分使用。网络模体(network motif)是指大图中反复出现、统计显著的子图或模式，由于能使人们对复杂网络的结构与功能有深入地理解，现已应用到生物学网络、社交网络、电子电路、软件架构、交通运输网络等。随着大数据的发展，图的动态性研究在使用图建模的分析系统和应用中逐渐重要，由于各界的不同应用，分别有时态网络(temporal network)、动态图(dynamic graph)、演化网络(evolving network)、进化网络(evolutionary network)、图流(graph stream)等不同的术语来描述图的动态性。作为用于理解复杂网络的网络模体，在图的动态性研究中网络模体计算是必要的。本发明涉及的是其中一类重要的时态网络，即顶点和边保持固定、边随时间不断变化的网络，因此该类网络可视为由网络在每个时刻的快照(snapshot)组成，道路交通网络就是典型的该类网络，在城市计算中有重要应用。总之，时态网络模体计算就是在给定时态图数据的情况下，计算图中符合定义要求的网络模体。

对于时态网络模体计算，有以下几个方面直接关系到其在应用时的质量和效率。第一，时态网络模体定义的易用性，需要设计在实际应用中能够有价值的时态网络模体定义。第二，时态网络模体计算方法的复杂度，时态网络模体计算方法复杂度过高会导致需要过多时间计算结果，致使方法在大图中效率过低从而限制方法的应用可行性。第三，时态网络的动态性，时态网络模体计算方法需要在时态网络动态更新后，动态地处理计算结果，而非全部重新计算，使方法在数据动态更新的实际场景下也能得到应用。

现有的时态网络模体计算方法都将网络模体定义在边随时间变化的时态网络中，且根据不同的应用需要有不同的时态网络模体定义，包括边的时间属性之间有偏序、全序等不同的时序关系，以及整个模体每条边的时间属性满足全局、局部等不同的时序窗口。然而现有计算方法都具有以下缺点：1)计算复杂度过高,由于这些方法都基于同构或子图同构(subgraph isomorphism，是NP-complete问题)，导致基于子图同构的模体计算方法计算耗时过长，现有方法往往要求限定模体的结构大小(边数、顶点数)，因此无法在大图中的各类应用中广泛使用；2)没有考虑时态网络的动态性，时态网络在实际应用中随时间不断变化，时态网络模体的计算结果也会相应更新，方法重新计算整个结果的代价高，因此亟需支持动态更新的时态网络模体方法。

从技术背景介绍中可以看出，当前时态网络模体计算方法存在诸多问题。

首先，当前时态网络模体计算方法的计算效率存在问题。大数据时代下的图数据是海量的，现有时态网络模体计算方法涉及子图同构检查，计算复杂度较高，在大图中计算时态网络模体的效率更是难以接受的，实用性差。

其次，当前时态网络模体的结构大小定义有局限性。为了能够短时间计算时态网络模体，现有方法限制了时态网络模体的结构大小，不利于实际使用。

再次，当前时态网络模体计算方法的无法适应动态更新场景。实际场景中时态网络动态更新，要求方法能够快速计算结果，当前时态网络模体计算方法只支持计算全部结果，而无法支持动态更新，即在原有结果基础上进行更新和计算得到新的结果，限制了这些方法的实际使用。

发明内容

为此，本发明首先提出一种支持增量更新的时态网络模体计算方法及系统，将实体网络传感器记录的时态信息参数及网络结构作为时态图数据，如道路交通网络传感器记录的道路的在每个时间的拥堵状况或电力系统传感器记录的每个地区在每个时间的用电量等，输入，首先以静态方法计算结果模体集合，进而对于动态增量更新的时态图，在所述静态方法的基础上，以增量计算方法更新计算最终结果时态网络模体集合，输出所有在长时间内保持时态信息参数不变的连通时态子图，即时态网络模体，如若干个由多条连通道路组成的拥堵区域及区域内道路共同持续拥堵时段，或若干个由多个连通管道组成的用电高峰区域及用电持续高峰时段；

所述静态方法计算结果模体集合基于三角化的区间列表计算网络模体，对于一个极大且不可扩展的时态模体

所述静态方法的八个步骤包括：静态步骤一：读取时态图G和频度阈值k；静态步骤二：初始化当前计算行号m＝1；静态步骤三：从边集E中选出三角化的区间列表第m行各区间中保持标签不变的边；静态步骤四；初始化当前计算列号i＝T，T＝T

所述静态步骤三或所述增量步骤三的具体实现方式为：定义集合S[m，i]为边集E中在区间[m，i]中保持标签不变的所有边；定义集合R[m，i]为S[m，i]和S[m，i+1]的差集，其中m+k-1≤i＜T，且R[m，T]＝S[m，T]；每个集合R[m，i]表示在区间[m，i]中保持标签不变的边集；定义集合EMaxIntvl为每条边e对应的最大区间，集合EMaxIntvl包含区间[m，m+k-1]，边e在[m，m+k-1]区间中保持标签不变，且该区间扩大后无法保持标签不变；

那么所述静态步骤三或所述增量步骤三的实现方式为：首先，初始化每个集合R[m，i]为空集；其次，从边集E中取第1条边e；之后，从初始化为空集的集合EMaxIntvl中取区间EMaxIntvl[e]，记作[m′，i′]；如果EMaxIntvl[e]为空，或i′＜m，计算一个最大区间，记作[m*，i*]，并满足集合EMaxIntvl的条件，如果[m*，i*]存在，更新EMaxIntvl[e]为[m*，i*]，边e保存至集合R[m*，i*]；如果i′≥m+k-1，边e保存至集合R[m，i′]；如果m≤i′＜m+k-1，不进行任何操作；最后从边集E中取下1条边e，继续从集合EMaxIntvl中取区间；如果所有边都已遍历，步骤结束。

所述静态步骤五或所述增量步骤五的具体实现方式为：首先，初始化集合CC[i，T]为空集；之后，从集合R[m，i]中取第1条边e，判断边e与集合CC[i，T]中各连通分量的连通性，如果边e与任何连通分量都不连通，则构建新的连通分量G

所述静态步骤六或所述增量步骤六的具体实现方式为：首先，对于每执行一次所述静态步骤五，保存左不可扩展的时态模体，即当构建区间为[m，i]的极大且不可扩展的时态模体时，已经求得所有区间[m，i′]，的极大且不可扩展的时态模体，m′＜m或m′＝m，i＜i′≤T，那么记区间为[m，i]的时态模体集合为TF[m，i]，初始化集合TF[m，i]为空集；从集合CC[i，T]中取第1个在所述静态步骤五中有更新的连通分量G

所述增量计算方法的十个步骤包括：增量步骤一：读取增加ΔT时刻更新后时态图G[1，T+ΔT]、频度阈值k和已计算结果模体集合TF；增量步骤二：初始化当前计算行号m＝1；增量步骤三：从边集TF[m，T]中选出TI-Table第m行各区间中保持标签不变的边；增量步骤四：初始化当前计算列号i＝T+ΔT；增量步骤五：使用增量步骤三中所选的在区间[m，i]中保持标签不变的边，构建区间为[m，i]的极大时态模体；增量步骤六：保存增量步骤五中左不可扩展的时态模体到最终结果TF[m，i]中；增量步骤七：判断列号i是否大于T，如果是，将列号i减小1，转至步增量步骤五继续；增量步骤八：将行号m增大1，判断行号m是否大于T-k+1，如果否，转至增量步骤三继续；增量步骤九：执行所述静态方法的八个步骤；增量步骤十：判断行号m是否小于T+ΔT-k+1，如果是，将行号m增大1，转至增量步骤九继续；如果否，则输出更新后的最终结果模体集合TF。

获取模块，用于获取时态图数据和用户指定的频度阈值k；时态图处理模块，用于将所述时态图处理为时态网络模体计算模块和时态网络模体增量计算模块能高效使用的数据结构；时态网络模体增量计算模块，应用权利要求1-6中任一所述的支持增量更新的时态网络模体计算方法，计算输出增量更新时态网络模体计算结果。

本发明所要实现的技术效果在于：

(1)提出一种新的时态网络模体及其若干扩展性质(如maximal、expandable等)，要求模体在顶点和边保持固定、边随时间不断变化的网络中持续出现足够长时间，符合原有网络模体要求的反复出现、统计显著性质，有实际使用价值。

(2)基于新型时态网络模体，在不限制时态网络模体结构大小的情况下，提出一种时态网络模体计算方法，计算复杂度低，能够在低阶多项式时间内高效计算，适合在大图场景下应用。

(3)该新型时态网络模体计算方法能有效支持增量更新环境下的计算，在时态网络更新后，仅需要根据已计算结果和一定范围内的图数据信息，得到新计算结果。

(4)本发明对于现实中的时态图数据输入，如道路交通网络图数据、电力系统图数据进行输入，针对网络的实时更新，输出所有在长时间内保持时态信息参数不变的连通时态子图。

附图说明

图1时态图与时态模体；

图2计算方法的基础区间列表TI-Table

图3新型时态网络模体计算方法基本流程图

图4新型时态网络模体增量更新计算方法基本流程图

图5新型时态网络模体增量更新计算系统实施例的结构示意图

具体实施方式

以下是本发明的优选实施例并结合附图，对本发明的技术方案作进一步的描述，但本发明并不限于此实施例。

本发明提出了一种支持增量更新的时态网络模体计算方法及系统。为了实现上述的发明目的，将实体网络传感器记录的时态信息参数及网络结构作为时态图数据输入，首先提出一种新型时态网络模体，并基于该模体，给出一种新型时态网络模体计算方法，最后给出该方法的支持增量更新机制，以此输出所有在长时间内保持时态信息参数不变由多条连通图组成的网络内参数峰值构成的连通时态子图，即时态网络模体。

时态网络模体计算问题基本概念定义：

时态图：时态图G(V，E，L，T

时态图的示意图如图1(a)所示，是一个区间为[1，6]的时态图。可以直观地看出，(1)一个时态图G(V，E，L)本质上是一个由T＝T

时态子图：时态图

时态模体：时态子图

可扩展的时态模体：时态模体

极大的时态模体：时态模体

时态网络模体计算问题：给定一个时态图G(V，E，L，T

静态的新型时态网络模体计算方法：

给出了时态模体相关定义及问题定义后，本发明下面给出该时态网络模体的计算方法。为方便起见，假定起始时间T

容易得知，所有极大且不可扩展的时态模体

具体来讲，计算过程分为以下几步：

(1)读取时态图G和频度阈值k

(2)初始化当前计算行号m＝1

(3)从边集E中选出TI-Table第m行各区间中保持标签不变的边(computeRES)

(4)初始化当前计算列号i＝T

(5)使用(3)中所选的在区间[m，i]中保持标签不变的边，构建区间为[m，i]的极大时态模体(generateMaxTM)

(6)保存(5)中左不可扩展的时态模体到最终结果TF[m，i]中(generateExpTM)

(7)判断列号i是否大于m+k-1。如果是，将列号i减1(R2L)，转至步骤(5)继续

(8)判断行号m是否小于T-k+1。如果是，将行号m增1(T2B)，转至步骤(3)继续；如果否，则输出最终结果模体集合TF

下面分别对其中的步骤(3)、(5)和(6)展开描述。

步骤(3)：从边集E中选出TI-Table第m行各区间中保持标签不变的边(computeRES)

定义集合S[m，i]为边集E中在区间[m，i]中保持标签不变的所有边；定义集合R[m，i]为S[m，i]和S[m，i+1]的差集(m+k-1≤i＜T)，且R[m，T]＝S[m，T]。由于集合R[m，i]两两互斥，因此每个集合R[m，i]可以用来表示在区间[m，i]中保持标签不变的边集，且这些边不能在区间[m，i+1]中保持标签不变。基于以上性质，步骤(3)就是在计算集合R[m，i](m+k-1≤i≤T)。

记集合EMaxIntvl为每条边e对应的最大区间，满足：(1)包含区间[m，m+k-1]，(2)边e在该区间中保持标签不变，且该区间扩大后无法保持标签不变。下面给出步骤(3)的具体流程。

1)初始化每个集合R[m，i]为空集

2)从边集E中取第1条边e

3)从集合EMaxIntvl(初始化为空)中取区间EMaxIntvl[e]，记作[m′，i′]

4)如果EMaxIntvl[e]为空，或i′＜m，计算一个最大区间(记作[m*，i*])，并满足集合EMaxIntvl的2个条件。如果[m*，i*]存在，更新EMaxIntvl[e]为[m*，i*]，边e保存至集合R[m*，i*]

5)如果i′≥m+k-1，边e保存至集合R[m，i′]；如果m≤i′＜m+k-1，不进行任何操作。

6)从边集E中取下1条边e，转至步骤3)继续；如果所有边都已遍历，步骤结束

步骤(5)：构建区间为[m，i]的极大时态模体(generateMaxTM)

步骤(5)的主要功能是使用步骤(3)中计算的集合R[m，i]中的边，构建区间为[m，i]的极大时态模体。由于采用自顶向下、自右向左方式，当构建区间为[m，i]的极大时态模体时，已经求得所有区间[m，j](j∈[i+1，T])的极大且不可扩展的时态模体、第1行到第m行的集合R[m，i]。用连通分量集合CC[i，T]表示由边集合S[m，i]＝R[m，i]∪R[m，i+1]∪...∪R[m，T]中所有边构成的连通分量。步骤(5)就是将集合R[m，i]中的边添加到集合CC[i+1，T](为方便起见，用集合CC[T+1，T]表示为空集)，根据连通性计算集合CC[i，T]，其中每个有更新的连通分量对应一个极大的时态模体。下面给出步骤(5)的具体流程。

1)初始化集合CC[i，T]为集合CC[i+1，T]

2)从集合R[m，i]中取第1条边e

3)判断边e与集合CC[i，T]中各连通分量的连通性

4)如果边e与任何连通分量都不连通，则构建新的连通分量G

5)如果边e与一个连通分量G

6)如果边e与两个连通分量G

7)从集合R[m，i]中取下1条边e，转至步骤3)继续；如果所有边都已遍历，步骤结束

步骤(6)：保存左不可扩展的时态模体(generateExpTM)

步骤(6)的主要功能是保存步骤(5)中左不可扩展的时态模体到最终结果TF[m，i]中，这是基于步骤(5)求得的极大时态模体都是右不可扩展的性质。每执行一次步骤(5)，就从中保存左不可扩展的时态模体，即当构建区间为[m，i]的极大且不可扩展的时态模体时，已经求得所有区间[m，i′](m′＜m或m′＝m，i＜i′≤T)的极大且不可扩展的时态模体。

记区间为[m，i]的时态模体集合为TF[m，i]，下面给出步骤(6)的具体流程。

1)初始化集合TF[m，i]为空集

2)从集合CC[i，T]中取第1个在步骤(5)中有更新的连通分量G

3)记G

4)从集合CC[i，T]中取下1个在步骤(5)中有更新的连通分量G

新型时态网络模体的增量计算方法：

下面给出新型时态网络模体的增量计算方法。由于对动态性的支持，增量计算方法相比直接使用静态的新型时态网络模体计算方法的效率要高。新型时态网络模体的增量计算方法的流程图如图4所示。

具体来讲，计算过程分为以下几步：

(1)读取更新后时态图G[1，T+ΔT]、频度阈值k和已计算结果模体集合TF

(2)初始化当前计算行号m＝1

(3)从边集TF[m，T]中选出TI-Table第m行各区间中保持标签不变的边(computeRES)

(4)初始化当前计算列号i＝T+ΔT

(5)使用(3)中所选的在区间[m，i]中保持标签不变的边，构建区间为[m，i]的极大时态模体(generateMaxTM)

(6)保存(5)中左不可扩展的时态模体到最终结果TF[m，i]中(generateExpTM)

(7)判断列号i是否大于T。如果是，将列号i减小1(R2L)，转至步骤(5)继续

(8)将行号m增大1(T2B)，判断行号m是否大于T-k+1。如果否，转至步骤(3)继续；(9)执行静态方法(3.2.2中的方法)

(10)判断行号m是否小于T+ΔT-k+1，如果是，将行号m增大1(T2B)，转至步骤(9)继续；如果否，则输出更新后的最终结果模体集合TF，

与静态的新型时态网络模体计算方法相比，本发明的增量计算方法如下特点：1)在步骤(3)中从边集E中选边更改为从边集TF[m,T]中选边，最小化了计算范围，避免冗余计算；2)在行号m不大于T-k+1时，仅仅计算区间为[m,j](T≤j≤T+ΔT)的时态模体，其他区间的时态模体已经计算，无需重复计算；3)只有在行号m大于T-k+1时，增量计算方法才与静态方法步骤相同。综上所述，增量计算方法具有效率上的优势。