Extracting Minimal Steiner Maximum-Connected Subgraphs from Large Graph Databases

Given a graph G and a set Q of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS). The SMCS, or G's induced subgraph that contains Q with the largest connectivity, can be useful for customer prediction, product promotion, and team assembling. Despite its importance, the SMCS problem has only been recently studied. Existing solutions evaluate the maximum SMCS, whose number of nodes is the largest among all the SMCSs of Q. However, the maximum SMCS, which may contain a gigantic number of nodes, can be difficult to understand and use. In this paper, we investigate the minimal SMCS, which is the minimal subgraph of G with the maximum connectivity containing Q. The minimal SMCS contains much fewer nodes than its maximum counterpart, enabling it to be interpreted more easily. However, the minimal SMCS can be costly to evaluate. We plan to devise efficient algorithms for computing minimal SMCS, as well as their approximate versions with accuracy guarantees. Moreover, we will extend those methods to solve the minimal subgraph problem under other cohesive metrics, like k-core, k-truss.