Search

This thesis studies random walks and its algorithmic applications in distributed networks. Random walk is a fundamental technique which has found numerous applications in computer science, mathematics, statistics, physics, and among others. The simulation of random walks in a network is an important tool, with a lot of applications in algorithms and complexity theory. In particular, in communication networks, random walks have been used in various applications including token management, load balancing, network topology discovery and construction, search, and peer-to-peer membership management, local and lightweight algorithms for dynamic networks etc. While several such algorithms are ubiquitous, and use random walk sampling, the walks themselves have always been performed in a naive way --- simply passing the random walk token from one node to its neighbor. Thus, to perform a random walk of length $\ell$, the naive approach requires $\ell$ steps. Therefore, a natural question is whether a better algorithm is possible in the distributed model. In this thesis, we focus on two main questions: (1) How efficiently random walks can be performed in distributed networks? (2) How random walks can be used in designing efficient distributed algorithms for important distributed computing problems? Towards the first question, the thesis studies efficient distributed random walk sampling in networks, where we focus on both static and dynamic networks. For static networks, we present a round and message optimal algorithm which can be used to output several random walk samples in a continuous online fashion. This significantly improves upon both the naive technique that requires linear time and messages, and the sophisticated algorithm presented by Das Sarma et al. \cite{drw-jacm} which has the same sub-linear (quadratic) running time as our algorithm, but requires a large number of messages (depending on the number of edges in the network). Moreover, we perform a comprehensive experimental evaluation on numerous network topologies which proves the effectiveness and efficiency of our algorithm. For dynamic networks, we present a fast distributed algorithm for performing random walks. Our algorithm is the first-known algorithm that provably speeds up random walks in dynamic networks. Furthermore, we show a key application of this random walk algorithm for the fundamental problem of information spreading (a.k.a gossip) in dynamic networks. We use our random walk algorithm to obtain a fast distributed information spreading algorithm. Towards the second question, we study two important algorithmic applications: (1) Distributed computation of PageRank (2) Distributed computation of sparse cuts. PageRank has emerged as a powerful measure of relative importance of nodes in a network. In distributed computing, PageRank vectors have been used for several different applications ranging from determining important nodes, load balancing, search, and identifying connectivity structures. We devise random walk-based algorithms for computing PageRank and prove strong bounds on the round complexity. Our algorithms are the first and fully distributed algorithms for computing PageRank with provably efficient running time. Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the Internet and Peer-to-Peer networks, as well as large-scale graphs such as the web graph, online social communities, and VLSI circuits. Sparse cuts are particularly useful in graph clustering and partitioning. We develop fast distributed algorithms for computing sparse cuts in distributed networks, where random walks are used as a key ingredient. DOCTOR OF PHILOSOPHY (SPMS)

State space methods have proved to be powerful theoretical and computational tools in a number of areas of applications, in particular filtering and control theory. In this paper we advocate the use of state space methods for the study of discrete probability densities on the set {0,1,2,…}. The fundamental approach is to consider the class D of all discrete probability densities that can be represented as the impulse response/convolution kernel of a finite dimensional discrete time state space system. We show that all standard operations such as the calculation of moments, convolution, scaling, translation, product, etc. can be carried out using system representations.

This paper proposes a general formalism for representation, inference and learning with general hybrid Bayesian networks in which continuous and discrete variables may appear anywhere in a directed acyclic graph. The formalism fuzzifies a hybrid Bayesian network into two alternative forms: the first form replaces each continuous variable in the given directed acyclic graph (DAG) by a partner discrete variable and adds a directed link from the partner discrete variable to the continuous one. The mapping between two variables is not crisp quantization but is approximated (fuzzified) by a conditional Gaussian (CG) distribution. The CG model is equivalent to a fuzzy set but no fuzzy logic formalism is employed. The conditional distribution of a discrete variable given its discrete parents is still assumed to be multinomial as in discrete Bayesian networks. The second form only replaces each continuous variable whose descendants include discrete variables by a partner discrete variable and adds a directed link from that partner discrete variable to the continuous one. The dependence between the partner discrete variable and the original continuous variable is approximated by a CG distribution, but the dependence between a continuous variable and its continuous and discrete parents is approximated by a conditional Gaussian regression (CGR) distribution. Obviously, the second form is a finer approximation, but restricted to CGR models, and requires more complicated inference and learning algorithms. This results in two general approximate representations of a general hybrid Bayesian networks, which are called here the fuzzy Bayesian network (FBN) form-I and form-II. For the two forms of FBN, general exact inference algorithms exists, which are extensions of the junction tree inference algorithm for discrete Bayesian networks. Learning fuzzy Bayesian networks from data is different from learning purely discrete Bayesian networks because not only all the newly converted discrete variables are latent in the data, but also the number of discrete states for each of these variables and the CG or CGR distribution of each continuous variable given its partner discrete parents or both continuous and discrete parents have to be determined.

