Network robustness issues are crucial in a variety of application areas. In many situations, one of the key robustness requirements is the connectivity between each pair of nodes through a path that is short enough, which makes a network cluster more robust with respect to potential network component disruptions. A k‐club, which by definition is a subgraph of a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We develop a new compact linear 0–1 programming formulation for finding maximum k‐clubs that has substantially fewer entities compared to the previously known formulation (O(kn
2) instead of O(n
k+1), which is important in the general case of k >2) and is rather tight despite its compactness. Moreover, we introduce a new related concept referred to as an R‐robust k‐club (or, (k, R)‐club), which naturally arises from the developed k‐club formulations and extends the standard definition of a k‐club by explicitly requiring that there must be at least R distinct paths of length at most k between all pairs of nodes. A compact formulation for the maximum R‐robust k‐club problem is also developed, and error and attack tolerance properties of the important special case of R‐robust 2‐clubs are investigated. Computational results are presented for multiple types of random graph instances.
