Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem Academic Article uri icon

abstract

  • This paper introduces and studies the maximum k-plex problem, which arises in social network analysis and has wider applicability in several important areas employing graph-based data mining. After establishing NP-completeness of the decision version of the problem on arbitrary graphs, an integer programming formulation is presented, followed by a polyhedral study to identify combinatorial valid inequalities and facets. A branch-and-cut algorithm is implemented and tested on proposed benchmark instances. An algorithmic approach is developed exploiting the graph-theoretic properties of a k-plex that is effective in solving the problem to optimality on very large, sparse graphs such as the power law graphs frequently encountered in the applications of interest.

published proceedings

  • OPERATIONS RESEARCH

altmetric score

  • 2.5

author list (cited authors)

  • Balasundaram, B., Butenko, S., & Hicks, I. V.

citation count

  • 167

complete list of authors

  • Balasundaram, Balabhaskar||Butenko, Sergiy||Hicks, Illya V

publication date

  • January 2011