THEORY AND ALGORITHMS FOR COMMUNITY DETECTION AND CLUSTERING IN NETWORKS

Abstract

This dissertation is focused on certain clustering and partitioning problems in networks. We present a comprehensive study of the maximum independent union of cliques problem and its generalizations in uniform random graphs. The main result is the logarithmic upper bound, similarly to the maximum clique, which suggests a subexponential algorithm. Then we propose a parallel version of Russian Doll Search, an algorithm that can be used to find the maximum independent union of cliques. We enhance existing verification procedure for this problem by a simple observation, which also leads to an elegant constant time biclique verification. Finally, we perform the first computational study for finding Hadwiger’s number of a graph. We present several integer formulations, scale-reduction techniques, heuristics, and bounds, together with a scheme for future exact combinatorial algorithms.