Efficient Behavior of Small-World Networks

Efficient Behavior of Small-World Networks

February 1, 2008 | Vito Latora and Massimo Marchiori
The paper introduces the concept of network efficiency to characterize the information exchange capability of networks. Small-world networks are shown to be both globally and locally efficient, providing a clear physical meaning to the concept. This measure allows for a precise quantitative analysis of both weighted and unweighted networks. The study includes neural networks, communication, and transportation systems, showing that their construction follows a small-world principle of high efficiency. Small-world networks have a structure that is highly clustered like regular lattices but with short path lengths like random graphs. This behavior is characterized by a balance between local efficiency (high clustering) and global efficiency (short path lengths). The efficiency of a network is defined as the average inverse of the shortest path lengths between all pairs of nodes. For a fully connected ideal graph, the efficiency is maximized. The paper compares the efficiency measure with the previously used path length (L) and clustering coefficient (C). While L measures the efficiency of a sequential system, efficiency (E) measures the efficiency of a parallel system. The efficiency measure is more accurate in capturing the true efficiency of real networks, especially when there are significant differences in path lengths. The paper analyzes several real-world networks, including neural networks, communication networks (World Wide Web and Internet), and transportation networks (Boston subway system). It shows that these networks exhibit small-world behavior, with high global and local efficiency. For example, the neural networks of the macaque and cat show high efficiency, while the Boston subway system, when considered as a weighted graph, shows high global efficiency but low local efficiency. The study highlights that the small-world principle is not only applicable to social and biological networks but also to man-made systems. The efficiency measure provides a more accurate and comprehensive understanding of network behavior, allowing for a better analysis of both unweighted and weighted networks. The results indicate that various existing networks, including neural, communication, and transport networks, exhibit small-world behavior, supporting the idea that the diffusion of small-world networks is driven by the need to create networks that are both globally and locally efficient.The paper introduces the concept of network efficiency to characterize the information exchange capability of networks. Small-world networks are shown to be both globally and locally efficient, providing a clear physical meaning to the concept. This measure allows for a precise quantitative analysis of both weighted and unweighted networks. The study includes neural networks, communication, and transportation systems, showing that their construction follows a small-world principle of high efficiency. Small-world networks have a structure that is highly clustered like regular lattices but with short path lengths like random graphs. This behavior is characterized by a balance between local efficiency (high clustering) and global efficiency (short path lengths). The efficiency of a network is defined as the average inverse of the shortest path lengths between all pairs of nodes. For a fully connected ideal graph, the efficiency is maximized. The paper compares the efficiency measure with the previously used path length (L) and clustering coefficient (C). While L measures the efficiency of a sequential system, efficiency (E) measures the efficiency of a parallel system. The efficiency measure is more accurate in capturing the true efficiency of real networks, especially when there are significant differences in path lengths. The paper analyzes several real-world networks, including neural networks, communication networks (World Wide Web and Internet), and transportation networks (Boston subway system). It shows that these networks exhibit small-world behavior, with high global and local efficiency. For example, the neural networks of the macaque and cat show high efficiency, while the Boston subway system, when considered as a weighted graph, shows high global efficiency but low local efficiency. The study highlights that the small-world principle is not only applicable to social and biological networks but also to man-made systems. The efficiency measure provides a more accurate and comprehensive understanding of network behavior, allowing for a better analysis of both unweighted and weighted networks. The results indicate that various existing networks, including neural, communication, and transport networks, exhibit small-world behavior, supporting the idea that the diffusion of small-world networks is driven by the need to create networks that are both globally and locally efficient.
Reach us at info@study.space
Understanding Efficient behavior of small-world networks.