Algorithms and Models for the Web Graph

Name: Algorithms and Models for the Web Graph | 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings
Brand: Springer
Price: 50.28 EUR
Availability: OnlineOnly

12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings

David F. Gleich Júlia Komjáthy Nelly Litvak(Herausgeber*in)

Springer (Verlag)

Erschienen am 8. Dezember 2015

VIII, 203 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-26784-5 (ISBN)

50,28 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Contents
Properties of Large Graph Models
Robustness of Spatial Preferential Attachment Networks
1 Introduction
2 The Model
3 Statement of the Result
4 Proof Ideas and Strategies
4.1 Robustness: Strategy of Proof
4.2 Non-robustness: Strategy of Proof
References
Local Clustering Coefficient in Generalized Preferential Attachment Models
1 Introduction
2 Generalized Preferential Attachment
2.1 Definition of the PA-class
2.2 Power Law Degree Distribution
2.3 Clustering Coefficient
3 The Average Local Clustering for the Vertices of Degree d
4 Proofs
4.1 Proof of Theorem ??
4.2 Proof of Theorem ??
5 Conclusion
References
Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs
1 Introduction
2 Preliminaries
2.1 Random Intersection Graphs
2.2 Degeneracy and Expansion
2.3 Gromov's Hyperbolicity
3 Structural Sparsity of Random Intersection Graphs
3.1 Bounded Attribute-Degrees
3.2 Alternative Characterization of Bounded Expansion
3.3 Stable r-Subdivisions
3.4 Density
3.5 Main Result
4 Hyperbolicity
5 Conclusion and Open Problems
References
Degree-Degree Distribution in a Power Law Random Intersection Graph with Clustering
1 Introduction
2 Proofs
References
Upper Bounds for Number of Removed Edges in the Erased Configuration Model
1 Introduction
2 Erased Configuration Model
3 Main Result
4 Upper Bounds for Erased Edges
4.1 The Upper Bounds OP (n4 - 3) and OP (n-1)
4.2 The Upper Bound OP (n1 - 1)
5 Discussion
References
The Impact of Degree Variability on Connectivity Properties of Large Networks
1 Introduction
2 The Branching Functional of the Configuration Model
2.1 Size Biasing and Downshifting
2.2 Branching Functional of the Configuration Model
3 Ordering of Branching Processes
3.1 Strong and Convex Stochastic Orders
3.2 Stochastic Ordering and Branching Processes
4 Stochastic Ordering of the Configuration Model
4.1 A Counterexample
4.2 A Monotonicity Result When One Extinction Probability is Small
4.3 Application to Social Network Modeling
5 Conclusions
References
Navigability is a Robust Property
1 Introduction
1.1 Related Work
2 Our Contribution
2.1 Geometric Requirements and a Unifying Framework for RBA
2.2 Navigability from Organic Growth
2.3 Navigability as a Reflection of the Cost of Indexing
3 Navigability via Reducibility and Uniform Richness
4 Analyzing the Set of All Feasible Graphs
References
Dynamic Processes on Large Graphs
Local Majority Dynamics on Preferential Attachment Graphs
1 Introduction
2 Preferential Attachment Graphs
3 Results and Related Work
4 Structural Results
5 Convergence of the Majority Dynamics
6 Conclusion and Open Problems
References
Rumours Spread Slowly in a Small World Spatial Network
1 Introduction
1.1 The SPA Model
1.2 Rumour Spreading
1.3 Main Results
2 The Effective Diameter of SPA Model Graphs
3 Lower Bounds for Rumour Spreading
References
A Note on Modeling Retweet Cascades on Twitter
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Evaluating the SIR Model on the Twitter Network
2.1 Defining the Null Hypothesis
2.2 Refuting the SIR Model
3 An Interest Based Model for Tweet Propagation
4 Conclusion
References
The Robot Crawler Number of a Graph
1 Introduction
2 The Robot Crawler Process: Definition and Properties
3 Binomial Random Graphs
4 Preferential Attachment Model
5 Conclusion and Open Problems
References
Properties of PageRank on Large Graphs
PageRank in Undirected Random Graphs
1 Introduction
2 Definitions
3 Convergence in Total Variation
4 Chung-Lu Random Graphs
4.1 Chung-Lu Random Graph Model
4.2 Element-Wise Convergence
5 Experimental Results
6 Conclusions
References
Bidirectional PageRank Estimation: From Average-Case to Worst-Case
1 Introduction
1.1 Our Contribution
1.2 Existing Approaches for PageRank Estimation
2 PageRank Estimation in Undirected Graphs
2.1 Preliminaries
2.2 A Symmetry for PPR in Undirected Graphs
2.3 The Undirected-BiPPR Algorithm
2.4 Analyzing the Performance of Undirected-BiPPR
3 Extension to Graph Diffusions
4 Conclusion
References
Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank
1 Introduction
1.1 Related Work
2 The Setting and Our Contributions
2.1 Models of Computation
2.2 Local Clusters and Heat Kernel Pagerank
2.3 Our Results
3 Fast Distributed Heat Kernel Pagerank Computation
4 Distributed Local Cluster Detection
5 Computing Local Clusters in the k-machine Model
References
Strong Localization in Personalized PageRank Vectors
1 Introduction
1.1 Related Work on Weak Localization
1.2 Related Work on Functions of Matrices and Diffusions
2 A Negative Result for Strong Localization
3 Localization in Personalized PageRank
3.1 Our Class of Skewed Degree Sequences
3.2 Deriving the Bound
3.3 Using the degree sequence
4 Experiments
4.1 Generating the Graphs
4.2 Measuring the Non-zeros
4.3 Testing the Theoretical Bound
4.4 Empirical Non-zero Analysis
4.5 Results
5 Discussion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken