title: Smallest small-world network.
abstract: Efficiency in passage times is an important issue in designing networks, such as transportation or computer networks. The small-world networks have structures that yield high efficiency, while keeping the network highly clustered. We show that among all networks with the small-world structure, the most efficient ones have a "single center" node, from which all shortcuts are connected to uniformly distributed nodes over the network. The networks with several centers and a connected subnetwork of shortcuts are shown to be "almost" as efficient. Genetic-algorithm simulations further support our results.
authors.affiliation: Department of Mathematics, Center for Systems Science and Engineering Research, Arizona State University, Tempe 85287, USA. tnishi@chaos6.la.asu.edu
authors.forename: Takashi
authors.initials: T
authors.lastname: Nishikawa
authors.forename: Adilson E
authors.initials: AE
authors.lastname: Motter
authors.forename: Ying-Cheng
authors.initials: YC
authors.lastname: Lai
authors.forename: Frank C
authors.initials: FC
authors.lastname: Hoppensteadt