Algorithms and Models for the Web-Graph

1. Front Matter

   PDF

2. Graph Models for Complex Networks

   1. Information Theoretic Comparison of Stochastic Graph Models: Some Experiments

      • Kevin J. Lang

      Pages 1-12

   2. Approximating the Number of Network Motifs

      • Mira Gonen, Yuval Shavitt

      Pages 13-24

   3. Finding Dense Subgraphs with Size Bounds

      • Reid Andersen, Kumar Chellapilla

      Pages 25-37

   4. The Giant Component in a Random Subgraph of a Given Graph

      • Fan Chung, Paul Horn, Linyuan Lu

      Pages 38-49

   5. Quantifying the Impact of Information Aggregation on Complex Networks: A Temporal Perspective

      • Fernando Mourão, Leonardo Rocha, Lucas Miranda, Virgílio Almeida, Wagner Meira Jr.

      Pages 50-61

3. PageRank and Web Graph

   1. A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank

      • Fan Chung

      Pages 62-75

   2. Choose the Damping, Choose the Ranking?

      • Marco Bressan, Enoch Peserico

      Pages 76-89

   3. Characterization of Tail Dependence for In-Degree and PageRank

      • Nelly Litvak, Werner Scheinhardt, Yana Volkovich, Bert Zwart

      Pages 90-103

   4. Web Page Rank Prediction with PCA and EM Clustering

      • Polyxeni Zacharouli, Michalis Titsias, Michalis Vazirgiannis

      Pages 104-115

   5. Permuting Web Graphs

      • Paolo Boldi, Massimo Santini, Sebastiano Vigna

      Pages 116-126

4. Social Networks and Search

   1. A Dynamic Model for On-Line Social Networks

      • Anthony Bonato, Noor Hadi, Paul Horn, Paweł Prałat, Changping Wang

      Pages 127-142

   2. TC-SocialRank: Ranking the Social Web

      • Antonio Gulli, Stefano Cataudella, Luca Foschini

      Pages 143-154

   3. Exploiting Positive and Negative Graded Relevance Assessments for Content Recommendation

      • Maarten Clements, Arjen P. de Vries, Marcel J. T. Reinders

      Pages 155-166

   4. Cluster Based Personalized Search

      • Hyun Chul Lee, Allan Borodin

      Pages 167-183

5. Back Matter

   PDF

This book constitutes the refereed proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009, held in Barcelona, Spain, in February 2009 - co-located with WSDM 2009, the Second ACM International Conference on Web Search and Data Mining. The 14 revised full papers presented were carefully reviewed and selected from numerous submissions for inclusion in the book. The papers address a wide variety of topics related to the study of the Web-graph such as theoretical and empirical analysis of the Web graph and Web 2.0 graphs, random walks on the Web and Web 2.0 graphs and their applications, and design and performance evaluation of the algorithms for social networks. The workshop papers have been naturally clustered in three topical sections on graph models for complex networks, pagerank and Web graph, and social networks and search.

• PageRank
• Performance
• algorithms
• bookmarks
• collaborative editing
• computational graph theory
• connectivity
• distributed systems
• graph-based Web search
• multivariate extremes
• networking algorithms
• online algorithms
• power law graphs
• ran
• random graph
• algorithm analysis and problem complexity

• INRIA Sophia Antipolis, 2004, Route des Lucioles, France

  Konstantin Avrachenkov

• Yahoo! Research, Barcelona Catalunya, Spain

  Debora Donato

• Dept. of Applied Mathematics, University of Twente, Enschede, The Netherlands

  Nelly Litvak

Policies and ethics