Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
From MaRDI portal
Publication:3013924
DOI10.1287/opre.1100.0851zbMath1218.90228OpenAlexW2169088933MaRDI QIDQ3013924
Illya V. Hicks, Balabhaskar Balasundaram, Sergiy I. Butenko
Publication date: 19 July 2011
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.1100.0851
maximum clique problemscale-free graphssocial network analysisclique relaxationspower law graphscohesive subgroupsmaximum \(k\)-plex problem
Related Items (76)
The triangle \(k\)-club problem ⋮ Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ The minimal \(k\)-core problem for modeling \(k\)-assemblies ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Finding maximum subgraphs with relatively large vertex connectivity ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ A review on algorithms for maximum clique problems ⋮ Approximating 2-cliques in unit disk graphs ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Social structure optimization in team formation ⋮ Extended and discretized formulations for the maximum clique problem ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Integer models and upper bounds for the 3‐club problem ⋮ Robustness and Strong Attack Tolerance of Low-Diameter Networks ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Enhancing quantum annealing performance for the molecular similarity problem ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ BDD-based optimization for the quadratic stable set problem ⋮ On atomic cliques in temporal graphs ⋮ Approximating power node-deletion problems ⋮ On maximum ratio clique relaxations ⋮ In search of dense subgraphs: How good is greedy peeling? ⋮ Co-2-plex polynomials ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ On solving simplified diversified top-\(k\,s\)-plex problem ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ Asymptotic bounds for clustering problems in random graphs ⋮ Combinatorial algorithms for the maximum \(k\)-plex problem ⋮ Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems ⋮ CrawISN: community-aware data acquisition with maximum willingness in online social networks ⋮ Discovery of extreme events-related communities in contrasting groups of physical system networks ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ The maximum clique interdiction problem ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ Generalization of machine learning for problem reduction: a case study on travelling salesman problems ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ Graph signatures: identification and optimization ⋮ Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Upper bounds and heuristics for the 2-club problem ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ Discrete Optimization with Decision Diagrams ⋮ On Making a Distinguished Vertex Minimum Degree by Vertex Deletion ⋮ A network-based data mining approach to portfolio selection via weighted clique relaxations ⋮ A branch-and-bound approach for maximum quasi-cliques ⋮ A classification for community discovery methods in complex networks ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters ⋮ Worst-case analysis of clique MIPs ⋮ Continuous cubic formulations for cluster detection problems in networks ⋮ Optimization problems for the maximum \(k\)-plex ⋮ An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem ⋮ Finding groups with maximum betweenness centrality ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
Uses Software
This page was built for publication: Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
