(2025). Evolutionary computation approaches to link prediction in complex networks: from genetic algorithms to symbolic heuristic learning. [Doctoral dissertation, Ionian University, Department of Informatics]. https://doi.org/10.12681/eadd/60582
Περίληψη
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.
- DOI
- 10.12681/eadd/60582
- Τύπος
- Διδακτορική Διατριβή
- Έτος
- 2025
Σύνδεσμοι
BibTeX
@phdthesis{dimitriou2025evolutionary,
title = {Evolutionary computation approaches to link prediction in complex networks: from genetic algorithms to symbolic heuristic learning},
author = {Paraskevas Dimitriou},
url = {https://doi.org/10.12681/eadd/60582},
doi = {10.12681/eadd/60582},
year = {2025},
date = {2025-01-01},
address = {Corfu, Greece},
school = {Ionian University, Department of Informatics},
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.},
note = {Supervisor: Vasileios Karyotis},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}