Network Medicine relies on RNA sequencing to infer gene co-expression networks, which are crucial to identify functional gene clusters and gene regulatory interactions, and offer a deeper understanding of disease phenotypes and drug mechanisms. It remains unknown, however, how many samples do we need to make reliable predictions. Here, we propose a power-law model to predict the relationship between the number of inferred significant interactions and sample size, allowing us to quantitatively link sample size to the accuracy of the inferred networks. We apply our model to investigate the effect of sample size on biomarker discovery and differentiation of protein-protein interactions from non-interacting pairs, ultimately unveiling the critical role of data quality in generating meaningful predictions in Network Medicine.