- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Ab-initio reconstruction of complex Euclidean networks in two dimensions

S. R. Gujarathi, C. L. Farrow, C. Glosser, L. Granlund, and P. M. Duxbury*

  • Department of Physics and Astronomy, Michigan State University, East Lansing, Michigan 48824, USA

  • *duxbury@pa.msu.edu
PDF

Phys. Rev. E 89, 053311 – Published 20 May, 2014

DOI: https://doi.org/10.1103/PhysRevE.89.053311

Abstract

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.

View figure in article

Article Text

References (41)

  1. G. M. Crippen and T. F. Havel, Distance Geometry and Molecular Conformation (Wiley and Sons, New York, 1988).
  2. G. Crippen, J. Math. Chem. 6, 307 (1991).
  3. S. B. Lindström, D. A. Vader, A. Kulachenko, and D. A. Weitz, Phys. Rev. E 82, 051905 (2010).
  4. K. Wuthrich, Acc. Chem. Res. 22, 36 (1989).
  5. K. Wuthrich, Science 243, 45 (1989).
  6. L. Liberti, C. Lavor, A. Mucherino, and N. Maculan, Int. Trans. Operation. Res. 18, 33 (2011).
  7. M. Li, Y. Otachi, and T. Tokuyama, in 7th International Symposium on Algorithms for Sensor Systems, Wireless AD HOC Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Lecture Notes in Computer Science 7111 (Springer-Verlag, Berlin, 2012), pp. 101–114.
  8. L. Liberti, C. Lavor, N. Maculan, and A. Mucherino, SIAM Rev. 56, 3 (2014).
  9. R. L. McGreevy and L. Pusztai, Mol. Simul. 1, 359 (1988).
  10. A. Patterson, Nature (London) 143, 939 (1939).
  11. J. Yoon, Y. Gad, and Z. Wu, technical report, 2000.
  12. J. C. Kendrew, R. E. Dickerson, B. E. Strandberg, R. G. Hart, D. R. Davies, D. C. Phillips, and V. C. Shore, Nature (London) 185, 422 (1960).
  13. M. F. Perutz, M. Rossmann, A. Cullis, H. Muirhead, G. Will, and A. C. T. North, Nature (London) 185, 416 (1960).
  14. J. Miao, H. N. Chapman, J. Kirz, D. Sayre, and K. O. Hodgson, Annu. Rev. Biophys. Biomol. Struct. 33, 157 (2004).
  15. J. Miao, J. Kirz, and D. Sayre, Acta Crystallogr. Sect. D 56, 1312 (2000).
  16. J. Wu, K. Leinenweber, J. C. H. Spence, and M. O'Keeffe, Nat. Mater. 5, 647 (2006).
  17. V. L. Shneerson, A. Ourmazd, and D. K. Saldin, Acta Crystallog. Sect. A 64, 303 (2008).
  18. Y. Jiao, F. H. Stillinger, and S. Torquato, Phys. Rev. E 81, 011105 (2010).
  19. Y. Jiao, F. Stillinger, and S. Torquato, Phys. Rev. E 82, 011106 (2010).
  20. D. Cule and S. Torquato, J. Appl. Phys. 86, 3428 (1999).
  21. M. Nilges and S. I. O'Donoghue, Prog. Nucl. Magn. Reson. Spectrosc. 32, 107 (1998).
  22. B. Hendrickson, SIAM J. Optim. 5, 835 (1995).
  23. B. Berger, J. Kleinberg, and T. Leighton,' JACM 46, 449 (1996).
  24. J. Moré and Z. Wu, technical report, 1995.
  25. J. Saxe, in Proceedings of the 17th Allerton Conference on Communications, Control and Computing, edited by J. B. Cruz and F. P. Preparata (University of Illinois Urbana-Champagne, Urbana, IL, 1979), pp. 480–489.
  26. H. Lin, E. S. Božin, S. J. L. Billinge, E. Quarez, and M. G. Kanatzidis, Phys. Rev. B 72, 174113 (2005).
  27. L. Malavasi, G. A. Artioli, H. Kim, B. Maroni, B. Joseph, Y. Ren, T. Proffen, and S. J. L. Billinge, J. Phys.: Condens. Matter 23, 272201 (2011).
  28. T. Proffen and S. Billinge, Appl. Phys. A 74, s1770 (2002).
  29. S. J. Billinge, J. Solid State Chem. 181, 1695 (2008).
  30. S. J. L. Billinge and M. G. Kanatzidis, Chem. Commun. (Cambridge, UK) 7, 749 (2004).
  31. S. J. L. Billinge and I. Levin, Science 316, 561 (2007).
  32. P. Juhás, D. M. Cherba, P. M. Duxbury, W. F. Punch, and S. J. L. Billinge, Nature (London) 440, 655 (2006).
  33. P. Juhás, L. Granlund, P. M. Duxbury, W. F. Punch, and S. J. L. Billinge, Acta Crystallogr. Sect. A 64, 631 (2008).
  34. P. Juhas, L. Granlund, S. R. Gujarathi, P. M. Duxbury, and S. J. L. Billinge, J. Appl. Crystallogr. 43, 623 (2010).
  35. B. Roth, Am. Math. Mon. 88, 6 (1981).
  36. H. Crapo, Struct. Topol. 1, 26 (1979).
  37. L. Asimow and B. Roth, J. Math. Anal. Appl. 1, 2572 (2010).
  38. L. Asimow and B. Roth, Trans. Am. Math. Soc. 245, 279 (1978).
  39. G. Laman, J. Eng. Math. 4, 331 (1970).
  40. L.-s. Li and X. Yan, J. Phys. Chem. Lett. 1, 1595 (2010).
  41. T. Egami and S. J. L. Billinge, Underneath the Bragg Peaks: Structural Analysis of Complex Materials (Elsevier, Oxford, 2003).

Outline

Information

Phys. Rev. E 89, 053311– Published 20 May, 2014
  • Received 19 August 2013

©2014 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation