Complex Networks: A Networking and Signal Processing Perspective

Chapter 4Small-World Networks

A regular network is structured in a particular pattern (e.g., a 2-D grid network) where a node is always connected to its immediate neighbors. Immediate neighbors, in this context, are the nodes with the shortest Euclidean distances in all directions in a 2-D network. On the contrary, a random network is formed when nodes are connected with certain probability p ∈ [0, 1]. However, a node in a random network may not be connected to its immediate neighbors. This chapter introduces the small-world network. The term small-world refers to the fact that it requires a small number of hops to reach a distant node from a source node. The characteristics of a small-world network lay between a regular network where nodes ...