Algorithms and Models for the Web Graph: 18th International Workshop, WAW 2023, Toronto, ON, Canada, May 23–26, 2023, Proceedings

Description

This book constitutes the proceedings of the 18th International Workshop on Algorithms and Models for the Web Graph, WAW 2023, held in Toronto, Canada, in May 23–26, 2023.The 12 Papers presented in this volume were carefully reviewed and selected from 21 submissions. The aim of the workshop was understanding of graphs that arise from the Web and various user activities on the Web, and stimulate the development of high-performance algorithms and applications that exploit these graphs. Preface Organization Contents Correcting for Granularity Bias in Modularity-Based Community Detection Methods 1 Introduction 2 Hyperspherical Geometry 3 The Heuristic 4 Derivation of the Heuristic 5 Experiments 6 Discussion References The Emergence of a Giant Component in One-Dimensional Inhomogeneous Networks with Long-Range Effects 1 Introduction and Statement of Result 1.1 The Weight-Dependent Random Connection Model 1.2 Main Result 1.3 Examples 2 Proof of the Main Theorem 2.1 Some Construction and Notation 2.2 Connecting Far Apart Vertex Sets 2.3 Existence of a Giant Component 2.4 Absence of an Infinite Component References Unsupervised Framework for Evaluating Structural Node Embeddings of Graphs 1 Introduction 2 Framework 2.1 Input/Output 2.2 Formal Description of the Algorithm 2.3 Properties 3 Experimentation 3.1 Synthetic Graphs Design 3.2 Algorithmic Properties of the Framework 3.3 Role Classification Case Study 4 Conclusion References Modularity Based Community Detection in Hypergraphs 1 Introduction 2 Modularity Functions 3 Hypergraph Modularity Optimization Algorithm 3.1 Louvain Algorithm 3.2 Challenges with Adjusting the Algorithm to Hypergraphs 3.3 Our Approach to Hypergraph Modularity Optimization: h-Louvain 4 Results 4.1 Synthetic Hypergraph Model: h-ABCD 4.2 Exhaustive Search for the Best Strategy 4.3 Comparing Basic Policies for Different Modularity Functions 5 Conclusions References Establishing Herd Immunity is Hard Even in Simple Geometric Networks 1 Introduction 2 Preliminaries 3 Unanimous Thresholds 4 Constant Thresholds 5 Majority Thresholds 6 Conclusions References Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix 1 Introduction 2 Related Work 3 Algorithm and Main Results 4 Numerical Illustrations 5 Analysis of the Algorithm 5.1 SDP Analysis 5.2 Upper Bound on 5.3 Lower Bound on Dii 5.4 Assortativity 5.5 Proof of Theorem 1 6 Conclusions References The Myth of the Robust-Yet-Fragile Nature of Scale-Free Networks: An Empirical Analysis 1 Introduction 2 Data 2.1 Network Collection 2.2 Network Categorization 2.3 Handling Weighted Networks 2.4 Preprocessing 3 Scale-Freeness Analysis 3.1 Scale-Freeness Classification Methods 3.2 Results 4 Robustness Analysis 4.1 Network Robustness 4.2 Configuration 4.3 Results 5 Conclusions 6 Appendix 6.1 Scale-Freeness Classification: Further Analysis 6.2 Robustness: Further Analysis 6.3 The Curious Case of Collins Yeast Interactome References A Random Graph Model for Clustering Graphs 1 Introduction 2 Preliminaries 3 Homomorphism Counts in the Chung-Lu Model 4 Random Clustering Graph Model 5 Homomorphism Counts 5.1 Extension Configurations 5.2 Expected Homomorphism Counts 5.3 Concentration of Subgraph Counts References Topological Analysis of Temporal Hypergraphs 1 Introduction 2 Method and Background 2.1 Temporal Hypergraphs 2.2 Sliding Windows for Hypergraph Snapshots 2.3 Associated ASC of a Hypergraph 2.4 Simplicial Homology 2.5 Zigzag Persistent Homology 3 Applications 3.1 Social Network Analysis 3.2 Cyber Data Analysis 4 Conclusion References PageRank Nibble on the Sparse Directed Stochastic Block Model 1 Introduction 2 Main Results 3 Proofs 4 Results from Simulations 5 Remarks and Conclusions References A Simple Model of Influence 1 Introduction 2 Analysis for Random Graphs G(n,m) 3 Proof of Lemma 1 4 The Effect of Stubborn Vertices 5 The Largest Fragment in G(n,m) References The Iterated Local Transitivity Model for Tournaments 1 Introduction 2 Small World Property 3 Motifs and Universality 4 Graph-Theoretic Properties of the Models 4.1 Hamiltonicity 4.2 Spectral Properties 4.3 Domination Numbers 5 Conclusion and Further Directions References Author Index