Eigenvector synchronization, graph rigidity and the molecule problem.

Area of Science:

• Computational geometry
• Network science
• Structural bioinformatics

Background:

• The graph realization problem is crucial for applications like wireless sensor networks and structural biology.
• Existing methods face challenges with sparse and noisy distance measurements in 3D space.

Purpose of the Study:

• To propose a novel algorithm, 3D-As-Synchronized-As-Possible (3D-ASAP), for solving the 3D graph realization problem.
• To develop a robust method that integrates local distance information for global structure determination, even with sparse and noisy data.
• To incorporate specific biological insights for molecular structure determination.

Main Methods:

• The 3D-ASAP algorithm employs a divide and conquer strategy, embedding local 1-hop neighborhood subgraphs into individual coordinate systems.
• It estimates Euclidean group transformations to align these local embeddings into a globally consistent structure.
• A faster variant, 3D-spectral-partitioning (SP)-ASAP, utilizes spectral partitioning for pre-processing.

Main Results:

• 3D-ASAP and 3D-SP-ASAP demonstrate high robustness against significant noise in distance measurements and sparse connectivity.
• The algorithms accurately determine global structures by effectively integrating local geometric constraints.
• Performance comparisons show favorable results against state-of-the-art localization algorithms.

Conclusions:

• 3D-ASAP provides a robust and accurate solution for the 3D graph realization problem with sparse and noisy distance data.
• The algorithm's ability to handle noise and integrate biological prior information makes it valuable for structural biology and sensor network localization.
• 3D-SP-ASAP offers a computationally efficient alternative without compromising accuracy.