Deterministic small-world communication networks

Many real life networks, including the World Wide Web, electric power grids , and social networks, are small-world networks. The two distinguishing cha racteristics of small-world networks are strong local clustering (nodes hav e many mutual neighbors), and small average distance between two nodes. Sma ll-world networks are promising candidates for communication networks since typical data-flow patterns in communication networks show a large amount o f clustering with a small number of "long-distance" communications that nee d to be completed quickly. Most previous research on small-world networks has used simulations, probab ilistic techniques, and random replacements of edges to study the limiting behaviour of these networks. In this paper, we initiate the study of small- world networks as communication networks using graph-theoretic methods to o btain exact results. We construct networks with strong local clustering and small diameter (instead of average distance). Our networks have the additi onal property that they are regular. (C) 2000 Elsevier Science B.V. All rig hts reserved.