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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-1539 |
| Date | 15 May 2009 |
| Creators | Balasundaram, Balabhaskar |
| Contributors | Butenko, Sergiy |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0021 seconds