Improving network degree correlation through a finite number of degree-preserving rewirings

Degree correlation is a critical measure in network analysis. Generally, increasing degree correlation is beneficial for the network’s topology and dynamic behavior. Therefore, in this study, considering the cost and budget of manipulating network topology, we investigate the problem of improving degree correlation through a finite number of degree-preserving rewirings. First, we introduce the Maximum Assortative Improvement (MAI) problem, proving that it is monotone and submodular, which leads to the development of the Greedy Assortative (GA) method. Recognizing that the GA method may not be suitable for large-scale networks, we propose several heuristic rewiring methods: Edge Difference Assortative (EDA), Target Assortative (TA) and Probabilistic Edge Assortative (PEA). Finally, through experiments, we validate the rationality of our assumption and demonstrate the effectiveness of the GA method and the applicability of the three heuristic methods to different types of networks. In addition, extended experiments analyze the impact of these methods on network robustness.