Search

Cliques and their generalizations are frequently used to model "tightly knit" clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the s-club, which is a vertex subset that induces a subgraph of diameter at most s. This model has found use in a variety of fields because low-diameter clusters have practical significance in many applications. As this property is not hereditary on vertex-induced subgraphs, the diameter of a subgraph could increase upon the removal of some vertices and the subgraph could even become disconnected. For example, star graphs have diameter two but can be disconnected by removing the central vertex. The pursuit of a fault-tolerant extension of the s-club model has spawned two variants that we study in this article: robust s-clubs and hereditary s-clubs. We analyze the complexity of the verification and optimization problems associated with these variants. Then, we propose cut-like integer programming formulations for both variants whenever possible and investigate the separation complexity of the cut-like constraints. We demonstrate through our extensive computational experiments that the algorithmic ideas we introduce enable us to solve the problems to optimality on benchmark instances with several thousand vertices. This work lays the foundations for effective mathematical programming approaches for finding fault-tolerant s-clubs in large-scale networks. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: The computing for this project was performed at the High Performance Computing Center at Oklahoma State University supported in part through the National Science Foundation [Grant OAC-1531128]. This material is based upon work supported by the National Science Foundation under [Grants 1662757 and 1942065]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1231. [ABSTRACT FROM AUTHOR]

A k-plex is a clique relaxation introduced in social network analysis to model cohesive social subgroups that allows for a limited number of nonadjacent vertices (strangers) inside the cohesive subgroup. Several exact algorithms and heuristic approaches to find a maximum-size k-plex in the graph have been developed recently for this NP-hard problem. This article develops a greedy randomized adaptive search procedure (GRASP) for the maximum k-plex problem. We offer a key improvement in the design of the construction procedure that alleviates a drawback observed in multiple past studies. In existing construction heuristics, k-plexes found for smaller values of parameter k are sometimes not found for larger k even though they are feasible; instead inferior solutions are found. We identify the reasons behind this behavior and address these in our new construction procedure. We then show that an existing exact algorithm for solving this problem on power-law graphs can be considerably enhanced by using GRASP. The overall approach is able to solve the problem to optimality on massive social networks, including some with several million vertices and edges. These are orders of magnitude larger than the largest real-life social networks on which this problem has been solved to optimality in the current literature. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 388-407 2017 [ABSTRACT FROM AUTHOR]

A k-club is a subset of vertices of a graph that induces a subgraph of diameter at most k, where k is a positive integer. By definition, 1-clubs are cliques and the model is a distance-based relaxation of the clique definition for larger values of k. The k-club model is particularly interesting to study from a polyhedral perspective as the property is not hereditary on induced subgraphs when k is larger than one. This article introduces a new family of facet-defining inequalities for the 2-club polytope that unifies all previously known facets through a less restrictive combinatorial property, namely, independent (distance) 2-domination. The complexity of separation over this new family of inequalities is shown to be NP-hard. An exact formulation of this separation problem and a greedy separation heuristic are also proposed. The polytope described by the new inequalities (and nonnegativity) is then investigated and shown to be integral for acyclic graphs. An additional family of facets is also demonstrated for cycles of length indivisible by three. The effectiveness of these new facets as cutting planes and the difficulty of solving the separation problem in practice are then investigated via computational experiments on a test bed of benchmark instances. [ABSTRACT FROM AUTHOR]

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem. [ABSTRACT FROM AUTHOR]