File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On Minimal Steiner Maximum-Connected Subgraph Queries

TitleOn Minimal Steiner Maximum-Connected Subgraph Queries
Authors
KeywordsCommunity search
k-edge connectivity
Minimal steiner maximum-connected subgraph
Subgraph search
Issue Date2017
PublisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69
Citation
IEEE Transactions on Knowledge and Data Engineering, 2017, v. 29 n. 11, p. 2455-2469 How to Cite?
AbstractGiven 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.
Persistent Identifierhttp://hdl.handle.net/10722/243929
ISSN
2017 Impact Factor: 2.775
2015 SCImago Journal Rankings: 2.087
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHu, J-
dc.contributor.authorWu, X-
dc.contributor.authorCheng, CK-
dc.contributor.authorLuo, S-
dc.contributor.authorFang, Y-
dc.date.accessioned2017-08-25T03:01:22Z-
dc.date.available2017-08-25T03:01:22Z-
dc.date.issued2017-
dc.identifier.citationIEEE Transactions on Knowledge and Data Engineering, 2017, v. 29 n. 11, p. 2455-2469-
dc.identifier.issn1041-4347-
dc.identifier.urihttp://hdl.handle.net/10722/243929-
dc.description.abstractGiven 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.-
dc.languageeng-
dc.publisherIEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69-
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineering-
dc.subjectCommunity search-
dc.subjectk-edge connectivity-
dc.subjectMinimal steiner maximum-connected subgraph-
dc.subjectSubgraph search-
dc.titleOn Minimal Steiner Maximum-Connected Subgraph Queries-
dc.typeArticle-
dc.identifier.emailWu, X: wxw0711@hku.hk-
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hk-
dc.identifier.authorityCheng, CK=rp00074-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/TKDE.2017.2730873-
dc.identifier.scopuseid_2-s2.0-85028849934-
dc.identifier.hkuros275461-
dc.identifier.volume29-
dc.identifier.issue11-
dc.identifier.spage2455-
dc.identifier.epage2469-
dc.identifier.isiWOS:000412454900006-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats