Soutenance mémoire
Le monde qui nous entoure peut être vu comme un ensemble d’interactions entre éléments, qui peuvent être d’origine naturelle et concrète, par exemple des contacts entre être humains, ou bien basées sur des constructions plus abstraites comme les interactions économiques régissant les marchés financiers. Elles peuvent avoir lieu à l’échelle microscopique, telles les interactions entre protéines en permanence à l’œuvre dans notre corps, ou au contraire à une échelle macroscopique à l’instar des interactions gravitationnelles entre corps célestes.
Ces interactions ou ensembles d’interactions, appelés systèmes complexes (Vicsek, 2002), sont étudiés dans de nombreux domaines scientifiques : sociologie, physique, économie, biologie… Si les plus simples ont pu être expliquées au fil du temps, une grande majorité d’entre elles échappe encore à une modélisation qui les rendrait prédictibles : un exemple connu est la théorie cinétique des gaz en thermodynamique qui constitue encore aujourd’hui un objet de recherche intense en mathématiques et en sciences physiques.
Les outils et modèles développés ont traditionnellement été apportés par les mathématiques, par exemple sous la forme d’équations analytiques, algèbre matricielle… Avec le développement au XXème siècle de la théorie des graphes, de nouvelles méthodes d’étude des systèmes complexes ont vu le jour en formalisant les interactions comme des réseaux dont les éléments forment les sommets et les arêtes représentent la présence, le type, la force, ou autres paramètres, de l’interaction. Ces réseaux spécifiques sont nommés complex networks (Newman, 2003), littéralement réseaux complexes, ou plus fréquemment en français graphes de terrain, car ils sont utilisés afin de modéliser une situation réelle, « de terrain ». Ils ont l’avantage de présenter un modèle simple, accessible aux scientifiques non spécialistes en mathématiques : chaque sommet est représenté par un disque et chaque arête par une ligne joignant deux disques. De nombreuses visualisations sont donc envisageables (Scott, 2012).
Ces graphes de terrain sont utilisés dans tous les domaines de la science cités précédemment (Wasserman & Faust, 1994,Knoke, 2014), et bien d’autres, motivant en conséquence le développement de méthodes visant à les analyser, en particulier concernant les interactions à très large échelle dont il résulte de très grands graphes de terrain : à la décennie des big data, l’échelle du milliard de sommets est en voie d’être dépassée. Ils ne peuvent être analysés « à la main », comme le furent les premiers réseaux sociaux par exemple (Moreno & Jennings, 1938), en premier lieu pour une raison évidente de taille, mais également de compréhension des processus à l’œuvre : les interactions ayant lieu à différentes échelles, du voisinage entre éléments à une échelle globale très large pouvant impliquer des milliards d’éléments simultanément, il est très difficile voire impossible de les appréhender.
Une tâche très courante d’analyse des graphes de terrain, qui a engendré une littérature prolifique ces vingt dernières années, est la détection de communautés (Fortunato, 2009). Il s’agit de trouver dans un graphe des ensembles d’éléments interagissant plus particulièrement entre eux qu’avec le reste du graphe, formant ainsi les dénommées communautés. Cette notion de communauté est héritée de la sociologie mais revêt un sens beaucoup plus général dont il n’existe pas de définition universelle. On comprend aisément que la forme des communautés diffère selon les domaines : communautés sociologiques, protéines interagissant spécifiquement et fréquemment, acteur économiques liés… on pourrait définir une variété de communautés par graphe étudié. Cette solution ne serait bien évidemment pas satisfaisante, et une partie du travail lié à la détection de communautés dans des graphes de terrain est de poser une définition à la fois suffisamment générale pour qu’elle puisse être appliquée de façon générique à un grand nombre de graphes, mais tout de même particulière car aucune définition ne peut recouvrir l’ensemble des graphes de terrain.
Rappels et notations à propos des graphes
Cette section rappelle quelques définitions classiques de la théorie des graphes, telles qu’elles peuvent par exemple être trouvées dans des ouvrages de référence (Gondran & Minoux, 1995, Newman, 2003, Barabási, 2016), et introduit les notations utilisées dans la thèse. La première sous-section donne quelques définitions générales décrivant ce qu’est un graphe, en tant qu’objet mathématique, la seconde présente quelques éléments topologiques caractéristiques des graphes et la troisième quelques caractéristiques numériques.
Définitions élémentaires
Nous présentons ici des définitions générales d’éléments mathématiques utilisés dans l’ensemble du manuscrit.
Graphe
Un graphe G est défini comme un couple G = (V, E) composé d’un ensemble de sommets V (vertices en anglais) et d’un ensemble d’arêtes E (edges) reliant certaines paires de sommets de V . Formellement, E ⊆ V × V . Nous considérons le cas de graphes finis, c’est-à-dire ayant un nombre fini de sommets et d’arêtes et notons n = |V | et m = |E|.
Incidence, degré, adjacence, voisinage
Le nombre d’arêtes incidentes à un sommet v, c’est-à-dire telles que v constitue une de ses extrémités, est appelé degré de v, noté d(v) ou dv. Deux arêtes incidentes à un même sommet sont dites adjacentes. Les sommets avec lesquels v partage une arête sont appelés les voisins (neighbours) de v et sont notés Γ(v). Deux sommets reliés par une arête sont donc voisins, on les dit également adjacents. On peut représenter le graphe G sous la forme d’une matrice d’adjacence A de taille n×n, où chaque Ai,j vaut 1 ou 0 selon qu’il existe ou non une arête entre les sommets i et j.
Sous-graphe
Un graphe H = (VH, EH) est un sous-graphe de G = (VG, EG) si et seulement si VH ⊆ VG et EH ⊆ EG. G est alors appelé le super-graphe de H. H est dit induit par VH si ∀u, v ∈ VH,(u, v) ∈ EG ⇔ (u, v) ∈ EH, autrement dit on définit H uniquement par l’ensemble de ses sommets VH et il contient implicitement toutes les arêtes du super-graphe G incidentes à deux extrémités de ces sommets.
Orientation, pondération, complétude
Les arêtes peuvent avoir un sens, amenant par exemple à distinguer pour l’arête (u, v) les sens u → v et v → u. Dans ce cas on les appelle arcs et le graphe G est dit orienté. On distingue alors pour un sommet v un arc entrant (aboutissant à v) d’un arc sortant (issu de v). Par exemple l’arc (u → v) est un arc entrant pour v et sortant pour u. Le degré entrant din de v (resp. sortant dout) est ainsi le nombre d’arcs entrants (resp. sortants) de v.
Une arête (u, u) joignant un sommet à lui-même est appelée boucle (loop ou self loop). Les arêtes peuvent également se voir affecter un poids –entier ou réel, positif ou négatif– et le graphe est alors dit pondéré (weighted).
Chaînes, chemins, cycles, circuits, cliques
Nous donnons ici quelques définitions supplémentaires utiles pour comprendre le manuscrit. On considère un graphe G = (V, E).
Définition Une chaîne est une suite d’arêtes successivement adjacentes. Formellement, une chaîne S de taille p reliant u à v est une suite de p arêtes de E, S= {ei , i = 0..p − 1} avec e0 = (u, s1), e1 = (s1, s2), …, ep−2 = (sp−2, sp−1), ep−1 = (sp−1, v). Chaque arête ei ∈ S, 0 ≤ i < p est donc incidente à un sommet auquel est également incidente l’arête ei+1. Une chaîne est dite élémentaire si elle ne passe pas deux fois par le même sommet. Tout graphe comportant au moins deux sommets possède au moins une chaîne élémentaire. Une chaîne est appelée walk en anglais, une chaîne élémentaire trail ou path .
Définition Un chemin est une chaîne dans un graphe orienté, autrement dit une suite d’arcs successivement adjacents : formellement, un chemin T de taille p reliant u à v est un ensemble d’arcs T ⊆ A, T = {(u → t1),(t1 → t2)…(tp−2 → tp−1),(tp−1 → v)}. Chaque arc ai ∈ T, 0 ≤ i < p est donc entrant sur un sommet pour lequel l’arc ti+1 est sortant. Un chemin peut être élémentaire au même sens qu’une chaîne s’il ne passe pas deux fois par le même sommet. Un chemin est appelé directed path en anglais.
Définition Un cycle est une chaîne dont les sommets de départ et d’arrivée sont identiques. Formellement, une chaîne S est donc un cycle si :
S = {(u, s1),(s1, s2)…(sp−2, sp−1),(sp−1, u)}
Un cycle peut être élémentaire au même sens qu’une chaîne s’il ne passe pas deux fois par le même sommet. Un cycle est appelé closed walk en anglais, l’appellation cycle désignant généralement un cycle élémentaire.
Définition Un circuit est un cycle orienté, i.e. un chemin dont les sommets de départ et d’arrivée sont identiques. Formellement, un chemin T est donc un circuit si :
T = {(u → s1),(s1 → s2)…(sp−2 → sp−1),(sp−1 → u)}
Un circuit peut être élémentaire au même sens qu’une chaîne et qu’un cycle s’il ne passe pas deux fois par le même sommet. Un circuit est dit minimal s’il n’est inclus dans aucun autre. Un circuit est appelé directed cycle en anglais, l’appellation circuit étant ambiguë car pouvant référer à un directed cycle aussi bien qu’à une closed walk permettant les répétitions.
Définition Une clique c d’un graphe G = (V, E) est un sous-ensemble de sommets dont chacun est connecté à tous les autres dans G : c ⊆ V, ∀u ∈ c, ∃v 6= u ∈ c / (u, v) ∈ E
|
Table des matières
Introduction générale
Chapitre 1 Contexte et application considérés
1.1 Rappels et notations à propos des graphes
1.2 Graphes de terrain
1.3 La tâche de détection de communautés
1.4 Contexte applicatif : routage dans des réseaux mobiles opportunistes sociaux
1.5 Bilan
Chapitre 2 Etat de l’art : détection de communautés disjointes
2.1 Communautés disjointes vs. recouvrantes
2.2 Méthodes de fouille de graphes précurseures
2.3 Caractéristiques des méthodes existantes
2.4 Principales familles de méthodes de détection disjointe
2.5 Les méthodes orientées-sommet
2.6 Bilan
Chapitre 3 VOLCAN : détection de communautés disjointes
3.1 Objectifs et caractéristiques
3.2 Description de l’algorithme
3.3 Implémentation décentralisée
3.4 Etude théorique
3.5 Etude expérimentale
3.6 Bilan
Chapitre 4 LOCNeSs : détection de communautés recouvrantes
4.1 Sommets multi-appartenants, communautés recouvrantes
4.2 Etat de l’art
4.3 Algorithme LOCNeSs
4.4 Etude expérimentale
4.5 Bilan
Chapitre 5 Méthodes de détection pour le cas dynamique
5.1 Motivations
5.2 Représentations de graphes dynamiques et modèles d’évolution
5.3 Détection de communautés sur collection d’instantanés
5.4 Bilan
Conclusion générale
Télécharger le rapport complet
