Paper Info
Title
Querying Minimal Steiner Maximum-Connected Subgraphs in Large Graphs
Abstract
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 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 containing Q. 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 versions with accuracy guarantees. Extensive experiments on six large real graph datasets validate the effectiveness and efficiency of our approaches.
Year
DOI
Venue
2016
10.1145/2983323.2983748
ACM International Conference on Information and Knowledge Management
Keywords
Field
DocType
Community Search,Graph Query,Edge Connectivity,Steiner Maximum-Connected Subgraph Search
Data mining,Community search,Graph,Mathematical optimization,Computer science,Induced subgraph,Theoretical computer science
Conference
Citations 
PageRank 
References 
6
0.46
21
Authors
5
Name
Order
Citations
PageRank
Jiafeng Hu116210.87
Xiaowei Wu2131.57
Reynold Cheng33069154.13
Siqiang Luo424014.59
Yixiang Fang522723.06