On Searching 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$(k,\ell)$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell)$-plex has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$K$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum directed$(k, \ell)$-plex search problem which finds a directed$(k, \ell)$-plex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm called DPHeuris, which finds a directed$(k, \ell)$-plex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm called DPBB to find the exact maximum directed$(k, \ell)$-plex and develop effective graph reduction strategies for boosting the empirical performance. 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.