Finding strongly connected components of simple digraphs based on granulation strategy.

*(English)*Zbl 07174797Summary: Strongly connected components (SCCs) are an important kind of subgraphs in digraphs. It can be viewed as a kind of knowledge in the viewpoint of knowledge discovery. In our previous work, a knowledge discovery algorithm called RSCC was proposed for finding SCCs of simple digraphs based on two operators, \(k\)-step \(R\)-related set and \(k\)-step upper approximation, of rough set theory (RST). RSCC algorithm can find SCCs more efficiently than Tarjan algorithm of linear complexity. However, on the one hand, as the theoretical basis of RST applied to SCCs discovery of digraphs, the theoretical relationships between RST and graph theory investigated in previous work only include four equivalences between fundamental RST and graph concepts relating to SCCs. The reasonability of using the two RST operators to find SCCs still need to be investigated. On the other hand, it is found that there are three SCCs correlations between vertices after we use three RST concepts, \(R\)-related set, lower and upper approximation sets, to analyze SCCs. RSCC algorithm ignores these SCCs correlations so that the efficiency of RSCC is affected negatively. For the above two issues, firstly, we explore the equivalence between the two RST operators and Breadth-First Search (BFS) which is one of the most basic graph search algorithms and the most direct way to find SCCs. These equivalences explain the reasonability of using the two RST operators to find SCCs, and enrich the content of the theoretical relationships between RST and graph theory. Secondly, we design a granulation strategy according to these three SCCs correlations. Then an algorithm called GRSCC for finding SCCs of simple digraphs based on granulation strategy is proposed. Experimental results show that GRSCC provides better performance to RSCC.

##### MSC:

68T37 | Reasoning under uncertainty in the context of artificial intelligence |

05C85 | Graph algorithms (graph-theoretic aspects) |

68R10 | Graph theory (including graph drawing) in computer science |

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Software:

SparseMatrix
PDF
BibTeX
XML
Cite

\textit{T. Xu} et al., Int. J. Approx. Reasoning 118, 64--78 (2020; Zbl 07174797)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Allesina, S.; Bodini, A.; Bondavalli, C., Ecological subsystems via graph theory: the role of strongly connected components, Oikos, 110, 1, 164-176 (2005) |

[2] | Ioannidis, Y.; Ramakrishnan, R.; Winger, L., Transitive closure algorithms based on graph traversal, ACM Trans. Database Syst., 18, 3, 512-576 (1993) |

[3] | Yang, H. G.; Shen, D. R.; Kou, Y.; Nie, T. Z.; Ge, Y., Strongly connected components based efficient PPR algorithms, Chinese J. Comput., 18, 3, 584-600 (2017) |

[4] | Adamic, L. A., The small world web, (Proceedings of International Conference on Theory and Practice of Digital Libraries (1999), Springer), 443-452 |

[5] | Xu, T. H.; Zhang, Q. H., Research on suspicious transaction recognition based on heuristic listing of directed primary circuit, Chin. J. Nanjing Univ. (Natural Sciences), 52, 5, 879-889 (2016) |

[6] | Pearce, D. J.; Kelly, P. H.J.; Hankin, C., Efficient field-sensitive pointer analysis of C, ACM Trans. Program. Lang. Syst., 30, 1, 4 (2007) |

[7] | Burke, M., An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Trans. Program. Lang. Syst., 12, 3, 341-395 (1990) |

[8] | Fan, J. C.; Chow, T. W., Exactly robust kernel principal component analysis, IEEE Trans. Neural Netw. Learn. Syst., 1-13 (2019) |

[9] | Fan, J. C.; Tian, Z. Y.; Zhao, M. B.; Chow, T. W., Accelerated low-rank representation for subspace clustering and semi-supervised classification on large-scale data, Neural Netw., 100, 39-48 (2018) |

[10] | Fan, J. C.; Chow, T. W.; Zhao, M. B.; John, K. H., Nonlinear dimensionality reduction for data with disconnected neighborhood graph, Neural Process. Lett., 47, 2, 697-716 (2018) |

