Source author record

Matteo Pontecorvi

Matteo Pontecorvi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Cryptography and Security

Catalog footprint

What is connected

5works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Fully Dynamic All Pairs All Shortest Paths

We consider the all pairs all shortest paths (APASP) problem, which maintains all of the multiple shortest paths for every vertex pair in a directed graph $G=(V,E)$ with a positive real weight on each edge. We present two fully dynamic algorithms for this problem in which an update supports either weight increases or weight decreases on a subset of edges incident to a vertex. Our first algorithm runs in amortized $O({ν^*}^2 \cdot \log^3 n)$ time per update, where $n = |V|$, and $ν^*$ bounds the number of edges that lie on shortest paths through any single vertex. Our APASP algorithm leads to the same amortized bound for the fully dynamic computation of betweenness centrality (BC), which is a parameter widely used in the analysis of large complex networks. Our method is a generalization and a variant of the fully dynamic algorithm of Demetrescu and Italiano [DI04] for unique shortest path, and it builds on our recent decremental APASP [NPR14]. Our second (faster) algorithm reduces the amortized cost per operation by a logarithmic factor, and uses new data structures and techniques that are extensions of methods in a fully dynamic algorithm by Thorup.

preprint2020arXiv

BAD: Blockchain Anomaly Detection

Anomaly detection tools play a role of paramount importance in protecting networks and systems from unforeseen attacks, usually by automatically recognizing and filtering out anomalous activities. Over the years, different approaches have been designed, all focused on lowering the false positive rate. However, no proposal has addressed attacks targeting blockchain-based systems. In this paper we present BAD: the first Blockchain Anomaly Detection solution. BAD leverages blockchain meta-data, named forks, in order to collect potentially malicious activities in the network/system. BAD enjoys the following features: (i) it is distributed (thus avoiding any central point of failure), (ii) it is tamper-proof (making not possible for a malicious software to remove or to alter its own traces), (iii) it is trusted (any behavioral data is collected and verified by the majority of the network) and (iv) it is private (avoiding any third party to collect/analyze/store sensitive information). Our proposal is validated via both experimental results and theoretical complexity analysis, that highlight the quality and viability of our Blockchain Anomaly Detection solution.

preprint2015arXiv

A Faster Algorithm for Fully Dynamic Betweenness Centrality

We present a new fully dynamic algorithm for maintaining betweenness centrality (BC) of vertices in a directed graph $G=(V,E)$ with positive edge weights. BC is a widely used parameter in the analysis of large complex networks. We achieve an amortized $O((ν^*)^2 \log^2 n)$ time per update, where $n = |V| $ and $ν^*$ bounds the number of distinct edges that lie on shortest paths through any single vertex. This result improves on the amortized bound for fully dynamic BC in [Pontecorvi-Ramachandran2015] by a logarithmic factor. Our algorithm uses new data structures and techniques that are extensions of the method in the fully dynamic algorithm in Thorup [Thorup2004] for APSP in graphs with unique shortest paths. For graphs with $ν^* = O(n)$, our algorithm matches the fully dynamic APSP bound in [Thorup2004], which holds for graphs with $ν^* = n-1$, since it assumes unique shortest paths.

preprint2014arXiv

Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G=(V,E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(\vstar^2 \cdot \log n) time per update, where n=|V|, and \vstar bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of betweenness centrality (BC), a graph parameter that is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [DI04] for unique shortest paths, and for graphs with \vstar =O(n), we match the bound in [DI04]. Thus for graphs with a constant number of shortest paths between any pair of vertices, our algorithm maintains APASP and BC scores in amortized time O(n^2 \log n) under decremental updates, regardless of the number of edges in the graph.

preprint2013arXiv

Betweenness Centrality -- Incremental and Faster

We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm to compute the betweenness centrality of all vertices in G is the Brandes algorithm that runs in O(mn + n^2 log n) time, where n = |V| and m = |E|. We present an incremental algorithm that updates the betweenness centrality score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m' n + n^2) time, where m' is the size of a certain subset of E*, the set of edges in G that lie on a shortest path. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm. Our algorithm is also likely to be much faster than the Brandes algorithm on dense graphs since m*, the size of E*, is often close to linear in n. Our incremental algorithm is very simple and the only data structures it uses are arrays, lists, and stack. We give an efficient cache-oblivious implementation that incurs O(scan(n^2) + n sort(m')) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static algorithm for computing betweenness centrality of all vertices that runs in time O(m* n + n^2 log n), which is faster than the Brandes algorithm on any graph with n log n = o(m) and m* = o(m).