University of Twente Student Theses


Machine-learning methods for discovering growth mechanisms in complex networks

Cai, Weiting (2021) Machine-learning methods for discovering growth mechanisms in complex networks.

[img] PDF
Abstract:Preferential attachment (PA) and fitness (F) are two hypothetical mechanisms that explain the formation of scale-free networks, which are networks with asymptotically power-law distribution. These mechanisms are interesting because they both lead to scale-free networks, which are often seen in real-life, but they are different with respect to the process of network development. So far, considerable progress has been achieved in random graph theory that describes how scale-free networks develop, while there is little work on uncovering and explaining these mechanisms behind a given network. Therefore, in this article, we aim to train a machine-learning classifier that can differentiate between PA mechanism and F mechanism behind networks. We use a flexible and scalable feature design that organizes features in a matrix. To reduce overfitting by removing the noise in the data, we normalize the feature matrix. We use synthetic networks generated by a PA-based model and an F-based model to evaluate the performance of the classifier and show that the PA and the F mechanisms can be perfectly distinguished by a decision tree classifier. In addition, we clearly see one dominating feature out of all features in the matrix. We show how different parameters of the two models will affect the values of the features and the dominating feature. Importantly, we show that the threshold value of the decision tree model to distinguish the two mechanisms are in accordance with the result of mathematical analysis in a special case.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page