Search

Granular computing (GrC) is a methodology for reducing the complexity of problem solving and includes two basic aspects: granulation and granular-based computing. Strongly connected components (SCCs) are a significant subgraph structure in digraphs. In this paper, two new granulation strategies were devised to improve the efficiency of computing SCCs. Firstly, four SCC correlations between the vertices were found, which can be divided into two classes. Secondly, two granulation strategies were designed based on correlations between two classes of SCCs. Thirdly, according to the characteristics of the granulation results, the parallelization of computing SCCs was realized. Finally, a parallel algorithm based on granulation strategy for computing SCCs of simple digraphs named GPSCC was proposed. Experimental results show that GPSCC performs with higher computational efficiency than algorithms. [ABSTRACT FROM AUTHOR]

As a key part of data preprocessing, namely attribute reduction, is effectively applied in the rough set field. The purpose of attribute reduction is to prevent too many attributes from affecting classifier operations and reduce the dimensionality of data space. Presently, in order to further improve the simplification performance of attribute reduction, numerous researchers have proposed a variety of methods. However, given the current findings, the challenges are: to reasonably compress the search space of candidate attributes; to fulfill multi-perspective evaluation; and to actualize attribute reduction based on guidance. In view of this, forward greedy searching to κ -reduct based on granular ball is proposed, which has the following advantages: (1) forming symmetrical granular balls to actualize the grouping of the universe; (2) continuously merging small universes to provide guidance for subsequent calculations; and (3) combining supervised and unsupervised perspectives to enrich the viewpoint of attribute evaluation and better improve the capability of attribute reduction. Finally, based on three classifiers, 16 UCI datasets are used to compare our proposed method with six advanced algorithms about attribute reduction and an algorithm without applying any attribute reduction algorithms. The experimental results indicate that our method can not only ensure the result of reduction has considerable performance in the classification test, but also improve the stability of attribute reduction to a certain degree. [ABSTRACT FROM AUTHOR]

Calculating single-source shortest paths (SSSPs) rapidly and precisely from weighted digraphs is a crucial problem in graph theory. As a mathematical model of processing uncertain tasks, rough sets theory (RST) has been proven to possess the ability of investigating graph theory problems. Recently, some efficient RST approaches for discovering different subgraphs (e.g. strongly connected components) have been presented. This work was devoted to discovering SSSPs of weighted digraphs by aid of RST. First, SSSPs problem was probed by RST, which aimed at supporting the fundamental theory for taking RST approach to calculate SSSPs from weighted digraphs. Second, a heuristic search strategy was designed. The weights of edges can be served as heuristic information to optimize the search way of $ k $-step $ R $-related set, which is an RST operator. By using heuristic search strategy, some invalid searches can be avoided, thereby the efficiency of discovering SSSPs was promoted. Finally, the W3SP@R algorithm based on RST was presented to calculate SSSPs of weighted digraphs. Related experiments were implemented to verify the W3SP@R algorithm. The result exhibited that W3SP@R can precisely calculate SSSPs with competitive efficiency.