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

Balabhaskar Balasundaram
Balabhaskar Balasundaram
[email protected]
School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Search for more papers by this author
,
Sergiy Butenko
Sergiy Butenko
[email protected]
Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843
Search for more papers by this author
,
Illya V. Hicks
Illya V. Hicks
[email protected]
Computational and Applied Mathematics Department, Rice University, Houston, Texas 77005
Search for more papers by this author

Balabhaskar Balasundaram

[email protected]

School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078

Search for more papers by this author

Sergiy Butenko

[email protected]

Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843

Search for more papers by this author

Illya V. Hicks

[email protected]

Computational and Applied Mathematics Department, Rice University, Houston, Texas 77005

Search for more papers by this author

Published Online:8 Feb 2011https://doi.org/10.1287/opre.1100.0851

Supplemental Material

opre.1100.0851-sm-ec.pdf (188 KB)

Cited by
- Computing maximum cliques in unit disk graphs
  Computational Geometry, Vol. 135
- An observer-enhanced evolutionary search framework for solving the simplified diversified top-k s-plex problem
  Expert Systems with Applications, Vol. 328
- Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance
  18 May 2026 | Proceedings of the ACM on Management of Data, Vol. 4, No. 3
- Finding the Maximum Subgraph of Prescribed Strength
  10 December 2025 | Networks, Vol. 87, No. 2
- Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
  5 December 2025 | Proceedings of the ACM on Management of Data, Vol. 3, No. 6
- Rank-sparsity decomposition for planted quasi clique recovery
  19 November 2025 | Journal of Global Optimization, Vol. 93, No. 4
- Contractions in perfect graphs
  Discrete Applied Mathematics, Vol. 377
- Efficient $k$k-Plex Mining in Temporal Graphs
  IEEE Transactions on Knowledge and Data Engineering, Vol. 37, No. 12
- Applications of Gaussian Boson Sampling to Solve Some Chemistry Problems
  28 November 2025 | Quantum Reports, Vol. 7, No. 4
- An Implicit Enumeration Approach for Maximum Ratio Clique Relaxations
  13 June 2025 | Networks, Vol. 86, No. 3
- Efficient Antagonistic $k$k-Plex Enumeration in Signed Graphs
  IEEE Transactions on Big Data, Vol. 11, No. 5
- Maximum Degree-Based Quasi-Clique Search via an Iterative Framework
  3 August 2025
- Efficient Detection of $k$-Plex Structures in Large Graphs Through Constraint Learning
  IEEE Transactions on Computational Social Systems, Vol. 12, No. 4
- On Searching and Querying Maximum Directed (k,ℓ)-Plex
  IEEE Transactions on Knowledge and Data Engineering, Vol. 37, No. 8
- An efficient iterated local search for the minimum quasi-clique partitioning problem
  Computers & Operations Research, Vol. 179
- Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach
  18 June 2025 | Proceedings of the ACM on Management of Data, Vol. 3, No. 3
- Improving local search algorithms for clique relaxation problems via group driven initialization
  12 December 2024 | Frontiers of Computer Science, Vol. 19, No. 6
- Efficient k -Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory
  4 September 2025 | Proceedings of the VLDB Endowment, Vol. 18, No. 10
- With Anchors or Not: Fairness-Aware Truss-Based Community Search on Attributed Graphs
- A fast maximum clique algorithm based on network decomposition for large sparse networks
  Chaos, Solitons & Fractals, Vol. 194
- Maximum k -Plex Finding: Choices of Pruning Techniques Matter!
  3 September 2025 | Proceedings of the VLDB Endowment, Vol. 18, No. 9
- Identifying most lethal cliques in disease comorbidity graphs
  3 April 2025 | IISE Transactions on Healthcare Systems Engineering, Vol. 15, No. 2
- Categories of important edges in dynamics on graphs
  23 April 2025 | Royal Society Open Science, Vol. 12, No. 4
- Degree and Distance-Based Clique Relaxations
  18 October 2024
- k-plex-based community detection with graph neural networks
  Information Sciences, Vol. 689
- Finding conserved low‐diameter subgraphs in social and biological networks
  29 August 2024 | Networks, Vol. 84, No. 4
- A survey on optimization studies of group centrality metrics
  21 August 2024 | Networks, Vol. 84, No. 4
- On finding the community with maximum persistence probability
  26 December 2023 | 4OR, Vol. 22, No. 4
- The Maximum Influence k-Plex Problem and its Branch-and-Bound Algorithm
  22 February 2025 | International Journal on Artificial Intelligence Tools, Vol. 33, No. 08
- In-Depth Analysis of Densest Subgraph Discovery in a Unified Framework
  20 May 2025 | Proceedings of the VLDB Endowment, Vol. 18, No. 4
- Flexi-clique: Exploring Flexible and Sub-linear Clique Structures
  21 October 2024
- Approximating power node-deletion problems
  Theoretical Computer Science, Vol. 1012
- Theoretically and Practically Efficient Maximum Defective Clique Search
  30 September 2024 | Proceedings of the ACM on Management of Data, Vol. 2, No. 4
- Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance
  28 February 2025 | Proceedings of the VLDB Endowment, Vol. 18, No. 2
- Maximum k -Plex Search: An Alternated Reduction-and-Bound Method
  28 February 2025 | Proceedings of the VLDB Endowment, Vol. 18, No. 2
- Structural Parameterizations for Two Bounded Degree Problems Revisited
  10 September 2024 | ACM Transactions on Computation Theory, Vol. 16, No. 3
- Maximizing Engagement in Large-Scale Social Networks
  Samuel Kroger,
  Hamidreza Validi,
  Illya V. Hicks
  5 August 2024 | INFORMS Journal on Optimization, Vol. 6, No. 3-4
- A local search algorithm with movement gap and adaptive configuration checking for the maximum weighted s-plex problem
  Engineering Applications of Artificial Intelligence, Vol. 133
- Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks
  30 August 2024 | Proceedings of the VLDB Endowment, Vol. 17, No. 11
- Discovering stable communities in massive temporal graphs
  29 July 2024
- Quantum Algorithms for the Maximum K-Plex Problem
- Bottom-up k-Vertex Connected Component Enumeration by Multiple Expansion
- Efficient Maximal Temporal Plex Enumeration
- Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling
  23 May 2024 | PRX Quantum, Vol. 5, No. 2
- Asymptotic bounds for clustering problems in random graphs
  13 December 2023 | Networks, Vol. 83, No. 3
- Dense subgraphs induced by edge labels
  6 September 2023 | Machine Learning, Vol. 113, No. 4
- Maximum k-Plex Computation: Theory and Practice
  26 March 2024 | Proceedings of the ACM on Management of Data, Vol. 2, No. 1
- Network Higher-Order Structure Dismantling
  11 March 2024 | Entropy, Vol. 26, No. 3
- Efficient Distributed Core Graph Decomposition
- Efficient Maximum k-Defective Clique Computation with Improved Time Complexity
  13 November 2023 | Proceedings of the ACM on Management of Data, Vol. 1, No. 3
- Fairness-Aware Maximal Clique in Large Graphs: Concepts and Algorithms
  IEEE Transactions on Knowledge and Data Engineering, Vol. 35, No. 11
- Efficient Exact Minimum k-Core Search in Real-World Graphs
  21 October 2023
- Parallel Bounded Search for the Maximum Clique Problem
  30 September 2023 | Journal of Computer Science and Technology, Vol. 38, No. 5
- Maximum weight t -sparse set problem on vector-weighted graphs
  31 October 2023 | RAIRO - Operations Research, Vol. 57, No. 5
- Maximal Clique Search in Weighted Graphs
  IEEE Transactions on Knowledge and Data Engineering, Vol. 35, No. 9
- On atomic cliques in temporal graphs
  7 February 2023 | Optimization Letters, Vol. 17, No. 4
- On solving simplified diversified top-k s-plex problem
  Computers & Operations Research, Vol. 153
- Core Decomposition and Maintenance in Bipartite Graphs
  Tsinghua Science and Technology, Vol. 28, No. 2
- Approximating Power Node-Deletion Problems
  25 April 2023
- Identifying Critical Nodes in a Network
  21 July 2023
- Quantifying Node-Based Core Resilience
  17 September 2023
- Efficient Maximum k-plex Search via Selective Branch-and-Bound
  22 November 2023
- Listing maximal k-relaxed-vertex connected components from large graphs
  Information Sciences, Vol. 620
- On maximum ratio clique relaxations
  15 April 2022 | Networks, Vol. 80, No. 4
- Reinforcement learning based coarse-to-fine search for the maximum k -plex problem
  Applied Soft Computing, Vol. 131
- Maximum independent sets of graph vertices searching for software projects improvement
  1 December 2022 | PROBLEMS IN PROGRAMMING, No. 3-4
- Continuous cubic formulations for cluster detection problems in networks
  16 October 2020 | Mathematical Programming, Vol. 196, No. 1-2
