This repository contains C++ codes and datasets for the paper:

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework

In this paper, we condcut an in-depth study on sequential densest subgraph discovery (DSD) algorithms. We first propose a unified framework with three modules, namely graph reduction, vertex weight update ( VWU) and candidate subgraph extract and verify (CSV), which capture the core ideas of all existing algorithms.

Given a graph $G$ and an error threshold $\epsilon$, graph reduction aims to locate the DS in a small subgraph; VWU aims to update vertex weights over $T$ iterations; and CSV extracts a candidate subgraph based on vertex weights and verifies if it satisfies the $\epsilon$ error requirement.

Under this framework, we systematically compare 12 and 7 representative algorithms (including both exact and approximation algorithms) for undirected and directed graphs, respectively.

We conduct comprehensive experiments on both real-world and synthetic datasets and provide an in-depth analysis.

The codes of our in-depth study are implemented and tested under the following development environment:

• Hardware : Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz and 512GB of memory.
• Operation System : Ubuntu 20.04.5 LTS (GNU/Linux 5.15.0-101-generic x86_64)

We use twelve real datasets from different domains including 6 undirected graphs and 6 directed graphs, which are available on the Stanford Network Analysis Platform, Laboratory of Web Algorithmics, Network Repository, and Konect.

Undirected:

Directed:

After cloning the codes from GitHub, use the following command to compile the codes in the repository :

cmake CMakeLists.txt

make

A general command of our program is like:

./DensestSubgraph [-option1 value1] [-option2 value2] ...

For example, you could run core-exact on DP in the following command:

./DensestSubgraph -path ./data/DP.txt -t u -a e -red k-core -alloc flow-exact -ext flow-exact -ver flow-exact

There are a lot of options for you to conduct a thorough evalution among different algorithms:

You can download the datasets from the following Google driven link:

XXXXXXXXXXXXXXXXXX

Our one-click script for reproducibility is comming soon.