基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法

摘要：

强连通分量挖掘是图论中的经典问题之一,如何设计更高效率的串行强连通分量挖掘算法具有现实需求.GRSCC算法利用k步上近似和k步R相关集这两个粗糙集算子所构成的SUB-RSCC函数,可实现简单有向图中的强连通分量挖掘,而SUB-RSCC函数的调用次数决定了挖掘效率.根据挖掘强连通分量时顶点间存在的相关性,GRSCC算法引入了粒化策略,减少了SUB-RSCC函数的调用次数,提高了挖掘效率.在GRSCC算法的基础上,分析发现了顶点间的另外两种强连通分量相关性,由此设计了一种新的顶点粒化策略,进而提出了一种顶点粒k步搜索方法,可更大程度地减少SUB-RSCC函数的调用次数.最后,提出了一种基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法KGRSCC.实验结果表明,相比RSCC算法、GRSCC算法和Tarjan算法,KGRSCC算法具有更好的性能.

关键词：强连通分量、粗糙集、图论、粒化策略、顶点粒k步搜索

所属期刊栏目：49

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;江苏省高等学校自然科学基金;镇江市重点研发计划

在线出版日期：2022-08-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：97-107