Dynamics of directed graphs: the world-wide Web

Abstract

We introduce and simulate a growth model of the world-wide Web based on the dynamics of outgoing links that is motivated by the conduct of the agents in the real Web to update outgoing links (re)directing them towards constantly changing selected nodes. Emergent statistical correlation between the distributions of outgoing and incoming links is a key feature of the dynamics of the Web. The growth phase is characterized by temporal fractal structures which are manifested in the hierarchical organization of links. We obtain quantitative agreement with the recent empirical data in the real Web for the distributions of in- and out-links and for the size of connected component. In a fully grown network of $N$ nodes we study the structure of connected clusters of nodes that are accessible along outgoing links from a randomly selected node. The distributions of size and depth of the connected clusters with a giant component exhibit supercritical behavior. By decreasing the control parameter---average fraction $\beta$ of updated and added links per time step---towards ${\beta }_c(N)<10$ the Web can resume a critical structure with no giant component in it. We find a different universality class when the updates of links are not allowed, i.e., for $\beta \equiv 0$, corresponding to the network of science citations.

Revtex, 4 PostScript figures, small changes in the text

References in corpus (4)

• Emergence of scaling in random networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• The Fractal Properties of Internet

Cited by in corpus (37)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Epidemic dynamics and endemic states in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Efficient routing on complex networks
• Are randomly grown graphs really random?
• Preferential attachment in the growth of social networks: the case of Wikipedia
• Degree Distributions of Growing Networks
• Small-world behavior in time-varying graphs
• Giant strongly connected component of directed networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations
• Anomalous percolating properties of growing networks
• World-Wide Web scaling exponent from Simon's 1955 model
• Growing Random Networks with Fitness
• Transport on Complex Networks: Flow, Jamming and Optimization
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Signatures of small-world and scale-free properties in large computer programs
• Components in time-varying graphs
• Information Super-Diffusion on Structured Networks
• Scaling of human behavior during portal browsing
• Magnetization reversal in spin patterns with complex geometry
• Response time of internauts
• Evolving networks through deletion and duplication
• A directed network model for World-Wide Web
• Complex scale-free networks with tunable power-law exponent and clustering
• Temporal fractal structures: Origin of power-laws in the world-wide Web
• Scaling behavior of an artificial traffic model on scale-free networks
• Simple models of small world networks with directed links
• Robustness of the in-degree exponent for the world-wide web
• Directed Accelerated Growth: Application in Citation Network
• Flow of emotional messages in artificial social networks
• Modeling and Performance Studies of Data Communication Networks using Dynamic Complex Networks
• Growing Networks: Limit in-degree distribution for arbitrary out-degree one
• Estimating Formation Mechanisms and Degree Distributions in Mixed Attachment Networks
• Nonreciprocal random networks and their percolation properties