Adrian Kosowski

NeurIPS Conference 2020 Conference Paper

On the Power of Louvain in the Stochastic Block Model

• Vincent Cohen-Addad
• Adrian Kosowski
• Frederik Mallmann-Trenn
• David Saulpic

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

SODA Conference 2018 Conference Paper

Ergodic Effects in Token Circulation

• Adrian Kosowski
• Przemyslaw Uznanski

STOC Conference 2018 Conference Paper

Universal protocols for information dissemination using emergent signals

• Bartlomiej Dudek 0001
• Adrian Kosowski

SODA Conference 2017 Conference Paper

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

• Adrian Kosowski
• Laurent Viennot

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.

FOCS Conference 2016 Conference Paper

Local Conflict Coloring

• Pierre Fraigniaud
• Marc Heinrich
• Adrian Kosowski

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.

TCS Journal 2015 Journal Article

Distinguishing views in symmetric networks: A tight lower bound

• Dariusz Dereniowski
• Adrian Kosowski
• Dominik Pająk

The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Ω ( D log ⁡ ( n / D ) ) are identical.

TCS Journal 2015 Journal Article

Rendezvous of heterogeneous mobile agents in edge-weighted networks

• Dariusz Dereniowski
• Ralf Klasing
• Adrian Kosowski
• Łukasz Kuszner

We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time T OPT in the offline scenario in which the agents have complete knowledge about each others' speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time O ( n T OPT ) in an n-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to Θ ( T OPT ) when the agents are allowed to exchange Θ ( n ) bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time Θ ( T OPT ).

SODA Conference 2013 Conference Paper

A Õ ( n 2 ) Time-Space Trade-off for Undirected s-t Connectivity

• Adrian Kosowski

TCS Journal 2013 Journal Article

Maximum matching in multi-interface networks

• Adrian Kosowski
• Alfredo Navarra
• Dominik Pajak
• Cristina M. Pinotti

In heterogeneous networks, devices can communicate by means of multiple wireless interfaces. By choosing which interfaces to switch on at each device, several connections might be established. That is, the devices at the endpoints of each connection share at least one active interface. In this paper, we consider the standard matching problem in the context of multi-interface wireless networks. The aim is to maximize the number of parallel connections without incurring interferences. Given a network G = ( V, E ), nodes V represent the devices, and edges E represent the connections that can be established. If node x participates in the communication with one of its neighbors by means of interface i, then another neighboring node of x can establish a connection (but not with x ) only if it makes use of interface j ≠ i. The size of a solution for an instance of the outcoming matching problem, which we call Maximum Matching in Multi-Interface networks (MMMI for short), is always in between the sizes of the solutions for the same instance with respect to the standard matching and its induced version problems. However, we prove that MMMI is NP-hard even for proper interval graphs and for bipartite graphs of maximum degree Δ ≥ 3. We also show polynomially solvable cases of MMMI with respect to different assumptions.

TCS Journal 2013 Journal Article

Preface

• Adrian Kosowski
• Masafumi Yamashita

TCS Journal 2011 Journal Article

Synchronous black hole search in directed graphs

• Adrian Kosowski
• Alfredo Navarra
• Cristina M. Pinotti

The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that G is a directed graph, the robots are associated with unique identifiers, they know the number of nodes n of G (or at least an upper bound on n ), and they know the number of edges Δ leading to the black holes. Each node is associated with a whiteboard where robots can read and write information in a mutual exclusive way. A recently posed question [J. Czyzowicz, S. Dobrev, R. Kralovic, S. Miklik, D. Pardubska, Black hole search in directed graphs, in: Proc. of 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO, LNCS, vol. 5869, 2009, pp. 182–194. ] is whether some number of robots, expressed as a function of parameter Δ only, is sufficient to detect black holes in directed graphs of arbitrarily large order n. We give a positive answer to this question for the synchronous case, i. e. , when the robots share a common clock, showing that O ( Δ ⋅ 2 Δ ) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2 Δ robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for Δ = 2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.