In this paper we propose a distributed algorithm for the estimation and control of the connectivity of ad-hoc networks in the presence of a random topology. First, given a generic random graph, we introduce a novel stochastic power iteration method that allows each node to estimate and track the algebraic connectivity of the underlying expected graph. Using results from stochastic approximation theory, we prove that the proposed method converges almost surely (a.s.) to the desired value of connectivity even in the presence of imperfect communication scenarios. The estimation strategy is then used as a basic tool to adapt the power transmitted by each node of a wireless network, in order to maximize the network connectivity in the presence of realistic Medium Access Control (MAC) protocols or simply to drive the connectivity toward a desired target value. Numerical results corroborate our theoretical findings, thus illustrating the main features of the algorithm and its robustness to fluctuations of the network graph due to the presence of random link failures., Comment: To appear in IEEE Transactions on Signal Processing

International audience; We propose in this paper a segmentation process that can deal with noisy discrete objects. A flexible approach considering arithmetic discrete planes with a variable width is used to avoid the over-segmentation that might happen when classical segmentation algorithms based on regular discrete planes are used to decompose the surface of the object. A method to choose a seed and different segmentation strategies according to the shape of the surface are also proposed.

We consider partitioning problems subject to the constraint that the subsets in the partition are independent sets or bases of given matroids. We derive conditions for the functions F and [fnof] such that an optimal partition (S∗1, S∗2,…, S∗k) which minimizes F([fnof](S1),…, [fnof](S k)) has certain order properties. These order properties allow to determine optimal partitions by Greedy-like algorithms. In particular balancing partitioning problems can be solved in this way.

The classical connectivity is typically used to capture the robustness of networks. Robustness, however, encompasses more than this simple definition of being connected. A spectral metric, referred to as the algebraic connectivity, plays a special role for the robustness since it measures the extent to which it is difficult to cut the network into independent components. We rely on the algebraic connectivity to study the robustness to random node and link failures in three important network models: the random graph of Erdos-Renyi, the small-world graph of Watts and Strogatz and the scale-free graph of Barabasi-Albert. We show that the robustness to random node and link failures significantly differs between the three models. This points to explicit influence of the network structure on the robustness. The homogeneous structure of the random graph of Erdos-Renyi implies an invariant robustness under random node failures. The heterogeneous structure of the small-world graph of Watts and Strogatz and scale-free graph of Barabasi-Albert, on the other hand, implies a non-trivial robustness to random node and link failures.

International audience; The present paper deals with discrete lines in the $3$-dimensional space. In particular, we focus on the minimal $0$-connected set of closest integer points to a Euclidean line. We propose a definition which leads to geometric, arithmetic and algorithmic characterizations of naive discrete lines in the $3$-dimensional space.

Variational formulations have been proposed for a number of tasks in early vision. Discrete versions of these problems are closely related to Markov random field models and are typically used in implementing such methods. In particular, discrete and continuous versions for the problem of image segmentation have received considerable attention from both theoretical and algorithmic perspectives. It has been previously pointed out that the usual discrete version of the segmentation problem does not properly approximate the continuous formulation in the sense that the discrete solutions may not converge to a solution of the continuous problem as the lattice spacing tends to zero. One method for modifying the discrete formulations to ensure such convergence has been previously discussed. Here we consider two other partially discrete formulations which also satisfy desirable convergence properties in the continuum limit, and we discuss some general ideas about digitized versions of the variational formulation of the segmentation problem.

The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.