%A CHENG Fu-hao, XU Tai-hua, CHEN Jian-jun, SONG Jing-jing, YANG Xi-bei %T Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory %0 Journal Article %D 2022 %J Computer Science %R 10.11896/jsjkx.210700202 %P 97-107 %V 49 %N 8 %U {https://www.jsjkx.com/CN/abstract/article_20954.shtml} %8 2022-08-15 %X Strong connected components (SCCs) mining is one of the classic problems in graph theory.It has practical requirements to design a serial SCCs mining algorithm with high efficiency.GRSCC algorithm can use SUB-RSCC function to discover SCCs of simple digraphs.SUB-RSCC function is formed by two operators of rough set theory (RST),k-step upper approximation set and k-step R-related,which are the main contributors to time consumption.Then the invocation times of SUB-RSCC decide the efficiency of GRSCC algorithm.Based on the SCCs correlations among vertices,GRSCC algorithm introduces granulation strategy to reduce the invocation times of SUB-RSCC function,then improve the mining efficiency.Two new SCCs correlations are found by analysis of SCCs in the framework of RST,then a new vertex granulation strategy is designed to granulate the vertex set of target digraphs.In order to reduce the invocation times of SUB-RSCC function to a greater extent,a method called k-step search of vertex granule is proposed.Finally,combining with GRSCC algorithm,an algorithm called KGRSCC for mining SCCs based on k-step search of vertex granule and RST is proposed.Experimental results show that,compared with RSCC,GRSCC and Tarjan algorithms,the proposed KGRSCC algorithm has better performance.