本体演化的波及效应计算优化研究

鉴于使用Floyd-Warshall算法对规模较大的本体评估具有时间复杂度与空间复杂度较高且未考虑本体演化过程中各版本之间的关联，提出基于邻接表的SPFA（shortest path faster algorithm）优化波及效应的计算。该算法不仅在大规模本体计算中具有计算效率的优势，而且可以简化版本迭代过程中波及效应的计算过程。实验结果表明，使用SPFA在计算本体的波及效应相比于基于邻接矩阵的方式具有一定的时间优势，并且这种优势随着时间的变化逐渐增加；在本体演化的波及效应计算时间中，本体演化后的版本的计算时间大约与原有方法相差较少，证明了优化计算的有效性。

Improved method for ripple effect calculation in ontology evolution

In view of the use of Floyd-Warshall algorithm, the large-scale ontology evaluation had higher time complexity and higher space complexity and didn''t consider the association between versions in the ontology evolution process, this paper proposed the calculation of the ripple effect optimized by the SPFA(shortest path faster algorithm) algorithm based on the adjacency list. The algorithm not only had the advantage of computational efficiency in large-scale ontology calculation, but also could simplify the calculation process of the ripple effect in the iterative process. The experimental results show that the SPFA has a certain time advantage in calculating the ontology ripple effect compared with the adjacency matrix based method, and this advantage gradually increases with time. In the ontology evolution ripple effect calculation time, the calculation time of the evolved version is about the original method, which proves the effectiveness of the optimization calculation.