Logo Università degli Studi di Milano


 

 
 
Notizie  

Ordering nodes to scale to massive real-world networks

DATA: Mar 31/01/2023
ORE: 14:30
LUOGO: Sala del Consiglio (VIII piano), via Celoria 18

SPEAKER: Fabrice Lécuyer (Sorbonne Université + LIP6, Paris)

RESPONSIBLE: Paolo Boldi

ABSTRACT

Networks can represent a variety of real-life situations (hyperlinks on the internet, trade, scientific citations...) and their ever-increasing size requires fast and scalable graph algorithms. A crucial technique consists in ordering the nodes of a graph according to some properties, such as their degree or centrality. This technique is used in state-of-the-art methods for various graph problems, among which cache optimisation, compression and pattern mining.
We present two contributions based on this method. First, we analyse the precise complexity of a triangle listing algorithm and we infer new orderings that reduce it and accelerate the listing. Second, we show how an approximation algorithm or vertex cover can leverage two distinct orderings to give better guarantees without losing on scalability.

 

18 gennaio 2023
Torna ad inizio pagina