Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Partitionnement de graphe
Résumé
En théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. Plusieurs propriétés peuvent être recherchées pour ce découpage, par exemple on peut minimiser le nombre d'arêtes liant deux parties différentes. Coupe maximum et Coupe minimum sont deux exemples communs de partitionnement de graphe.
Une partition d'un graphe est une partition de ses nœuds, ou plus rarement de ses arêtes. Si le nombre de groupes dans la partition est fixé à un entier k, on parle de k-partition. Pour k=2, on parle parfois de bisection.
Le partitionnement est le fait de calculer une partition. Le plus souvent le partitionnement de graphe consiste à créer une subdivision de l'ensemble des sommets de S en k sous ensembles de tailles réduites de façon à minimiser un ou plusieurs critères.
On peut considérer plusieurs objectifs pour les partitionnements.
On cherche le plus souvent à minimiser une quantité liée à la coupe, c'est-à-dire le nombre d'arêtes dont les extrémités ne sont pas dans le même groupe, avec certaines contraintes sur les propriétés des groupes eux-mêmes. Par exemple, on peut minimiser la taille de la coupe avec la contrainte que les groupes doivent être de même taille (plus ou moins un).
D'autres fonctions objectifs sont le ratio de coupe et la coupe normalisée.
La plupart des problèmes de partitionnement de graphe sont NP-difficile, c'est pourquoi des algorithmes utilisant une heuristique ou des algorithmes d'approximations sont souvent utilisés pour résoudre des problèmes de partitionnement de graphe.
Parmi les méthodes classiques de partitionnement, on compte les méthodes inertielles (comme k-moyennes), le partitionnement spectral et des méthodes locales d'échange de points entre clusters (dans le même esprit que heuristique de Lin-Kernighan pour le problème du voyageur de commerce).
Un algorithme de partitionnement multiniveau de graphe fonctionne en appliquant une ou plusieurs étapes.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (1)
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
Publications associées (28)
The Power of Two Matrices in Spectral Algorithms for Community Recovery
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...
Ieee-Inst Electrical Electronics Engineers Inc2024Annihilation Filter Approach For Estimating Graph Dynamics From Diffusion Processes
Pascal Frossard, Arun Venkitaraman
We propose an approach for estimating graph diffusion processes using annihilation filters from a finite set of observations of the diffusion process made at regular intervals. Our approach is based on the key observation that a graph diffusion process can ...
IEEE2022Motif Cut Sparsifiers
Mikhail Kapralov, Mikhail Makarov, Jakab Tardos
A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...
IEEE COMPUTER SOC2022Personnes associées (3)