Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem

Balabhaskar Balasundaram (), Sergiy Butenko () and Illya V. Hicks ()
Additional contact information
Balabhaskar Balasundaram: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Sergiy Butenko: Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843
Illya V. Hicks: Computational and Applied Mathematics Department, Rice University, Houston, Texas 77005

Operations Research, 2011, vol. 59, issue 1, 133-142

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.

Keywords: maximum k-plex problem; maximum clique problem; social network analysis; clique relaxations; cohesive subgroups; scale-free graphs; power law graphs (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0851 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:1:p:133-142

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().