5 papers
Geometric Routing in Geometric Inhomogeneous Random Graphs
Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis +1
We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol…
Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi +1
This paper presents gossip algorithms for aggregation tasks that demonstrate both robustness to adversarial corruptions of any order of magnitude and optimality across a substantia…
Assortativity in geometric and scale-free networks
Marc Kaufmann, Ulysse Schaller, Thomas Bläsius +1
The assortative behavior of a network is the tendency of similar (or dissimilar) nodes to connect to each other. This tendency can have an influence on various properties of the ne…
Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models
Marc Kaufmann, Kostas Lakis, Johannes Lengler +3
We study push-pull rumour spreading in ultra-small-world models for social networks where the degrees follow a power-law distribution. In a non-geometric setting, Fountoulakis, Pan…
Expanders in Models of Social Networks
Marc Kaufmann, Johannes Lengler, Ulysse Schaller +1
A common model for social networks are Geometric Inhomogeneous Random Graphs (GIRGs), in which vertices draw a random position in some latent geometric space, and the probability o…