Discovering well-connected parts in graphs and hypergraphs

Abstract

Graphs and hypergraphs have proved to be powerful in representing discrete objects and their relationships. In this thesis, we study several combinatorial problems raised for detecting ``well-connected'' parts in graphs and hypergraphs.

First, we propose a polynomial-time $O(\sqrt{\log n})$-approximate algorithm for the directed hyperedge expansion problem and directed hypergraph sparsest cut problem with product demands, generalizing the existing results on directed normal graphs. The algorithm is established in a semidefinite programming (SDP) primal-dual framework.

Next, we consider the $k$-core decomposition in the distributed setting and the dynamic setting. In the distributed setting, each node is a computer. By employing a well-known elimination procedure that repeatedly ``peels off'' nodes with low degree, we give a distributed algorithm that requires $O(\log_{1 + \epsilon}n)$ synchronous communication rounds and produces a $2(1 + \epsilon)$-approximation to the core value of each node, which is shown to be tight. The min-max edge orientation problem and the densest subgraph problem turn out to be closely related to $k$-core decomposition, and we augment our distributed algorithm to approximately solve them. Then, in the dynamic setting, using a similar technique, we develop partially dynamic (insertion-only) and fully dynamic algorithms that maintain $2(1 + \epsilon)$-approximate core values on hypergraphs in amortized polylogarithmic time per update.

Finally, we consider the $k$-clique densest subgraph problem, which is generalized from the densest subgraph problem and useful for finding quasi-cliques. The task is challenging because the number of $k$-cliques explodes as $k$ increases. Adapting a convex-optimization-based approach designed for the densest subgraph problem, we give $(1 + \epsilon)$-approximate and exact algorithms featuring low memory consumption and a high convergence rate.

Most of the theoretical results are supplemented with extensive experiments on multiple large real-world graphs and hypergraphs. The experiments show that our algorithms are effective and efficient in practice.