Sublinear Cuts are the Exception in BDF-GIRGs
METADATA ONLY
Loading...
Author / Creator
Date
2025
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The introduction of geometry has proven instrumental in the efforts towards more realistic models for real-world networks. In Geometric Inhomogeneous Random Graphs (GIRGs), Euclidean Geometry induces clustering of the vertices, which is widely observed in networks in the wild. Euclidean Geometry in multiple dimensions however restricts proximity of vertices to those cases where vertices are close in each coordinate. We introduce a large class of GIRG extensions, called BDF-GIRGs, which capture arbitrary hierarchies of the coordinates within the distance function of the vertex feature space. These distance functions have the potential to allow more realistic modeling of the complex formation of social ties in real-world networks, where similarities between people lead to connections. Here, similarity with respect to certain features, such as familial kinship or a shared workplace, suffices for the formation of ties. It is known that - while many key properties of GIRGs, such as log-log average distance and sparsity, are independent of the distance function - the Euclidean metric induces small separators, i.e. sublinear cuts of the unique giant component in GIRGs, whereas no such sublinear separators exist under the component-wise minimum distance. Building on work of Lengler and Todorović, we give a complete classification for the existence of small separators in BDF-GIRGs. We further show that BDF-GIRGs all fulfill a stochastic triangle inequality and thus also exhibit clustering.
Permanent link
Publication status
published
External links
Book title
Complex Networks & Their Applications XIII
Journal / series
Studies in Computational Intelligence
Volume
1189
Pages / Article No.
366 - 377
Publisher
Springer
Event
13th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2024)
Edition / version
Methods
Geographic location
Date collected
Date created
Subject
Social and Information Networks (cs.SI); Combinatorics (math.CO); Metric Geometry (math.MG); FOS: Computer and information sciences; FOS: Mathematics
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)
08738 - Lengler, Johannes (Tit.-Prof.) / Lengler, Johannes (Tit.-Prof.)
Notes
Funding Info about funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2405.19369