一种改进的K-Reach索引的快速创建算法

摘要

基于经典网络可达性问题的k可达性问题对于无线网络、社交网络等新型网络具有重要意义。最新提出的K-Reach[1]可以快速地计算任意两个顶点之间是否存在长度小于为k的路径。注意到随着K-Reach索引的逐步建立,已经计算过的顶点包含其所有可达顶点的路径信息。因此,提出一种改进的K-Reach索引创建算法,其充分利用了这些路径信息,避免了重复访问大量顶点,从而提升了算法效率。通过对不同实际数据进行的实验表明,改进算法所用时间明显小于原始算法。