On Searching and Querying Maximum Directed (k,ℓ)-Plex

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(k,\ell )$</tex-math></inline-formula>-plex for a cohesive directed subgraph, which is generalized from the concept of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-plex that is only applicable to undirected graphs. Directed <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(k,\ell )$</tex-math></inline-formula>-plex (or DPlex) has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> vertices and is meanwhile not pointed to by at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> vertices. In this paper, we study the maximum DPlex search problem which finds a DPlex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm called <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DPHeuris</monospace>, which finds a DPlex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm called <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DPBB</monospace> to find the exact maximum DPlex and develop effective graph reduction strategies for boosting the empirical performance. We also consider the problem of querying personalized maximum DPlex, and design a new method called <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DPBBQ</monospace> for the problem. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.