[11] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107 |

[12] | Gabow, H. N., Path-based depth-first search for strong and biconnected components, Inf. Process. Lett., 74, 3, 107-114 (2000) · Zbl 1339.68301 |

[13] | Sharir, M., A strong-connectivity algorithm and its applications in data flow analysis, Comput. Math. Appl., 7, 1, 67-72 (1981) · Zbl 0443.68046 |

[14] | Fleischer, L. K.; Hendrickson, B.; Pinar, A., On identifying strongly connected components in parallel, (Lecture Notes Comput. Sci., vol. 1800 (2000)), 505-511 |

[15] | McLendon, W.; Hendrickson, B.; Plimpton, S. J.; Rauchwerger, L., Finding strongly connected components in distributed graphs, J. Parallel Distrib. Comput., 65, 8, 901-910 (2005) · Zbl 1082.68086 |

[16] | He, T., Rough graph and its application (2008), Shandong University, Ph.D. thesis |

[17] | Pawlak, Z., Rough sets, Int. J. Comput. Inf. Sci., 11, 5, 341-356 (1982) · Zbl 0501.68053 |

[18] | Chen, L. F.; Tsai, C. T., Data mining framework based on rough set theory to improve location selection decisions: a case study of a restaurant chain, Tour. Manag., 53, 197-206 (2016) |

[19] | Pawlak, Z., Rough set approach to knowledge-based decision support, Eur. J. Oper. Res., 99, 1, 48-57 (1995) · Zbl 0923.90004 |

[20] | Ma, X. A.; Zhao, X. R., Cost-sensitive three-way class-specific attribute reduction, Int. J. Approx. Reason., 105, 153-174 (2019) · Zbl 1452.68219 |

[21] | Huang, Z. H.; Li, J. J.; Dai, W. Z.; Lin, R. D., Generalized multi-scale decision tables with multi-scale decision attributes, Int. J. Approx. Reason., 115, 194-208 (2019) |

[22] | Dou, H. L.; Yang, X. B.; Song, X. N.; Yu, H. L.; Wu, W. Z.; Yang, J. Y., Decision-theoretic rough set: a multicost strategy, Knowl.-Based Syst., 91, 71-83 (2016) |

[23] | Ma, X. A.; Yao, Y. Y., Min-max attribute-object bireducts: on unifying models of reducts in rough set theory, Inf. Sci., 501, 68-83 (2019) |

[24] | Ma, X. A.; Yao, Y. Y., Three-way decision perspectives on class-specific attribute reducts, Inf. Sci., 450, 227-245 (2018) |

[25] | Hirano, S.; Tsumoto, S., Segmentation of medical images based on approximations in rough set theory, (Proceeding of International Conference on Rough Sets and Current Trends in Computing (2002), Springer), 554-563 · Zbl 1013.68841 |

[26] | Yang, X. B.; Ming, Z.; Dou, H. L.; Yang, J. Y., Neighborhood systems-based rough sets in incomplete information system, Knowl.-Based Syst., 24, 6, 858-867 (2011) |

[27] | Yang, X. B.; Yong, Q.; Yu, H. L.; Song, X. N.; Yang, J. Y., Updating multigranulation rough approximations with increasing of granular structures, Knowl.-Based Syst., 64, 1, 59-69 (2014) |

[28] | Tan, R. R., Rule-based life cycle impact assessment using modified rough set induction methodology, Environ. Model. Softw., 20, 5, 509-513 (2005) |

[29] | Afridi, M. K.; Azam, N.; Yao, J. T.; Alanazi, E., A three-way clustering approach for handling missing data using GTRS, Int. J. Approx. Reason., 98, 11-24 (2018) · Zbl 1451.62070 |

[30] | Wang, L. J.; Yang, J. Y.; Chen, W., Relationships among generalized rough sets in six coverings and pure reflexive neighborhood system, Inf. Sci., 207, 207, 66-78 (2012) · Zbl 1250.68261 |

