(February 1, 2008) | Vito Latora1,2 and Massimo Marchiori3,4
The paper introduces the concept of *efficiency* as a measure of how efficiently information is exchanged in a network, providing a clear physical interpretation of small-world networks. Small-world networks are characterized by both high global and local efficiency. The efficiency measure, denoted as \( E \), is defined as the average efficiency of all possible pairs of vertices in a network, calculated using the shortest path lengths and physical distances between vertices. This measure allows for a precise quantitative analysis of both unweighted and weighted networks, including disconnected and non-sparse graphs.
The authors demonstrate that small-world behavior can be understood through the efficiency measure \( E \), which encompasses both global and local efficiency. They show that small-world networks exhibit high \( E_{\text{glob}} \) and \( E_{\text{loc}} \), indicating efficient global and local communication. The paper also discusses the correspondence between the efficiency measure and the characteristic path length \( L \) and clustering coefficient \( C \), highlighting that \( 1/L \) and \( C \) are first approximations of \( E_{\text{glob}} \) and \( E_{\text{loc}} \), respectively.
The authors analyze various real-world networks, including neural networks, communication networks (such as the World Wide Web and the Internet), and transportation networks (such as the Boston subway system). They find that these networks exhibit small-world behavior, with high global and local efficiency. For example, neural networks like the cerebral cortex and C. elegans show high \( E_{\text{glob}} \) and \( E_{\text{loc}} \), indicating a balance between global connectivity and fault tolerance. Communication networks like the World Wide Web and the Internet also show high efficiency, while transportation networks like the Boston subway system exhibit lower local efficiency due to their non-closed nature.
Overall, the introduction of the efficiency measure provides a robust framework for understanding the properties of small-world networks and their applications in various real-world systems.The paper introduces the concept of *efficiency* as a measure of how efficiently information is exchanged in a network, providing a clear physical interpretation of small-world networks. Small-world networks are characterized by both high global and local efficiency. The efficiency measure, denoted as \( E \), is defined as the average efficiency of all possible pairs of vertices in a network, calculated using the shortest path lengths and physical distances between vertices. This measure allows for a precise quantitative analysis of both unweighted and weighted networks, including disconnected and non-sparse graphs.
The authors demonstrate that small-world behavior can be understood through the efficiency measure \( E \), which encompasses both global and local efficiency. They show that small-world networks exhibit high \( E_{\text{glob}} \) and \( E_{\text{loc}} \), indicating efficient global and local communication. The paper also discusses the correspondence between the efficiency measure and the characteristic path length \( L \) and clustering coefficient \( C \), highlighting that \( 1/L \) and \( C \) are first approximations of \( E_{\text{glob}} \) and \( E_{\text{loc}} \), respectively.
The authors analyze various real-world networks, including neural networks, communication networks (such as the World Wide Web and the Internet), and transportation networks (such as the Boston subway system). They find that these networks exhibit small-world behavior, with high global and local efficiency. For example, neural networks like the cerebral cortex and C. elegans show high \( E_{\text{glob}} \) and \( E_{\text{loc}} \), indicating a balance between global connectivity and fault tolerance. Communication networks like the World Wide Web and the Internet also show high efficiency, while transportation networks like the Boston subway system exhibit lower local efficiency due to their non-closed nature.
Overall, the introduction of the efficiency measure provides a robust framework for understanding the properties of small-world networks and their applications in various real-world systems.