This paper presents a variable neighborhood search (VNS) algorithm that is specially designed for the blockmodeling of two-mode binary network matrices in accordance with structural equivalence. Computational results for 768 synthetic test networks revealed that the VNS heuristic outperformed a relocation heuristic (RH) and a tabu search (TS) method for the same problem. Next, the three heuristics were applied to two-mode network data pertaining to the votes of member countries on resolutions in the United Nations General Assembly. A comparative analysis revealed that the VNS heuristic often provided slightly better criterion function values than RH and TS, and that these small differences in criterion function values could sometimes be associated with substantial differences in the actual partitions obtained. Overall, the results suggest that the VNS heuristic is a promising approach for blockmodeling of two-mode binary networks. Recommendations for extensions to stochastic blockmodeling applications are provided.

Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide local search methods that use large neighborhoods like VNS. We propose DGVNS (Decomposition Guided VNS) which uses the graph of clusters in order to build neighborhood structures enabling better diversification and intensification. Second, we introduce tightness dependent tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Third, experiments performed on random instances (GRAPH) and real life instances (CELAR, SPOT5 and tagSNP) show the appropriateness and the efficiency of our approach. Moreover, we study and discuss the influence of the width of the tree decomposition on our approach and the relevance of removing clusters with very few proper variables from the tree decomposition.