Andrea Clementi

TCS Journal 2024 Journal Article

Bond percolation in small-world graphs with power-law distribution

• Luca Becchetti
• Andrea Clementi
• Francesco Pasquale
• Luca Trevisan
• Isabella Ziccardi

Full-bond percolation with parameter p is the process in which, given a graph, we keep each edge independently with probability p and delete it with probability 1 − p. Bond percolation is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Moreover, the full-bond percolation is equivalent to the Reed-Frost process, a network version of SIR epidemic spreading. We consider one-dimensional power-law small-world graphs with parameter α obtained as the union of a cycle with additional long-range random edges: each pair of nodes { u, v } at distance L on the cycle is connected by a long-range edge { u, v }, with probability proportional to 1 / L α. Our analysis determines three phases for the percolation subgraph G p of the small-world graph, depending on the value of α. • If α < 1, there is a p < 1 such that, with high probability, there are Ω ( n ) nodes that are reachable in G p from one another in O ( log ⁡ n ) hops; • If 1 < α < 2, there is a p < 1 such that, with high probability, there are Ω ( n ) nodes that are reachable in G p from one another in log O ( 1 ) ⁡ ( n ) hops; • If α > 2, for every p < 1, with high probability all connected components of G p have size O ( log ⁡ n ).

SODA Conference 2024 Conference Paper

The Minority Dynamics and the Power of Synchronicity

• Luca Becchetti
• Andrea Clementi
• Francesco Pasquale
• Luca Trevisan 0001
• Robin Vacus
• Isabella Ziccardi

IJCAI Conference 2023 Conference Paper

On the Role of Memory in Robust Opinion Dynamics

• Luca Becchetti
• Andrea Clementi
• Amos Korman
• Francesco Pasquale
• Luca Trevisan
• Robin Vacus

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i. e. , the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

TCS Journal 2021 Journal Article

Parallel Load Balancing on constrained client-server topologies

• Andrea Clementi
• Emanuele Natale
• Isabella Ziccardi

We study parallel Load Balancing protocols for the client-server distributed model defined as follows. There is a set C of n clients and a set S of n servers where each client has (at most) a constant number d ⩾ 1 of requests that must be assigned to some server. The client set and the server one are connected to each other via a fixed bipartite graph: the requests of client v can only be sent to the servers in its neighborhood N ( v ). The goal is to assign every client request so as to minimize the maximum load of the servers. In this setting, efficient parallel protocols are available only for dense topologies. In particular, a simple protocol, named raes, has been recently introduced by Becchetti et al. [1] for regular dense bipartite graphs. They show that this symmetric, non-adaptive protocol achieves constant maximum load with parallel completion time O ( log ⁡ n ) and overall work O ( n ), w. h. p. Motivated by proximity constraints arising in some client-server systems, we analyze raes over almost-regular bipartite graphs where nodes may have neighborhoods of small size. In detail, we prove that, w. h. p. , the raes protocol keeps the same performances as above (in terms of maximum load, completion time, and work complexity, respectively) on any almost-regular bipartite graph with degree Ω ( log 2 ⁡ n ). Our analysis significantly departs from that in [1] since it requires to cope with non-trivial stochastic-dependence issues on the random choices of the algorithmic process which are due to the worst-case, sparse topology of the underlying graph.

SODA Conference 2020 Conference Paper

Finding a Bounded-Degree Expander Inside a Dense One

• Luca Becchetti
• Andrea Clementi
• Emanuele Natale
• Francesco Pasquale
• Luca Trevisan 0001

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if G = ( V, E ) is a Δ-regular dense expander then there is an edge-induced subgraph H = ( V, E h ) of G of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in O (log n ) rounds and does O ( n ) total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

MFCS Conference 2018 Conference Paper

A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors

• Andrea Clementi
• Mohsen Ghaffari 0001
• Luciano Gualà
• Emanuele Natale
• Francesco Pasquale
• Giacomo Scornavacca

