Modeling the webgraph evolution

The impact of the web as source of information and services is growing continuously and consequently the importance of appropriate design of algorithms for the web has increased. Such algorithms depend both on the web structure and how it evolves over time. The webgraph is formed by the link structure of webpages. It is well known that this graph is sparse, huge and dynamic, i.e., it changes over time. A challenge related to this topic is how to model the webgraph evolution taking into account its characteristics.As main contribution, in this work we propose a new approach to model webgraph evolution. Three different models are defined. The last presented model describes webgraph evolution in a more faithful way, as it can be seen from the analysis of the generated graphs. Nevertheless, other models are also interesting on their own, and could be used when only some characteristics of the generated graphs are of interest. Moreover, the stepwise construction and comparison of the models is useful to make explicit how the generated graphs are affected by changes of the rules governing the proposed evolution models. All proposed models are based on node and arc insertions according to the preferential attachment. The probabilistic algorithms derived from the models were implemented and their resulting graphs analysed and compared with results from the literature. This study has revealed that the models were able to generate synthetic webgraphs with many important characteristics found in real-world webgraphs. As a second contribution of the paper, we introduce the use of graph grammars as a specification language to describe the webgraph evolution. Graph grammars is a formalism that allows the description of graph transformations in a natural, graphical and precise way, providing a good basis for understanding, reasoning and comparing specifications.

Research highlights▶ Proposal of a new model for generating webgraphs. ▶ Use of graph grammars to specify the graph transformations. ▶ Analysis of the generated graphs and comparison with realworld graphs. ▶ The generated graphs present most of the features commonly found in webgraphs.