Generation of Random Graphs for Graph Theory Analysis Applied to the Study of Brain Connectivity

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/256343
Download file(s):
File Description SizeFormat 
256343.pdfFulltext649.96 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Generation of Random Graphs for Graph Theory Analysis Applied to the Study of Brain Connectivity
Authors: Bielikh, Oleksii
Abstract: 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.
Keywords: Fysik;Physical Sciences
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för fysik (Chalmers)
Chalmers University of Technology / Department of Physics (Chalmers)
URI: https://hdl.handle.net/20.500.12380/256343
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.