Design and Application of Network Topology Robustness Optimization Algorithms Based on Cheeger's Inequality

Cheeger's inequality is used to estimate a lower bound on the number of edges that need to be cut off to split a regular graph into two subgraphs with the same number of nodes. Therefore, we design a network topology that is robust under malicious attacks based on Cheeger's inequality. Considering that Cheeger's inequality cannot be directly used to optimize complex networks in reality, we generalize the conclusion of Cheeger's inequality and use this conclusion to propose the Good Regular Graph algorithm (GRG) for generating strongly robust network topologies under malicious attacks. In addition, we explain the design principle of the algorithm from a graph-theoretic perspective and give the corresponding network topology expansion algorithm. GRG, after appropriate processing, can be applied to optimize the substructures of a wide range of real-world network topologies to enhance their robustness. Experiments show that the algorithms proposed in this research perform better compared to other algorithms. We prove from both theoretical and experimental perspectives that Cheeger's inequality can serve as a basis for designing robust network topologies under malicious attacks.