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

• 成果类型: Article
• 署名作者: Balasundaram, Balabhaskar; Butenko, Sergiy; Hicks, Illya V.
• 署名单位: Oklahoma State University System; Oklahoma State University - Stillwater; Texas A&M University System; Texas A&M University College Station; Rice University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0851
• 发表日期: 2011
• 页码: 133-142
• 关键词: algorithm

摘要

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.