Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings

✍ Scribed by Fan Chung, Alexander Tsiatas (auth.), Anthony Bonato, Jeannette Janssen (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2012
• Tongue: English
• Leaves: 185
• Series: Lecture Notes in Computer Science 7323
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 9th International Workshop on Algorithms and Models for the Web-Graph, WAW 2012, held in Halifax, Nova Scotia, Canada, in June 2012. The 13 papers presented were carefully reviewed and selected for inclusion in this volume. They address a number of topics related to the complex networks such hypergraph coloring games and voter models; algorithms for detecting nodes with large degrees; random Appolonian networks; and a sublinear algorithm for Pagerank computations.

✦ Table of Contents

Front Matter....Pages -
Hypergraph Coloring Games and Voter Models....Pages 1-16
On a DAG Partitioning Problem....Pages 17-28
Some Typical Properties of the Spatial Preferred Attachment Model....Pages 29-40
A Sublinear Time Algorithm for PageRank Computations....Pages 41-53
Quick Detection of Nodes with Large Degrees....Pages 54-65
Ranking and Sparsifying a Connection Graph....Pages 66-77
A Game-Theoretic Model of Attention in Social Networks....Pages 78-92
On Certain Properties of Random Apollonian Networks....Pages 93-112
Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links....Pages 113-125
Dynamic PageRank Using Evolving Teleportation....Pages 126-137
Multi-commodity Allocation for Dynamic Demands Using PageRank Vectors....Pages 138-152
Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs....Pages 153-164
A Fast Algorithm to Find All High Degree Vertices in Graphs with a Power Law Degree Sequence....Pages 165-178
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Information Systems Applications (incl. Internet); Data Mining and Knowledge Discovery; Computer Communication Networks; Information Storage and Retriev