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

dc.contributor.authorBielikh, Oleksii
dc.contributor.departmentChalmers tekniska högskola / Institutionen för fysik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Physics (Chalmers)en
dc.date.accessioned2019-07-03T14:56:27Z
dc.date.available2019-07-03T14:56:27Z
dc.date.issued2017
dc.description.abstractOne 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.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/256343
dc.language.isoeng
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectFysik
dc.subjectPhysical Sciences
dc.titleGeneration of Random Graphs for Graph Theory Analysis Applied to the Study of Brain Connectivity
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComplex adaptive systems (MPCAS), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
256343.pdf
Storlek:
649.96 KB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext