A Simulated Annealing Algorithm for Randomizing Weighted Networks
Poster No:
1178
Submission Type:
Abstract Submission
Authors:
Filip Milisav1, Vincent Bazinet1, Rick Betzel2, Bratislav Misic1
Institutions:
1Montréal Neurological Institute, McGill University, Montréal, Canada, 2University of Minnesota, Minneapolis, USA
First Author:
Co-Author(s):
Introduction:
Scientific discovery in connectomics relies on network null models. The prominence of network features is conventionally evaluated against null distributions estimated using randomized networks. Modern imaging technologies provide an increasingly rich array of biologically meaningful edge weights. Despite the prevalence of weighted graph analysis in connectomics, randomization models that only preserve degree remain most widely used. Here we propose a simulated annealing procedure for generating randomized networks that preserve weighted degree (strength) sequences. We show that the procedure outperforms other rewiring algorithms and generalizes to multiple network formats, including directed and signed networks.
Methods:
Simulated annealing is a powerful and versatile optimization technique with wide-ranging applications (Kirkpatrick, 1983). Moreover, it is particularly advantageous when dealing with large combinatorial search spaces, making it a prime candidate for solving network modeling problems. For generating strength-preserving randomized networks, simulated annealing is applied on the output of the classic degree-preserving rewiring method (Maslov, 2002; Fig. 1a, top): randomly selected pairs of edge weights are permuted either if they lower the energy of the system (mean squared error between the strength sequences of the empirical and the randomized network) or if they meet a probabilistic acceptance criterion. This allows permutations which can increase the energy of the system but prevents it from getting stuck in a local minimum (Fig. 1a, bottom; Milisav, 2024). To benchmark the algorithm's performance, we compare it to another strength-preserving randomization algorithm developed by Rubinov & Sporns (2011), as well as degree-preserving rewiring (Maslov, 2002).
Benchmarking analyses were performed on diffusion-weighted MRI data acquired in n = 327 healthy participants from the Human Connectome Project (Van Essen, 2013). Individual structural connectomes were reconstructed using deterministic streamline tractography and used to build a group-representative weighted network. Finally, three ensembles of 10000 null networks were generated from the empirical network according to the three randomization algorithms.
Importantly, the simulated annealing algorithm can easily be adapted to directed (reconstructing in- and out-strengths) and signed (reconstructing positive and negative strengths) networks. To showcase its performance in these network formats, we further consider directed, weighted wiring diagrams of the drosophila (Shih, 2015), mouse (Rubinov, 2015), rat (Bota, 2015), and macaque (Scholtens, 2014), as well as a dataset of signed brain networks reflecting inter-regional similarity across six local biological features (Hansen, 2023).
Benchmarking analyses were performed on diffusion-weighted MRI data acquired in n = 327 healthy participants from the Human Connectome Project (Van Essen, 2013). Individual structural connectomes were reconstructed using deterministic streamline tractography and used to build a group-representative weighted network. Finally, three ensembles of 10000 null networks were generated from the empirical network according to the three randomization algorithms.
Importantly, the simulated annealing algorithm can easily be adapted to directed (reconstructing in- and out-strengths) and signed (reconstructing positive and negative strengths) networks. To showcase its performance in these network formats, we further consider directed, weighted wiring diagrams of the drosophila (Shih, 2015), mouse (Rubinov, 2015), rat (Bota, 2015), and macaque (Scholtens, 2014), as well as a dataset of signed brain networks reflecting inter-regional similarity across six local biological features (Hansen, 2023).
Results:
The simulated annealing procedure yields larger Spearman correlation coefficients between strengths of the empirical and the randomized networks than the other two models (p ≈ 0, common-language effect size (CLES) = 100%, two-tailed Wilcoxon-Mann-Whitney-WMW-tests; Fig. 1b, top). Similar, near-perfect fits can also be observed for in- and out-strengths and positive and negative strengths across all directed and signed networks considered (Fig. 2). The simulated annealing procedure also exhibits a better fit between the strength distributions of the empirical and the randomized networks, as shown by significantly lower Kolmogorov-Smirnov statistics (p ≈ 0, CLES = 100%, two-tailed WMW tests; Fig. 1b, bottom).
Conclusions:
We find that the simulated annealing method outperforms other network randomization algorithms in preserving strength. Building on top of conventional rewiring procedures, this algorithm allows for flexible constraint optimization. Here, by constraining surrogate strength sequence, we show that this method holds the potential to transform weighted network inference, allowing greater insight into the principles that shape brain networks.
Modeling and Analysis Methods:
Connectivity (eg. functional, effective, structural) 1
Diffusion MRI Modeling and Analysis
Methods Development 2
Keywords:
Open-Source Code
Statistical Methods
Other - network null model; connectomics; weighted brain networks
1|2Indicates the priority used for review
Abstract Information
By submitting your proposal, you grant permission for the Organization for Human Brain Mapping (OHBM) to distribute your work in any format, including video, audio print and electronic text through OHBM OnDemand, social media channels, the OHBM website, or other electronic publications and media.
The Open Science Special Interest Group (OSSIG) is introducing a reproducibility challenge for OHBM 2025. This new initiative aims to enhance the reproducibility of scientific results and foster collaborations between labs. Teams will consist of a “source” party and a “reproducing” party, and will be evaluated on the success of their replication, the openness of the source work, and additional deliverables. Click here for more information. Propose your OHBM abstract(s) as source work for future OHBM meetings by selecting one of the following options:
Please indicate below if your study was a "resting state" or "task-activation” study.
Healthy subjects only or patients (note that patient studies may also involve healthy subjects):
Was this research conducted in the United States?
Were any human subjects research approved by the relevant Institutional Review Board or ethics panel? NOTE: Any human subjects studies without IRB approval will be automatically rejected.
Were any animal research approved by the relevant IACUC or other animal research panel? NOTE: Any animal studies without IACUC approval will be automatically rejected.
Please indicate which methods were used in your research:
Provide references using APA citation style.
Hansen, J. Y. (2023). Integrating multimodal and multiscale connectivity blueprints of the human cerebral cortex in health and disease. PLOS Biology, 21(9), e3002314.
Kirkpatrick, S. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Maslov, S. (2002). Specificity and stability in topology of protein networks. Science, 296(5569), 910-913.
Milisav, F. (2024). A simulated annealing algorithm for randomizing weighted networks. Nature Computational Science, 1-17.
Rubinov, M. (2011). Weight-conserving characterization of complex functional brain networks. Neuroimage, 56(4), 2068-2079.
Rubinov, M. (2015). Wiring cost and topological participation of the mouse brain connectome. Proceedings of the National Academy of Sciences, 112(32), 10032-10037.
Scholtens, L. H. (2014). Linking macroscale graph analytical organization to microscale neuroarchitectonics in the macaque connectome. Journal of Neuroscience, 34(36), 12192-12205.
Shih, C. T. (2015). Connectomics-based analysis of information flow in the Drosophila brain. Current Biology, 25(10), 1249-1258.
Van Essen, D. C. (2013). The WU-Minn human connectome project: an overview. Neuroimage, 80, 62-79.