Simplification et partitionnement d'un graphe

César Ducruet (1)

1 GC (UMR_8504) - Géographie-cités

This document from the fmr group introduces four types of methods for simplifying and/or partitioning graphs. Two methods produce tree-like structures that are easy to visualize: the minimum spanning tree (introduced among other classic methods of path detection), and the nodal regions algorithm (i.e. single or multiple linkage analysis). Two other methods provide groups of nodes characterized by a variety of structures: the filtering of links through a cohesion level based on the proportion of common neighbours of nodes, and the topological decomposition (i.e. looking at links among nodes having similar degree centrality). The application of the two latter methods in geography remains rather limited.

Ce document du groupe fmr (flux, matrices, réseaux) présente quatre méthodes de simplification et/ou de partitionnement de graphes. Deux d'entre elles produisent des structures en arbre facilement visualisables : l'arbre d'étendue minimum (l'une des méthodes possibles de recherche d'un chemin reliant tous les sommets) et l'algorithme des régions nodales (flux majeurs ou dominants). Deux autres méthodes produisent des sous-graphes caractérisés par des structures variées : le filtrage des liens par l'application d'un indice de cohésion basé sur la proportion de voisins communs, et la décomposition topologique (liens entre sommets de degré comparable). L'application par les géographes de ces deux dernières méthodes reste encore limitée.

Mots clés: graph partitioning; network; subgraph; group fmr

Mots clés: partitionnement de graphe; réseau; sous-graphe; groupe fmr

Domaines: Géographie

César Ducruet. Simplification et partitionnement d'un graphe. 2011. ⟨halshs-00579065⟩