Michele Borassi

Michele Borassi

Auto-generated profile, based on publicly available information

Michele Borassi

IMT Insitute for Advanced Studies 55100 Lucca Italy

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 June 2015 in Theoretical Computer Science
Verified
Journal Article
Closed access
MBMichele Borassi
Michele Borassi
PCPierluigi Crescenzi
Pierluigi Crescenzi
MHMichel Habib
Michel Habib
WKWalter A. Kosters
Walter A. Kosters
Andrea MarinoAndrea Marino
Andrea Marino
FTFrank W. Takes
Frank W. Takes

1 October 2016 in Information Processing Letters
Verified
Journal Article
Closed access
MBMichele Borassi
Michele Borassi

1 January 2013 in Lecture Notes in Computer Science
Verified
Book Chapter
Closed access
PDF file
MBMichele Borassi
Michele Borassi
PCPierluigi Crescenzi
Pierluigi Crescenzi
VLVincent Lacroix
Vincent Lacroix
Andrea MarinoAndrea Marino
Andrea Marino
MSMarie-France Sagot
Marie-France Sagot
PMPaulo Vieira Milreu
Paulo Vieira Milreu

12 August 2016 in arXiv
Verified
Preprint
Open access
PDF file
MBMichele Borassi
Michele Borassi
ENEmanuele Natale
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 complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time $|E|^{\frac{1}{2}+o(1)}$ with high probability, obtaining a significant speedup with respect to the $\Theta(|E|)$ worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the $k$ most central nodes. Furthermore, our analysis is general, and it might be extended to other settings.

18 July 2014 in arXiv
Verified
Preprint
Open access
PDF file
MBMichele Borassi
Michele Borassi
Pierluigi CrescenziPierluigi Crescenzi
Pierluigi Crescenzi
MHMichel Habib
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 $O(n^{2-\epsilon})$ for some $\epsilon>0$) and problems that are not, unless the well known Strong Exponential Time Hypothesis (SETH) is false. In particular, we will prove that some quadratic-time solvable problems are indeed easier than expected. We will provide an algorithm that computes the transitive closure of a directed graph in time $O(mn^{\frac{\omega+1}{4}})$, where $m$ denotes the number of edges in the transitive closure and $\omega$ is the exponent for matrix multiplication. As a side effect, we will prove that our algorithm runs in time $O(n^{\frac{5}{3}})$ if the transitive closure is sparse. The same time bounds hold if we want to check whether a graph is transitive, by replacing m with the number of edges in the graph itself. As far as we know, this is the fastest algorithm for sparse transitive digraph recognition. Finally, we will apply our algorithm to the comparability graph recognition problem (dating back to 1941), obtaining the first truly subquadratic algorithm. The second part of the paper deals with hardness results. Starting from an artificial quadratic-time solvable variation of the k-SAT problem, we will construct a graph of Karp reductions, proving that a truly subquadratic-time algorithm for any of the problems in the graph falsifies SETH. The analyzed problems are the following: computing the subset graph, finding dominating sets, computing the betweenness centrality of a vertex, computing the minimum closeness centrality, and computing the hyperbolicity of a pair of vertices. We will also be able to include in our framework three proofs already appeared in the literature, concerning the graph diameter computation, local alignment of strings and orthogonality of vectors.

10 March 2015 in arXiv
Verified
Preprint
Open access
PDF file
MBMichele Borassi
Michele Borassi
ACAlessandro Chessa
Alessandro Chessa
GCGuido Caldarelli
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 is "aristocratic", because it contains a small set of vertices involved in many shortest paths, so that few elements "connect" the systems, while a network with large hyperbolicity has a more "democratic" structure with a larger number of crucial elements. We prove mathematically the soundness of this interpretation, and we derive its consequences by analyzing a large dataset of real-world networks. We confirm and improve previous results on hyperbolicity, and we analyze them in the light of our interpretation. Moreover, we study (for the first time in our knowledge) the hyperbolicity of the neighborhood of a given vertex. This allows to define an "influence area" for the vertices in the graph. We show that the influence area of the highest degree vertex is small in what we define "local" networks, like most social or peer-to-peer networks. On the other hand, if the network is built in order to reach a "global" goal, as in metabolic networks or autonomous system networks, the influence area is much larger, and it can contain up to half the vertices in the graph. In conclusion, our newly introduced approach allows to distinguish the topology and the structure of various complex networks.