[31] | Zhang, J. H.; Wang, Y. Y., A rough margin based support vector machine, Inf. Sci., 178, 9, 2204-2214 (2008) |

[32] | Li, X. Y.; Li, X. C.; Zhao, Z. H., Combining deep learning with rough set analysis: a model of cyberspace situational awareness, (Proceedings of the 6th International Conference on Electronics Information and Emergency Communication (ICEIEC) (2016), IEEE), 182-185 |

[33] | Chiaselotti, G.; Ciucci, D.; Gentile, T., Simple graphs in granular computing, Inf. Sci., 340, C, 279-304 (2016) · Zbl 1395.68260 |

[34] | Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Generalizations of rough set tools inspired by graph theory, Fundam. Inform., 148, 1-2, 207-227 (2016) · Zbl 1388.03045 |

[35] | Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Rough set theory applied to simple undirected graphs, (Proceeding of International Conference on Rough Sets and Knowledge Technology (2015), Springer), 423-434 |

[36] | Chiaselotti, G.; Gentile, T.; Infusino, F. G.; Oliverio, P. A., The adjacency matrix of a graph as a data table: a geometric perspective, Ann. Mat. Pura Appl., 196, 3, 1073-1112 (2017) · Zbl 1366.05029 |

[37] | Chen, J. K.; Li, J. J.; Lin, Y. J., Computing connected components of simple undirected graphs based on generalized rough sets, Knowl.-Based Syst., 37, 2, 80-85 (2013) |

[38] | Xu, T. H.; Wang, G. Y., Finding strongly connected components of simple digraphs based on generalized rough sets theory, Knowl.-Based Syst., 149, 88-98 (2018) |

[39] | Wang, S. P.; Zhu, F.; Min, F., Transversal matroid and covering-based rough sets, J. Frontiers Comput. Sci. Technol., 06, 3, 281-286 (2012) |

[40] | Wang, S. P.; Zhu, Q. X.; Zhu, W.; Min, F., Graph and matrix approaches to rough sets through matroids, Inf. Sci., 288, 1, 1-11 (2014) · Zbl 1355.68265 |

[41] | Wang, S. P.; Zhu, Q. X.; Zhu, W.; Min, F., Equivalent characterizations of some graph problems by covering-based rough sets, J. Appl. Math., 2013, 9-10, 2862-2890 (2013) |

[42] | Orzan, S. M., On distributed verification and verified distribution (2004), Free University of Amsterdam, Ph.D. thesis |

[43] | Hong, S.; Rodia, N. C.; Olukotun, K., On fast parallel detection of strongly connected components (SCC) in small-world graphs, (Proceedings of International Conference on High Performance Computing, Networking, Storage and Analysis (SC) (2013)), 1-11 |

[44] | Slota, G. M.; Rajamanickam, S.; Madduri, K., BFS and coloring-based parallel algorithms for strongly connected components and related problems, (Proceedings of the 28th IEEE International Symposium on Parallel and Distributed Processing (2014)), 550-559 |

[45] | Barnat, J.; Moravec, P., Parallel algorithms for finding SCCs in implicitly given graphs, (Form. Methods Appl. Technol., vol. 4346 (2006)), 316-330 |

[46] | Devshatwar, S.; Amilkanthwar, M.; Nasre, R., GPU centric extensions for parallel strongly connected components computation, (Proceedings of the 9th Annual Workshop on General Purpose Processing Using Graphics Processing Unit, GPGPU’16 (2016), ACM: ACM New York, NY, USA), 2-11 |

[47] | Barnat, J.; Bauch, P.; Brim, L.; Ceška, M., Computing strongly connected components in parallel on CUDA, (Proceedings of IEEE International Symposium on Parallel & Distributed Processing (2011), IEEE), 544-555 |

[48] | Li, G. H.; Zhu, Z.; Zhang, C.; Yang, F. M., Efficient decomposition of strongly connected components on GPUs, J. Syst. Archit., 60, 1, 1-10 (2014) |

[49] | Wijs, A.; Katoen, J. P.; Bošnački, D., Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components, Form. Methods Syst. Des., 48, 3, 274-300 (2016) · Zbl 1404.68204 |

