Search

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. [ABSTRACT FROM AUTHOR]

• Defining two IvIF granular structure distances. • Developing an extended partial order relation in IvIF granular space based on granular structure distance. • Proposing new uncertainty measures based on this partial order relation. • Presenting IvIF approximate granular structure for describing the target concept and a new attribute reduction algorithm. • Presenting a new method based on uncertainty measures for the linguistic large group decision-making problem. The interval-valued intuitionistic fuzzy (IvIF) set, a combination of intuitionistic fuzzy sets and interval-valued sets, has been widely employed for multi-attribute decision-making and group decision-making. However, two urgent problems remain to be solved. The first is to determine the coarseness/fineness relation in the IvIF granular space, and the other is to determine the difference between two IvIF granular structures with the same uncertainty. In this paper, a pair of IvIF granular structure distances is proposed to address the aforementioned issues. Then, a more generalized coarseness/fineness relation is defined for the IvIF granular space. Furthermore, two complementary uncertainty measures were formulated based on the coarseness/fineness relation. Finally, we investigate the IvIF approximate granular structure of a target concept and propose a new algorithm for attribute reduction from the perspective of distance. The experiments show that our algorithm possesses a shorter reduct than the other algorithms, ensuring relatively high classification accuracy. Furthermore, a case study is presented to demonstrate the feasibility of using the proposed method to solve a large linguistic group decision-making problem. [ABSTRACT FROM AUTHOR]