Preface: Special issue on algorithms and models for the web graph

This special issue of Internet Mathematics is dedicated to the 6th International Workshop on Algorithms and Models for the Web Graph (WAW 2009), held at Barcelona, Spain, on February 12–13, 2009. The workshop has reported state-of-the-art achievements in the analysis of the World Wide Web and online social networking sites where the notion of a graph is central. The workshop program consisted of 14 regular refereed papers. The papers have been naturally clustered in three sections: “Graph Models for Complex Networks,‿ “PageRank and theWeb Graph,‿ and “Social Networks and Search.‿ The first section lays a foundation for theoretical and empirical analysis of the Web graph and Web 2.0 graphs. The second section analyzes random walks on the Web and Web 2.0 graphs and their applications. It is interesting to observe that the PageRank algorithm finds new exciting applications beyond now classical Web-page ranking. Nowadays, social networks are among the most popular applications on the Web. The third section of the workshop program is devoted to the design and performance evaluation of the algorithms for social networks. After the workshop, the authors were invited to submit an extended version of their work for this special issue. These extended papers were independently reviewed following the usual standards of Internet Mathematics. The papers selected for the special issue also represent well the three above-mentioned topics. The papers of P. Boldi, M. Santini, and S. Vigna; F. Chung, P. Horn, and L. Lu; and C. Karande, K. Chellapilla, and R. Andersen belong to the topic “Graph Models for Complex Networks.‿ The paper of F. Chung belongs to the topic “PageRank and the Web Graph.‿ The papers of A. Bonato, N. Hadi, P. Horn, P. Pralat, and C. Wang; and M. Gonen and Y. Shavitt belong to the topic “Social Networks and Search.‿ The paper of H. C. Lee and A. Borodin equally belongs to the last two topics. We would like to thank all the authors for their high-quality scientific contributions to the workshop and to this special issue, as well as all the reviewers who helped us to keep very high review standards. We would like to thank Andrei Broder, the general chair of WAW 2009, for his very valuable advice. We also would like to thank Charlotte Henderson for helping us to prepare this special volume.