Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
A meta-learning framework for link prediction algorithm selection based on network structure analysis
Brown, L. M. 2025. A meta-learning framework for link prediction algorithm selection based on network structure analysis. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e14dfd36-18cd-4933-8555-fd609c8c1672
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614101902983168 |
|---|---|
| access_status_str | Open Access |
| author | Brown, Lienke Marie |
| author2 | Van Vuuren, J. H. |
| author_browse | Brown, Lienke Marie Van Vuuren, J. H. |
| author_facet | Van Vuuren, J. H. Brown, Lienke Marie |
| author_sort | Brown, Lienke Marie |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Brown, L. M. 2025. A meta-learning framework for link
prediction algorithm selection based on network structure analysis. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e14dfd36-18cd-4933-8555-fd609c8c1672 |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/132090 |
| institution | Stellenbosch University (South Africa) |
| last_indexed | 2026-06-10T12:46:41.344Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/132090 A meta-learning framework for link prediction algorithm selection based on network structure analysis Brown, Lienke Marie Van Vuuren, J. H. Nel, G. S. Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. Graph theory -- Data processing Machine learning Algorithms UCTD Brown, L. M. 2025. A meta-learning framework for link prediction algorithm selection based on network structure analysis. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e14dfd36-18cd-4933-8555-fd609c8c1672 Thesis (PhD)--Stellenbosch University, 2025. ENGLISH ABSTRACT: Link prediction is an important problem in the multi-disciplinary field of network science, which is focused on systematically inferring potential (or missing) links in graph models of networks. This problem spans multiple domains, including social networks, biological systems, and recommender systems, to name but a few. Link prediction is aimed at uncovering relationships that are not immediately apparent in networks associated with these domains by leveraging techniques from the research areas of network analysis and machine learning. The algorithms utilised for this task may be classified into three main paradigms, namely similarity-based methods, machine learning classifiers, and embedding-based methods. The increasing availability and structural diversity of network data, coupled with the extensive variety of the algorithms available, demands a systematic approach towards selecting a suitable algorithm for link prediction purposes in a given graph model. Existing approaches towards selecting such an algorithm often rely on ad hoc approaches. As such, there is a lack of structured frameworks facilitating comprehensive algorithmic comparisons in view of the diverse structural graph properties inherent to different network types. The link prediction algorithm selection problem arises from a need to identify the most appropriate algorithm for a given network, taking into account its structural characteristics and the relative performances of available algorithms. It has been shown that no single link prediction algorithm consistently outperforms others with respect to all networks. In this dissertation, a framework, called the LinkPAL framework, is proposed as a comprehensive solution to this problem. This framework adopts a meta-learning approach towards recommending suitable link prediction algorithms based on an analysis of relevant network meta-features, such as community structure, degree distribution, and assortativity, to name but a few. The framework is able to predict algorithmic performance and provides tailored recommendations for new, unseen link prediction problem instances by training a meta-learner on a curated suite of benchmark network data sets. The novelty of the LinkPAL framework pertain s to its ability to address the link prediction algorithm selection problem according to a structured, data-driven methodology with a view to enhance the algorithmic performance when presented with a network data set exhibiting specific structural graph properties. The working of the proposed framework consists of two distinct phases, namely an offline phase and an online phase. During the execution of the offline phase, meta-features are extracted from a benchmark data suite, and meta-learners are subsequently trained in respect of these data. During the online phase, the trained meta-learners generate suitable algorithm recommendations for new networks. This two-phased approach ensures that computationally intensive processes are handled offline, allowing for efficient and accurate algorithm selection recommendation during the online phase. In addition, the modular design of the framework also ensures its adaptability to future advancements in the field. The methodological utility of the LinkPAL framework is demonstrated by means of a computerised instantiation as a proof-of-concept decision support system by utilising open-source benchmark problem instances. The instantiation verifies the functional correctness of the framework and evaluates algorithmic performance both quantitatively by means of statistical analyses, and qualitatively through visualisations of, and contextual reflections on, the output of the algorithms. The quality of the algorithm recommendations is assessed in three evaluation scenarios, each representing a different distribution of structural graph properties. These scenarios serve to verify and validate the recommendations produced by the framework. AFRIKAANSE OPSOMMING: Skakelvoorspelling is 'n belangrike probleem in die multi-dissiplin^ere veld van netwerkwetenskap wat daarop gefokus is om sistematies potensi ele (of ontbrekende) skakels in gra_ekmodelle van netwerke af te lei. Hierdie probleem strek oor verskeie toepassingsareas, insluitend sosiale netwerke, biologiese stelsels en aanbevelingstelsels, om maar 'n paar te noem. Skakelvoorspelling is daarop gemik om verwantskappe te ontbloot wat nie onmiddellik in netwerke sigbaar is wat met hierdie areas geassosieer word nie, deur tegnieke uit die navorsingsgebiede van netwerkanalise en masjienleer te benut. Die algoritmes wat vir hierdie taak gebruik word, kan in drie hoofparadigmas geklassi_seer word, naamlik ooreenkoms-gebaseerde metodes, masjienleerklassi_seerders en inbedding-gebaseerde metodes. Die toenemende beskikbaarheid en strukturele diversiteit van netwerkdata, tesame met die uitgebreide verskeidenheid van die beskikbare algoritmes, vereis 'n sistematiese benadering tot die keuse van 'n geskikte algoritme vir skakelvoorspelling in 'n gegewe gra_ekmodel. Bestaande benaderings tot die keuse van so 'n algoritme maak dikwels staat op ad hoc-benaderings. As sodanig is daar 'n gebrek aan gestruktureerde raamwerke wat omvattende algoritmiese vergelykings fasiliteer in die lig van die uiteenlopende strukturele gra_ekeienskappe wat inherent is aan verskillende netwerktipes. Die skakelvoorspellingsalgoritme-seleksieprobleem ontstaan uit 'n behoefte om die mees geskikte algoritme vir 'n gegewe netwerk te identi_seer, met inagneming van die strukturele eienskappe daarvan asook die relatiewe prestasies van beskikbare algoritmes. Dit is bekend dat geen enkele skakelvoorspellingsalgoritme konsekwent beter presteer as ander met betrekking tot alle netwerke nie. In hierdie proefskrif word 'n raamwerk, bekend as die LinkPAL-raamwerk, as 'n omvattende oplossing vir hierdie probleem voorgestel. Hierdie raamwerk volg 'n meta-leer benadering om geskikte skakelvoorspellingsalgoritmes aan te beveel gebaseer op 'n ontleding van relevante netwerk meta-kenmerke, soos gemeenskapstruktuur, graadverdeling en assortatiwiteit, om maar 'n paar te noem. Die raamwerk is in staat om algoritmiese doeltre_endheid te voorspel en verskaf pasgemaakte aanbevelings vir nuwe, ongesiene skakelvoorspellingsprobleemgevalle deur 'n meta-leerder in terme van 'n saamgestelde reeks maatstafnetwerkdatastelle op te lei. Die oorspronklikheid van die LinkPAL-raamwerk hou verband met sy vermo e om die skakelvoorspellingsalgoritme-seleksieprobleem volgens 'n gestruktureerde, data-gedrewe metodologie aan te spreek met die oog op die verbetering van die algoritmiese werkverrigting wanneer dit op 'n netwerkdatastel met spesi_eke strukturele gra_ekeienskappe toegepas word. Die werking van die voorgestelde raamwerk bestaan uit twee afsonderlike fases, naamlik 'n ayn fase en 'n aanlyn fase. Tydens die uitvoering van die ayn fase word meta-kenmerke uit 'n maatstafdatastel onttrek, en meta-leerders word vervolgens opgelei gebaseer op hierdie data. Tydens die aanlynfase genereer die opgeleide meta-leerders geskikte algoritme-aanbevelings vir nuwe netwerke. Hierdie tweefase-benadering verseker dat berekeningsintensiewe prosesse ayn hanteer word, wat doeltre_ende en akkurate algoritmeseleksie-aanbeveling tydens die aanlynfase moontlik maak. Daarbenewens verseker die modul^ere ontwerp van die raamwerk ook die aanpasbaarheid daarvan by toekomstige vooruitgang in die veld. Doctoral 2025-05-23T07:22:41Z 2025-05-23T07:22:41Z 2025-03 Thesis https://scholar.sun.ac.za/handle/10019.1/132090 Stellenbosch University xxii, 292 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Graph theory -- Data processing Machine learning Algorithms UCTD Brown, Lienke Marie A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title | A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title_full | A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title_fullStr | A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title_full_unstemmed | A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title_short | A meta-learning framework for link prediction algorithm selection based on network structure analysis |
| title_sort | meta learning framework for link prediction algorithm selection based on network structure analysis |
| topic | Graph theory -- Data processing Machine learning Algorithms UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/132090 |
| work_keys_str_mv | AT brownlienkemarie ametalearningframeworkforlinkpredictionalgorithmselectionbasedonnetworkstructureanalysis AT brownlienkemarie metalearningframeworkforlinkpredictionalgorithmselectionbasedonnetworkstructureanalysis |