On the maximum small-world subgraph problem

A clique (or a complete subgraph) is a popular model for an “ideal” cluster in a network. However, in many practical applications this notion turns out to be overly restrictive as it requires the existence of all pairwise links within the cluster. Thus, the researchers and practitioners often rely on various clique relaxation ideas for more flexible models of highly connected clusters. In this paper, we propose a new clique relaxation model referred to as a small-world subgraph, which represents a network cluster with “small-world” properties: low average distance and high clustering coefficient. In particular, we demonstrate that the proposed small-world subgraph model has better “cohesiveness” characteristics than other existing clique relaxation models in some worst-case scenarios. The main focus of the paper is on the problem of finding a small-world subgraph of maximum cardinality in a given graph. We describe a mixed integer programming (MIP) formulation of the problem along with several algorithmic enhancements. For solving large-scale instances of the problem we propose a greedy-type heuristic referred to as the iterative depth-first search (IDF) algorithm. Furthermore, we show that the small-world subgraphs identified by the IDF algorithm have an additional property that may be attractive from the practical perspective, namely, 2-connectivity. Finally, we perform extensive computational experiments on real-world and randomly generated networks to demonstrate the performance of the developed computational approaches that also reveal interesting insights about the proposed clique relaxation model.