Première partie.
Définitions et état de l'art
La première partie a pour but de donner au lecteur les
éléments nécessaires à la compréhension de
ce mémoire et d'effectuer un état de l'art des technologies de
regroupement.
Le premier chapitre introduit les graphes et leurs
caractéristiques. Cette partie ne se veut en rien exhaustive. Au
contraire, nous ne couvrons ici que les notions présentes dans ce
travail. Il est conseillé au lecteur recherchant des informations plus
complètes sur les graphes de se référer à d'autres
ouvrages tels que « Théorie des graphes et ses applications
» de Claude Berge [Berge-1958] ou encore du
même auteur « Graphes et hypergraphes »
[Berge-1970] et enfin de Béllé Bolllobas
« Modern Graph Theory »
[Bollobas-1998]. Dans ce chapitre, nous explicitons
aussi, autant que faire se peut, en avant-propos, les termes spécifiques
utilisés et tentons de les situer et d'en évaluer la
pertinence.
Dans un second chapitre, nous effectuons un état de
l'art des diverses méthodes de détection de communautés
dans les graphes. Nous tentons de cerner leurs intérêts et leurs
limites.
1.1. Introduction 27
Chapitre 1. État de l'art, notions, définitions et
vocabulaire sur les graphes
Chapitre 1.
État de l'art, notions, définitions
et vocabulaire sur les graphes
1.1 Introduction
Manuel Castells, sociologue américain, définit
Internet comme le « ... produit d'une combinaison unique de
stratégie militaire, de coopération scientifique et d'innovation
contestataire ». Ce qui est notable dans cette définition
amusante est la diversité des composantes d'Internet. Cette
diversité est un facteur de croissance. D'une manière plus
générale, les réseaux créés à des
fins d'utilisation, tels que les transports en commun, le mail, le
téléphone, ou le « cloud computing », ont souvent des
croissances d'usage exponentielles et ceci d'autant plus que leurs clients sont
hétérogènes. Devenus populaires, les réseaux se
mettent à porter des noms, quelquefois des noms de marques et parfois
même des noms propres comme Internet. Identifiés, utilisés
par tous, ces réseaux offrent l'attrait de nouveaux usages.
Pour symboliser ces réseaux constitués, par
définition, d'objets en relation les uns avec les autres, on utilise le
plus souvent une représentation sous forme de « graphes ».
L'étude des graphes ou « Théorie des graphes » est en
premier lieu une théorie mathématique. Mais l'importance de ces
réseaux dans notre quotidien pousse de plus en plus les femmes et les
hommes « de l'art » à les étudier. Ainsi, nombre
d'informaticiens étudient Internet en passant par des
représentations graphiques et nombre de sociologues utilisent les
graphes dans des études de réseaux sociaux, par exemple. Les
graphes ont leurs règles, leurs vocables et leur histoire. C'est de ces
éléments dont nous allons traiter dans ce chapitre.
1.2. Historique 28
Chapitre 1. État de l'art, notions, définitions et
vocabulaire sur les graphes
| 
