Clique Relaxations in Biological and Social Network Analysis Foundations and Algorithms
Abstract
The objective of this project is to provide a unifying theoretical and computational framework for the study of clique relaxation models arising in biological and social networks. This project examines the elementary clique-defining properties inherently exploited in the available clique relaxation models and proposes a taxonomic framework that not only allows to classify the existing models in a systematic fashion, but also yields new clique relaxations of potential practical interest. Based on the proposed taxonomy, a comprehensive study of the resulting optimization problems is carried out, aiming to study the cohesiveness properties of various clique relaxation aiming to assist researchers in selecting the most appropriate model for a particular application of interest; explore the fundamental properties of the clique relaxation models of interest that are responsible for the computational complexity of the corresponding optimization problems, and exploit these properties in designing appropriate computational tools for solving the problems in question; identify robust clique relaxation structures of practical interest.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 26, 2015
- Accession Number
- AD1001338
Entities
People
- Balabhaskar Balasundaram
- Sergiy Butenko
- Vladimir Boginski
Organizations
- Texas A&M University