43 citations · 116 across the 21 of their papers we have counts for
26 papers
The Minority Dynamics and the Power of Synchronicity
Luca Becchetti, Andrea Clementi, Francesco Pasquale +3
We study the minority-opinion dynamics over a fully-connected network of nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number…
On a Voter Model with Context-Dependent Opinion Adoption
Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani +1
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 i…
On the Role of Memory in Robust Opinion Dynamics
Luca Becchetti, Andrea Clementi, Amos Korman +3
We investigate opinion dynamics in a fully-connected system, consisting of identical and anonymous agents, where one of the opinions (which is called correct) represents a piec…
Bond Percolation in Small-World Graphs with Power-Law Distribution
Luca Becchetti, Andrea Clementi, Francesco Pasquale +2
\emph{Full-bond percolation} with parameter is the process in which, given a graph, for every edge independently, we delete the edge with probability . Bond percolation is…
Percolation and Epidemic Processes in One-Dimensional Small-World Networks
Luca Becchetti, Andrea Clementi, Riccardo Denni +3
We obtain tight thresholds for bond percolation on one-dimensional small-world graphs, and apply such results to obtain tight thresholds for the \emph{Independent Cascade} process…
Biased Opinion Dynamics: When the Devil Is in the Details
Aris Anagnostopoulos, Luca Becchetti, Emilio Cruciani +2
We investigate opinion dynamics in multi-agent networks when a bias toward one of two possible opinions exists; for example, reflecting a status quo vs a superior alternative. Star…
Expansion and Flooding in Dynamic Random Networks with Node Churn
Luca Becchetti, Andrea Clementi, Francesco Pasquale +2
We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffu…
Finding a Bounded-Degree Expander Inside a Dense One
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if is a -regular dense expander then there is an edge-induced subgraph $H=(V…
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
Andrea Clementi, Luciano Gualà, Emanuele Natale +3
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast,…
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
Andrea E. F. Clementi, Luciano Gualà, Francesco Pasquale +3
The \emph{Undecided-State Dynamics} is a well-known protocol for distributed consensus. We analyze it in the parallel \pull\ communication model on the complete graph for the \emph…
Average whenever you meet: Opportunistic protocols for community detection
Luca Becchetti, Andrea Clementi, Pasin Manurangsi +4
Consider the following asynchronous, opportunistic communication model over a graph : in each round, one edge is activated uniformly and independently at random and (only) its t…
Find Your Place: Simple Distributed Algorithms for Community Detection
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
Given an underlying graph, we consider the following \emph{dynamics}: Initially, each node locally chooses a value in , uniformly at random and independently of other nod…
Stabilizing Consensus with Many Opinions
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
We consider the following distributed consensus problem: Each node in a complete communication network of size initially holds an \emph{opinion}, which is chosen arbitrarily fr…
Probabilistic Self-Stabilization
Luca Becchetti, Andrea Clementi, Emanuele Natale +1
By using concrete scenarios, we present and discuss a new concept of probabilistic Self-Stabilization in Distributed Systems.
Self-Stabilizing Repeated Balls-into-Bins
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
We study the following synchronous process that we call "repeated balls-into-bins". The process is started by assigning balls to bins in an arbitrary way. In every subseque…
Plurality Consensus in the Gossip Model
L. Becchetti, A. Clementi, E. Natale +2
We study Plurality Consensus in the Gossip Model over a network of anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of…
Simple Dynamics for Plurality Consensus
Luca Becchetti, Andrea Clementi, Emanuele Natale +3
We study a \emph{Plurality-Consensus} process in which each of anonymous agents of a communication network initially supports an opinion (a color chosen from a finite set …
Rumor Spreading in Random Evolving Graphs
Andrea Clementi, Pierluigi Crescenzi, Carola Doerr +5
Randomized gossip is one of the most popular way of disseminating information in large scale networks. This method is appreciated for its simplicity, robustness, and efficiency. In…
Convergence to Equilibrium of Logit Dynamics for Strategic Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +2
We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noi…
Logit Dynamics with Concurrent Updates for Local-Interaction Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +2
Logit choice dynamics are a family of randomized best response dynamics based on the logit choice function [McFadden, 1974], used for modeling players with limited rationality and…
Flooding Time in Opportunistic Networks under Power Law and Exponential Inter-Contact Times
Luca Becchetti, Andrea Clementi, Francesco Pasquale +3
Performance bounds for opportunistic networks have been derived in a number of recent papers for several key quantities, such as the expected delivery time of a unicast message, or…
Metastability of Logit Dynamics for Coordination Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +1
Logit Dynamics [Blume, Games and Economic Behavior, 1993] are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and…
Information Spreading in Stationary Markovian Evolving Graphs
Andrea Clementi, Angelo Monti, Francesco Pasquale +1
Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely genera…
Mixing Time and Stationary Expected Social Welfare of Logit Dynamics
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +1
We study "logit dynamics" [Blume, Games and Economic Behavior, 1993] for strategic games. This dynamics works as follows: at every stage of the game a player is selected uniformly…