36 citations · 96 across the 8 of their papers we have counts for
8 papers
Sliding Window Algorithms for k-Clustering Problems
Michele Borassi, Alessandro Epasto, Silvio Lattanzi +2
The sliding window model of computation captures scenarios in which data is arriving continuously, but only the latest elements should be used for analysis. The goal is to desi…
Computing top-k Closeness Centrality Faster in Unweighted Graphs
Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi +2
Given a connected graph , the closeness centrality of a vertex is defined as . This measure is widely used in the analysis of real-w…
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
Michele Borassi, Emanuele Natale
We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world c…
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is n…
A Note on the Complexity of Computing the Number of Reachable Vertices in a Digraph
Michele Borassi
In this work, we consider the following problem: given a digraph , for each vertex , we want to compute the number of vertices reachable from . In other words, we wa…
Fast and Simple Computation of Top-k Closeness Centralities
Michele Borassi, Pierluigi Crescenzi, Andrea Marino
Closeness is an important centrality measure widely used in the analysis of real-world complex networks. In particular, the problem of selecting the k most central nodes with respe…
Hyperbolicity Measures "Democracy" in Real-World Networks
Michele Borassi, Alessandro Chessa, Guido Caldarelli
We analyze the hyperbolicity of real-world networks, a geometric quantity that measures if a space is negatively curved. In our interpretation, a network with small hyperbolicity i…
Into the Square - On the Complexity of Quadratic-Time Solvable Problems
Michele Borassi, Pierluigi Crescenzi, Michel Habib
This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $…