A classic problem in machine learning and data analysis is to partition the vertices of a network in such a way that vertices in the same set are densely connected and vertices in different sets are loosely connected. In practice, the most popular approaches rely on local search algorithms; not only for the ease of implementation and the efficiency, but also because of the accuracy of these methods on many real world graphs. For example, the Louvain algorithm -- a local search based algorithm -- has quickly become the method of choice for clustering in social networks. However, explaining the success of these methods remains an open problem: in the worst-case, the runtime can be up to \Omega(n^2), much worse than what is typically observed in practice, and no guarantee on the quality of its output can be established. The goal of this paper is to shed light on the inner-workings of Louvain; only if we understand Louvain, can we rely on it and further improve it. To achieve this goal, we study the behavior of Louvain in the famous two-bloc Stochastic Block Model, which has a clear ground-truth and serves as the standard testbed for graph clustering algorithms. We provide valuable tools for the analysis of Louvain, but also for many other combinatorial algorithms. For example, we show that the probability for a node to have more edges towards its own community is 1/2 + \Omega( \min( \Delta(p-q)/\sqrt{np},1 )) in the SBM(n,p,q), where \Delta is the imbalance. Note that this bound is asymptotically tight and useful for the analysis of a wide range of algorithms (Louvain, Kernighan-Lin, Simulated Annealing etc).

For fixed h >= 2, we consider the task of adding to a graph G a set of weighted shortcut edges on the same vertex set, such that the length of a shortest h-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in G. A set of shortcut edges with this property is called an exact h-hopset and may be applied in processing distance queries on graph G. In particular, a 2-hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on 3-hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that 3-hopsets require exponentially fewer shortcuts per node than any previously described distance oracle, and also offer a speedup in query time when compared to simple oracles based on a direct application of 2-hopsets. Finally, we consider the problem of computing minimum-size h-hopset (for any h >= 2) for a given graph G, showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When h=3, for a given bound on the space used by the distance oracle, we provide a construction of hopset achieving polylog approximation both for space and query time compared to the optimal 3-hopset oracle given the space bound.

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. An important class of distance labeling schemes is that of hub labelings, where a node ν ∈ G stores its distance to the so-called hubs Sν ⊆ V, chosen so that for any u,ν ∈ V there is w ∈ Su ∩ Sv belonging to some shortest uv path. Notice that for most existing graph classes, the best distance labelling constructions existing use at some point a hub labeling scheme at least as a key building block.

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d -regular undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms that are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of O ( d min { √ log n /μ,√ n }) in time O ( T ), where μ is the spectral gap of the transition matrix of the graph. We also show that, in general, neither of these assumptions may be omitted without increasing discrepancy. We then show, by a combinatorial potential reduction argument, that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of O ( d ) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.

We consider a dynamical process in a network which distributes all particles (tokens) located at a node among its neighbors, in a round-robin manner. We show that in the recurrent state of this dynamics (i.e., disregarding a polynomially long initialization phase of the system), the number of particles located on a given edge, averaged over an interval of time, is tightly concentrated around the average particle density in the system. Formally, for a system of k particles in a graph of m edges, during any interval of length T, this time-averaged value is k/m±Õ(1/T), whenever gcd(m, k) = Õ(1) (and so, e.g., whenever m is a prime number). To achieve these bounds, we link the behavior of the studied dynamics to ergodic properties of traversals based on Eulerian circuits on a symmetric directed graph. These results are proved through sum set methods and are likely to be of independent interest. As a corollary, we also obtain bounds on the idleness of the studied dynamics, i.e., on the longest possible time between two consecutive appearances of a token on an edge, taken over all edges. Designing trajectories for k tokens in a way which minimizes idleness is fundamental to the study of the patrolling problem in networks. Our results immediately imply a bound of Õ(m/k) on the idleness of the studied process, showing that it is a distributed Õ(1)-competitive solution to the patrolling task, for all of the covered cases. Our work also provides some further insights that may be interesting in load-balancing applications.

