Heterogeneous 2Phase Method for Strongly Connected Components Detection and Classification of Graphs Different sequential and parallel methods exist for decomposing a directed graph into its Strongly Connected Components (SCCs). To speed up the execution for very large graphs, Graphics Processing Units (GPUs) have been used. The realworld graphs have smallworld property with a single giant SCC and many smallsized SCCs. For such graphs, twophase methods have been used with different parallelism strategies, both on CPU and GPU in the previous research. Our research indicates that the existing methods have great variance in their performances for different types of graphs. This research classifies the graphs on the basis of which method works best for them after analyzing their properties. Such classification ensures applying the best SCC detection method in case the type of the input graph is known. We have also developed a new method that has consistently better performance for all types of graphs. This method can be used when the type of the input graph is not known or it doesnu0027t fit into the classification. In this method, the first phase is run on the GPU whereas the second phase is run on the CPU using either sequential or multithreaded routine.

Discovering Robustly Connected Subgraphs with Simple Descriptions We study the problem of discovering robustly connected subgraphs that have simple descriptions. Our aim is, hence, to discover vertex sets which not only a) induce a subgraph that is difficult to fragment into disconnected components, but also b) can be selected from the entire graph using just a simple conjunctive query on their vertex attributes. Since many subgraphs do not have such a simple logical description, first mining robust subgraphs and posthoc discovering their description leads to suboptimal results. Instead, we propose to optimise over describable subgraphs only. To do so efficiently we propose a nonredundant iterative deepening approach, which we equip with a lineartime tight optimistic estimator that allows pruning large parts of the search space. Extensive empirical evaluation shows that our method can handle large realworld graphs, and discovers easily interpretable and meaningful subgraphs.