Algorithms and Models for the Web Graph: 16th International Workshop, WAW 2019, Brisbane, QLD, Australia, July 6–7, 2019, Proceedings (Lecture Notes in Computer Science Book 11631)

This book constitutes the proceedings of the 16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019, held in Brisbane, QLD, Australia, in July 2019. The 9 full papers presented in this volume were carefully reviewed and selected from 13 submissions. The papers cover topics of all aspects of algorithmic and mathematical research in the areas pertaining to the World Wide Web, espousing the view of complex data as networks. Preface 6 Organization 7 Contents 9 Using Synthetic Networks for Parameter Tuning in Community Detection 10 1 Introduction 10 2 Background and Related Work 11 2.1 Modularity 11 2.2 Modularity Optimization and Louvain Algorithm 12 2.3 Likelihood Optimization Methods 12 2.4 LFR Model 13 3 Tuning Parameters 13 4 Experiments 16 4.1 Parametric Algorithms 16 4.2 Datasets 17 4.3 Evaluation Metrics 17 4.4 Experimental Setup 18 4.5 Results 18 5 Conclusion 23 References 23 Efficiency of Transformations of Proximity Measures for Graph Clustering 25 1 Introduction 25 2 Related Work 26 3 Preliminaries 27 3.1 Definitions 27 3.2 Kernels 27 3.3 Transformations 27 4 Experiments and Results 28 4.1 Experimental Methodology 28 4.2 Analysis 29 4.3 Examining the Results by Friedman and Nemenyi Tests 31 5 Conclusion 35 References 37 Almost Exact Recovery in Label Spreading 39 1 Introduction and Previous Work 39 2 Semi-supervised Graph Clustering with the Normalized Laplacian Matrix (Label Spreading) 40 3 Analysis on Random SBM Graphs 42 3.1 Exact Expression for Mean Field SBM 43 3.2 Concentration Towards Mean Field 45 3.3 Asymptotically Almost Exact Recovery for SBM 47 4 Discussion and Future Works 47 A Background Results on Matrix Analysis 48 A.1 Inversion of the Identity Matrix Minus a Rank 2 Matrix 48 A.2 Spectral Study of a Rank 2 Matrix 49 A.3 Spectral Study of EL 51 B Spectral Norm of an Extracted Matrix 51 References 52 Strongly n-e.c. Graphs and Independent Distinguishing Labellings 53 1 Introduction 53 2 Constructing Infinite Graphs by (n)-extensions 56 3 Constructing Infinite Graphs by (n)-extensions 58 4 An Application of the Strong e.c. Property to Graph Distinguishing 61 5 Conclusion 63 References 64 The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs 66 1 Introduction 66 2 Erdős-Rényi Random Graph 67 3 Complete k-Partite Graphs 75 3.1 Results 75 3.2 Proofs 75 References 79 Estimating the Parameters of the Waxman Random Graph 80 1 Introduction 80 2 Background and Related Work 81 3 General Properties of Waxman Graphs 83 4 Estimation Techniques 85 4.1 Log-Linear Regression 85 4.2 Generalised Linear Model (GLM) 85 4.3 Sufficient Statistics 86 4.4 Maximum Likelihood Estimator 87 4.5 Existence and Uniqueness of the MLE 87 4.6 The MLE of 88 4.7 Numerical Calculation of the MLE 88 5 Performance 89 5.1 Comparisons 89 5.2 Estimating q 91 6 Case Study 92 7 Discussion and Conclusion 93 References 94 Understanding the Effectiveness of Data Reduction in Public Transportation Networks 96 1 Introduction 96 2 Preliminary Considerations 97 2.1 Graph-Theoretic Perspective 98 2.2 Hitting Set Perspective 99 3 Analysis of Real-World Networks 100 4 Analysis of Generated Instances 102 4.1 The Generative Model 103 4.2 Evaluation 104 5 Impact on Other Domains 108 6 Conclusion 109 References 110 A Spatial Small-World Graph Arising from Activity-Based Reinforcement 111 1 Introduction 111 2 Model and Results 114 3 Proofs 116 3.1 Lower Bound 116 3.2 Theorem2; a3 117 3.3 Theorem2; a< 3 120 References 123 SimpleHypergraphs.jl—Novel Software Framework for Modelling and Analysis of Hypergraphs 124 1 Introduction 124 2 Modelling and Hypergraphs with SimpleHypergraphs.jl 125 2.1 Motivation 125 2.2 Definitions and Notation 127 2.3 Library Design and Functionalities 128 2.4 Hypergraph Modularity 129 3 Use Case—Yelp Dataset 130 3.1 The Yelp Open Dataset 130 3.2 The Yelp Hypergraph 131 3.3 Results 132 4 Conclusion 137 References 137 Author Index 139 Front Matter ....Pages i-ix Using Synthetic Networks for Parameter Tuning in Community Detection (Liudmila Prokhorenkova)....Pages 1-15 Efficiency of Transformations of Proximity Measures for Graph Clustering (Rinat Aynulin)....Pages 16-29 Almost Exact Recovery in Label Spreading (Konstantin Avrachenkov, Maximilien Dreveton)....Pages 30-43 Strongly n-e.c. Graphs and Independent Distinguishing Labellings (Christopher Duffy, Jeannette Janssen)....Pages 44-56 The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs (A. Davidson, A. Ganesh)....Pages 57-70 Estimating the Parameters of the Waxman Random Graph (Matthew Roughan, Jonathan Tuke, Eric Parsonage)....Pages 71-86 Understanding the Effectiveness of Data Reduction in Public Transportation Networks (Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Martin Schirneck)....Pages 87-101 A Spatial Small-World Graph Arising from Activity-Based Reinforcement (Markus Heydenreich, Christian Hirsch)....Pages 102-114 SimpleHypergraphs.jl—Novel Software Framework for Modelling and Analysis of Hypergraphs (Alessia Antelmi, Gennaro Cordasco, Bogumił Kamiński, Paweł Prałat, Vittorio Scarano, Carmine Spagnuolo et al.)....Pages 115-129 Back Matter ....Pages 131-131