Arrow Research search

Author name cluster

Luca Becchetti

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

TIST Journal 2024 Journal Article

Fair Projections as a Means toward Balanced Recommendations

  • Aris Anagnostopoulos
  • Luca Becchetti
  • Matteo Böhm
  • Adriano Fazzone
  • Stefano Leonardi
  • Cristina Menghini
  • Chris Schwiegelshohn

The goal of recommender systems is to provide to users suggestions that match their interests, with the eventual goal of increasing their satisfaction, as measured by the number of transactions (clicks, purchases, and so forth). Often, this leads to providing recommendations that are of a particular type. For some contexts (e.g., browsing videos for information) this may be undesirable, as it may enforce the creation of filter bubbles. This is because of the existence of underlying bias in the input data of prior user actions. Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. In this article, we consider both the densest subgraph and the \(k\) -clustering problem, two primitives that are being used by some recommender systems. We are given a coloring on the nodes, respectively the points, and aim to compute a fair solution \(S\), consisting of a subgraph or a clustering, such that none of the colors is disparately impacted by the solution. Unfortunately, introducing fair solutions typically makes these problems substantially more difficult. Unlike the unconstrained densest subgraph problem, which is solvable in polynomial time, the fair densest subgraph problem is NP-hard even to approximate, which means that with the standard computational model it is probably impossible to solve (or even approximate it sufficiently well) in polynomial time. For \(k\) -clustering, the fairness constraints make the problem very similar to capacitated clustering, which is a notoriously hard problem to even approximate. Despite such negative premises, we are able to provide positive results in important use cases. In particular, we are able to prove that a suitable spectral embedding allows recovery of an almost optimal, fair, dense subgraph hidden in the input data, whenever one is present, a result that is further supported by experimental evidence. We also show a polynomial-time, \(2\) -approximation algorithm to the problem of fair densest subgraph, assuming that there exist only two colors and both colors occur equally often in the graph. This result turns out to be optimal assuming the small set expansion hypothesis. For fair \(k\) -clustering, we show that we can recover high quality fair clusterings effectively and efficiently. For the special case of \(k\) -median and \(k\) -center, we offer additional, fast and simple approximation algorithms as well as new hardness results. The above theoretical findings drive the design of heuristics, which we experimentally evaluate on a scenario based on real data, in which our aim is to strike a good balance between diversity and highly correlated items from Amazon co-purchasing graphs and Facebook contacts. We additionally evaluated our algorithmic solutions for the fair \(k\) -median problem through experiments on various real-world datasets.

Details DOI

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.

PDF Details DOI

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.

PDF

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.

PDF Details DOI

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.

PDF Details DOI

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.

Details

AAMAS Conference 2018 Conference Paper

Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation

  • Luca Becchetti
  • Vincenzo Bonifaci
  • Emanuele Natale

The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized subroutine, the ability to perform this task in a fully decentralized way is implicit in a number of biological systems. Thus, a natural question is whether this task can provably be accomplished in an efficient way by a network of agents executing a simple protocol. We provide a positive answer, proposing two distributed approaches to electrical flow computation on a weighted network: a deterministic process mimicking Jacobi’s iterative method for solving linear systems, and a randomized token diffusion process, based on revisiting a classical random walk process on a graph with an absorbing node. We show that both processes converge to a solution of Kirchhoff’s node potential equations, derive bounds on their convergence rates in terms of the weights of the network, and analyze their time and message complexity.

PDF

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.

Details

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.

Details

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.

Details

FOCS Conference 2003 Conference Paper

Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

  • Luca Becchetti
  • Stefano Leonardi 0001
  • Alberto Marchetti-Spaccamela
  • Guido Schäfer
  • Tjark Vredeveld

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng (2001) to explain the behavior of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2/sup K/] We use a partial bit randomization model, where the initial processing times are smoothened by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2/sup k///spl sigma/)/sup 3/ + (2/sup k///spl sigma/)/sup 2/2/sup K-k/), where /spl sigma/ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2/sup K-k/) if /spl sigma/ = /spl Theta/(2/sup k/). We also prove an /spl Omega/(2/sup K-k/) lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, we give a higher lower bound of /spl Omega/(2/sup K/). A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.

Details

STOC Conference 2001 Conference Paper

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

  • Luca Becchetti
  • Stefano Leonardi 0001

Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, i.e. the average time spent by jobs in the system between release and completion. The Windows NT and the Unix operating system scheduling policies are based on the Multi-level Feedback algorithm [12, 1]. In this paper we prove that a randomized version of the Multi-level Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has been very effective in practice along the last two decades. The randomized Multi-level Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs [7] for a single machine achieving an O(\log n \log\log n) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where n is the number of jobs that are released. We present a version of RMLF working for any number m of parallel machines. We show for RMLF a first O(\log n\log \frac{n}{m}) competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight O(\log n) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound of [10].

Details