Balasundaram, Balabhaskar (2007-08). Graph theoretic generalizations of clique: optimization and extensions. Doctoral Dissertation. Thesis uri icon

abstract

  • This dissertation considers graph theoretic generalizations of the maximum clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first time. A social network is usually represented by a graph, and cliques were the first models of "tightly knit groups" in social networks, referred to as cohesive subgroups. Cliques are idealized models and their overly restrictive nature motivated the development of clique relaxations that relax different aspects of a clique. Identifying large cohesive subgroups in social networks has traditionally been used in criminal network analysis to study organized crimes such as terrorism, narcotics and money laundering. More recent applications are in clustering and data mining wireless networks, biological networks as well as graph models of databases and the internet. This research has the potential to impact homeland security, bioinformatics, internet research and telecommunication industry among others. The focus of this dissertation is a degree-based relaxation called k-plex. A distance-based relaxation called k-clique and a diameter-based relaxation called k-club are also investigated in this dissertation. We present the first systematic study of the complexity aspects of these problems and application of mathematical programming techniques in solving them. Graph theoretic properties of the models are identified and used in the development of theory and algorithms. Optimization problems associated with the three models are formulated as binary integer programs and the properties of the associated polytopes are investigated. Facets and valid inequalities are identified based on combinatorial arguments. A branch-and-cut framework is designed and implemented to solve the optimization problems exactly. Specialized preprocessing techniques are developed that, in conjunction with the branch-and-cut algorithm, optimally solve the problems on real-life power law graphs, which is a general class of graphs that include social and biological networks. Computational experiments are performed to study the effectiveness of the proposed solution procedures on benchmark instances and real-life instances. The relationship of these models to the classical maximum clique problem is studied, leading to several interesting observations including a new compact integer programming formulation. We also prove new continuous non-linear formulations for the classical maximum independent set problem which maximize continuous functions over the unit hypercube, and characterize its local and global maxima. Finally, clustering and network design extensions of the clique relaxation models are explored.
  • This dissertation considers graph theoretic generalizations of the maximum
    clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first
    time. A social network is usually represented by a graph, and cliques were the first
    models of "tightly knit groups" in social networks, referred to as cohesive subgroups.
    Cliques are idealized models and their overly restrictive nature motivated the development of clique relaxations that relax different aspects of a clique. Identifying large
    cohesive subgroups in social networks has traditionally been used in criminal network
    analysis to study organized crimes such as terrorism, narcotics and money laundering.
    More recent applications are in clustering and data mining wireless networks, biological networks as well as graph models of databases and the internet. This research
    has the potential to impact homeland security, bioinformatics, internet research and
    telecommunication industry among others.
    The focus of this dissertation is a degree-based relaxation called k-plex. A
    distance-based relaxation called k-clique and a diameter-based relaxation called k-club are also investigated in this dissertation. We present the first systematic study
    of the complexity aspects of these problems and application of mathematical programming techniques in solving them. Graph theoretic properties of the models are
    identified and used in the development of theory and algorithms.
    Optimization problems associated with the three models are formulated as binary integer programs and the properties of the associated polytopes are investigated. Facets and valid inequalities are identified based on combinatorial arguments.
    A branch-and-cut framework is designed and implemented to solve the optimization
    problems exactly. Specialized preprocessing techniques are developed that, in conjunction with the branch-and-cut algorithm, optimally solve the problems on real-life
    power law graphs, which is a general class of graphs that include social and biological
    networks. Computational experiments are performed to study the effectiveness of the
    proposed solution procedures on benchmark instances and real-life instances.
    The relationship of these models to the classical maximum clique problem is
    studied, leading to several interesting observations including a new compact integer
    programming formulation. We also prove new continuous non-linear formulations for
    the classical maximum independent set problem which maximize continuous functions
    over the unit hypercube, and characterize its local and global maxima. Finally, clustering and network design extensions of the clique relaxation models are explored.

publication date

  • August 2007