[50] | Bloemen, V., On-The-Fly parallel decomposition of strongly connected components (2015), University of Twente, Master’s thesis |

[51] | Bloemen, V.; Laarman, A.; Pol, J. V.D., Multi-core on-the-fly SCC decomposition, ACM SIGPLAN Not., 51, 8, 1-12 (2016) |

[52] | Laarman, A.; Langerak, R.; van de Pol, J.; Weber, M.; Wijs, A., Multi-core nested depth-first search, (Proceeding of the 9th International Symposium on Automated Technology for Verification and Analysis (2011), Springer), 321-335 · Zbl 1348.68142 |

[53] | Evangelista, S.; Petrucci, L.; Youcef, S., Parallel nested depth-first searches for LTL model checking, (Proceeding of the 9th International Symposium on Automated Technology for Verification and Analysis (2011), Springer), 381-396 · Zbl 1348.68134 |

[54] | Evangelista, S.; Laarman, A.; Petrucci, L.; van de Pol, J., Improved multi-core nested depth-first search, (Proceeding of the 10th International Symposium on Automated Technology for Verification and Analysis (2012), Springer), 269-283 · Zbl 1374.68281 |

[55] | Renault, E.; Duret-Lutz, A.; Kordon, F.; Poitrenaud, D., Parallel explicit model checking for generalized büchi automata, (Proceeding of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (2015), Springer), 613-627 · Zbl 1420.68137 |

[56] | Lowe, G., Concurrent depth-first search algorithms based on Tarjan’s algorithm, Int. J. Softw. Tools Technol. Transf., 18, 2, 129-147 (2016) |

[57] | Yao, J. T.; Vasilakos, A. V.; Pedrycz, W., Granular computing: perspectives and challenges, IEEE Trans. Cybern., 43, 6, 1977-1989 (2013) |

[58] | Stell, J. G., Granulation for graphs, (Spatial Information Theory. Spatial Information Theory, Lecture Notes in Computer Science, vol. 4736 (1999)), 438-454 |

[59] | Stell, J. G., Relations in mathematical morphology with applications to graphs and rough sets, (Spatial Information Theory. Spatial Information Theory, Lecture Notes in Computer Science, vol. 1661 (2007)), 417-432 |

[60] | Chen, G.; Zhong, N., Granular structures in graphs, (International Conference on Rough Sets and Knowledge Technology (2011), Springer), 649-658 |

[61] | Chen, G.; Zhong, N., Three granular structure models in graphs, (International Conference on Rough Sets and Knowledge Technology (2012), Springer), 351-358 |

[62] | Bryniarska, A., Certain information granule system as a result of sets approximation by fuzzy context, Int. J. Approx. Reason., 111, 1-20 (2019) · Zbl 1460.68107 |

[63] | Kaburlasos, V. G.; Moussiades, L.; Vakali, A., Granular graph clustering in the web, (Proceedings of the 8th International Conference on Natural Computing (2011), World Scientific Publishing: World Scientific Publishing Utah), 1639-1645 |

[64] | Bianchi, F. M.; Livi, L.; Rizzi, A.; Sadeghian, A., A granular computing approach to the design of optimized graph classification systems, Soft Comput., 18, 2, 393-412 (2014) |

[65] | Bang-Jensen, J.; Gutin, G. Z., Digraphs: Theory, Algorithms and Applications (2009), Springer Science & Business Media · Zbl 1170.05002 |

[66] | Yao, Y. Y., Two views of the theory of rough sets in finite universes, Int. J. Approx. Reason., 15, 4, 291-317 (1996) · Zbl 0935.03063 |

[67] | Järvinen, J., Lattice theory for rough sets, (Lect. Notes Comput. Sci., vol. 4374 (2007)), 400-498 · Zbl 1186.03069 |

[68] | Ooof, L., Gephi Chinese Tutorial (2012) |

[69] | Davis, T. A.; Hu, Y., University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1, 734-747 (2011) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.