Optimization Techniques for Analysis of Biological and Social Networks.

摘要

This project focused on a multifaceted study of a class of cluster- detection problems arising in biological and social networks. This includes defining new cluster models and their alternative mathematical programming formulations, their theoretical analysis, the development of exact algorithms, and heuristics. Originally, clusters (complexes, modules, cohesive subgroups) in biological and social networks were described by cliques (complete subgraphs) or connected components. However, in many practical situations cliques appear to be overly restrictive, whereas connected components are insufficiently 'tight' clusters. This project considers a class of concepts describing clusters that 'relax' the definition of a clique and are tighter than connected components. Such problems are of great practical as well as theoretical interest and this project is the first attempt to approach the clique relaxation models in a systematic fashion under a unifying theoretical and algorithmic framework.