Skip to main content

Clique Relaxation Models in Network Analysis

Sergiy Butenko, Associate Professor and Donna and Jim Furber '64 Faculty Fellow, Department of Industrial and Systems Engineering, Texas A&M University

Increasing interest in studying community structures, or clusters in complex networks arising in various applications has led to a large and diverse body of literature introducing numerous graph-theoretic models relaxing certain characteristics of the classical clique concept. This talk first discusses a rigorous, systematic framework for studying the clique relaxation models from optimization perspective.  In particular, new clique relaxation structures are proposed, some of which can be used in clustering algorithms as well as effective scale-reduction techniques that help solving real-life instances of the classical maximum clique problem with tens of millions of nodes to optimality. To illustrate some of the methodological tools used, a part of the talk focuses on a special case of distance-based clique relaxations in unit-disk graphs arising in wireless networks.


Sergiy Butenko is an Associate Professor and Donna and Jim Furber `64 Faculty Fellow in Industrial and Systems Engineering at Texas A&M University. He received his B.S. and M.S. degrees in Mathematics at Kyiv National Taras Shevchenko University (Ukraine) and M.S. and Ph.D. degrees in Industrial and Systems Engineering at the University of Florida. His research focuses on network analysis and network-based data mining, discrete and global optimization, and graph theory. Applications of interest include biological, social, and financial networks, wireless ad hoc and sensor networks, transportation, and energy systems. His work has been supported by the Air Force office of Scientific Research, the U.S. Department of Energy, the National Science Foundation, and NATO.