File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Querying minimal steiner maximum-connected subgraphs in large graphs

TitleQuerying minimal steiner maximum-connected subgraphs in large graphs
Authors
Issue Date2016
PublisherACM.
Citation
The 25th ACM International Conference on Information and Knowledge Management (CIKM), Indianapolis, IN., 24-28 October 2016. In Conference Proceedings, 2016, p. 1-10 How to Cite?
AbstractGiven 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.
Persistent Identifierhttp://hdl.handle.net/10722/232181
ISBN

 

DC FieldValueLanguage
dc.contributor.authorHu, J-
dc.contributor.authorWu, X-
dc.contributor.authorCheng, R-
dc.contributor.authorLuo, S-
dc.contributor.authorFang, Y-
dc.date.accessioned2016-09-20T05:28:17Z-
dc.date.available2016-09-20T05:28:17Z-
dc.date.issued2016-
dc.identifier.citationThe 25th ACM International Conference on Information and Knowledge Management (CIKM), Indianapolis, IN., 24-28 October 2016. In Conference Proceedings, 2016, p. 1-10-
dc.identifier.isbn978-1-4503-4073-1-
dc.identifier.urihttp://hdl.handle.net/10722/232181-
dc.description.abstractGiven 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.-
dc.languageeng-
dc.publisherACM.-
dc.relation.ispartofConference on Information and Knowledge Management, CIKM 2016 Proceedings-
dc.titleQuerying minimal steiner maximum-connected subgraphs in large graphs-
dc.typeConference_Paper-
dc.identifier.emailCheng, R: ckcheng@cs.hku.hk-
dc.identifier.authorityCheng, R=rp00074-
dc.identifier.doi10.1145/2983323.2983748-
dc.identifier.hkuros265238-
dc.identifier.spage1-
dc.identifier.epage10-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 161026-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats