Average Shortest Path Length in a Novel Small-World Network

We study a novel model of random graph which exhibits the structural characteristics of the Watts- Strogatz small-world network. The small-world network is characterized by a high level of local clustering while also having a relatively small graph diameter. The same behavior that makes the Watts-Strogatz model behave like this also makes it difficult to analyze. Our model addresses this issue, closely mimicking the same structure experimentally while following a constructive process that makes it easier to analyze mathematically. We present a bound on the average shortest path length in our new model, which we approach by looking at the two key geometric components