An adaptive multi‐start graph partitioning algorithm for structuring cellular networks

In mobile network design, the problem of assigning network elements to controllers when defining network structure can be modeled as a graph partitioning problem. In this paper, a comprehensive analysis of a sophisticated graph partitioning algorithm for grouping base stations into packet control units in a mobile network is presented. The proposed algorithm combines multi‐level and adaptive multi‐start schemes to obtain high quality solutions efficiently. Performance assessment is carried out on a set of problem instances built from measurements in a live network. Overall results confirm that the proposed algorithm finds solutions better than those obtained by the classical multi‐level approaches and much faster than classical multi‐start approaches. The analysis of the optimization surface shows that the best local minima values follow a Gumbel distribution, which justifies the stagnation of naive multi‐start approaches after a few attempts. Likewise, the analysis shows that the best local minima share strong similarities, which is the reason for the superiority of adaptive multi‐start approaches. Finally, a sensitivity analysis shows the best internal parameter settings in the algorithm.