Updating dynamic random hyperbolic graphs in sublinear time

DOI10.1145/3195635MaRDI QIDQ4629530zbMATH OpenOpenAlexWikidataFDO

Authors Moritz von Looz, Henning Meyerhenke

Publication date 27 March 2019

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.03297

zbMATH Keywords

complex networksefficient range querygenerative graph modelhyperbolic geometrypolar quadtreerandom hyperbolic graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Elementary problems in hyperbolic and elliptic geometries (51M09) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. A complex network model gaining considerable popularity builds random hyperbolic graphs, generated by distributing points within a disk in the hyperbolic plane and then adding edges between points with a probability depending on their hyperbolic distance. We present a dynamic extension to model gradual network change, while preserving at each step the point position probabilities. To process the dynamic changes efficiently, we formalize the concept of a probabilistic neighborhood: Let $P$ be a set of $n$ points in Euclidean or hyperbolic space, $q$ a query point, $operatornamedist$ a distance metric, and $f:mathbb{R}^{+}ightarrow[0,1]$ a monotonically decreasing function. Then, the probabilistic neighborhood $N(q,f)$ of $q$ with respect to $f$ is a random subset of $P$ and each point $pinP$ belongs to $N(q,f)$ with probability $f(operatornamedist(p,q))$. We present a fast, sublinear-time query algorithm to sample probabilistic neighborhoods from planar point sets. For certain distributions of planar $P$, we prove that our algorithm answers a query in $O((|N(q,f)|+sqrtn)logn)$ time with high probability. This enables us to process a node movement in random hyperbolic graphs in sublinear time, resulting in a speedup of about one order of magnitude in practice compared to the fastest previous approach. Apart from that, our query algorithm is also applicable to Euclidean geometry, making it of independent interest for other sampling or probabilistic spreading scenarios.

Recommendations

• Generating Random Hyperbolic Graphs in Subquadratic Time
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Sampling geometric inhomogeneous random graphs in linear time
• Efficient embedding of scale-free graphs in the hyperbolic plane
• Querying probabilistic neighborhoods in spatial data sets efficiently

Cites work

• A Bound for the Diameter of Random Hyperbolic Graphs
• A Scalable Generative Graph Model with Community Structure
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Efficient embedding of scale-free graphs in the hyperbolic plane
• Foundations of multidimensional and metric data structures.
• Generating Random Hyperbolic Graphs in Subquadratic Time
• scientific article; zbMATH DE number 6303023 (Why is no real title available?)
• Nearest-neighbor searching under uncertainty. II
• Networks. An introduction.
• On the diameter of hyperbolic random graphs
• Probability and Computing
• Probability Inequalities for Sums of Bounded Random Variables
• Querying probabilistic neighborhoods in spatial data sets efficiently
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Sampling geometric inhomogeneous random graphs in linear time
• The probability of connectivity in a hyperbolic model of complex networks
• Tutorial on large deviations for the binomial distribution

Cited in

(2)

• Generating Random Hyperbolic Graphs in Subquadratic Time
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory

This page was built for publication: Updating dynamic random hyperbolic graphs in sublinear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629530)