Algorithms and Models for the Web-Graph
7th International Workshop, WAW 2010, Stanford, CA, USA, December 13-14, 2010, Proceedings
Published on 3. December 2010
VIII, 163 pages
978-3-642-18009-5 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Illustrations
VIII, 163 p. 30 illus., 16 illus. in color.
File size
3,38 MB
ISBN-13
978-3-642-18009-5 (9783642180095)
DOI
10.1007/978-3-642-18009-5
Schweitzer Classification
Other editions
Additional editions
Ravi Kumar | D. Sivakumar
Algorithms and Models for the Web-Graph
7th International Workshop, WAW 2010, Stanford, CA, USA, December 13-14, 2010, Proceedings
Book
01/2011
Springer
€53.49
Shipment within 5-7 days
Content
- Title
- Preface
- Organization
- Table of Contents
- The Anatomy of the Long Tail of Consumer Demand
- A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification
- Introduction
- A Sharp PageRank Approximation Algorithm
- The Green Values for Edges in a Graph
- Graph Sparsification Using Green Values
- Analyzing the Sparsifier
- Proof of Theorem 4
- Sparsification Using Approximate PageRank Vectors
- Graph Sparsification by Using Sharply Approximate Green Values
- Partitioning Using Approximate PageRank Vectors
- References
- Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
- Introduction
- Preliminaries
- Existing Work
- Concentration of Measure
- Random Projections
- Proposed Method
- Edge Sparsification
- Triple Sampling
- Hybrid Algorithm
- Experiments
- Experimental Setup and Implementation Details
- Results
- Remarks
- Theoretical Ramifications
- Random Projections and Triangles
- Sampling in the Semi-streaming Model
- Conclusions and Future Work
- References
- Computing an Aggregate Edge-Weight Function for Clustering Graphs with Multiple Edge Types
- Introduction
- Background
- Clustering in Graphs
- Comparing Two Clusterings
- Recovering a Graph Given a Ground Truth Clustering
- Solving an Inverse Problem
- Maximizing the Quality of Ground-Truth Clustering
- Solving the Optimization Problems
- Experimental Results
- Recovering Edge Weights
- Clustering Quality vs. Holding Vertices
- Inverse Problems vs. Maximizing Clustering Quality
- Runtime Scalability
- Conclusion and Future Work
- References
- Component Evolution in General Random Intersection Graphs
- Introduction
- Model and Previous Work
- Mathematical Preliminaries
- Auxiliary Process on General Random Intersection Graphs
- Process Description in Terms of Random Variable Yt
- Expectation and Variance of t
- Giant Component
- Subcritical Regime
- Supercritical Regime
- Conclusion
- References
- Modeling Traffic on the Web Graph
- Introduction
- Background
- Empirical Traffic Data
- ABC Model
- Model Evaluation
- Conclusions
- References
- Multiplicative Attribute Graph Model of Real-World Networks
- Introduction
- Formulation of the Multiplicative Attribute Graph Model
- The Number of Edges
- Connectivity
- Diameter
- Degree Distribution
- Extensions: Power-Law Degree Distribution
- References
- Random Walks on Digraphs, the Generalized Digraph Laplacian and the Degree of Asymmetry
- Introduction
- Preliminaries: Random Walks on Undirected Graphs
- Random Walk Theory on Digraphs
- Random Walks on Directed Graphs and Fundamental Matrix
- (Normalized) Digraph Laplacian and Green's Function for Digraphs
- Computing Hitting and Commute Times for Digraphs Using Digraph Laplacian
- Degree of Asymmetry, Generalized Cheeger Constant and Bounds on Mixing Rate
- The Degree of Asymmetry, and Relations to Symmetrized Digraph Laplacian
- Bounding the Mixing Rate of Random Walks on Digraphs
- References
- Finding and Visualizing Graph Clusters Using PageRank Optimization
- Introduction
- Preliminaries
- PageRank Variance and Cluster Variance Measures
- The PageRank-Clustering Algorithms
- Analyzing PageRank Clustering Algorithms
- A Graph Drawing Algorithm Using PageRank
- References
- Improving Random Walk Estimation Accuracy with Uniform Restarts
- Introduction
- Reducing Mixing Time by Restart
- Numerical Results
- Conclusions and Future Work
- References
- The Geometric Protean Model for On-Line Social Networks
- Introduction
- The GEO-P Model for OSNs
- Results and Dimension
- Dimension of OSNs
- Proofs of Results
- Degree Distribution
- Proof of Theorem 1
- Bad Expansion: Proof of Theorem 4
- Diameter
- Proof of Theorem 3
- Conclusion and Discussion
- References
- Constant Price of Anarchy in Network Creation Games via Public Service Advertising
- Introduction
- A Tight Upper Bound for Price of Anarchy in Uniform Games
- How the Public Service Advertising Affects the Price of Anarchy
- How to Deal with Unknown and
- References
- Fast Katz and Commuters: Efficient Estimation of Social Relatedness in Large Networks
- Introduction
- Related Work
- Algorithms for Pairwise Score
- Top-k Algorithms
- Empirical Evaluation
- Conclusions and Future Work
- References
- Game-Theoretic Models of Information Overload in Social Networks
- Introduction
- Modeling the Resulting Networks
- Our Models
- Our Results
- Related Work
- Empirical Evidence
- A Model of Friendship Selection: The Followership Game
- A Specific Utility Model
- Greedy Users
- Matchings Characterize Pure Rate Equilibria
- A Model of User Engagement: The Engagement Game
- Pure Equilibria under Sparse or Regular Users
- Conclusions
- References
- Author Index