We consider a population of n agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may act as authoritative sources of information, and the objective of the remaining agents is to obtain information from or about these source agents. We study two basic tasks: broadcasting, in which the agents are to learn the bit-state of an authoritative source which is present in the population, and source detection, in which the agents are required to decide if at least one source agent is present in the population or not.

The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) ⊆ V to each node u ∊, in such a way that for any pair of nodes u,v, the intersection of hub sets S (u) n S (v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.

We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. The behavior of the rotor-router is fully deterministic but its performance characteristics (cover time, return time) closely resemble the expected values of the corresponding parameters of the random walk. In this work we consider the setting in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. We propose new techniques which allow us to perform a theoretical analysis of the multi-agent rotor-router model, and to compare it to the scenario of parallel independent random walks in a graph. Our main results concern the n-node ring, and suggest a strong similarity between the performance characteristics of this deterministic model and random walks. We show that on the ring the rotor-router with k agents admits a cover time of between $$\varTheta (n^2 / k^2)$$ in the best case and $$\varTheta (n^2 / \log k)$$ in the worst case, depending on the initial locations of the agents, and that both these bounds are tight. The corresponding expected value of the cover time for k random walks, depending on the initial locations of the walkers, is proven to belong to a similar range, namely between $$\varTheta (n^2 / (k^2/\log ^2 k))$$ and $$\varTheta (n^2 / \log k)$$ . Finally, we study the limit behavior of the rotor-router system. We show that, once the rotor-router system has stabilized, all the nodes of the ring are always visited by some agent every $$\varTheta (n / k)$$ steps, regardless of how the system was initialized. This asymptotic bound corresponds to the expected time between successive visits to a node in the case of k random walks. All our results hold up to a polynomially large number of agents ( $$1 \le k < n^{1/11}$$ ).

Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations - conflict coloring includes all locally checkable labeling tasks from [Naor & Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters l and d, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard LOCAL model for distributed network computing, if l/d > Δ, then conflict coloring can be solved in Õ(√Δ)+log*n rounds in n-node graphs with maximum degree Δ, where Õ ignores the polylog factors in Δ. The dependency in n is optimal, as a consequence of the Ω(log*n) lower bound by [Linial, SIAM J. Comp. 1992] for (Δ + 1)-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed (Δ + 1)-coloring due to [Barenboim, PODC 2015], which required Õ(Δ3/4) + log*n rounds. Improvements for other variants of coloring, including (Δ + 1)-list-coloring, (2Δ-1)-edge-coloring, coloring with forbidden color distances, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs S(u) ⊆ V. For a queried pair of nodes (u,v), the length of a shortest u--v-path passing through a hub node from S(u)∩S(v) is then used as an upper bound on the distance between u and v.

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time T = O(log (Kn)/μ), any algorithm of their class achieves a discrepancy of O(d log n/μ), where μ is the spectral gap of the transition matrix of the graph, and K is the initial load discrepancy in the system.

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in round-robin fashion, according to the fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the starting locations of the walks. In the case of k=1, [Yanovski et al., 2003] and [Bampas et al., 2009] showed that a single walk achieves a cover time of exactly Theta(mD) for any n-node graph with m edges and diameter D, and that the walker eventually stabilizes to a traversal of an Eulerian circuit on the set of all directed edges of the graph. For k>1 parallel walks, no similar structural behaviour can be observed. In this work we provide tight bounds on the cover time of k parallel rotor walks in a graph. We show that this cover time is at most (mD/log(k)) and at least Theta(mD/k) for any graph, which corresponds to a speedup of between Theta(log(k)) and Theta(k) with respect to the cover time of a single walk. Both of these extremal values of speedup are achieved for some graph classes. Our results hold for up to a polynomially large number of walks, k=O(poly(n)).

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, an agent is initially placed at one of the nodes of the graph. Each node maintains a cyclic ordering of its outgoing arcs, and during successive visits of the agent, propagates it along arcs chosen according to this ordering in round-robin fashion. In this work we consider the setting in which multiple, indistinguishable agents are deployed in parallel in the nodes of the graph, and move around the graph in synchronous rounds, interacting with a single rotor-router system. We propose new techniques which allow us to perform a theoretical analysis of the multi-agent rotor-router model, and to compare it to the scenario of parallel independent random walks in a graph. Our main results concern the n-node ring, and suggest a strong similarity between the performance characteristics of this deterministic model and random walks.

In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the -connectivity problem in undirected graphs (USTCON). As our main result, we propose a family of randomized algorithms for USTCON which achieves a time-space product of S · T = Õ(n) in graphs with n nodes and m edges (where the Õ-notation disregards poly-logarithmic terms). This improves the previously best trade-off of Õ(nm), due to Feige (1995). Our algorithm consists in deploying several short Metropolis-type walks, starting from landmark nodes distributed using the scheme of Broder et al. (1994) on a modified input graph. In particular, we obtain an algorithm running in time Õ(n + m) which is, in general, more space-efficient than both BFS and DFS. We close the paper by showing how to fine-tune the Metropolis-type walk so as to match the performance parameters (e.g., average hitting time) of the unbiased random walk for any graph, while preserving a worst-case bound of Õ(n2) on cover time.

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their uniform maximum speeds. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness.

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that {\it separate} these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with k memory bits, we show that optimal rendezvous time is Θ(n+n2/k) in n-node trees. More precisely, if k ≥ c log n, for some constant c, we design agents accomplishing rendezvous in arbitrary trees of unknown size n in time O(n+n2/k), starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time o(n+n2/k), even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a n-node line.

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. Intuitively, the rendezvous problem is more difficult than exploration, as it reduces to the latter, if one of the agents is inert. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically.

We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2Ω(min d,k}), for any d,k = O(log n), even when G is a tree.

Abstract Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)‐Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Given a graph G = (V,E) with |V| = n and |E| = m, which models a set of wireless devices (nodes V) connected by multiple radio interfaces (edges E), the aim is to switch on the minimum cost set of interfaces at the nodes to satisfy all the connections. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. Depending on whether k is a priori bounded or not, the problem is called Cost Minimization in Multi‐Interface Networks or Cost Minimization in Unbounded Multi‐Interface Networks, respectively. We distinguish two main variations for both problems by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or nonuniform. For bounded k, we show that the problem is APX‐hard while we obtain an approximation factor of min ${\{\lceil {k + 1 \over 2} \rceil, {2m \over n}}\}$ for the uniform caseand a (k − 1)‐approximation for the nonuniform case. For unbounded k, i.e., k is not set a priori but depends on the given instance, we prove that the problem is not approximable within O(log k) while the same approximation factor of the k‐bounded case holds in the uniform case, and a min $\{k-1, \, \sqrt{n} \, {(1 + {\rm In} \, n)} \}$ ‐approximation factor holds for the nonuniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar, and complete graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Augmented graphs were introduced for the purpose of analyzing the "six degrees of separation between individuals" observed experimentally by the sociologist Standley Milgram in the 60's. Formally, an augmented graph is a pair (G,φ) where G is a graph, and φ is a collection of probability distributions {φu, u ∈ V(G)}. Every node u ∈ V(G) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr{u → v} = φu(v). In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. Roughly, augmented graphs aim at modeling the structure of social networks, while greedy routing aims at modeling the searching procedure applied in Milgram's experiment. Our objective is to design efficient universal augmentation schemes, i.e., augmentation schemes that give to any graph G a collection of probability distributions φ such that greedy routing in (G,φ) is fast. It is known that the uniform scheme φunif is a universal scheme ensuring that, for any n-node graph G, greedy routing in (G,φunif) performs in O(√n) expected number of steps. Our main result is the design of a universal augmentation scheme φ such that greedy routing in (G,φ) performs in Õ(n1/3) expected number of steps for any n-node graph G. We also show that under some more restricted model, the √n-barrier cannot be overcome.