Algorithms and Models for the Web Graph : 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings / / edited by David F. Gleich, Júlia Komjáthy, Nelly Litvak

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
• Edizione: 1st ed. 2015.
• Descrizione fisica: 1 online resource (VIII, 203 p. 17 illus. in color.)
• Disciplina: 005.1
• Soggetto topico: Algorithms; Computer science—Mathematics; Discrete mathematics; Data mining; Information storage and retrieval systems; Application software; Computer networks; Discrete Mathematics in Computer Science; Data Mining and Knowledge Discovery; Information Storage and Retrieval; Computer and Information Systems Applications; Computer Communication Networks
• Persona (resp. second.): GleichDavid F; KomjáthyJúlia; LitvakNelly
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: 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.
• Sommario/riassunto: This book constitutes the proceedings of the 12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015, held in Eindhoven, The Netherlands, in December 2015. The 15 full papers presented in this volume were carefully reviewed and selected from 24 submissions. They are organized in topical sections named: properties of large graph models, dynamic processes on large graphs, and properties of PageRank on large graphs.
• Titolo autorizzato: Algorithms and Models for the Web-Graph
• ISBN: 3-319-26784-1
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910483242503321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 9479