File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2983323.2983748
- Scopus: eid_2-s2.0-84996566992
- WOS: WOS:000390890800128
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Querying minimal steiner maximum-connected subgraphs in large graphs
Title | Querying minimal steiner maximum-connected subgraphs in large graphs |
---|---|
Authors | |
Issue Date | 2016 |
Publisher | ACM. |
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? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/232181 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, J | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Cheng, R | - |
dc.contributor.author | Luo, S | - |
dc.contributor.author | Fang, Y | - |
dc.date.accessioned | 2016-09-20T05:28:17Z | - |
dc.date.available | 2016-09-20T05:28:17Z | - |
dc.date.issued | 2016 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 978-1-4503-4073-1 | - |
dc.identifier.uri | http://hdl.handle.net/10722/232181 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.publisher | ACM. | - |
dc.relation.ispartof | Conference on Information and Knowledge Management, CIKM 2016 Proceedings | - |
dc.title | Querying minimal steiner maximum-connected subgraphs in large graphs | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Cheng, R: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, R=rp00074 | - |
dc.identifier.doi | 10.1145/2983323.2983748 | - |
dc.identifier.scopus | eid_2-s2.0-84996566992 | - |
dc.identifier.hkuros | 265238 | - |
dc.identifier.hkuros | 275515 | - |
dc.identifier.spage | 1 | - |
dc.identifier.epage | 10 | - |
dc.identifier.isi | WOS:000390890800128 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 161026 | - |