Load balancing in hypergraphs

DOI10.1007/S10955-018-1977-1zbMATH Open1403.60015arXiv1710.00308OpenAlexW2761797504MaRDI QIDQ1633962FDOQ1633962

Authors: Payam Delgosha, Venkat Anantharam 

Publication date: 21 December 2018

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

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).

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

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
• Balanced allocation on graphs: a random walk approach

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)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Stochastic orders
• Balanced loads in infinite networks
• Processes on unimodular random networks
• The densest subgraph problem in sparse random graphs
• Performance of global load balancing by local adjustment
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Information Theory
• Title not available (Why is that?)
• Gibbs measures and phase transitions on sparse random graphs
• An introduction to measure theory

Cited In (8)

• Community detection in the sparse hypergraph stochastic block model
• Balanced allocation on hypergraphs
• Distributed Weight Balancing Over Digraphs
• Load balancing by graph coloring, an algorithm
• Title not available (Why is that?)
• Load balancing for Markov chains with a specified directed graph
• Balanced loads in infinite networks
• Normal approximation for statistics of randomly weighted complexes

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)