Algorithms and Models for the Web Graph

Name: Algorithms and Models for the Web Graph | 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012, Proceedings

Anthony Bonato Jeannette Janssen(Herausgeber*in)

Springer (Verlag)

Erschienen am 19. Juni 2012

VIII, 179 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-30541-2 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken