Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (8): 97-107.doi: 10.11896/jsjkx.210700202

• Database & Big Data & Data Science • Previous Articles     Next Articles

Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory

CHENG Fu-hao1, XU Tai-hua1, CHEN Jian-jun1, SONG Jing-jing1,2, YANG Xi-bei1   

  1. 1 School of Computer,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212000,China
    2 Key Laboratory of Data Science and Intelligent Application,Fujian Province University,Zhangzhou,Fujian 363000,China
  • Received:2021-07-20 Revised:2021-10-23 Published:2022-08-02
  • About author:CHENG Fu-hao,born in 1994, postgraduate.His main research interests include granular computing and graph theory.
    XU Tai-hua,born in 1989,Ph.D,lecture,master supervisor,is a member of China Computer Federation.His main research interests include intelligent information processing,granular computing and graph theory.
  • Supported by:
    National Natural Science Foundation of China(62006099,62076111,61906078),Natural Science Foundation of Jiangsu Provincial Colleges and Universities(20KJB520010) and Key Research and Development Plan of Zhenjiang City－Social Development(SH2018005).

PDF (PC)

451

Abstract: 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.

Key words: k-step search of vertex granule, Granulation strategy, Graph theory, Rough set, Strongly connected components

CLC Number: 

  • TP181
[1]PEARCE D J,KELLY P H,HANKIN C.Efficient field-sensitive pointer analysis of C[J].ACM Transactions on Programming Languages and Systems,2007,30(1):4-14.
[2]BURKE M.An interval-based approach to exhaustive and incremental interprocedural data-flow analysis[J].ACM Transactions on Programming Languages and Systems,1990,12(3):341-395.
[3]YANG H G,SHEN D R,KOU Y,et al.Strongly connectedcomponents based efficient computation of page rank[J].Frontiers of Computer Science,2018,12(6):1208-1219.
[4]ADAMIC L A.The Small World Web [C]//Proceedings of International Conference on Theory and Practice of Digital Lib-raries.Springer,1999:443-452.
[5]IOANNIDIS Y,RAMAKRISHNAN R,WINGER L.Transitive closure algorithms based on graph traversal[J].ACM Transactions on Database Systems,1993,18(3):512-576.
[6]NUUTILA E,SOISALON-SOININEN E.On finding thestrongly connected components in a directed graph[J].Information Processing Letters,1994,49(1):9-14.
[7]PEARCE D J.A space-efficient algorithm for finding strongly connected components[J].Information Processing Letters,2016,116(1):47-52.
[8]TARJAN R.Depth-First Search and Linear Graph Algorithms[J].SIAM Journal on Computing,1972,1(2):146-160.
[9]SHARIR M.A strong-connectivity algorithm and its applica-tions in data flow analysis[J].Computers& Mathematics with Applications,1981,7(1):67-72.
[10]GABOW H N.Path-based depth-first search for strong and biconnected components[J].Information Processing Letters,2000,74(3):107-114.
[11]GAZIT H,MILLER G L.An improved parallel algorithm that computes the BFS numbering of a directed graph[J].Information Processing Letters,1988,28(2):61-65.
[12]FLEISCHER L K,HENDRICKSON B,PINAR A.OnIdenti-fying Strongly Connected Components in Parallel[J].Lecture Notes in Computer Science,2000,1800(4):505-511.
[13]MCLENDON III W,HENDRICKSON B,PLIMPTON S J,et al.Finding strongly connected components in distributed graphs[J].Journal of Parallel and Distributed Computing,2005,65(8):901-910.
[14]BARNAT J,BAUCH P,BRIM L,et al.Computing StronglyConnected Components in Parallel on CUDA [C]//Proceedings of International Parallel and Distributed Processing Sympo-sium.IEEE,2011:544-555.
[15]LOWE G.Concurrent depth-first search algorithms based onTarjan’s Algorithm[J].International Journal on Software Tools for Technology Transfer,2016,18(2):129-147.
[16]PAWLAK Z.Rough sets:Theoretical aspects of reasoning about data[M].Kluwer Academic Publishers,1992.
[17]YAO Y Y,ZHANG X Y.Class-specific attribute reducts inrough set theory[J].Information Sciences,2017,418-419:601-618.
[18]QIAN Y H,LIANG X Y,WANG Q,et al.Local rough set:A solution to rough data analysis in big data[J].International Journal of Approximate Reasoning,2018,97:38-63.
[19]WANG G Y,MA X A,YU H.Monotonic uncertainty measures for attribute reduction in probabilistic rough set model[J].International Journal of Approximate Reasoning,2015,59:41-67.
[20]YANG X B,ZHANG M,DOU H L,et al.Neighborhood systems-based rough sets in incomplete information system[J].Knowledge-Based Systems,2011,24(6):858-867.
[21]YANG X B,YAO Y Y.Ensemble selector for attribute reduction[J].Applied Soft Computing,2018,70:1-11.
[22]YANG X B,LIANG S C,YU H L,et al.Pseudo-label neighborhood rough set:measures and attribute reductions[J].International Journal of Approximate Reasoning,2019,105:112-129.
[23]SONG J J,TSANG E,CHEN D G,et al.Minimal decision cost reduct in fuzzy decision-theoretic rough set model[J].Know-ledge-Based Systems,2017,126:104-112.
[24]LIU K Y,YANG X B,YU H L,et al.Rough set based semi-supervised feature selection via ensemble selector[J].Knowledge-Based Systems,2019,165:282-296.
[25]XU T H,WANG G Y.Finding strongly connected components of simple digraphs based on generalized rough sets theory[J].Knowledge Based Systems,2018,149:88-98.
[26]XU T H,WANG G Y,YANG J.Finding strongly connectedcomponents of simple digraphs based on granulation strategy[J].International Journal of Approximate Reasoning,2020,118:64-78.
[27]BANG-JENSEN J,GUTIN G Z.Digraphs Theory,Algorithmsand Applications,Second Edition[M].Berlin:Springer Science &Business Media,2009.
[28]YAO Y Y.Two views of the theory of rough sets in finite universes[J].International Journal of Approximate Reasoning,1996,15(4):291-317.
[29]JARVINEN J.Lattice theory for rough sets[J].Transactions on Rough Sets,2007,6:400-498.
[30]FAN T F.Rough set analysis of relational structures[J].Information Sciences,2013,221:230-244.
[31]CHEN J K,LI J J,LIN Y J.Computing connected components of simple undirected graphs based on generalized rough sets[J].Knowledge-Based Systems,2013,37:80-85.
[32]DAVIS T A,HU Y F.The university of Florida sparse matrix collection[J].ACM Transactions on Mathematical Software,2011,38(1):1-25.
[1] XU Si-yu, QIN Ke-yun. Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices [J]. Computer Science, 2022, 49(6A): 140-143.
[2] FANG Lian-hua, LIN Yu-mei, WU Wei-zhi. Optimal Scale Selection in Random Multi-scale Ordered Decision Systems [J]. Computer Science, 2022, 49(6): 172-179.
[3] CHEN Yu-si, AI Zhi-hua, ZHANG Qing-hua. Efficient Neighborhood Covering Model Based on Triangle Inequality Checkand Local Strategy [J]. Computer Science, 2022, 49(5): 152-158.
[4] SUN Lin, HUANG Miao-miao, XU Jiu-cheng. Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief [J]. Computer Science, 2022, 49(4): 152-160.
[5] WANG Zi-yin, LI Lei-jun, MI Ju-sheng, LI Mei-zheng, XIE Bin. Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost [J]. Computer Science, 2022, 49(4): 161-167.
[6] WANG Zhi-cheng, GAO Can, XING Jin-ming. Three-way Approximate Reduction Based on Positive Region [J]. Computer Science, 2022, 49(4): 168-173.
[7] XUE Zhan-ao, HOU Hao-dong, SUN Bing-xin, YAO Shou-qian. Label-based Approach for Dynamic Updating Approximations in Incomplete Fuzzy Probabilistic Rough Sets over Two Universes [J]. Computer Science, 2022, 49(3): 255-262.
[8] LI Yan, FAN Bin, GUO Jie, LIN Zi-yuan, ZHAO Zhao. Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets [J]. Computer Science, 2021, 48(6A): 342-348.
[9] XUE Zhan-ao, SUN Bing-xin, HOU Hao-dong, JING Meng-meng. Optimal Granulation Selection Method Based on Multi-granulation Rough Intuitionistic Hesitant Fuzzy Sets [J]. Computer Science, 2021, 48(10): 98-106.
[10] XUE Zhan-ao, ZHANG Min, ZHAO Li-ping, LI Yong-xiang. Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation [J]. Computer Science, 2021, 48(1): 157-166.
[11] SANG Bin-bin, YANG Liu-zhong, CHEN Hong-mei, WANG Sheng-wu. Incremental Attribute Reduction Algorithm in Dominance-based Rough Set [J]. Computer Science, 2020, 47(8): 137-143.
[12] CHEN Yu-jin, XU Ji-hui, SHI Jia-hui, LIU Yu. Three-way Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications [J]. Computer Science, 2020, 47(8): 144-150.
[13] ZHOU Jun-li, GUAN Yan-yong, XU Fa-sheng and WANG Hong-kai. Core in Covering Approximation Space and Its Properties [J]. Computer Science, 2020, 47(6A): 526-529.
[14] GAO Lin, DUAN Guo-lin and YAO Tao. Research on Organizational Interoperability Modeling and Evaluation Based on Graph Theory [J]. Computer Science, 2020, 47(6A): 572-576.
[15] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.