The Undecided-State Dynamics is a well-known protocol for distributed consensus. We analyze it in the parallel PULL communication model on the complete graph with n nodes for the binary case (every node can either support one of two possible colors, or be in the undecided state). An interesting open question is whether this dynamics is an efficient Self-Stabilizing protocol, namely, starting from an arbitrary initial configuration, it reaches consensus quickly (i. e. , within a polylogarithmic number of rounds). Previous work in this setting only considers initial color configurations with no undecided nodes and a large bias (i. e. , Theta(n)) towards the majority color. In this paper we present an unconditional analysis of the Undecided-State Dynamics that answers to the above question in the affirmative. We prove that, starting from any initial configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability. This bound turns out to be tight. Our analysis also shows that, if the initial configuration has bias Omega(sqrt(n log n)), then the dynamics converges toward the initial majority color, with high probability.

SODA Conference 2017 Conference Paper

Find Your Place: Simple Distributed Algorithms for Community Detection

• Luca Becchetti
• Andrea Clementi
• Emanuele Natale
• Francesco Pasquale
• Luca Trevisan 0001

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1, 1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting. Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models.

SODA Conference 2016 Conference Paper

Stabilizing Consensus with Many Opinions

• Luca Becchetti
• Andrea Clementi
• Emanuele Natale
• Francesco Pasquale
• Luca Trevisan 0001

We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i. e. , it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ n α, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2.

TCS Journal 2015 Journal Article

Distributed community detection in dynamic graphs

• Andrea Clementi
• Miriam Di Ianni
• Giorgio Gambosi
• Emanuele Natale
• Riccardo Silvestri

Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model dyn- G ( n, p, q ) where the node set [ n ] of the network is partitioned into two unknown communities and, at every time step, each possible edge ( u, v ) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q ≪ p ) otherwise. We also consider a time-Markovian generalization of this model. We propose a distributed protocol based on the popular Label-Propagation approach and prove that, when the ratio p / q is larger than n b (for an arbitrarily small constant b > 0 ), the protocol finds the right “planted” partition in O ( log ⁡ n ) time even when the snapshots of the dynamic graph are sparse and disconnected (i. e. , when p = Θ ( 1 / n ) ).

SODA Conference 2015 Conference Paper

Plurality Consensus in the Gossip Model

• Luca Becchetti
• Andrea Clementi
• Emanuele Natale
• Francesco Pasquale
• Riccardo Silvestri

We study Plurality Consensus in the Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md( ) which measures the distance of the initial color configuration from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within O (md( ) log n ) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration, the convergence time is Ω(md( )). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in O (md( ) polylog( n )) rounds using only polylog( n ) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.

MFCS Conference 2007 Conference Paper

Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults

• Andrea Clementi
• Angelo Monti
• Francesco Pasquale
• Riccardo Silvestri

Abstract We study deterministic fault-tolerant gossiping protocols in directed Geometric Radio Networks (in short, directed GRN). Unpredictable node and link faults may happen during every time slot of the protocol’s execution. We first consider the single-message model where every node can send at most one message per time slot. We provide a protocol that, in any directed GRN G of n nodes, completes gossiping in O ( n Δ ) time (where Δ is the maximal in-degree of G ) and has message complexity O ( n 2 ). Both bounds are then shown to be optimal. As for the combined-message model, we give a protocol working in optimal completion time O ( DΔ ) (where D is the maximal source eccentricity) and message complexity O ( Dn ). Finally, our protocol performs the (single) broadcast operation within the same optimal time and optimal message complexity O ( n ).

SODA Conference 2001 Conference Paper

Selective families, superimposed codes, and broadcasting on unknown radio networks

• Andrea Clementi
• Angelo Monti
• Riccardo Silvestri

FOCS Conference 1997 Conference Paper

Weak Random Sources, Hitting Sets, and BPP Simulations

• Alexander E. Andreev
• Andrea Clementi
• José D. P. Rolim
• Luca Trevisan 0001

We show how to simulate any BPP algorithm in polynomial time using a weak random source of min-entropy r/sup /spl gamma// for any /spl gamma/>0. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP (Saks et al. , 1995) and a n(log/sup (k)/n)-time simulation of BPP for fixed k (Ta-Shma, 1996). Departing significantly from previous related works, we do not use extractors; instead we use the OR-disperser of (Saks et al. , 1995) in combination with a tricky use of hitting sets borrowed from Andreev et al. (1996). Of independent interest is our new (simplified) proof of the main result of Andreev et al. , (1996). Our proof also gives some new hardness/randomness trade-offs for parallel classes.