Related Experiment Videos
Giant strongly connected component of directed networks
S N Dorogovtsev1, J F Mendes, A N Samukhin
1Departamento de Física and Centro de Física do Porto, Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687, Portugal. sdorogov@fc.up.pt
Summary
This study introduces a method to calculate giant connected components in directed graphs, like the World Wide Web. It reveals how component sizes, especially the giant strongly connected component, are affected by degree distributions.
Area of Science:
- Network Science
- Graph Theory
- Statistical Physics
Background:
- The World Wide Web is a large-scale directed network.
- Understanding the structure of giant connected components is crucial for analyzing network properties.
- Previous analyses often assumed factorizable degree distributions.
Purpose of the Study:
- To develop a method for calculating the sizes of all giant connected components in directed graphs.
- To analyze the impact of non-factorizable joint in- and out-degree distributions on component sizes.
- To compare the resilience of different giant components.
Main Methods:
- Analytical calculations for directed graphs with statistically uncorrelated vertices.
- Derivation of formulas for the relative sizes of giant components.
- Examination of the joint in- and out-degree distribution P(k(i),k(o)).
Main Results:
- A method to compute the sizes of all giant connected components, including the strongly connected one.
- Demonstration that non-factorizable P(k(i),k(o)) leads to deviations in the giant strongly connected component size.
- The giant strongly connected component may be less resilient to random damage than the giant weakly connected component.
Conclusions:
- The joint degree distribution significantly influences the size of the giant strongly connected component.
- Network resilience can vary between different types of giant components.
- The findings have implications for understanding large-scale directed networks like the internet.