We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Accelerating directed densest subgraph queries with software and hardware approaches.
- Authors
Ma, Chenhao; Fang, Yixiang; Cheng, Reynold; Lakshmanan, Laks V. S.; Han, Xiaolin; Li, Xiaodong
- Abstract
Given 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.
- Subjects
DIRECTED graphs; APPROXIMATION algorithms; BIPARTITE graphs; NONCONVEX programming; COMPUTER software; SUBGRAPHS; CONVEX programming
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2024, Vol 33, Issue 1, p207
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-023-00805-0