File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.14778/3342263.3342645
- Scopus: eid_2-s2.0-85082832192
- WOS: WOS:000497645900036
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Efficient Algorithms for Densest Subgraph Discovery
Title | Efficient Algorithms for Densest Subgraph Discovery |
---|---|
Authors | |
Issue Date | 2019 |
Publisher | Very Large Data Base (VLDB) Endowment Inc. The Journal's web site is located at http://vldb.org/pvldb/index.html |
Citation | Proceedings of the VLDB Endowment (PVLDB), 2019, v. 12 n. 11, p. 1719-1732 How to Cite? |
Abstract | Densest subgraph discovery (DSD) is a fundamental problem in
graph mining. It has been studied for decades, and is widely used in
various areas, including network science, biological analysis, and
graph databases. Given a graph G, DSD aims to find a subgraph D
of G with the highest density (e.g., the number of edges over the
number of vertices in D). Because DSD is difficult to solve, we
propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a
k-core (a kind of dense subgraph of G), with theoretical guarantees.
Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the
densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have
performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four
orders of magnitude faster than existing approaches. |
Persistent Identifier | http://hdl.handle.net/10722/275410 |
ISSN | 2023 Impact Factor: 2.6 2023 SCImago Journal Rankings: 2.666 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Fang, Y | - |
dc.contributor.author | Yu, K | - |
dc.contributor.author | Cheng, CK | - |
dc.contributor.author | Lakshmanan, L | - |
dc.contributor.author | Lin, X | - |
dc.date.accessioned | 2019-09-10T02:42:01Z | - |
dc.date.available | 2019-09-10T02:42:01Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Proceedings of the VLDB Endowment (PVLDB), 2019, v. 12 n. 11, p. 1719-1732 | - |
dc.identifier.issn | 2150-8097 | - |
dc.identifier.uri | http://hdl.handle.net/10722/275410 | - |
dc.description.abstract | Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G, DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a k-core (a kind of dense subgraph of G), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches. | - |
dc.language | eng | - |
dc.publisher | Very Large Data Base (VLDB) Endowment Inc. The Journal's web site is located at http://vldb.org/pvldb/index.html | - |
dc.relation.ispartof | Proceedings of the VLDB Endowment (PVLDB) | - |
dc.rights | Proceedings of the VLDB Endowment (PVLDB). Copyright © Very Large Data Base (VLDB) Endowment Inc. | - |
dc.title | Efficient Algorithms for Densest Subgraph Discovery | - |
dc.type | Article | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.14778/3342263.3342645 | - |
dc.identifier.scopus | eid_2-s2.0-85082832192 | - |
dc.identifier.hkuros | 302949 | - |
dc.identifier.volume | 12 | - |
dc.identifier.issue | 11 | - |
dc.identifier.spage | 1719 | - |
dc.identifier.epage | 1732 | - |
dc.identifier.isi | WOS:000497645900036 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 2150-8097 | - |