File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient Algorithms for Densest Subgraph Discovery

TitleEfficient Algorithms for Densest Subgraph Discovery
Authors
Issue Date2019
PublisherVery 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?
AbstractDensest 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 Identifierhttp://hdl.handle.net/10722/275410
ISSN

 

DC FieldValueLanguage
dc.contributor.authorFang, Y-
dc.contributor.authorYu, K-
dc.contributor.authorCheng, CK-
dc.contributor.authorLakshmanan, L-
dc.contributor.authorLin, X-
dc.date.accessioned2019-09-10T02:42:01Z-
dc.date.available2019-09-10T02:42:01Z-
dc.date.issued2019-
dc.identifier.citationProceedings of the VLDB Endowment (PVLDB), 2019, v. 12 n. 11, p. 1719-1732-
dc.identifier.issn2150-8097-
dc.identifier.urihttp://hdl.handle.net/10722/275410-
dc.description.abstractDensest 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.languageeng-
dc.publisherVery Large Data Base (VLDB) Endowment Inc. The Journal's web site is located at http://vldb.org/pvldb/index.html-
dc.relation.ispartofProceedings of the VLDB Endowment (PVLDB)-
dc.rightsProceedings of the VLDB Endowment (PVLDB). Copyright © Very Large Data Base (VLDB) Endowment Inc.-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.titleEfficient Algorithms for Densest Subgraph Discovery-
dc.typeArticle-
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hk-
dc.identifier.authorityCheng, CK=rp00074-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.14778/3342263.3342645-
dc.identifier.hkuros302949-
dc.identifier.volume12-
dc.identifier.issue11-
dc.identifier.spage1719-
dc.identifier.epage1732-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats