Load balancing in hypergraphs

DOI10.1007/S10955-018-1977-1MaRDI QIDQ1633962zbMATH OpenOpenAlexFDO

Authors Payam Delgosha, Venkat Anantharam

Publication date 21 December 2018

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphsload balancinglocal weak convergenceobjective methodunimodularityconfiguration modelsparse graph limits

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Information theory (general) (94A15) Combinatorial probability (60C05) Hypergraphs (05C65) Phase transitions (general) in equilibrium statistical mechanics (82B26) Stochastic network models in operations research (90B15)

Abstract: Consider a simple locally finite hypergraph on a countable vertex set, where each edge represents one unit of load which should be distributed among the vertices defining the edge. An allocation of load is called balanced if load cannot be moved from a vertex to another that is carrying less load. We analyze the properties of balanced allocations of load. We extend the concept of balancedness from finite hypergraphs to their local weak limits in the sense of Benjamini and Schramm (2001) and Aldous and Steele (2004). To do this, we define a notion of unimodularity for hypergraphs which could be considered an extension of unimodularity in graphs. We give a variational formula for the balanced load distribution and, in particular, we characterize it in the special case of unimodular hypergraph Galton Watson processes. Moreover, we prove the convergence of the maximum load under some conditions. Our work is an extension to hypergraphs of Anantharam and Salez (2016), which considered load balancing in graphs, and is aimed at more comprehensively resolving conjectures of Hajek (1990).

Recommendations

• Load balancing and orientability thresholds for random hypergraphs
• Balanced loads in infinite networks
• Graphical balanced allocations and the \((1+\beta )\)-choice process
• Perfectly balanced allocation

Cites work

• scientific article; zbMATH DE number 3426516 (Why is no real title available?)
• scientific article; zbMATH DE number 5544150 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1461253 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• An introduction to measure theory
• Balanced loads in infinite networks
• Gibbs measures and phase transitions on sparse random graphs
• Information Theory
• Performance of global load balancing by local adjustment
• Processes on unimodular random networks
• Recurrence of distributional limits of finite planar graphs
• Stochastic orders
• The densest subgraph problem in sparse random graphs

Cited in

(8)

• Community detection in the sparse hypergraph stochastic block model
• Normal approximation for statistics of randomly weighted complexes
• scientific article; zbMATH DE number 975375 (Why is no real title available?)
• Load balancing by graph coloring, an algorithm
• Load balancing for Markov chains with a specified directed graph
• Balanced allocation on hypergraphs
• Balanced loads in infinite networks
• Distributed Weight Balancing Over Digraphs

This page was built for publication: Load balancing in hypergraphs

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