LEADER 08999nam 22008895 450 001 9910483242503321 005 20251226202717.0 010 $a3-319-26784-1 024 7 $a10.1007/978-3-319-26784-5 035 $a(CKB)4340000000001220 035 $a(SSID)ssj0001599524 035 $a(PQKBManifestationID)16306137 035 $a(PQKBTitleCode)TC0001599524 035 $a(PQKBWorkID)14892358 035 $a(PQKB)10735127 035 $a(DE-He213)978-3-319-26784-5 035 $a(MiAaPQ)EBC6303209 035 $a(MiAaPQ)EBC5588069 035 $a(Au-PeEL)EBL5588069 035 $a(OCoLC)933755428 035 $a(PPN)190884665 035 $a(EXLCZ)994340000000001220 100 $a20151208d2015 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms and Models for the Web Graph $e12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings /$fedited by David F. Gleich, Júlia Komjáthy, Nelly Litvak 205 $a1st ed. 2015. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2015. 215 $a1 online resource (VIII, 203 p. 17 illus. in color.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9479 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-319-26783-3 327 $aIntro -- 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. 327 $a3 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. 327 $aPageRank 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. 330 $aThis 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. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9479 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aData mining 606 $aInformation storage and retrieval systems 606 $aApplication software 606 $aComputer networks 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aData Mining and Knowledge Discovery 606 $aInformation Storage and Retrieval 606 $aComputer and Information Systems Applications 606 $aComputer Communication Networks 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aData mining. 615 0$aInformation storage and retrieval systems. 615 0$aApplication software. 615 0$aComputer networks. 615 14$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aData Mining and Knowledge Discovery. 615 24$aInformation Storage and Retrieval. 615 24$aComputer and Information Systems Applications. 615 24$aComputer Communication Networks. 676 $a005.1 702 $aGleich$b David F$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aKomjáthy$b Júlia$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aLitvak$b Nelly$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483242503321 996 $aAlgorithms and Models for the Web-Graph$9772606 997 $aUNINA