Algorithms and Models for the Web Graph
9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012, Proceedings
Published on 19. June 2012
VIII, 179 pages
978-3-642-30541-2 (ISBN)
Description
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.
More details
Other editions
Additional editions
Anthony Bonato | Jeannette Janssen
Algorithms and Models for the Web Graph
9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012, Proceedings
Book
06/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Table of Contents
- Hypergraph Coloring Games and Voter Models
- Introduction
- The Voting Game on a Hypergraph as a Random Walk on the Associated State Graph
- Memoryless Interactions and Semigroup Spectral Graph Theory
- The Cut-Off Time for Voter Interaction Games
- Estimating the Expected Value of a Given Event
- The Interaction Model with Partially Memoryless Interactions
- The General Interaction Model
- References
- Semigroup Details for Proving Theorem 3
- Proof of Theorem 5
- Proof of Theorem 7
- On a DAG Partitioning Problem
- Introduction
- The Hardness Result
- Linear-Time Algorithm for Bounded-Pathwidth Graphs
- Concluding Remarks
- References
- Some Typical Properties of the Spatial Preferred Attachment Model
- Introduction
- The SPA Model
- Directed Diameter
- Upper Bound
- Lower Bound
- Small Separators
- Emergence of Giant Component
- References
- A Sublinear Time Algorithm for PageRank Computations
- Introduction
- Identifying Nodes with Significant PageRanks: Our Results
- Matrix Sampling and Personalized PageRank Approximation
- Additional Related Work
- Organization
- Preliminaries
- Multi-scale Matrix Sampling and Approximation of PageRank
- Lower Bound Construction for PageRank Approximations
- Local Robust Computation of Personalized PageRank
- References
- Quick Detection of Nodes with Large Degrees
- Introduction
- Random Walk with Uniform Jumps
- Estimating the Largest Degrees in the Configuration Network Model
- Stopping Criteria
- Relaxation of Top k Lists
- Conclusions and Future Research
- References
- Ranking and Sparsifying a Connection Graph
- Introduction
- Preliminaries
- The Connection Laplacian
- The Consistency of a Connection Graph
- Random Walks on a Connection Graph
- PageRank Vectors in a Connection Graph
- The Connection Resistance
- Ranking Edges by Using the Connection Resistance
- References
- A Game-Theoretic Model of Attention in Social Networks
- Introduction
- Model
- Existence and Computability of Nash Equilibrium
- Analysis of the Price of Anarchy
- A Bicriteria Bound on the Price of Anarchy
- Simple Games with Unbounded Price of Anarchy
- Robust Analysis of the Price of Anarchy
- Discussion
- References
- On Certain Properties of Random Apollonian Networks
- Introduction
- Related Work
- Proof of Theorem 1
- Proof of Theorem 2
- Proof of Theorem 3
- Proof of Theorem 4
- Waiting Times
- Open Problems
- References
- Appendix
- Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links
- Introduction
- Preliminaries, Related Work and Problem Definition
- Dyadic Analysis and Mutuality Tendency
- Spectral Clustering Theory and Extensions to Digraphs via Symmetrization
- Cluster-Based Mutuality Tendency Theory
- Mutuality-Tendency-Aware Spectral Clustering Algorithm
- Evaluations
- References
- Dynamic PageRank Using Evolving Teleportation
- Introduction
- PageRank Notation
- Dynamic and Evolving Rankings
- PageRank with Dynamic Teleportation
- Algorithms
- Discussion of the Algorithm & Practical Issues
- Ranking from Time-Series
- Clustering the Time-Series
- Datasets
- Empirical Results
- Ranking from Time-Series
- Top Dynamic Ranks
- Predicting Future Pageviews & Tweets
- Conclusion
- References
- Multi-commodity Allocation for Dynamic Demands Using PageRank Vectors
- Introduction
- Preliminaries and the Demand Model
- PageRank and Kronecker PageRank
- Global Analysis: Supplying Every Vertex
- Local Analysis: Supplying a Small Subset
- An Example
- References
- Appendix
- Appendix
- Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs
- Introduction
- Results
- Theoretical Analysis
- Approximation by Many 2-State Markov Chains
- Verifying the Edge-By-Edge Convergence
- Tests with Real Graphs
- Conclusions
- References
- Fast Algorithm to Find All High Degree Vertices in Graphs with a Power Law Degree Sequence
- Introduction
- Properties of the Web-Graph Process
- Biassed Random Walks
- Proof of Theorems 1 and 2
- Experimental Results
- References
- Appendix
- Author Index
