Evolutionary computation approaches to link prediction in complex networks: from genetic algorithms to symbolic heuristic learning

Abstract

This dissertation investigates the challenging problem of link prediction in complex networks, a key task in network science that aims to infer missing or future relation- ships among entities represented as nodes of a graph. Complex networks, appearing across domains such as social, biological, and information systems, exhibit intricate topological properties that hinder the performance of conventional link prediction algorithms. Classical methods—based on local structural metrics or random walks—tend to treat all networks homogeneously, neglecting their distinctive structural characteristics. On the other hand, deep learning and graph neural network (GNN) approaches often act as “black- box” models, achieving less than expected accuracy at the expense of interpretability and computational efficiency. The objective of this research is to bridge this methodological gap by proposing a family of interpretable, adaptive, and evolution-driven frame- works that exploit both the topology and semantics of networks through evolutionary computation techniques. The thesis follows a progressive research trajectory structured in three principal evolutionary stages. The first stage introduces a Combinatory Framework for Link Prediction, where multiple baseline algorithms—such as Resource Allocation, Adamic-Adar, Jaccard, and Preferential Attachment—are combined through a Genetic Algorithm (GA) to produce an enhanced predictor. The GA dynamically assigns weights to the outputs of each classical method, optimizing their contribution to the final prediction score. This evolutionary fusion yields consistently higher accuracy across diverse datasets, validating the hypothesis that no single heuristic is universally optimal for all network types. The approach demonstrates that evolutionary optimization can serve as a powerful metaheuristic engine for synthesizing the strengths of multiple link prediction paradigms. Building upon this foundation, the second stage introduces the Sigmoid Custom Similarity Index (SCSI). This model incorporates adaptive parameters, learned through genetic algorithms, into random-walk-based link prediction mechanisms. The SCSI leverages sigmoid functions—both logistic and hyperbolic tangent—to modulate similarity scores between node pairs dynamically. This adaptive parameterization allows the model to better capture the structural variability among networks, balancing sensitivity and specificity in edge estimation. Extensive experiments on multiple benchmark networks have confirmed that SCSI achieves substantial improvements over its fixed-parameter counterparts, demonstrating the importance of data-driven parameter adaptation in topological learning. The third and central contribution of the thesis is the Heuristic Custom Similarity In- dex (HCSI) and its genetic programming extension, Genetic Programming Heuristic Custom Similarity Index (GPHCSI). The HCSI represents a novel machine-learning based architecture designed to extract, evaluate, and combine heuristic descriptors derived from network topology, information theory, and kernel-based transformations. In total, ninety-three heuristics, organized into eleven functional classes, are constructed to capture both local and global structural patterns. These include neighborhood-based metrics, random walk variations, mean-based aggregations, radial basis and polynomial kernel functions, and other network-theoretic measures. The HCSI framework uses an evolutionary algorithm to identify the optimal subset and composition of these heuristics for each network, effectively constructing customized link prediction tools tailored to specific topologies. The GPHCSI framework extends this idea by employing Genetic Programming (GP) to automatically evolve symbolic expressions that define similarity functions. Instead of manually designing heuristic combinations, the GP algorithm generates and optimizes mathematical formulas represented as syntax trees, where terminal nodes correspond to heuristics and internal nodes to arithmetic or logical operators. This process allows the system to autonomously discover complex, interpretable expressions for link prediction that generalize well across datasets. GPHCSI unifies the interpretability of heuristic-based models with the adaptivity of evolutionary learning, yielding link prediction formulas that are both transparent and high-performing. Experimental evaluation across several benchmark datasets—including academic, biological, and e-commerce networks—demonstrates that GPHCSI outperforms classical algorithms and state-of-the-art GNNs in terms of Precision, Area Under the Curve (AUC), Mean Reciprocal Rank (MRR) and other link prediction metrics. It also exhibits superior computational efficiency and scalability on small to medium-sized networks. Detailed ablation studies confirm that the synergy among different heuristic classes is key to its success, highlighting the ability of the evolutionary process to uncover nontrivial feature interactions that enhance discriminative power. In addition to methodological contributions, the thesis provides a unifying framework for evolutionary feature extraction and network inference. It demonstrates empirically that Genetic Algorithms and Genetic Programming can autonomously generate interpretable and effective link prediction expressions without the need for deep neural architectures. Furthermore, it offers strong evidence that evolutionary computation can rival and, in some cases, surpass deep learning models, while preserving transparency and lower computational cost—an important advantage for explainable AI and applications where interpretability is crucial. The research also revisits a preliminary study on Delaunay triangulation via Genetic Algorithms and another one on humanitarian supply chains, which served as validations of evolutionary methods’ robustness and optimization capability in geometric and topological problems. The success of these works reinforced the suitability of genetic paradigms for the more complex domain of network link prediction. The thesis concludes by outlining several directions for future research. Key extensions include the development of distributed and memory-efficient implementations of GPHCSI for handling very large-scale networks, the integration of domain-specific or data-driven heuristics to enrich the feature space, and the adaptation of the framework to temporal and dynamic networks. Another promising avenue involves combining evolutionary heuristics with graph embedding and generative models, aiming to further bridge symbolic interpretability and latent representation learning. Finally, applications in bioinformatics, recommender systems, and social network analysis are identified as potential real-world domains for validating and extending the proposed methodologies. In summary, this thesis establishes a new paradigm for interpretable link prediction in complex networks, demonstrating that evolutionary and heuristic-based learning approaches constitute a robust, transparent, and computationally efficient alternative to black-box deep learning systems. By progressively evolving from combinatory models to fully automated symbolic learning, it contributes a cohesive and extensible framework for adaptive network inference—one that balances performance, scalability, and interpretability. The outcomes underscore the transformative potential of evolutionary computation as a cornerstone methodology for the next generation of link prediction and complex network analysis.

Η παρούσα διατριβή εξετάζει το απαιτητικό πρόβλημα της πρόβλεψης συνδέσμων (link prediction) σε σύνθετα και πολύπλοκα δίκτυα, μια βασική διαδικασία στην Επιστήμη Δικτύων που στοχεύει στην πρόβλεψη ή αναγνώριση των αγνοούμενων ή μελλοντικών σχέσεων μεταξύ οντοτήτων που αναπαρίστανται ως κόμβοι δικτύου. Τα πολύπλοκα δίκτυα, τα οποία συναντώνται σε πεδία όπως τα κοινωνικά, βιολογικά και πληροφοριακά συστήματα, εμφανίζουν περίπλοκες τοπολογικές ιδιότητες που δυσχεραίνουν τη λειτουργία των κλασικών αλγορίθμων πρόβλεψης συνδέσμων. Οι παραδοσιακές μέθοδοι — βασισμένες σε τοπικά μέτρα ή τυχαίους περιπάτους (random walks) — αντιμετωπίζουν τα δίκτυα ομοιόμορφα, αγνοώντας πολλές φορές τα ιδιαίτερα χαρακτηριστικά κάθε δομής. Από την άλλη πλευρά, οι προσεγγίσεις βαθιάς μάθησης και τα Γραφικά Νευρωνικά Δίκτυα (GNNs) επιτυγχάνουν λιγότερο από την αναμενόμενη ακρίβεια, η οποία είναι και σε βάρος της ερμηνευσιμότητας και της υπολογιστικής αποδοτικότητας. Στόχος της εργασίας είναι να γεφυρώσει αυτό το μεθοδολογικό χάσμα, προτείνοντας μια οικογένεια από ερμηνεύσιμα, προσαρμοστικά και εξελικτικά πλαίσια που εκμεταλλεύονται τόσο την τοπολογία όσο και τη σημασιολογία των δικτύων μέσω τεχνικών εξελικτικών υπολογισμών. Η εργασία ακολουθεί μια προοδευτική ερευνητική πορεία οργανωμένη σε τρία βασικά εξελικτικά στάδια. Στο πρώτο στάδιο παρουσιάζεται ένα Συνδυαστικό Πλαίσιο για την Πρόβλεψη Συνδέσμων (Combinatory Framework), στο οποίο πολλοί βασικοί αλγόριθμοι — όπως οι Resource Allocation, Adamic-Adar, Jaccard και Preferential Attachment — συνδυάζονται με τη χρήση ενός Γενετικού Αλγορίθμου (GA) για τη δημιουργία ενός ενισχυμένου προβλέπτη ελλειπουσών ακμών. Ο γενετικός αλγόριθμος αποδίδει δυναμικά βάρη στα αποτελέσματα κάθε επιμέρους μεθόδου, βελτιστοποιώντας τη συνεισφορά τους στο τελικό σκορ πρόβλεψης. Ο εξελικτικός αυτός συνδυασμός προσφέρει σταθερά καλύτερη ακρίβεια σε διαφορετικά σύνολα δεδομένων, επιβεβαιώνοντας την υπόθεση ότι κανένας μεμονωμένος αλγόριθμος δεν είναι βέλτιστος για όλα τα είδη δικτύων. Η προσέγγιση αυτή αποδεικνύει ότι η εξελικτική βελτιστοποίηση μπορεί να λειτουργήσει ως ισχυρή μετα-ευρετική μέθοδος που συνθέτει τα πλεονεκτήματα πολλών τεχνικών πρόβλεψης. Βασιζόμενο σε αυτό το υπόβαθρο, το δεύτερο στάδιο εισάγει τον Δείκτη Προσαρμοσμένης Ομοιότητας Sigmoid (SCSI – Sigmoid Custom Similarity Index). Το μοντέλο αυτό ενσωματώνει προσαρμοστικές παραμέτρους, οι οποίες μαθαίνονται μέσω γενετικών αλγορίθμων, σε μεθόδους πρόβλεψης βασισμένες σε τυχαίους περιπάτους. Ο δείκτης SCSI αξιοποιεί συναρτήσεις sigmoid — τόσο τη λογιστική όσο και την υπερβολική εφαπτομένη — για να ρυθμίζει δυναμικά τα σκορ ομοιότητας μεταξύ κόμβων. Αυτή η προσαρμογή επιτρέπει στο μοντέλο να αποτυπώνει καλύτερα την δομική μεταβλητότητα των δικτύων, επιτυγχάνοντας ισορροπία ανάμεσα στην ευαισθησία και την εξειδίκευση της εκτίμησης των συνδέσεων. Εκτεταμένα πειράματα σε διάφορα δίκτυα αναφοράς δείχνουν ότι ο SCSI υπερέχει σημαντικά των κλασικών εκδόσεων, αποδεικνύοντας τη σημασία της προσαρμογής παραμέτρων που προκύπτει από τα ίδια τα δεδομένα. Η τρίτη και κεντρική συνεισφορά της εργασίας είναι ο Ευρετικός Δείκτης Προσαρμοσμένης Ομοιότητας (HCSI – Heuristic Custom Similarity Index) και η γενετικά προγραμματισμένη του επέκταση, ο GPHCSI (Genetic Programming Heuristic Cus- tom Similarity Index). Ο HCSI αποτελεί μια νέα αρχιτεκτονική βασισμένη στη μηχανική μάθηση, σχεδιασμένη να εξάγει, να αξιολογεί και να συνδυάζει ευρετικούς περιγραφείς που προέρχονται από την τοπολογία, τη θεωρία πληροφορίας και μετασχηματισμούς πυρήνων (kernels). Συνολικά, αναπτύσσονται ενενήντα τρεις ευρετικές συναρτήσεις, οργανωμένες σε έντεκα λειτουργικές κατηγορίες, ώστε να αποτυπώνουν τόσο τοπικά όσο και καθολικά δομικά χαρακτηριστικά. Αυτές περιλαμβάνουν μετρικές γειτνίασης, παραλλαγές τυχαίων περιπάτων, στατιστικά μέτρα μέσων τιμών, συναρτήσεις βάσεων RBF και πολυωνυμικών πυρήνων, καθώς και άλλες τοπολογικές συναρτήσεις. Το πλαίσιο HCSI χρησιμοποιεί έναν εξελικτικό αλγόριθμο για να εντοπίσει τον βέλτιστο συνδυασμό αυτών των ευρετικών για κάθε δίκτυο, δημιουργώντας έτσι προσαρμοσμένα εργαλεία πρόβλεψης. Το πλαίσιο GPHCSI επεκτείνει αυτήν την ιδέα μέσω της χρήσης Γενετικού Προγραμματισμού (Genetic Programming), ώστε να εξελίσσει αυτόματα συμβολικές εκφράσεις που ορίζουν συναρτήσεις ομοιότητας. Αντί για χειροκίνητο σχεδιασμό συνδυασμών ευρετικών, ο αλγόριθμος GP δημιουργεί και βελτιστοποιεί μαθηματικούς τύπους που αναπαρίστανται ως συντακτικά δέντρα, όπου τα φύλλα αντιστοιχούν σε ευρετικές και οι εσωτερικοί κόμβοι σε τελεστές. Με αυτό τον τρόπο, το σύστημα ανακαλύπτει αυτόνομα πολύπλοκες και ερμηνεύσιμες εκφράσεις πρόβλεψης, οι οποίες δίνουν καλές προβλέψεις σε διαφορετικά σύνολα δεδομένων. Ο GPHCSI συνδυάζει την ερμηνευσιμότητα των ευρετικών μοντέλων με την προσαρμοστικότητα της εξελικτικής μάθησης, παράγοντας τύπους πρόβλεψης που είναι ταυτόχρονα διαφανείς και αποδοτικοί. Η πειραματική αξιολόγηση σε διάφορα σύνολα δεδομένων—όπως ακαδημαϊκά, βιολογικά και εμπορικά δίκτυα—δείχνει ότι ο GPHCSI υπερτερεί των κλασικών αλγορίθμων και των σύγχρονων GNNs ως προς την Ακρίβεια (Precision), την ΄Εκταση κάτω από την καμπύλη ROC (AUC) και τη Μέση Αντίστροφη Κατάταξη (MRR). Επιπλέον, παρουσιάζει ανώτερη υπολογιστική απόδοση και επεκτασιμότητα σε μικρά και μεσαίου μεγέθους δίκτυα. Οι μελέτες αφαίρεσης (ablation studies) αποκαλύπτουν ότι ο συνδυασμός διαφορετικών κατηγοριών ευρετικών αποτελεί τον κύριο παράγοντα επιτυχίας, καθώς η εξελικτική διαδικασία εντοπίζει αλληλεπιδράσεις χαρακτηριστικών που αυξάνουν τη διακριτική ισχύ. Πέρα από τις μεθοδολογικές συνεισφορές, η εργασία προτείνει ένα ενοποιημένο πλαίσιο εξελικτικής εξαγωγής χαρακτηριστικών και συμπερασμού σε δίκτυα. Αποδεικνύεται εμπειρικά ότι οι Γενετικοί Αλγόριθμοι και ο Γενετικός Προγραμματισμός μπορούν να παράγουν αυτόνομα ερμηνεύσιμες και αποτελεσματικές εκφράσεις πρόβλεψης συνδέσμων χωρίς την ανάγκη βαθιών νευρωνικών αρχιτεκτονικών. Επιπλέον, τεκμηριώνεται ότι οι εξελικτικές μέθοδοι μπορούν να ανταγωνιστούν ή και να υπερβούν κατά περίπτωση τα μοντέλα βαθιάς μάθησης, διατηρώντας παράλληλα την διαφάνεια και τη χαμηλή υπολογιστική πολυπλοκότητα — χαρακτηριστικά κρίσιμα για την τεχνητή νοημοσύνη (ΤΝ). Η εργασία αναφέρεται επίσης σε μια προγενέστερη μελέτη σχετικά με την τριγωνοποίηση Delaunay μέσω Γενετικών Αλγορίθμων, η οποία αποτέλεσε πρώιμη απόδειξη της ανθεκτικότητας και της ικανότητας βελτιστοποίησης των εξελικτικών μεθόδων σε γεωμετρικά και τοπολογικά προβλήματα. Η επιτυχία αυτής της προσέγγισης ενίσχυσε τη χρήση των γενετικών παραδειγμάτων στο πεδίο της πρόβλεψης συνδέσμων. Η εργασία ολοκληρώνεται προτείνοντας κατευθύνσεις για μελλοντική έρευνα, όπως η ανάπτυξη κατανεμημένων και αποδοτικών υλοποιήσεων του GPHCSI για μεγάλης κλίμακας δίκτυα, η ενσωμάτωση ευρετικών ειδικού πεδίου ή δεδομένων για τον εμπλουτισμό των χαρακτηριστικών, καθώς και η προσαρμογή του πλαισίου σε δυναμικά και χρονικά δίκτυα. Μια ακόμη προοπτική αφορά τον συνδυασμό των εξελικτικών ευρετικών με μοντέλα ενσωμάτωσης γράφων και γενετικά μοντέλα, ώστε να γεφυρωθεί περαιτέρω η συμβολική ερμηνευσιμότητα με τη λανθάνουσα αναπαράσταση. Τέλος, προτείνονται εφαρμογές σε βιοπληροφορική, συστήματα συστάσεων και ανάλυση κοιν- ωνικών δικτύων ως πιθανά πεδία πρακτικής αξιοποίησης των προτεινόμενων μεθοδολογιών. Συνοψίζοντας, η παρούσα εργασία θεμελιώνει ένα νέο παράδειγμα ερμηνεύσιμης πρόβλεψης συνδέσμων σε πολύπλοκα δίκτυα, αποδεικνύοντας ότι οι εξελικτικές και ευρετικές μέθοδοι μάθησης αποτελούν μια ισχυρή, διαφανή και αποδοτική εναλλακτική λύση έναντι των «μαύρων κουτιών» της βαθιάς μάθησης. Εξελισσόμενη σταδιακά από συνδυαστικά μοντέλα έως πλήρως αυτόματη συμβολική μάθηση, συμβάλλει στην δημιουργία ενός συνεκτικού και επεκτάσιμου πλαισίου για προσαρμοστικό συμπερασμό σε σύνθετα δίκτυα— ενός πλαισίου που συνδυάζει απόδοση, επεκτασιμότητα και ερμηνευσιμότητα. Τα αποτελέσματα υπογραμμίζουν τη μετασχηματιστική δυναμική των εξελικτικών υπολογισμών ως θεμέλιο για τη νέα γενιά αλγορίθμων πρόβλεψης συνδέσμων και ανάλυσης σύνθετων και πολύπλοκων δικτύων.