Back to search

Boston University

Dense subgraph discovery: novel algorithms and applications

Abstract

dc:description.abstract

Dense subgraph discovery (DSD) is an important technique for analyzing and extracting valuable insights from large-scale graph data across various fields, including social sciences, biology, and chemistry. Lying at the core of DSD is the densest subgraph problem (DSP), which finds the subgraph that maximizes induced edge density given a graph. While the DSD problems, especially DSP, have been extensively studied in the last several decades, the major focus was simple undirected graphs. Nowadays, the graph data we collect and store carries more complex information beyond connections between nodes. For example, edges in transaction networks are associated with weights representing the transaction amounts, and social networks have users with attributes encoded as feature vectors. These complex graph data and the emergence of new use cases create challenges in DSD, necessitating novel formulations and solutions. How can we detect anomalous subgraphs in transaction networks using DSD? Given a social network, are dense clusters gender-balanced, and how can we detect them? Even seemingly unrelated questions, such as measuring the statistical significance of a motif, can be tackled using DSD. In this dissertation, we study a set of problems revolving around DSD on graphs that are associated with edge and node attributes, and possibly multiple edge layers. We propose novel mathematical formulations for these problems, study their hardness, and propose efficient algorithms with performance guarantees. Our methods are evaluated on synthetic data to verify their correctness and efficiency. We further deploy them on real-world networks, where their abilities are exhibited in applications, including anomaly detection, social network mining, and community detection.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Tianyi
Advisor dc:contributor.advisor
  • Tsourakakis, Charalampos
ORCID dc:identifier.orcid

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/49981

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chen, Tianyi. Dense subgraph discovery: novel algorithms and applications. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/49981