Unified Spectral Theory-based Dense Subgraph Detection

Fast Spectral Theory-based Algorithms for unified dense subgraphs detection in large graphs.

We propose and formulate the generalized densest subgraph detection problem (GenDS) and fast detection algorithms based on the graph spectral properties and greedy search, i.e., SPECGDS (SpecGreedy) and GEPGDS.

• Theory & Correspondences: The unified formulation, GenDS, subsumes many real problems from different applications; and its optimization is guaranteed by the spectral theory.
• Scalable: Propose fast and scalable algorithms to solve the unified detection problem over large graphs.
• Effectiveness: The performance (solution-quality and speedy) of SpecGreedy is verified on 40 real-world networks; and it can find some interesting patterns in real applications, like the sudden bursts in research co-authorship relationships

Environment

Python 3.6 is supported in the current version.

To install the required libraries, please type

pip install -r requirements

---

Running Demo

Demo for detecting the densest subgraph, please type

make

Datasets Resource

The datasets used are available online; they are from some popular network repositories, including Stanford's SNAP, AUS's Social Computing Data Repository, Network Repository, Aminer scholar datasets, Koblenz Nwtwork Collection, and MPI-SWS social datasets.

Reference

Please acknowledge the following papers if you use this code for any published research.

@article{feng2023unified,
  title={Unified Dense Subgraph Detection: Fast Spectral Theory based Algorithms},
  author={Feng, Wenjie and Liu, Shenghua and Koutra, Danai and Cheng, Xueqi},
  journal={IEEE Transactions on Knowledge and Data Engineering},
  year={2023},
  publisher={IEEE}
}

@inproceedings{feng2020specgreedy,
  title={SpecGreedy: Unified Dense Subgraph Detection},
  author={Wenjie Feng, Shenghua Liu, Danai Koutra, Huawei Shen, and Xueqi Cheng},
  booktitle={European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD)},
  year={2020},
}