File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3318464.3389697
- Scopus: eid_2-s2.0-85086237915
- WOS: WOS:000644433700071
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs
Title | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs |
---|---|
Authors | |
Keywords | densest subgraph discovery directed graph |
Issue Date | 2020 |
Publisher | Association for Computing Machinery. |
Citation | SIGMOD/PODS '20: International Conference on Management of Data, Portland, OR, USA, 14-19 June 2020, p. 1051–1066 How to Cite? |
Abstract | Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a three-thousand-edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art. |
Persistent Identifier | http://hdl.handle.net/10722/291191 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ma, C | - |
dc.contributor.author | Fang, Y | - |
dc.contributor.author | Cheng, CKR | - |
dc.contributor.author | Lakshmanan, L | - |
dc.contributor.author | Zhang, W | - |
dc.contributor.author | Lin, X | - |
dc.date.accessioned | 2020-11-07T13:53:32Z | - |
dc.date.available | 2020-11-07T13:53:32Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | SIGMOD/PODS '20: International Conference on Management of Data, Portland, OR, USA, 14-19 June 2020, p. 1051–1066 | - |
dc.identifier.isbn | 9781450367356 | - |
dc.identifier.uri | http://hdl.handle.net/10722/291191 | - |
dc.description.abstract | Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a three-thousand-edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. | - |
dc.relation.ispartof | SIGMOD '20 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data | - |
dc.rights | SIGMOD '20 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. Copyright © Association for Computing Machinery. | - |
dc.subject | densest subgraph discovery | - |
dc.subject | directed graph | - |
dc.title | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Cheng, CKR: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, CKR=rp00074 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3318464.3389697 | - |
dc.identifier.scopus | eid_2-s2.0-85086237915 | - |
dc.identifier.hkuros | 318672 | - |
dc.identifier.spage | 1051 | - |
dc.identifier.epage | 1066 | - |
dc.identifier.isi | WOS:000644433700071 | - |
dc.publisher.place | New York, NY | - |