Cafieri, Sonia; Hansen, Pierre; Mladenović, Nenad Variable neighborhood search for edge-ratio network clustering. (English) Zbl 1476.05192 Butenko, Sergiy (ed.) et al., Examining robustness and vulnerability of networked systems. Selected papers of the NATO Advanced Research Workshop (ARW) on examining robustness and vulnerability of critical infrastructure networks, Kiev, Ukraine, June 3–5, 2013. Amsterdam: IOS Press. NATO Sci. Peace Secur. Ser. D, Inf. Commun. Secur. 37, 51-64 (2014). This paper discusses the edge-ratio clustering problem in graph theory, which was introduced in 2010 as a criterion for optimal graph bipartitioning in hierarchical divisive algorithms for cluster identification in networks. The algorithms in literature are too time consuming to perform bipartitioning maximizing the edge ratio when applied to big datasets. In this paper, the authors propose a variable neighborhood search heuristic for solving the bipartitioning problem in a hierarchical divisive graph clustering algorithm, according to the recently introduced edge-ratio criterion. A full description including the pseudo-codes of the procedures used to implement the main steps of the heuristic is presented. Computational results show that their approach reduces the computational time.For the entire collection see [Zbl 1326.94006]. Reviewer: Zhuchun Li (Harbin) Cited in 2 Documents MSC: 05C90 Applications of graph theory 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 90B40 Search theory Keywords:network clustering; edge-ratio; variable neighborhood search PDFBibTeX XMLCite \textit{S. Cafieri} et al., NATO Sci. Peace Secur. Ser. D, Inf. Commun. Secur. 37, 51--64 (2014; Zbl 1476.05192) Full Text: Link