Network geometry inference using common neighbors.

Area of Science:

• Network Science
• Data Mining
• Computational Topology

Background:

• Complex networks are ubiquitous in nature and technology.
• Understanding the hidden geometric structure of networks is crucial for analyzing their dynamics.
• Existing methods like HyperMap rely solely on network connectivity.

Purpose of the Study:

• To introduce and evaluate a novel method for inferring network geometry using common neighbors.
• To compare this common-neighbors approach against link-based methods.
• To develop efficient hybrid methods for network mapping and apply them to real-world data.

Main Methods:

• Inferring node coordinates based on shared neighbors.
• Comparing common-neighbors method with HyperMap (link-based).
• Developing and optimizing hybrid common-neighbors and link-based methods.
• Applying the method to Autonomous Systems (AS) Internet data.

Main Results:

• The common-neighbors approach offers higher accuracy for high-degree nodes compared to basic link-based methods.
• A hybrid method achieves O(t3) running time, with a heuristic reducing it to O(t2) without significant accuracy loss.
• The method successfully mapped AS Internet data, revealing evolving soft communities and enabling link prediction.

Conclusions:

• The common-neighbors approach provides an accurate way to map complex networks to latent geometric spaces.
• Hybrid methods offer a practical balance between computational efficiency and mapping accuracy.
• This work enhances the understanding of network dynamics and provides tools for network analysis and prediction.