×

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].

MSC:

05C90 Applications of graph theory
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B40 Search theory
PDFBibTeX XMLCite
Full Text: Link