Resource allocation in sparsely connected networks
– Resource allocation in sparsely connected networks, a representative problem of systems with real variables, is studied using the replica and Bethe approximation methods. An efficient distributed algorithm is devised on the basis of insights gained from the analysis and is examined using numerical simulations, showing excellent performance and full agreement with the theoretical results. The physical properties of the resource allocation model are discussed. Many theoretically challenging and practically important problems involve interacting variables connected by network structures [1]. Statistical mechanics of disordered systems makes contributions towards the understanding of such systems at two levels. Macroscopically, it describes the typical behaviour of the networks, using established techniques such as the replica method. Microscopically, it analyses the relation between the variables, using techniques such as the cavity method, that give rise to efficient computational algorithms. Most of the studies carried out and approximations suggested so far have focused on cases of discrete variables. In this letter we study a system with real variables that can be mapped onto a sparse graph and suggest an efficient message passing approximation method. The system we use here as a prototype for this inference problem, termed resource allocation, is well known in the areas of computer science and operations management [2,3]. The problem itself is quite general and is applicable to typical situations where a large number of nodes are required to balance loads/resources, such as reducing internet traffic congestion and streamlining network flows of commodities [4]. In computer science, many practical solutions currently are employed to distribute computational load between computers connected in a network. They are usually heuristic and focus on practical aspects (e.g., communication protocols). The problem we are addressing here is more generic and, in the context of computer networks, is represented by nodes of some computational power that should carry out tasks. Both computational powers and tasks will be chosen at random from some arbitrary distribution. The nodes are located on a randomly chosen sparse network of some connectivity. The goal is to migrate tasks on the network such that demands will be satisfied while the migration of (sub-)tasks is minimised. We focus here on the satisfiable case where the total computing c © EDP Sciences 2 EUROPHYSICS LETTERS power is greater than the demand, and where the number of nodes involved is very large. This is of interest to physicists due to the applicability of the techniques we introduce to the analysis of sparsely connected systems with real variables. We consider a typical resource allocation task on a sparse network with N nodes, labelled i=1, . . . , N . Each node i is randomly connected to c other nodes, and has a capacity (computational capability minus allocated tasks) Λi randomly drawn from a distribution ρ(Λi). (The algorithms presented later can easily accommodate any connectivity profile within the same framework.) The current yij ≡ −yji drawn from node j to i is aimed at satisfying the capacity constraints ∑ j Aijyij + Λi ≥ 0, representing the ‘revised’ assignment for node i, where Aij = 1/0 for connected/unconnected node pairs i and j, respectively. We consider the load balancing task of minimizing the energy function (cost) E = ∑ (ij)Aijφ(yij), where the summation (ij) is over all node pairs, subject to the capacity constraints, and φ(y) is a general even function of the current y. To illustrate the replica approach, it is convenient to introduce the chemical potentials μi of nodes i, and approximate the current yij as driven by the potential differences between nodes yij = μj − μi. Since sparse networks are locally tree-like, the probability of finding short loops is vanishing in large networks, and we expect the approximation to work well. We focus here on the optimization problem in the space of chemical potentials. Since the energy function is invariant under the addition of an arbitrary global constant to all chemical potentials, we introduce a regularization term ǫ ∑ i μ 2 i /2 to break the translational symmetry, where ǫ→0. The replicated partition function [1], for a temperature T ≡ β, averaged over all network configurations of connectivity c and capacity distributions ρ(Λi), becomes 〈Z〉A,Λ = 1 N ∑