File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Accelerating directed densest subgraph queries with software and hardware approaches

TitleAccelerating directed densest subgraph queries with software and hardware approaches
Authors
KeywordsConvex programming
Densest subgraph discovery
Directed graph
GPU
Issue Date31-Jul-2023
PublisherSpringer
Citation
The VLDB Journal, 2023, v. 33, p. 207 How to Cite?
AbstractGiven a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. Theoretically, the DDS problem closely connects to other essential graph problems, such as network flow and bipartite matching. However, existing DDS solutions suffer from efficiency and scalability issues. In this paper, we develop a convex-programming-based solution by transforming the DDS problem into a set of linear programs. Based on the duality of linear programs, we develop efficient exact and approximation algorithms. Particularly, our approximation algorithm can support flexible parameterized approximation guarantees. We further investigate using GPU to speed up the solution of convex programs in parallel and achieve hundreds of times speedup compared to the original Frank–Wolfe computation. We have performed an extensive empirical evaluation of our approaches on eight real large datasets. The results show that our proposed algorithms are up to five orders of magnitude faster than the state of the art.
Persistent Identifierhttp://hdl.handle.net/10722/338628
ISSN
2023 Impact Factor: 2.8
2023 SCImago Journal Rankings: 1.853
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorMa, C-
dc.contributor.authorFang, Y-
dc.contributor.authorCheng, R-
dc.contributor.authorLakshmanan, LVS-
dc.contributor.authorHan, X-
dc.contributor.authorLi, X-
dc.date.accessioned2024-03-11T10:30:18Z-
dc.date.available2024-03-11T10:30:18Z-
dc.date.issued2023-07-31-
dc.identifier.citationThe VLDB Journal, 2023, v. 33, p. 207-
dc.identifier.issn1066-8888-
dc.identifier.urihttp://hdl.handle.net/10722/338628-
dc.description.abstractGiven a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. Theoretically, the DDS problem closely connects to other essential graph problems, such as network flow and bipartite matching. However, existing DDS solutions suffer from efficiency and scalability issues. In this paper, we develop a convex-programming-based solution by transforming the DDS problem into a set of linear programs. Based on the duality of linear programs, we develop efficient exact and approximation algorithms. Particularly, our approximation algorithm can support flexible parameterized approximation guarantees. We further investigate using GPU to speed up the solution of convex programs in parallel and achieve hundreds of times speedup compared to the original Frank–Wolfe computation. We have performed an extensive empirical evaluation of our approaches on eight real large datasets. The results show that our proposed algorithms are up to five orders of magnitude faster than the state of the art.-
dc.languageeng-
dc.publisherSpringer-
dc.relation.ispartofThe VLDB Journal-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectConvex programming-
dc.subjectDensest subgraph discovery-
dc.subjectDirected graph-
dc.subjectGPU-
dc.titleAccelerating directed densest subgraph queries with software and hardware approaches-
dc.typeArticle-
dc.identifier.doi10.1007/s00778-023-00805-0-
dc.identifier.scopuseid_2-s2.0-85166263046-
dc.identifier.volume33-
dc.identifier.epage207-
dc.identifier.eissn0949-877X-
dc.identifier.isiWOS:001040174300001-
dc.identifier.issnl1066-8888-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats