Algorithms and Models for the Web-Graph

1. Front Matter

   PDF

2. A Spectral Algorithm for Computing Social Balance

   • Evimaria Terzi, Marco Winkler

   Pages 1-13

3. High-Ordered Random Walks and Generalized Laplacians on Hypergraphs

   • Linyuan Lu, Xing Peng

   Pages 14-25

4. Detecting the Structure of Social Networks Using (α,β)-Communities

   • Jing He, John Hopcroft, Hongyu Liang, Supasorn Suwajanakorn, Liaoruo Wang

   Pages 26-37

5. Latent Clustering on Graphs with Multiple Edge Types

   • Matthew Rocklin, Ali Pinar

   Pages 38-49

6. Quick Detection of Top-k Personalized PageRank Lists

   • Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, Elena Smirnova, Marina Sokol

   Pages 50-61

7. Rank-Based Models of Network Structure and the Discovery of Content

   • Adam Douglas Henry, Paweł Prałat

   Pages 62-73

8. 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs

   • Rafał Witkowski, Janez Žerovnik

   Pages 74-84

9. Modeling Social Networks through User Background and Behavior

   • Ilias Foudalis, Kamal Jain, Christos Papadimitriou, Martha Sideri

   Pages 85-102

10. Dirichlet PageRank and Trust-Based Ranking Algorithms

    • Fan Chung, Alexander Tsiatas, Wensong Xu

    Pages 103-114

11. Efficient Generation of Networks with Given Expected Degrees

    • Joel C. Miller, Aric Hagberg

    Pages 115-126

12. Back Matter

    PDF

This book constitutes the refereed proceedings of the 8th International Workshop on Algorithms and Models for the Web-Graph, WAW 2011, held in Atlanta, GA, in May 2011 - co-located with RSA 2011, the 15th International Conference on Random Structures and Algorithms.
The 13 revised full papers presented together with 1 invited lecture were carefully reviewed and selected from 19 submissions. Addressing a wide variety of topics related to the study of the Web-graph such as theoretical and empirical analysis, the papers feature original research in terms of algorithmic and mathematical analysis in all areas pertaining to the World-Wide Web with special focus to the view of complex data as networks.

• PageRank
• Web links
• algorithmic game theory
• network model
• social networks
• algorithm analysis and problem complexity

• Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, USA

  Alan Frieze

• Department of Mathematics and Computer Science, Emory University, Atlanta, USA

  Paul Horn

• Department of Mathematics, West Virginia University, Morgantown, USA

  Paweł Prałat

Policies and ethics