File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/TKDE.2017.2730873
- Scopus: eid_2-s2.0-85028849934
- WOS: WOS:000412454900006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On Minimal Steiner Maximum-Connected Subgraph Queries
Title | On Minimal Steiner Maximum-Connected Subgraph Queries |
---|---|
Authors | |
Keywords | Community search k-edge connectivity Minimal steiner maximum-connected subgraph Subgraph search |
Issue Date | 2017 |
Publisher | IEEE. 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? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/243929 |
ISSN | 2023 Impact Factor: 8.9 2023 SCImago Journal Rankings: 2.867 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, J | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Cheng, CK | - |
dc.contributor.author | Luo, S | - |
dc.contributor.author | Fang, Y | - |
dc.date.accessioned | 2017-08-25T03:01:22Z | - |
dc.date.available | 2017-08-25T03:01:22Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | IEEE Transactions on Knowledge and Data Engineering, 2017, v. 29 n. 11, p. 2455-2469 | - |
dc.identifier.issn | 1041-4347 | - |
dc.identifier.uri | http://hdl.handle.net/10722/243929 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | IEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp/?punumber=69 | - |
dc.relation.ispartof | IEEE Transactions on Knowledge and Data Engineering | - |
dc.subject | Community search | - |
dc.subject | k-edge connectivity | - |
dc.subject | Minimal steiner maximum-connected subgraph | - |
dc.subject | Subgraph search | - |
dc.title | On Minimal Steiner Maximum-Connected Subgraph Queries | - |
dc.type | Article | - |
dc.identifier.email | Wu, X: wxw0711@hku.hk | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/TKDE.2017.2730873 | - |
dc.identifier.scopus | eid_2-s2.0-85028849934 | - |
dc.identifier.hkuros | 275461 | - |
dc.identifier.volume | 29 | - |
dc.identifier.issue | 11 | - |
dc.identifier.spage | 2455 | - |
dc.identifier.epage | 2469 | - |
dc.identifier.isi | WOS:000412454900006 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1041-4347 | - |