A Neighborhood-preserving Graph Summarization

Kiouche, Abd Errahmane; Baste, Julien; Haddad, Mohammed; Seba, Hamida

Type de document :

Pré-publication ou Document de travail

Titre :

A Neighborhood-preserving Graph Summarization

Auteur(s) :

Kiouche, Abd Errahmane [Auteur]
Graphes, AlgOrithmes et AppLications [GOAL]
Baste, Julien [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Haddad, Mohammed [Auteur]
Graphes, AlgOrithmes et AppLications [GOAL]
Seba, Hamida [Auteur]
Graphes, AlgOrithmes et AppLications [GOAL]

Discipline(s) HAL :

Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Autre [cs.OH]

Résumé en anglais : [en]

We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the graph. Our main aim is to simplify large ...
Lire la suite >We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the graph. Our main aim is to simplify large graphs so that they can be analyzed and processed effectively while preserving as many of the node neighborhood properties as possible. Since many graph algorithms are based on the neighborhood information available for each node, the idea is to produce a smaller graph which can be used to allow these algorithms to handle large graphs and run faster while providing good approximations. Moreover, our compression allows users to control the size of the compressed graph by adjusting the amount of information loss that can be tolerated. The experiments conducted on various real and synthetic graphs show that our compression reduces considerably the size of the graphs. Moreover, we conducted several experiments on the obtained summaries using various graph algorithms and applications, such as node embedding, graph classification and shortest path approximations. The obtained results show interesting trade-offs between the algorithms runtime speed-up and the precision loss.Lire moins >

Langue :

Anglais

Projet ANR :

COmpression de REseaux et de GRAPHes pour une Informatique Efficace

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

http://arxiv.org/pdf/2101.11559
Accès libre
Accéder au document

2101.11559
Accès libre
Accéder au document

A Neighborhood-preserving Graph Summarization BibTeX CSV Excel RIS

Fichiers

A Neighborhood-preserving Graph Summarization

BibTeX

CSV

Excel

RIS