- Scaling Up Maximal k -plex Enumeration
  17 October 2022
- Efficient maximum k -plex computation over large sparse graphs
  23 November 2022 | Proceedings of the VLDB Endowment, Vol. 16, No. 2
- Worst-case analysis of clique MIPs
  23 September 2021 | Mathematical Programming, Vol. 195, No. 1-2
- Interdicting Low-Diameter Cohesive Subgroups in Large-Scale Social Networks
  Niloufar Daemi,
  Juan S. Borrero,
  Balabhaskar Balasundaram
  24 February 2022 | INFORMS Journal on Optimization, Vol. 4, No. 3
- Optimization Problems for the Maximum k-Plex*
  18 October 2022 | Cybernetics and Systems Analysis, Vol. 58, No. 4
- Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem
  S. Raghavan,
  Rui Zhang
  8 February 2022 | INFORMS Journal on Computing, Vol. 34, No. 3
- BDD-based optimization for the quadratic stable set problem
  Discrete Optimization, Vol. 44
- Fairness-aware Maximal Clique Enumeration
- Continuous Geo-Social Group Monitoring over Moving Users
- K-core decomposition on super large graphs with limited resources
  6 May 2022
- Listing Maximal k-Plexes in Large Real-World Graphs
  25 April 2022
- Influence Maximization with Latency Requirements on Social Networks
  S. Raghavan,
  Rui Zhang
  9 November 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
  Stefano Coniglio,
  Stefano Gualandi
  29 November 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- Finding a Concise, Precise, and Exhaustive Set of Near Bi-Cliques in Dynamic Graphs
  15 February 2022
- Graph signatures: Identification and optimization
  European Journal of Operational Research, Vol. 296, No. 3
- An effective branch-and-bound algorithm for the maximum s -bundle problem
  European Journal of Operational Research, Vol. 297, No. 1
- Community Detection in Edge-Labeled Graphs
  6 November 2022
- An improved approximation for Maximum k -dependent Set on bipartite graphs
  Discrete Applied Mathematics, Vol. 307
- Incremental Graph Computation: Anchored Vertex Tracking in Dynamic Social Networks
  IEEE Transactions on Knowledge and Data Engineering, Vol. 33
- Continuous Geo-Social Group Monitoring in Dynamic LBSNs
  IEEE Transactions on Knowledge and Data Engineering, Vol. 51
- Cooperation patterns of members in networks during co-creation
  8 June 2021 | Scientific Reports, Vol. 11, No. 1
- Mining Largest Maximal Quasi-Cliques
  15 April 2021 | ACM Transactions on Knowledge Discovery from Data, Vol. 15, No. 5
- Scaling Up Distance-generalized Core Decomposition
  30 October 2021
- Generalization of machine learning for problem reduction: a case study on travelling salesman problems
  1 September 2020 | OR Spectrum, Vol. 43, No. 3
- Hardness and tractability of the γ-Complete Subgraph problem
  Information Processing Letters, Vol. 169
- A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques
  Timo Gschwind,
  Stefan Irnich,
  Fabio Furini,
  Roberto Wolfler Calvo
  12 November 2020 | INFORMS Journal on Computing, Vol. 33, No. 3
- A meta-algorithm for finding large k-plexes
  1 May 2021 | Knowledge and Information Systems, Vol. 63, No. 7
- In search of dense subgraphs: How good is greedy peeling?
  20 March 2021 | Networks, Vol. 77, No. 4
- Local search for the maximum k-plex problem
  8 October 2020 | Journal of Heuristics, Vol. 27, No. 3
- Rumor investigation in networks
  Economic Modelling, Vol. 98
- An Efficient Algorithm for the Anchored k-Core Budget Minimization Problem
- Structure-Aware Parameter-Free Group Query via Heterogeneous Information Network Transformer
- Computing maximum k-defective cliques in massive graphs
  Computers & Operations Research, Vol. 127
- Maximum (L, K)-Lasting Cores in Temporal Social Networks
  6 April 2021
- On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
  19 August 2020 | Algorithmica, Vol. 83, No. 1
- Towards Keyword-based Geo-Social Group Query Services
  IEEE Transactions on Services Computing
- MEA‐CNDP: A Membrane Evolutionary Algorithm for Solving Biobjective Critical Node Detection Problem
  28 November 2021 | Computational Intelligence and Neuroscience, Vol. 2021, No. 1
- The four dimensions of social network analysis: An overview of research methods, applications, and software tools
  Information Fusion, Vol. 63
