本发明涉及图计算领域，具体来说涉及增量图计算领域，更具体地说，涉及用于电网分析应用的增量图计算方法及计算系统。
背景技术：
1、在当前大数据与高速网络技术快速发展的背景下，电网系统中数据的规模、多样性和增长速度也呈现出前所未有的扩张。作为一种能够有效描述复杂系统内部各组成部分之间互动的结构化数据类型，图数据在电力系统的监控、优化及故障分析等多个电网应用领域中发挥着重要作用。在电网管理等应用场景中，设备和节点之间的互动及状态持续变化，使得电网结构日益复杂化，由此导致的图中节点和边的持续增加，迫切需要动态图来描述这些变化。然而，传统的大规模静态图计算系统在面对如此动态的电网图数据时，常常因无法实时捕捉和精确更新图结构变化而表现不佳。此外，传统图算法往往不适应快速变化的电网图场景，图数据的动态变化还会导致计算复杂度的大幅增加，从而使得现有系统难以实时更新计算结果。
2、针对这些问题，许多研究者已开始探索和发展动态图计算系统，特别是基于增量图计算的系统。这类系统通过存储之前的计算中间结果，有效减少了重复计算的需要，从而显著提高了图计算性能。由于电网结构的变化通常仅涉及局部区域，增量图计算系统能够重用现有的计算结果，并仅针对变化部分执行必要的计算，大幅提高了处理效率。这种策略不仅使动态图计算系统能够更加高效地管理动态电网数据，还提升了数据分析的速度，并能实时返回用户所需的数据挖掘算法结果。尽管电网数据规模的增大和复杂性的提升为增量图计算系统带来了新的挑战，这些挑战也带来了在大规模动态电网数据中挖掘深层知识和价值的重大机遇，从而使得这种系统在多个电网相关领域中找到了广泛应用。
3、在动态电网拓扑分析中，增量图计算系统通过存储每次迭代的中间结果(例如顶点状态信息或传递的消息)来避免不必要的重复计算，极大地提升了计算效率。这种增量计算推动了图计算系统的发展。为了缓解中间结果在内存中占用过大的问题，不同的系统采取了各自的策略：一些系统选择仅存储顶点的最终状态信息和依赖关系，支持那些单调收敛的图算法；另一些系统则选择不直接存储中间结果，仅维护依赖关系，适用于对初始状态不敏感的图算法；还有的系统则根据不同的图算法需求，设计了多样的中间结果存储策略，旨在减少内存使用和保持系统通用性之间找到平衡。然而，在处理大规模电网分析应用时，特定的拓扑分析算法仍然不可避免地需要存储所有迭代过程中的中间结果。随着电网图数据规模的持续增长，中间结果的存储对内存的需求也越来越大，这不仅严重加剧了系统的内存压力，还可能影响到系统的性能和扩展性。特别是在电网运行监测、故障预测与响应等关键应用中，数据实时性和处理效率的要求异常严格，现有的图计算系统在处理动态、大规模的电网图数据时面临的挑战尤为突出。
4、基于上述分析，现有增量图计算系统存在以下问题：(1)现有增量图计算系统基于增量图原始结构进行图计算，存在许多冗余的遍历和迭代操作，这不仅增加了计算的复杂度，还生成了过多的中间结果，进而导致存储资源的大量占用。(2)尽管现有系统采用内存存储器来存储中间结果可以提高读取速度，但这种存储策略在面对大量中间数据时，对内存资源造成了极大的压力，可能影响系统的稳定性、响应速度及可扩展性。
5、需要说明的是：本背景技术仅用于介绍本发明的相关信息，以便于帮助理解本发明的技术方案，但并不意味着相关信息必然是现有技术。在没有证据表明相关信息已在本发明的申请日以前公开的情况下，相关信息不应被视为现有技术。
技术实现思路
1、因此，本发明的目的在于克服上述现有技术的缺陷，提供一种内外存结合增量图计算系统
2、本发明的目的是通过以下技术方案实现的：
3、根据本发明的第方面，提出一种增量图计算方法，用于对不断变化的图数据进行计算，所述方法包括：图层构建步骤：基于原始图数据构建用于计算的三层结构图，该三层结构图包括原始图层、中间子图层、顶层图层，其中：原始图层为原始图数据对应的顶点和边构成的图结构；中间子图层包括多个中间子图结构，每个中间子图结构为原始图层依次进行图结构简化、子图划分后得到的多个子图中的一个子图的内部顶点与边组成的图结构，每个子图对应于一个中间子图结构；顶层图层为由所有子图的出口顶点与入口顶点组成的图结构；计算步骤：响应图数据的变化，通过调整三层结构图的内部结构以实现不断变化的图数据的增量计算，每次计算进行多轮迭代直至图结构收敛，其中，在计算过程中，用外存储器存储图计算的所有中间结果，用内存储器动态存储图计算的部分中间结果，并且在外存储器和内存储器中均以中间子图结构为存储单位进行中间结果的读取或存储，其中，顶层图层的所有中间结果作为一个整体进行存储。
4、优选的，所述图层构建步骤包括：图结构简化：识别原始图层中的强连通分量，为每个强连通分量配置一个代表顶点，并将每个强连通分量内所有顶点与该强连通分量对应的代表顶点相连，以及将强连通分量内所有顶点与外部顶点相连的边重定向至该强连通分量对应的代表顶点使得所有代表顶点与其他顶点组成新的图结构以实现图结构简化；子图划分：将简化后的图结构划分成为若干个子图，其中，每个子图的顶点数量不超过预设阈值；中间子图层构建：提取每个子图中的出口顶点和入口顶点以外的所有顶点及这些顶点之间的连边，以构成与该子图对应的中间子图结构，所有中间子图结构组合成中间子图层；顶层图层构建：提取所有子图的入口顶点与出口顶点以及这些顶点间的连边，并将其组合以构成顶层图层。
5、优选的，所述预设阙值通过以下方式确定：
6、
7、其中，k为预设阙值，g为简化后的图结构的顶点数。
8、优选的，通过如下方式调整三层结构图的内部结构：响应图数据的变化，判断图数据变化的类型：若图数据变化类型为删除节点或边，则重构三层图结构；若图数据变化类型为增加节点或边，则判断增加的量级，若为增加小于或等于10条边的图数据变化，则在已有的三层图结构上进行从上之下的调整，反之，则重构三层图结构。
9、优选的，对于增加小于或等于10条边的图数据变化，通过如下方式在已有的三层图结构上进行从上之下的调整:将新增的边直接添加至顶层图层，在顶层图层上执行图遍历直至顶层图层收敛；汇聚顶层图中每个顶点的状态值更新，将汇聚结果同步更新至中间子图层中的顶点，完成状态值的跨层传递。
10、优选的，通过如下方式在外存储器中存储图计算的所有中间结果：增量计算中的每轮计算结束后，在外存储器中划定一个新的存储分区，将当前迭代轮次产生的所有中间结果划分为多个存储单元，并储存至对应的存储分区，其中，中间子图层的中间结果以中间子图结构为单位划分为多个存储单元，顶层图层的所有中间结果作为一个存储单元。
11、优选的，通过如下方式在内存储器中动态存储图计算的部分中间结果：基于预设顶层图缓存区大小在内存储器划分出顶层图缓存区用于储存顶层图层中顶点的中间状态，以及基于预设中间子图缓存块大小与数量在内存储器划分出包含多个大小相同的中间子图缓存块的中间子图缓存区用于分别存储多个中间子图结构中的部分中间结果，其中，每个中间子图缓存块储存一个中间子图结构中的部分中间结果。
12、优选的，所述预设的顶层图缓存区大小为顶层图层顶点数与单个中间结果大小的乘积。
13、优选的，所述预设中间子图缓存块大小通过如下方式确定：
14、m＝1/3*(k*α)*b
15、其中，m为中间子图缓存块的大小，k为子图的顶点数，α为修正系数，b为单个中间结果大小；所述预设中间子图缓存块数量通过如下方式确定：基于确定的预设中间子图缓存块大小配置中间子图缓存块的大小，随机改变中间子图缓存块数量形成多个中间子图缓存区模型，并评估每个中间子图缓存区模型的缓存命中率以及占用的存储空间，筛选出其中性能最优的中间子图缓存区模型，并以此模型的中间子图缓存块数量作为预设的中间子图缓存块数量，其中，所述缓存命中率为计算过程中，在中间子图缓存区中成功获取到的中间结果的次数与尝试获取中间结果的总次数的比率。
16、优选的，在每轮计算中，中间子图缓存区存储的中间子图结构的部分中间结果基于启发式缓存替换策略进行动态替换。
17、优选的，所述基于启发式缓存替换策略进行动态替换包括：响应计算访问需求，若中间子图缓存区中不存在计算需要的中间结果，从外存储器中读取该中间结果所属中间子图结构对应的存储单元，并基于预设中间子图缓存块的大小从读取的存储单元中提取该中间结果及其相邻的多个中间结果，以构建目标中间子图缓存块；判断当前中间子图缓存区内中间子图缓存块的占用情况，若中间子图缓存块占用数量小于预设中间子图缓存块数量，将目标中间子图缓存块添加至中间子图缓存区；反之，根据每个中间子图缓存块的优先级对所有子图缓存块进行排序，将优先级最低的中间子图缓存块替换为目标中间子图缓存块，其中，所述中间子图缓存块的优先级由其顶点的平均度数确定，平均度数越高对应的中间子图缓存块的优先级也越高。
18、根据本发明的第二方面，提出一种基于本发明第一方面任一所述方法的增量图数据计算系统，用于对图数据进行增量计算，所述系统包括：图结构管理模块，用于将原始图数据构建成从顶层至底层依次为顶层图层、中间子图层、原始图层的三层结构图，以及在增量计算过程中，调整三层结构图的内部结构以适应不断变化的图数据的增量计算；存储模块，其包括外存储器和内存储器，其中，外存储器存储用于存储图计算的所有中间结果，内存储器用于动态存储图计算的部分中间结果，并且在外存储器和内存储器中均以中间子图结构为存储单位进行中间结果的读取或存储，顶层图层的所有中间结果作为一个整体进行存储，其中，所述存储模块被配置为采用启发式缓存替换策略，从外存储器中获取增量计算需要的中间结果，并将其用于更新内存储器内中间子图缓存区存储的中间结果。
19、根据本发明的第三方面，一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序可被处理器执行以实现本发明第一方面任一所述方法的步骤。
20、根据本发明的第四方面，一种电子设备，包括：一个或多个处理器；以及存储器，其中存储器用于存储可执行指令；所述一个或多个处理器被配置为经由执行所述可执行指令以实现本发明第一方面任一所述方法的步骤。
21、与现有技术相比，本发明的优点在于：
22、首先，本发明基于原始增量图构建包含原始图层、中间子图层、顶层图层的三层结构图，并以所构造的增量图作为计算框架，每次增量图的计算操作均限定于中间子图层及顶层图层内部，从而避免了无效的遍历和重复迭代，显著降低了计算的复杂性，并减少了中间结果的生成，优化了存储资源的使用。其次，本发明提出一种基于三层图结构图内外存结合的存储方案，该方案使用外存储器存储图计算的所有中间结果，以利用其较大的存储容量；同时，用内存储器存储数据图计算的部分中间结果，以提高响应速度。此外，本发明还引入了一种启发式缓存替换策略，该策略能够根据实时计算需求，从外存储器中调入必要的中间结果，并根据优先级只能替换内存储器中的数据。根据上述方法构建的图计算系统显著降低了大规模增量图计算过程中的内存占用，相对现有图计算系统平均降幅可达40％-60％，而且还增强了系统的稳定性和扩展性。
1.一种增量图计算方法，用于对不断变化的图数据进行计算，其特征在于，所述方法包括：
2.根据权利要求1所述的方法，其特征在于，所述图层构建步骤包括：
3.根据权利要求2所述的方法，其特征在于，所述预设阙值通过以下方式确定：
4.根据权利要求1所述的方法，其特征在于，通过如下方式调整三层结构图的内部结构：
5.根据权利要求4所述的方法，其特征在于，对于增加小于或等于10条边的图数据变化，通过如下方式在已有的三层图结构上进行从上之下的调整:
6.根据权利要求1所述的方法，其特征在于，通过如下方式在外存储器中存储图计算的所有中间结果：
7.根据权利要求1所述的方法，其特征在于，通过如下方式在内存储器中动态存储图计算的部分中间结果：
8.根据权利要求7所述的方法，其特征在于，所述预设的顶层图缓存区大小为顶层图层顶点数与单个中间结果大小的乘积。
9.根据权利要求7所述的方法，其特征在于，
10.根据权利要求7所述的方法，其特征在于，在每轮计算中，中间子图缓存区存储的中间子图结构的部分中间结果基于启发式缓存替换策略进行动态替换。
11.根据权利要求10所述的方法，其特征在于，所述基于启发式缓存替换策略进行动态替换包括：
12.一种基于权利要求1-11任一所述方法的增量图数据计算系统，用于对图数据进行增量计算，其特征在于，所述系统包括：
13.一种计算机可读存储介质，其特征在于，其上存储有计算机程序，所述计算机程序可被处理器执行以实现权利要求1至11中任一项所述方法的步骤。
14.一种电子设备，其特征在于，包括：
