%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.