- An opposition-based memetic algorithm for the maximum quasi-clique problem
  European Journal of Operational Research, Vol. 286, No. 1
- CrawlSN: community-aware data acquisition with maximum willingness in online social networks
  8 September 2020 | Data Mining and Knowledge Discovery, Vol. 34, No. 5
- Variable Neighborhood Search for Partitioning Sparse Biological Networks into the Maximum Edge-Weighted k-Plexes
  IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 17, No. 5
- An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph
  Zhuqi Miao,
  Balabhaskar Balasundaram
  3 February 2020 | INFORMS Journal on Computing, Vol. 32, No. 3
- Applications of near-term photonic quantum computers: software and algorithms
  12 May 2020 | Quantum Science and Technology, Vol. 5, No. 3
- Social network analysis of practice adoption facing outbreaks of African Swine Fever
  Preventive Veterinary Medicine, Vol. 179
- A Tutorial on Clique Problems in Communications and Signal Processing
  Proceedings of the IEEE, Vol. 108, No. 4
- A survey of community search over big graphs
  20 July 2019 | The VLDB Journal, Vol. 29, No. 1
- A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems
  7 February 2019 | Annals of Operations Research, Vol. 284, No. 1
- Static and Dynamic Community Detection Methods That Optimize a Specific Objective Function: A Survey and Experimental Evaluation
  IEEE Access, Vol. 8
- Listing All Maximal k -Plexes in Temporal Graphs
  5 September 2019 | ACM Journal of Experimental Algorithmics, Vol. 24
- On Efficient Processing of Group and Subsequent Queries for Social Activity Planning
  IEEE Transactions on Knowledge and Data Engineering, Vol. 31, No. 12
- The maximum l-triangle k-club problem: Complexity, properties, and algorithms
  Computers & Operations Research, Vol. 111
- Density-Friendly Graph Decomposition
  24 September 2019 | ACM Transactions on Knowledge Discovery from Data, Vol. 13, No. 5
- A Quantum-Inspired Method for Three-Dimensional Ligand-Based Virtual Screening
  18 October 2019 | Journal of Chemical Information and Modeling, Vol. 59, No. 10
- A Two-Stage Stochastic Optimization Approach for Detecting Structurally Stable Clusters in Randomly Changing Graphs
  IEEE Transactions on Network Science and Engineering, Vol. 6, No. 4
- On Crawling Community-aware Online Social Network Data
  12 September 2019
- The maximum clique interdiction problem
  European Journal of Operational Research, Vol. 277, No. 1
- Vertex Selection Heuristics in Branch-and-Bound Algorithms for the Maximum k -Plex Problem
  29 August 2019 | International Journal on Artificial Intelligence Tools, Vol. 28, No. 05
- An extension of adaptive multi-start tabu search for the maximum quasi-clique problem
  Computers & Industrial Engineering, Vol. 132
- A Parallel Hybrid Genetic Algorithm for Solving the Maximum Clique Problem
  20 October 2019
- Community Search over Big Graphs
  26 February 2022
- Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs
  Engineering Applications of Artificial Intelligence, Vol. 77
- MEAMCP: A Membrane Evolutionary Algorithm for Solving Maximum Clique Problem
  IEEE Access, Vol. 7
- A Swap-Based Heuristic Algorithm for the Maximum $k$ -Plex Problem
  IEEE Access, Vol. 7
- I/O Efficient Core Graph Decomposition: Application to Degeneracy Ordering
  IEEE Transactions on Knowledge and Data Engineering, Vol. 31, No. 1
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
  Discrete Applied Mathematics, Vol. 251
- GraphZIP: a clique-based sparse graph compression method
  3 March 2018 | Journal of Big Data, Vol. 5, No. 1
- Now You See Me: Identifying Duplicate Network Personas
- Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs
  European Journal of Operational Research, Vol. 269, No. 3
- Tight Running Time Lower Bounds for Vertex Deletion Problems
  14 April 2018 | ACM Transactions on Computation Theory, Vol. 10, No. 2
- Integer programming models for detecting graph bipartitions with structural requirements
  25 October 2017 | Networks, Vol. 71, No. 4
- A heuristic based harmony search algorithm for maximum clique problem
  7 September 2017 | OPSEARCH, Vol. 55, No. 2
- Knowledge-based analytics for massively distributed networks with noisy data
  30 November 2017 | International Journal of Production Research, Vol. 56, No. 8
