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

✍ Scribed by Megan Dewar, Paweł Prałat, Przemysław Szufel, François Théberge, Małgorzata Wrzosek

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 203
• Series: Lecture Notes in Computer Science, 13894
• Category: Library

✦ Table of Contents

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