Alexis est doctorant dans l’équipe Complex/Networks du LIP6. Son intervention aura lieu dans la salle G119 de l’ESIREM et  portera sur le calcul de communautés dans un graphe par percolation de cliques.

Résumé : La détection automatique de groupes de nœuds pertinents dans de grands graphes du monde réel, c’est-à-dire la détection de communautés, a des applications dans de nombreux domaines et a fait l’objet d’une grande attention au cours des vingt dernières années. L’une des méthodes les plus populaires conçues pour trouver des communautés qui se chevauchent (où un nœud peut appartenir à plusieurs communautés) est la méthode de percolation des cliques (CPM). Cette méthode formalise la notion de communauté comme une union maximale de 𝑘-cliques qui peuvent être atteintes les unes des autres par une série de 𝑘-cliques adjacentes, où deux cliques sont adjacentes si et seulement si elles se chevauchent sur 𝑘-1 nœuds. Malgré de nombreux efforts, CPM n’a pas pu être adapté à de grands graphes pour des valeurs moyennes de 𝑘. Des travaux récents ont montré qu’il est possible de lister efficacement toutes les 𝑘-cliques dans de très grands graphes du monde réel pour des valeurs moyennes de 𝑘. Nous nous appuyons sur ces travaux pour améliorer un algorithme de CPM. Dans les cas où ce premier algorithme fait face à des limitations de mémoire, nous proposons un autre algorithme, CPMZ, qui fournit une solution proche de la solution exacte, en utilisant plus de temps mais moins de mémoire.

kc_data:

a:8:{i:0;s:0:"";s:4:"mode";s:0:"";s:3:"css";s:0:"";s:9:"max_width";s:0:"";s:7:"classes";s:0:"";s:9:"thumbnail";s:0:"";s:9:"collapsed";s:0:"";s:9:"optimized";s:0:"";}

kc_raw_content:

Alexis est doctorant dans l'équipe Complex/Networks du LIP6. Son intervention aura lieu dans la salle G119 de l'ESIREM et  portera sur le calcul de communautés dans un graphe par percolation de cliques.

Résumé : La détection automatique de groupes de nœuds pertinents dans de grands graphes du monde réel, c’est-à-dire la détection de communautés, a des applications dans de nombreux domaines et a fait l’objet d’une grande attention au cours des vingt dernières années. L’une des méthodes les plus populaires conçues pour trouver des communautés qui se chevauchent (où un nœud peut appartenir à plusieurs communautés) est la méthode de percolation des cliques (CPM). Cette méthode formalise la notion de communauté comme une union maximale de 𝑘-cliques qui peuvent être atteintes les unes des autres par une série de 𝑘-cliques adjacentes, où deux cliques sont adjacentes si et seulement si elles se chevauchent sur 𝑘-1 nœuds. Malgré de nombreux efforts, CPM n’a pas pu être adapté à de grands graphes pour des valeurs moyennes de 𝑘. Des travaux récents ont montré qu’il est possible de lister efficacement toutes les 𝑘-cliques dans de très grands graphes du monde réel pour des valeurs moyennes de 𝑘. Nous nous appuyons sur ces travaux pour améliorer un algorithme de CPM. Dans les cas où ce premier algorithme fait face à des limitations de mémoire, nous proposons un autre algorithme, CPMZ, qui fournit une solution proche de la solution exacte, en utilisant plus de temps mais moins de mémoire.

entete_extrait:

lien_externe: