Research on Weighted Network Randomization Based on Simulated Annealing Algorithm

Background Introduction

In the field of neuroscience, connectomics is an important branch for studying the structure and function of brain neural networks. With the development of modern imaging technologies, researchers are able to acquire a wealth of biologically meaningful edge weights, which are crucial for understanding the organization and function of brain networks. However, despite the increasing prevalence of weighted network analysis in connectomics, most existing network randomization models primarily preserve binary node degree, often neglecting the importance of edge weights. This may lead to inaccurate assessments of the significance of network features when weight information is not adequately considered.

To address this issue, a research team from McGill University, University of Minnesota, and other institutions proposed a weighted network randomization method based on the simulated annealing algorithm. This algorithm generates randomized networks that preserve the weighted degree sequence and demonstrates superior performance across multiple network formats, including directed and signed networks. The study aims to provide a simple yet powerful tool for analyzing next-generation connectomics datasets and to reveal the importance of weight information in inferring brain network organization.

Source of the Paper

This research was conducted by Filip Milisav, Vincent Bazinet, Richard F. Betzel, and Bratislav Mišić and was published in the journal Nature Computational Science in January 2025 under the title “A simulated annealing algorithm for randomizing weighted networks”.

Research Process and Results

Research Process

1. Algorithm Design
   The research team proposed a weighted network randomization algorithm based on simulated annealing. Simulated annealing is a probabilistic optimization algorithm that approximates global optimal solutions in complex search spaces. Compared to other randomization algorithms, this algorithm’s advantage lies in its ability to preserve the original network’s weight distribution, degree sequence, and weighted degree sequence for each randomized network instance. Specifically, the algorithm randomly selects pairs of edge weights for permutation and decides whether to accept the permutation based on the system’s energy (the mean squared error between the weighted degree sequences of the original and randomized networks). The algorithm’s design does not rely on any analytical derivations but instead extends the classic Maslov-Sneppen rewiring algorithm in network science.

2. Performance Comparison
   To validate the algorithm’s performance, the research team compared it with the Rubinov-Sporns algorithm and the classic Maslov-Sneppen algorithm. Experiments were conducted on two publicly available Diffusion Weighted MRI (DWI) datasets from Lausanne University Hospital and the Human Connectome Project (HCP). The study generated 10,000 randomized networks and calculated the Spearman rank correlation coefficient between the original and randomized networks to evaluate the algorithm’s performance in preserving the weighted degree sequence. Additionally, the Kolmogorov-Smirnov statistic was used to measure the performance of the randomized networks in preserving the weighted degree distribution.

3. Morphospace Analysis
   To assess the variability of the randomized networks, the research team embedded the generated randomized networks into a two-dimensional morphospace spanned by characteristic path length and clustering coefficient. Morphospace analysis visually demonstrates the distribution of randomized networks in terms of global network features and provides a quantitative assessment of the variability of randomized networks generated by different algorithms.

4. Weighted Rich-Club Phenomenon Study
   The research team further explored the impact of network randomization model selection on network inference, particularly the evaluation of the weighted rich-club phenomenon. A rich club refers to a subnetwork where high-degree nodes (rich nodes) have more connections than would be expected by chance. By calculating the weighted rich-club coefficient and comparing randomized networks generated by different models, the study revealed differences in network inference across models.

Main Results

1. Preservation of Weighted Degree Sequence
   The simulated annealing algorithm demonstrated nearly perfect performance in preserving the weighted degree sequence across all datasets, with Spearman rank correlation coefficients close to 1.0, significantly outperforming the other two algorithms. Additionally, the algorithm excelled in preserving the weighted degree distribution, with Kolmogorov-Smirnov statistics significantly lower than those of other algorithms.

2. Morphospace Analysis Results
   Morphospace analysis showed that the randomized networks generated by the simulated annealing algorithm exhibited a distribution of global network features highly consistent with those generated by the Maslov-Sneppen algorithm, but with lower variability. This indicates that the simulated annealing algorithm offers higher stability in preserving global network features.

3. Inference of Weighted Rich-Club Phenomenon
   The study found that randomized networks generated using the simulated annealing algorithm could detect more significant weighted rich-club phenomena compared to other randomization models. This suggests that the simulated annealing algorithm provides more meaningful inferences when assessing brain network organization.

Research Conclusions and Significance

This study proposed a weighted network randomization method based on the simulated annealing algorithm and validated its performance across multiple datasets and network formats. The results demonstrate that the algorithm has significant advantages in preserving the weighted degree sequence and distribution and generates more stable randomized networks. Furthermore, the study highlights the important impact of network randomization model selection on network inference, particularly in the evaluation of the weighted rich-club phenomenon. This research provides a powerful tool for analyzing next-generation connectomics datasets and lays the foundation for further understanding the organization and function of brain networks.

Research Highlights

1. Algorithm Innovation: The study proposed a weighted network randomization algorithm based on simulated annealing, which preserves the original network’s weight distribution, degree sequence, and weighted degree sequence for each randomized network instance.
2. Performance Advantages: The simulated annealing algorithm significantly outperforms other randomization algorithms in preserving the weighted degree sequence and distribution.
3. Morphospace Analysis: For the first time, the study introduced morphospace analysis into the evaluation of network randomization, revealing the variability of randomized networks generated by different algorithms.
4. Weighted Rich-Club Phenomenon: The study is the first to explore the impact of network randomization models on the inference of the weighted rich-club phenomenon, uncovering differences in network inference across models.

Additional Value

The findings of this study are not only applicable to the field of neuroscience but can also be widely applied to the analysis of other complex networks. The research team has open-sourced the algorithm for further exploration and application by researchers.