Accession Number : AD1001338

Title :   Clique Relaxations in Biological and Social Network Analysis Foundations and Algorithms

Descriptive Note : Technical Report,01 Jul 2012,30 Jun 2015

Corporate Author : Texas A and M University College Station United States

Personal Author(s) : Butenko,Sergiy ; Balasundaram,Balabhaskar ; Boginski,Vladimir

Full Text :

Report Date : 26 Oct 2015

Pagination or Media Count : 18

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.

Descriptors :   optimization , social networks , classification , Mathematical models , Taxonomy , operations research , COMPUTATIONAL PROCESSES , algorithms

Distribution Statement : APPROVED FOR PUBLIC RELEASE