- A two-stage stochastic programming approach for influence maximization in social networks
  23 October 2017 | Computational Optimization and Applications, Vol. 69, No. 3
- On maximum degree‐based ‐quasi‐clique problem: Complexity and exact approaches
  20 November 2017 | Networks, Vol. 71, No. 2
- Enhancing response coordination through the assessment of response network structural dynamics
  15 February 2018 | PLOS ONE, Vol. 13, No. 2
- Discounted average degree density metric and new algorithms for the densest subgraph problem
  21 August 2017 | Networks, Vol. 71, No. 1
- Approximating Partially Bounded Degree Deletion on Directed Graphs
  31 January 2018
- Viewing the Meso-Scale Structures in Protein-Protein Interaction Networks Using 2-Clubs
  IEEE Access, Vol. 6
- Network-based optimization techniques for wind farm location decisions
  Frontiers of Engineering Management, Vol. 5, No. 4
- Query Optimal k-Plex Based Community in Graphs
  13 November 2017 | Data Science and Engineering, Vol. 2, No. 4
- Geo-social group queries with minimum acquaintance constraints
  19 July 2017 | The VLDB Journal, Vol. 26, No. 5
- Frequency-driven tabu search for the maximum s-plex problem
  Computers & Operations Research, Vol. 86
- Fast Enumeration of Large k-Plexes
  4 August 2017
- On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
  Computers & Operations Research, Vol. 84
- Approaches for finding cohesive subgroups in large‐scale social networks via maximum k ‐plex detection
  12 May 2017 | Networks, Vol. 69, No. 4
- Towards Social-Aware Ridesharing Group Query Services
  IEEE Transactions on Services Computing, Vol. 10, No. 4
- Enhancing quantum annealing performance for the molecular similarity problem
  9 April 2017 | Quantum Information Processing, Vol. 16, No. 5
- Community detection in social networks using user frequent pattern mining
  27 July 2016 | Knowledge and Information Systems, Vol. 51, No. 1
- The triangle k-club problem
  29 March 2016 | Journal of Combinatorial Optimization, Vol. 33, No. 3
- Finding groups with maximum betweenness centrality
  1 May 2016 | Optimization Methods and Software, Vol. 32, No. 2
- On a generalization of Nemhauser and Trotter's local optimization theorem
  Journal of Computer and System Sciences, Vol. 84
- Approximating Bounded Degree Deletion via Matroid Matching
  14 April 2017
- A Model for Optimal Reinforcement of Error- and Attack-Resilient Clusters in Networks Under Uncertainty
  7 December 2017
- Social structure optimization in team formation
  Computers & Operations Research, Vol. 74
- A local dynamic method for tracking communities and their evolution in dynamic networks
  Knowledge-Based Systems, Vol. 110
- Incremental k-core decomposition: algorithms and evaluation
  15 February 2016 | The VLDB Journal, Vol. 25, No. 3
- A model of friendship networks based on social network analysis
  2 April 2016 | Artificial Life and Robotics, Vol. 21, No. 2
- Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
  21 November 2015 | Computational Optimization and Applications, Vol. 64, No. 1
- STeller: An approach for context-aware story detection using different similarity metrics and dense subgraph mining
- I/O efficient Core Graph Decomposition at web scale
- Wine industry supply chain: international comparative study using social networks analysis
  27 April 2016 | Supply Chain Forum: An International Journal, Vol. 17, No. 2
- Multivariate Algorithmics for Finding Cohesive Subnetworks
  16 March 2016 | Algorithms, Vol. 9, No. 1
- Discrete Optimization with Decision Diagrams
  David Bergman,
  Andre A. Cire,
  Willem-Jan van Hoeve,
  J. N. Hooker
  21 January 2016 | INFORMS Journal on Computing, Vol. 28, No. 1
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
  20 July 2016
- Identification and ranking of key persons in a Social Networking Website using Hadoop & Big Data Analytics
- The Minimal k-Core Problem for Modeling k-Assemblies
  14 July 2015 | The Journal of Mathematical Neuroscience (JMN), Vol. 5, No. 1
- A branch-and-price-and-cut method for computing an optimal bramble
  Discrete Optimization, Vol. 18
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
  Discrete Applied Mathematics, Vol. 193
- Efficient Enumeration of Maximal k-Plexes
  27 May 2015
- Density-friendly Graph Decomposition
  18 May 2015
- A review on algorithms for maximum clique problems
  European Journal of Operational Research, Vol. 242, No. 3
- On a Generalization of Nemhauser and Trotter’s Local Optimization Theorem
  27 November 2015
