Finding dense subgraphs from a large graph is a fundamental graph mining task with many applications. The notion is recently formulated of locally densest subgraph (LDS) is recently formulated to identify multiple dense subgraphs that cover different regions of a large graph. Informally, an LDS is a subgraph with the highest density in its local region. The state-of-the-art algorithm for computing top-k LDSes with the highest densities is LDS. It iteratively computes the densest subgraph and removes it from the graph, where all the computed densest subgraphs form the candidates of LDSes. Then, each candidate is verified through a costly maximum flow computation. Although advanced pruning techniques are proposed in LDS, the verification step is still time consuming especially for not-so-small k values. In this paper, we aim to improve the efficiency of finding top-k LDSes by designing verification-free approaches. Our algorithms are based on our observation that the set of maximal λ-compact subgraphs for all possible λ values form a hierarchical structure, and LDSes are simply leaves in the hierarchical structure. Thus, we propose a divide-and-conquer algorithm LDS-DC as well as an optimized algorithm LDS-Opt to efficiently identify top-k LDSes without constructing the entire hierarchical structure. Both of our algorithms have lower time complexities than LDS. Extensive empirical studies on real graphs show that our optimized algorithm LDS-Opt outperforms LDS for all k values, and the improvement is up-to several orders of magnitude.

Arising from the need of all time for optimization of irrigation systems, distribution network and cable network, the Cluster Shortest Path Tree Problem (CSTP) has been attracting a lot of attention and interest from the research community. For such an NP-Hard problem with a great dimensionality, the approximation approach is usually taken. Evolutionary Algorithms, based on biological evolution, has been proved to be effective in finding approximate solutions to problems of various fields. The multifactorial evolutionary algorithm (MFEA) is one of the most recently exploited realms of EAs and its performance in solving optimization problems has been very promising. The main difference between the MFEA and the traditional Genetic Algorithm (GA) is that the former can solve multiple tasks at the same time and take advantage of implicit genetic transfer in a multitasking problem, while the latter solves one problem and exploit one search space at a time. Considering these characteristics, this paper proposes a MFEA for CSTP tasks, together with novel genetic operators: population initialization, crossover, and mutation operators. Furthermore, a novel decoding scheme for deriving factorial solutions from the unified representation in the MFEA, which is the key factor to the performance of any variant of the MFEA, is also introduced in this paper. For examining the efficiency of the proposed techniques, experiments on a wide range of diverse sets of instances were implemented and the results showed that the proposed algorithms outperformed an existing heuristic algorithm for most of the testing cases. In the experimental results section, we also pointed out which cases allowed for a good performance of the proposed algorithm.