Noise-Enhanced Network Science

Graphs are a versatile and powerful data structure used to model complex relationships in diverse domains such as social networks, biological systems, and transportation networks. In graphs, entities are represented by nodes, and interactions or relationships between them are represented by edges. For example, in the World Wide Web, web pages are considered vertices, and if there is a link from one page to another page on the web, there will be a directed edge between those pages in its graph data structure. These structures allow us to analyze and solve important problems like community detection (identifying closely related clusters of nodes) and link prediction (forecasting missing or future connections between nodes). Graph algorithms, therefore, are fundamental tools in applications ranging from e-commerce recommendation engines to biological research and road network optimization. Despite significant advances, many challenges remain in improving the effectiveness and accuracy of graph algorithms. Traditional methods for community detection, link prediction, and classification have limitations, particularly in handling noise—typically viewed as a disruptive element that decreases performance. However, insights from fields like signal processing suggest that noise, when applied appropriately, can enhance system performance. This thesis introduces a novel framework that leverages noise to improve graph algorithms. By using noise as a tool rather than an obstacle, the thesis presents new techniques that modify graph data structures to enhance the performance of community detection, link prediction, and classification. Through theoretical justification and empirical experiments on real-world and synthetic datasets, it is demonstrated that adding noise to graph data can enhance the robustness and accuracy of these algorithms. The proposed noise-enhanced methods not only improve the quality of results in tasks like community detection and link prediction but also mitigate over-smoothing in GNNs, enabling them to generalize better to large and complex graphs. This research offers a paradigm shift in how noise is perceived in graph algorithms, transforming it from an obstacle to a powerful tool for optimization. The findings have broad implications for improving graph-based models and applications, paving the way for future advancements in fields ranging from social network analysis to biological research and beyond.