Oleksii Bielikh defended his Master thesis in Complex Adaptive Systems at Chalmers University of Technology on 5 October 2017.
Thesis title: Generation of Random Graphs for Graph Theory Analysis Applied to the Study of Brain Connectivity
Thesis advisor: Giovanni Volpe
One of the current frontiers in neurosciences is to understand brain connectivity both in healthy subjects and patients. Recent studies suggest that brain connectivity measured with graph theory is a reliable candidate biomarker of neuronal dysfunction and disease spread in neurodegenerative disorders. Widespread abnormalities in the topology of the cerebral networks in patients correlate with a higher risk of developing dementia and worse prognosis.
In order to recognize such abnormalities, brain network graph measures should be compared with the corresponding measures calculated on random graphs with the same degree distribution. However, creating a random graph with prescribed degree sequence that has number of nodes of magnitude of 105 is a recognized problem. Existing algorithms have a variety of shortcomings, among which are slow run-time, non-uniformity of results and divergence of degree distribution with the target one.
The goal of this thesis is to explore the possibility of finding an algorithm that can be used with very large networks. Multiple common algorithms were tested to check their scaling with increasing number of nodes. The results are compared in order to find weaknesses and strengths of particular algorithms, and certain changes are offered that speed up their runtimes and/or correct for the downsides. The degree distributions of the resulting random graphs are compared to those of the target graphs, which are constructed in a way that mimics some of the most common characteristics of brain networks, namely small-worldness and scale-free topology, and it is discussed why some of the models are more appropriate than others in this case. Simulations prove that the majority of algorithms are vastly inefficient in creating random large graphs with necessary limitations on their topology, while some can be adapted to showcase to a certain extent promising results.