On Minimal Steiner Maximum-Connected Subgraph Queries

Given a graph G and a set Q of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS) problem. 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, t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2017-11, Vol.29 (11), p.2455-2469
Main Authors: Jiafeng Hu, Xiaowei Wu, Cheng, Reynold, Siqiang Luo, Yixiang Fang
Format: Article
Language:English
Subjects:
Approximation algorithms
Bipartite graph
Community search
Graph theory
Image edge detection
Indexes
k-edge connectivity
Measurement
minimal steiner maximum-connected subgraph
Nodes
Proteins
Social network services
subgraph search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph G and a set Q of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS) problem. 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. We further develop a cache-based processing model to improve the efficiency for an important case when Q consists of a single node. Extensive experiments on large real and synthetic graph datasets validate the effectiveness and efficiency of our approaches.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2017.2730873