Maximum Balanced Clique Search on Large Directed Graphs

The classical maximum clique problem, which aims to identify the largest clique, has various applications, such as community search, team formation, motif detection, etc. Recent studies mainly focus on undirected graphs. For directed graphs, a simple method is to consider the undirected version. However, neglecting the direction information may lead to unsatisfactory results. In this work, we aim to discover the maximum balanced clique, where each vertex has the same number of incoming and outgoing neighbors. This problem is computationally challenging because of its NP-hardness. In addition, there are currently no scalable algorithms for it. To fill the gap, we first introduce a branch-and-bound algorithm, namely DMBC, which incorporates several techniques to avoid unneeded computations. To further enhance the performance of DMBC, we then devise two types of optimizations, i.e., advanced pruning rules to discard useless branches and effective search strategies to improve the pruning capacity. Last, to discover a large enough and balanced clique, we develop a heuristic approach with high efficiency and accuracy. Extensive evaluations on 14 real-world datasets state that our methods achieve substantial improvements over existing baselines by up to 2 orders of magnitude.