| dc.description.abstract | This dissertation aims at developing generalized network models and solution approaches for studying cluster detection problems that typically arise in networks. More specifically, we consider graph theoretic relaxations of clique as models for characterizing structurally cohesive and robust subgroups, developing strong upper bounds for the maximum clique problem, and present a new relaxation that is useful in clustering applications.
We consider the clique relaxation models of k-block, and k-robust 2-club for describing cohesive clusters that are reliable and robust to disruptions, and introduce a new relaxation called s-stable cluster, for modeling stable clusters. First, we identify the structural properties associated with the models, and investigate the computational complexity of these problems. Next, we develop mathematical programming techniques for the optimization problems introduced, and apply them in presenting effective solution approaches to the problems.
We present integer programming formulations for the optimization problems of interest, and provide a detailed study of the associated polytopes. Particularly, we develop valid inequalities and identify different classes of facets for the polytopes. Exact solution approaches developed for solving the problems include simple branch and bound, branch and cut, and combinatorial branch and bound algorithms. In addition, we introduce many preprocessing techniques and heuristics to enhance their performance. The presented algorithms are tested computationally on a number of graph instances, that include social networks and random graphs, to study the capability of the proposed solution methods.
As a fitting conclusion to this work, we propose new techniques to get easily computable and strong upper bounds for the maximum clique problem. We investigate k-core and its stronger variant k-core/2-club in this light, and present minimization problems to get an upper bound on the maximization problems. Simple linear programming relaxations are developed and strengthened by valid inequalities, which are then compared with some standard relaxations from the literature. We present a detailed study of our computational results on a number of benchmark instances to test the effectiveness of our technique for getting good upper bounds. | en |