MFCS Conference 2010 Conference Paper

Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains

• Jurek Czyzowicz
• Adrian Kosowski
• Andrzej Pelc

Abstract Two mobile agents, modeled as points starting at different locations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and ε - RV, when these points have to get at distance less than ε in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e. g. , speed up or slow down the agent. Agents have bounded memory: their computational power is that of finite state machines. Our aim is to compare the feasibility of exact and of ε -RV when agents are anonymous vs. when they are labeled. We show classes of polygonal terrains which distinguish all the studied scenarios from the point of view of feasibility of rendezvous. The features which influence the feasibility of rendezvous include symmetries present in the terrains, boundedness of their diameter, and the number of vertices of polygons in the terrains.

TCS Journal 2010 Journal Article

Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

• Ralf Klasing
• Adrian Kosowski
• Alfredo Navarra

One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. More precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. When the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. In this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [R. Klasing, E. Markou, A. Pelc: Gathering asynchronous oblivious mobile robots in a ring, Theoret. Comput. Sci. 390 (1) (2008) 27–39]. The proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.

MFCS Conference 2009 Conference Paper

Graph Decomposition for Improving Memoryless Periodic Exploration

• Adrian Kosowski
• Alfredo Navarra

Abstract We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels from the range 1 to deg( v ) (the degree of v ). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled i, the robot proceeds with its exploration, leaving via the edge having label [ i mod deg(v)]+1 at v. A lot of attention has been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length π. It has recently been proved [Czyzowicz et al. , Proc. SIROCCO’09 [1]] that \(\pi \leq 4\frac13 n\) holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π ≤ 4 n − 2. This main result is shown to be tight with respect to the class of labelings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.

TCS Journal 2009 Journal Article

Universal augmentation schemes for network navigability

• Pierre Fraigniaud
• Cyril Gavoille
• Adrian Kosowski
• Emmanuelle Lebhar
• Zvi Lotker

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. We define an augmented graph as a pair ( G, M ) where G is an n -node graph with nodes labeled in { 1, …, n }, and M is an n × n stochastic matrix. 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 } = M u, v. In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses from 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. The best augmentation scheme known so far ensures that, for any n -node graph G, greedy routing performs in O ( n ) expected number of steps. Our main result is the design of an augmentation scheme that overcomes the O ( n ) barrier. Precisely, we prove that for any n -node graph G whose nodes are arbitrarily labeled in { 1, …, n }, there exists a stochastic matrix M such that greedy routing in ( G, M ) performs in O ̃ ( n 1 / 3 ), where the O ̃ notation ignores the polylogarithmic factors. We prove additional results when the stochastic matrix M is universal to all graphs. In particular, we prove that the O ( n ) barrier can still be overcame for large graph classes even if the matrix M is universal. This however requires an appropriate labeling of the nodes. If the node labeling is arbitrary, then we prove that the O ( n ) barrier cannot be overcome with universal matrices.

TCS Journal 2008 Journal Article

The maximum edge-disjoint paths problem in complete graphs

• Adrian Kosowski

In this paper, we consider the undirected version of the well known maximum edge-disjoint paths problem, restricted to complete graphs. We propose an off-line 3. 75-approximation algorithm and an on-line 6. 47-approximation algorithm, improving the earlier 9-approximation algorithm proposed by Carmi, Erlebach, and Okamoto [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143–155]. Moreover, we show that for the general case, no on-line algorithm is better than a ( 2 − ε ) -approximation, for all ε > 0. For the special case when the number of paths is within a linear factor of the number of vertices of the graph, it is established that the problem can be optimally solved in polynomial time by an off-line algorithm, but that no on-line algorithm is better than a ( 1. 5 − ε ) -approximation. Finally, the proposed techniques are used to obtain off-line and on-line algorithms with a constant approximation ratio for the related problems of edge congestion routing and wavelength routing in complete graphs.