Ab-initio reconstruction of complex Euclidean networks in two dimensions

• Published in: Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2014-05, Vol.89 (5), p.053311-053311, Article 053311
• Main Authors: Gujarathi, S R, Farrow, C L, Glosser, C, Granlund, L, Duxbury, P M
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Simulation; Models, Theoretical; Numerical Analysis, Computer-Assisted
• ISSN: 1539-3755; 1550-2376
• DOI: 10.1103/PhysRevE.89.053311

Reconstruction of complex structures is an inverse problem arising in virtually all areas of science and technology, from protein structure determination to bulk heterostructure solar cells and the structure of nanoparticles. We cast this problem as a complex network problem where the edges in a network have weights equal to the Euclidean distance between their endpoints. We present a method for reconstruction of the locations of the nodes of the network given only the edge weights of the Euclidean network. The theoretical foundations of the method are based on rigidity theory, which enables derivation of a polynomial bound on its efficiency. An efficient implementation of the method is discussed and timing results indicate that the run time of the algorithm is polynomial in the number of nodes in the network. We have reconstructed Euclidean networks of about 1000 nodes in approximately 24 h on a desktop computer using this implementation. We also reconstruct Euclidean networks corresponding to polymer chains in two dimensions and planar graphene nanoparticles. We have also modified our base algorithm so that it can successfully solve random point sets when the input data are less precise.