Francesco Pasquale

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 a Voter Model with Context-Dependent Opinion Adoption

• Luca Becchetti
• Vincenzo Bonifaci
• Emilio Cruciani
• Francesco Pasquale

Opinion diffusion is a crucial phenomenon in social networks, often underlying the way in which a collection of agents develops a consensus on relevant decisions. Voter models are well-known theoretical models to study opinion spreading in social networks and structured populations. Their simplest version assumes that an updating agent will adopt the opinion of a neighboring agent chosen at random. These models allow us to study, for example, the probability that a certain opinion will fixate into a consensus opinion, as well as the expected time it takes for a consensus opinion to emerge. Standard voter models are oblivious to the opinions held by the agents involved in the opinion adoption process. We propose and study a context-dependent opinion spreading process on an arbitrary social graph, in which the probability that an agent abandons opinion a in favor of opinion b depends on both a and b. We discuss the relations of the model with existing voter models and then derive theoretical results for both the fixation probability and the expected consensus time for two opinions, for both the synchronous and the asynchronous update models.

AAMAS Conference 2023 Conference Paper

On a Voter Model with Context-Dependent Opinion Adoption

• Luca Becchetti
• Vincenzo Bonifaci
• Emilio Cruciani
• Francesco Pasquale

Opinion diffusion is a crucial phenomenon in social networks, often underlying the way in which a collective of agents develops a consensus on relevant decisions. The voter model is a well-known theoretical model to study opinion spreading in social networks and structured populations. Its simplest version assumes that an updating agent will adopt the opinion of a neighboring agent chosen at random. The model allows to study, for example, the probability that a certain opinion will fixate into a consensus opinion, as well as the expected time it takes for a consensus opinion to emerge. Standard voter models are oblivious to the opinions held by the agents involved in the opinion adoption process. We propose and study a context-dependent opinion spreading process on an arbitrary social graph, in which the probability that an agent abandons opinion 𝑎 in favor of opinion 𝑏 depends on both 𝑎 and 𝑏. We discuss the relation of the model with existing voter models and then proceed to derive theoretical results for both the fixation probability and the expected consensus time for two opinions on an 𝑛-clique network topology, for both the synchronous and the asynchronous update modes.

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.

IJCAI Conference 2020 Conference Paper

Biased Opinion Dynamics: When the Devil is in the Details

• Aris Anagnostopoulos
• Luca Becchetti
• Emilio Cruciani
• Francesco Pasquale
• Sara Rizzo

We investigate opinion dynamics in multi-agent networks when there exists a bias toward one of two possible opinions; for example, reflecting a status quo vs a superior alternative. Starting with all agents sharing an initial opinion representing the status quo, the system evolves in steps. In each step, one agent selected uniformly at random adopts with some probability a the superior opinion, and with probability 1 - a it follows an underlying update rule to revise its opinion on the basis of those held by its neighbors. We analyze the convergence of the resulting process under two well-known update rules, namely majority and voter. The framework we propose exhibits a rich structure, with a nonobvious interplay between topology and underlying update rule. For example, for the voter rule we show that the speed of convergence bears no significant dependence on the underlying topology, whereas the picture changes completely under the majority rule, where network density negatively affects convergence. We believe that the model we propose is at the same time simple, rich, and modular, affording mathematical characterization of the interplay between bias, underlying opinion dynamics, and social structure in a unified setting.

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.

TCS Journal 2020 Journal Article

Step-by-step community detection in volume-regular graphs

• Luca Becchetti
• Emilio Cruciani
• Francesco Pasquale
• Sara Rizzo

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.

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.

TCS Journal 2012 Journal Article

A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model

• Chen Avin
• Zvi Lotker
• Francesco Pasquale
• Yvonne-Anne Pignolet

SODA Conference 2012 Conference Paper

Metastability of logit dynamics for coordination games

• Vincenzo Auletta
• Diodato Ferraioli
• Francesco Pasquale
• Giuseppe Persiano

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