<p>Link prediction is a crucial problem in social network analysis, aiming to estimate the likelihood of future connections based on network structures. This study presents an empirical evaluation of the impact of graph density and non-edge selection strategies on the performance of machine learning models for link prediction. The Facebook datasets are utilized to construct sparse, moderate, and dense past graphs from present networks by strategically removing edges while maintaining structural integrity. A balanced dataset is prepared by selecting non-edges based on the shortest or longest path lengths. For each non-edge in the present network, compute the shortest path length and then arrange them in ascending or descending order. Select the desired number of non-edges from this sorted data based on the minimum or maximum path length. For each edge in balanced data set, ten similarity-based features are extracted from past graphs. Seven machine learning models are trained and evaluated. The study indicates that graph density and non-edge selection significantly impact model performance, with ensemble models consistently outperforming others, particularly in dense graphs. Sparse graphs exhibit higher variance and lower predictive power due to limited structural information, while denser graphs enhance link prediction accuracy by providing richer features. Findings suggest that sparse graphs provide limited feature information, reducing model effectiveness, while dense graphs enhance predictive performance due to richer feature sets. The study also reveals that non-edge selection strategies influence bias and variance, impacting model generalization. This study highlights the need for systematic non-edge selection and graph density considerations in link prediction tasks.</p>