- K-core decomposition of a protein domain co-occurrence network reveals lower cancer mutation rates for interior cores
  Journal of Clinical Bioinformatics, Vol. 5, No. 1
- Two-phase heuristics for the k-club problem
  Computers & Operations Research, Vol. 52
- Finding maximum subgraphs with relatively large vertex connectivity
  European Journal of Operational Research, Vol. 239, No. 2
- CAST
  3 November 2014
- A branch-and-bound approach for maximum quasi-cliques
  14 November 2012 | Annals of Operations Research, Vol. 216, No. 1
- A network-based data mining approach to portfolio selection via weighted clique relaxations
  29 May 2013 | Annals of Operations Research, Vol. 216, No. 1
- On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion
  11 October 2012 | Algorithmica, Vol. 68, No. 3
- Approximating 2-cliques in unit disk graphs
  Discrete Applied Mathematics, Vol. 166
- Parallel Combinatorial Optimization with Decision Diagrams
- Detecting Maximum k-Plex with Iterative Proper ℓ-Plex Search
- The entry of logistics service provider (LSP) into the wine industry supply chain
  4 November 2014 | BIO Web of Conferences, Vol. 3
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
  14 March 2013 | Computational Optimization and Applications, Vol. 56, No. 1
- Discovery of extreme events-related communities in contrasting groups of physical system networks
  1 September 2012 | Data Mining and Knowledge Discovery, Vol. 27, No. 2
- Familial groups in social networks
  Social Networks, Vol. 35, No. 3
- OSN Crawling Schedulers and Their Implications on k -Plexes Detection
  26 March 2013 | International Journal of Intelligent Systems, Vol. 28, No. 6
- On clique relaxation models in network analysis
  European Journal of Operational Research, Vol. 226, No. 1
- Streaming algorithms for k-core decomposition
  1 April 2013 | Proceedings of the VLDB Endowment, Vol. 6, No. 6
- Combinatorial Optimization Techniques for Network-Based Data Mining
  26 July 2013
- Combinatorial Optimization in Data Mining
  26 July 2013
- Graph Theoretic Clique Relaxations and Applications
  26 July 2013
- On the maximum quasi-clique problem
  Discrete Applied Mathematics, Vol. 161, No. 1-2
- Clustering with local restrictions
  Information and Computation, Vol. 222
- Network clustering via clique relaxations: A community based approach
- Dense Percolation in Large-Scale Mean-Field Random Networks Is Provably “Explosive”
  18 December 2012 | PLoS ONE, Vol. 7, No. 12
- Integer models and upper bounds for the 3‐club problem
  21 February 2012 | Networks, Vol. 60, No. 3
- Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion
  1 February 2011 | Algorithmica, Vol. 62, No. 3-4
- Identifying large robust network clusters via new compact formulations of maximum k-club problems
  European Journal of Operational Research, Vol. 218, No. 2
- Clique Relaxation Models in Social Network Analysis
  27 October 2011
- Robustness and Strong Attack Tolerance of Low-Diameter Networks
  1 July 2012
- Finding Dense Subgraphs of Sparse Graphs
- Combinatorial algorithms for the maximum k-plex problem
  3 August 2010 | Journal of Combinatorial Optimization, Vol. 23, No. 1
- On Bounded-Degree Vertex Deletion parameterized by treewidth
  Discrete Applied Mathematics, Vol. 160, No. 1-2
- Co-2-plex polynomials
  8 April 2010 | Journal of Combinatorial Optimization, Vol. 22, No. 4
- A generalization of Nemhauser and Trotterʼs local optimization theorem
  Journal of Computer and System Sciences, Vol. 77, No. 6
- A classification for community discovery methods in complex networks
  9 September 2011 | Statistical Analysis and Data Mining: The ASA Data Science Journal, Vol. 4, No. 5
- On social-temporal group query with acquaintance constraint
  1 March 2011 | Proceedings of the VLDB Endowment, Vol. 4, No. 6
- On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
- Cohesive subgroup model for graph-based text mining

Volume 59, Issue 1

January-February 2011

Pages iii-266

Article Information

Supplemental Material

Metrics

Information

Received:December 01, 2006
Accepted:February 01, 2010
Published Online:February 08, 2011

Cite as

Balabhaskar Balasundaram, Sergiy Butenko, Illya V. Hicks, (2011) Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem. Operations Research 59(1):133-142.

https://doi.org/10.1287/opre.1100.0851

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

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

Supplemental Material

Volume 59, Issue 1

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News