Algorithms and Models for the Web-Graph

1. Front Matter

   PDF

2. The Anatomy of the Long Tail of Consumer Demand

   • Andrei Broder

   Pages 1-1

3. A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification

   • Fan Chung, Wenbo Zhao

   Pages 2-14

4. Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

   • Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, Charalampos E. Tsourakakis

   Pages 15-24

5. Computing an Aggregate Edge-Weight Function for Clustering Graphs with Multiple Edge Types

   • Matthew Rocklin, Ali Pinar

   Pages 25-35

6. Component Evolution in General Random Intersection Graphs

   • Milan Bradonjić, Aric Hagberg, Nicolas W. Hengartner, Allon G. Percus

   Pages 36-49

7. Modeling Traffic on the Web Graph

   • Mark R. Meiss, Bruno Gonçalves, José J. Ramasco, Alessandro Flammini, Filippo Menczer

   Pages 50-61

8. Multiplicative Attribute Graph Model of Real-World Networks

   • Myunghwan Kim, Jure Leskovec

   Pages 62-73

9. Random Walks on Digraphs, the Generalized Digraph Laplacian and the Degree of Asymmetry

   • Yanhua Li, Zhi-Li Zhang

   Pages 74-85

10. Finding and Visualizing Graph Clusters Using PageRank Optimization

    • Fan Chung Graham, Alexander Tsiatas

    Pages 86-97

11. Improving Random Walk Estimation Accuracy with Uniform Restarts

    • Konstantin Avrachenkov, Bruno Ribeiro, Don Towsley

    Pages 98-109

12. The Geometric Protean Model for On-Line Social Networks

    • Anthony Bonato, Jeannette Janssen, Pawel Prałat

    Pages 110-121

13. Constant Price of Anarchy in Network Creation Games via Public Service Advertising

    • Erik D. Demaine, Morteza Zadimoghaddam

    Pages 122-131

14. Fast Katz and Commuters: Efficient Estimation of Social Relatedness in Large Networks

    • Pooya Esfandiar, Francesco Bonchi, David F. Gleich, Chen Greif, Laks V. S. Lakshmanan, Byung-Won On

    Pages 132-145

15. Game-Theoretic Models of Information Overload in Social Networks

    • Christian Borgs, Jennifer Chayes, Brian Karrer, Brendan Meeder, R. Ravi, Ray Reagans et al.

    Pages 146-161

16. Back Matter

    PDF

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms and Models for the Web-Graph, WAW 2010, held in Stanford, CA, USA, in December 2010, which was co-located with the 6th International Workshop on Internet and Network Economics (WINE 2010). The 13 revised full papers and the invited paper presented were carefully reviewed and selected from 19 submissions.

• biological networks
• citation networks
• clustering
• collaborative filtering
• communities
• data models
• graph algorithms
• graph models
• patterns
• recommender networks
• reputation networks
• social networks
• structural properties
• visualization
• web mining
• web search
• algorithm analysis and problem complexity

• Yahoo! Research, Sunnyvale, USA

  Ravi Kumar

• Google Research, Mountain View, USA

  Dandapani Sivakumar

Policies and ethics