Maps of random walks on complex networks reveal community structure

Maps of random walks on complex networks reveal community structure

February 1, 2008 | M. Rosvall, C. T. Bergstrom
This paper introduces a new information-theoretic method to reveal community structure in complex networks, particularly in weighted and directed networks. The method identifies modules by optimally compressing the description of information flows on the network, resulting in a map that simplifies and highlights the structure and relationships. The approach is demonstrated by mapping scientific communication based on citation patterns among over 6,000 journals. The map reveals a multicentric organization of scientific fields, with varying sizes and integration levels. Information flows bidirectionally along the backbone of the network, including physics, chemistry, molecular biology, and medicine, but the map shows a directional pattern of citation from applied fields to basic sciences. The method uses random walks to model information flow and applies coding theory principles to compress the description of these walks. This allows for efficient representation of network structure while preserving important relationships. The approach is compared to modularity optimization, which focuses on maximizing the number of edges within modules. The map equation is used to find the optimal partitioning of the network, minimizing the average description length of a random walk. This method is shown to be more effective than modularity optimization in capturing the flow-based structure of networks. The paper maps scientific communication using citation data from 6,128 scientific and 1,431 social science journals. The resulting maps reveal the organization of scientific fields, with module sizes reflecting the fraction of time a random surfer spends within them. The maps highlight the flow of citations between fields, with the thickness and color of arrows indicating the volume of citations. The maps also show the directional relationship between applied and basic sciences, with applied fields citing basic sciences more frequently. The method is robust to the choice of teleportation probability, which introduces a small chance of random jumps in the random walk. The maps reveal a ring-like structure of scientific disciplines, with major fields connected through intermediate fields. However, the structure is more like the letter "U" with the social sciences at one end and engineering at the other, connected by a backbone of medicine, molecular biology, chemistry, and physics. The maps also show the research frontier, representing the most recent developments in science rather than long-term interdependencies. The method is applied to both scientific and social science networks, revealing the organization of fields and their relationships. The maps are visualized with module sizes proportional to the fraction of time a random surfer spends within them, and link widths proportional to the probability of transitions between modules. The maps highlight important structures while filtering out insignificant details, providing a clear and concise representation of complex networks. The method is shown to be effective in capturing the structure of complex systems, including biological and social networks, by focusing on the flow of information and interactions between nodes.This paper introduces a new information-theoretic method to reveal community structure in complex networks, particularly in weighted and directed networks. The method identifies modules by optimally compressing the description of information flows on the network, resulting in a map that simplifies and highlights the structure and relationships. The approach is demonstrated by mapping scientific communication based on citation patterns among over 6,000 journals. The map reveals a multicentric organization of scientific fields, with varying sizes and integration levels. Information flows bidirectionally along the backbone of the network, including physics, chemistry, molecular biology, and medicine, but the map shows a directional pattern of citation from applied fields to basic sciences. The method uses random walks to model information flow and applies coding theory principles to compress the description of these walks. This allows for efficient representation of network structure while preserving important relationships. The approach is compared to modularity optimization, which focuses on maximizing the number of edges within modules. The map equation is used to find the optimal partitioning of the network, minimizing the average description length of a random walk. This method is shown to be more effective than modularity optimization in capturing the flow-based structure of networks. The paper maps scientific communication using citation data from 6,128 scientific and 1,431 social science journals. The resulting maps reveal the organization of scientific fields, with module sizes reflecting the fraction of time a random surfer spends within them. The maps highlight the flow of citations between fields, with the thickness and color of arrows indicating the volume of citations. The maps also show the directional relationship between applied and basic sciences, with applied fields citing basic sciences more frequently. The method is robust to the choice of teleportation probability, which introduces a small chance of random jumps in the random walk. The maps reveal a ring-like structure of scientific disciplines, with major fields connected through intermediate fields. However, the structure is more like the letter "U" with the social sciences at one end and engineering at the other, connected by a backbone of medicine, molecular biology, chemistry, and physics. The maps also show the research frontier, representing the most recent developments in science rather than long-term interdependencies. The method is applied to both scientific and social science networks, revealing the organization of fields and their relationships. The maps are visualized with module sizes proportional to the fraction of time a random surfer spends within them, and link widths proportional to the probability of transitions between modules. The maps highlight important structures while filtering out insignificant details, providing a clear and concise representation of complex networks. The method is shown to be effective in capturing the structure of complex systems, including biological and social networks, by focusing on the flow of information and interactions between nodes.
Reach us at info@study.space
[slides] Maps of random walks on complex networks reveal community structure | StudySpace