The сomparative аnalysis of algorithms for creation of large interconnection networks with small-world properties

Abstract

 An approach to design of interconnection networks for next generation supercomputers is suggested. A number of both known in the literature and original algorithms for complex small-world networks construction are considered. The small-world property provides slow (logarithmic) growth of average distance between nodes with growth of the network size. The networks constructed on the basis of these algorithms have basic structure of regular lattice with additional shortcuts providing the smallworld properties. The technique for comparing the efficiency of the algorithms of different types is proposed.