
Algorithms and Models for the Web-Graph
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

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
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.