A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count on-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigen valus of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption conjecture" that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.

We show that several important resource allocation problems in wireless networks fit within the common framework of constraint satisfaction problems (CSPs). Inspired by the requirements of these applications, where variables are located at distinct network devices that may not be able to communicate but may interfere, we define natural criteria that a CSP solver must possess in order to be practical. We term these algorithms decentralized CSP solvers. The best known CSP solvers were designed for centralized problems and do not meet these criteria. We introduce a stochastic decentralized CSP solver, proving that it will find a solution in almost surely finite time, should one exist, and also showing it has many practically desirable properties. We benchmark the algorithm's performance on a well-studied class of CSPs, random k-SAT, illustrating that the time the algorithm takes to find a satisfying assignment is competitive with stochastic centralized solvers on problems with order a thousand variables despite its decentralized nature. We demonstrate the solver's practical utility for the problems that motivated its introduction by using it to find a noninterfering channel allocation for a network formed from data from downtown Manhattan.

Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determining a minimum cost route that allows the vehicle to satisfy every supply and demand. This article investigates the preemptive version of the SP in which the objects are allowed to be dropped at temporary locations along the route. The problem is modeled as a mixed integer linear program which is solved by branch‐and‐cut. Computational results on random geometric instances containing up to 100 vertices and eight object types are reported. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

We analyze the stability of standard, buffered, slotted-Aloha systems. Specifically, we consider a set of$N$users, each equipped with an infinite buffer. Packets arrive into user$i$'s buffer according to some stationary ergodic Markovian process of intensity$\lambda_{i}$. At the beginning of each slot, if user$i$has packets in its buffer, it attempts to transmit a packet with fixed probability$p_{i}$over a shared resource/channel. The transmission is successful only when no other user attempts to use the channel. The stability of such systems has been open since their very first analysis in 1979 by Tsybakov and Mikhailov. In this paper, we propose an approximate stability condition that is provably exact when the number of users$N$grows large. We provide theoretical evidence and numerical experiments to explain why the proposed approximate stability condition is extremely accurate even for systems with a restricted number of users (even two or three).

We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs converging locally to a tree, we give new formulas for the asymptotic of the multiplicity of the eigenvalue 0. In particular, the result depends only on the limiting tree structure, showing that the normalized rank is ‘continuous at infinity'. Our work also gives a new formula for the mass at zero of the spectral measure of a Galton-Watson tree. Our techniques of proofs borrow ideas from analysis of algorithms, random matrix theory, statistical physics and analysis of Schrödinger operators on trees.

A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over $A\subseteq\{1,2,\ldots,n\}$, the objective function $|A|-\sum_i\xi_i{\rm1\hspace{-0.90ex}1}(i\in A,i+1\in A)$ for given $\xi_i>0$. This problem, with random $(\xi_i)$, provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions differing from the optimal solution in a small proportion $\delta$ of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order $\delta^2$ but not of smaller order. We conjecture this relationship holds widely in the context of dynamic programming over random data, and Monte Carlo simulations for the Kauffman–Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in [D. J. Aldous and A. G. Percus, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 11211–11215] of relating such scaling exponents to the algorithmic difficulty of optimization problems.

Random Medium-Access-Control (MAC) algorithms have played an increasingly important role in the development of wired and wireless Local Area Networks (LANs) and yet the performance of even the simplest of these algorithms, such as slotted-Aloha, are still not clearly understood. In this paper we provide a general and accurate method to analyze networks where interfering users share a resource using random MAC algorithms. We show that this method is asymptotically exact when the number of users grows large, and explain why it also provides extremely accurate performance estimates even for small systems. We apply this analysis to solve two open problems: (a) We address the stability region of non-adaptive Aloha-like systems. Specifically, we consider a fixed number of buffered users receiving packets from independent exogenous processes and accessing the resource using Aloha-like algorithms. We provide an explicit expression to approximate the stability region of this system, and prove its accuracy. (b) We outline how to apply the analysis to predict the performance of adaptive MAC algorithms, such as the exponential back-off algorithm, in a system where saturated users interact through interference. In general, our analysis may be used to quantify how far from optimality the simple MAC algorithms used in LANs today are, and to determine if more complicated (e.g. queue-based) algorithms proposed in the literature could provide significant improvement in performance.

We study the capacity of multiple-access networks both on uplink and downlink. In our model each user requires a given signal-to-interference-plus-noise ratio (SINR) and the capacity region is obtained as a solution of a power allocation problem. In this paper, we emphasize the differences between uplink and downlink. The mathematical analysis of the capacity region is given in the framework of ergodic point processes and we show the links between the geometry of the network and its capacity region. On the downlink, we pay attention to various network architectures and levels of cooperation between base stations: macrodiversity, load balancing, and traditional cellular networks