SpecGreedy: Unified Dense Subgraph Detection (Best Student DM paper)

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.