Parallel Algorithms for Densest Subgraph Discovery Using Shared Memory Model
The problem of finding dense components of a graph is a widely explored area in data analysis, with diverse applications in fields and branches of study including community mining, spam detection, computer security and bioinformatics. This research project explores previously available algorithms in order to study them and identify potential modifications that could result in an improved version with considerable performance and efficiency leap. Furthermore, efforts were also steered towards devising a novel algorithm for the problem of densest subgraph discovery. This paper presents an improved implementation of a widely used densest subgraph discovery algorithm and a novel parallel algorithm which produces better results than a 2-approximation.
Code (0)
등록된 구현이 없습니다.
Tasks
Computer SecuritySpam detectionSimilar Papers 제목 키워드 기반
Differentially Private Densest Subgraph Detection
Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, i…
Graph MiningFast and Simple Densest Subgraph with Predictions
We study the densest subgraph problem and its variants through the lens of learning-augmented algorithms. For this problem, the greedy algorithm by Charikar (APPROX 2000) provides a linear-time $ 1/2 $-approximation, whi…
Faster Algorithms for Generalized Mean Densest Subgraph Problem
The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of $p$-means dense subgraph objectives by~\citet{veldt2021generalized}. The $p$…
ADS: Approximate Densest Subgraph for Novel Image Discovery
The volume of image repositories continues to grow. Despite the availability of content-based addressing, we still lack a lightweight tool that allows us to discover images of distinct characteristics from a large collec…
Perceptual DistanceConvex optimization for the densest subgraph and densest submatrix problems
We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum cliqu…