Preface

PrefaceThis volume constitutes the refereed proceedings of the 6th Workshop on Algorithms and Models for the Web Graph, WAW 2009, held in Barcelona in February 2009. The World Wide Web has become part of our everyday life, and information retrieval and data mining on the Web are now of enormous practical interest. The algorithms supporting these activities combine the view of the Web as a text repository and as a graph, induced in various ways by links among pages, links among hosts, or other similar networks. We also witness an increasing role of the second-generation Web-based applications Web 2.0, such as social networking sites and wiki sites.The workshop program consisted of 14 regular papers and two invited talks. The invited talks were given by Ravi Kumar (Yahoo! Research, USA) and José Fernando Mendes (University of Aveiro, Portugal). The regular papers went through a thorough review process. The workshop papers were naturally clustered in three sections: “Graph Models for Complex Networks", “PageRank and Web 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. We hope that the papers presented at WAW 2009 will stimulate further development of Web 2.0 applications and deepen our understanding of the World Wide Web evolution.We would like to thank the General Chair, Andrei Broder, and the Program Committee members for their time and effort which resulted in a very high quality program. We would like to thank the organizers of WAW 2007, Fan Chung and Anthony Bonato, for their valuable advice. We also would like to thank the Springer LNCS editorial team, particularly Alfred Hofmann, Ursula Barth and Anna Kramer, for their advice and prompt help. We thank Yana Volkovich very much for the design and continuing support of the WAW 2009 website. We would like to thank cordially our industrial sponsors Yahoo! Inc. and Google Inc. and our technical sponsors INRIA, University of Twente, Pompeu Fabra University, and Barcelona Media - Innovation Centre. Last but not least, we would like to extend our thanks to all the authors for their high-quality scientific contribution.February 2009 Konstantin AvrachenkovDebora DonatoNelly Litvak