Querying Minimal Steiner Maximum-Connected Subgraphsin Large Graphs

Given a graph G and a set Q of query nodes, we examine theSteiner Maximum-Connected Subgraph(SMCS). The SMCS,orG’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 ofQ. However, the maximum SMCS, which may contain a lot of nodes, can be difficult to interpret. In this paper, we investigate the minimal SMCS, which is the minimal subgraph of G with the maximum connectivity containingQ. The minimal SMCS contains much fewer nodes than its maximum counterpart,and is thus easier to be understood. However, the minimal SMCS can be costly to evaluate. We thus propose efficient Expand-Refine algorithms, as well as their approximate ver-sions with accuracy guarantees. Extensive experiments on six large real graph datasets validate the effectiveness andefficiency of our approaches.