» ÉVÈNEMENTS » Séminaires Digiteo » Précédents séminaires » Degeneracy based community evaluation - Michalis Vazirgiannis

20 octobre 2011

Degeneracy based community evaluation - Michalis Vazirgiannis

Titulaire de chaire Digiteo ; Professeur à University of Economics & Business, Grèce

Résumé

Les graphes constituent la structure dominante des données du World Wide Web et apparaissent quasiment dans toutes les formes d’informations. Des exemples en sont le graphe du web, les réseaux sociaux, les réseaux d’interaction entre protéines, les graphes de dépendances entre les termes, etc. La topologie macroscopique et les caractéristiques de ces graphes recèlent des connaissances importantes cachées.

Les principaux artefacts de connaissance extraits de ces graphes sont soit des scores individuels attribués aux nœuds (comme l’autorité, le degré d’interconnectivité ou de centralité) ou le regroupement non dirigé de nœuds en grappes ou dans des calculs statistiques globaux (comme les distributions de degré, etc.) Ce qui fait défaut, ce sont la métrique, les structures et les mesures représentant la connaissance plus profonde qui se cache dans la structure macroscopique des graphes potentiellement dirigés/pondérés.

Nous proposons une nouvelle métrique et de nouvelles modalités d’évaluation de la structure macroscopique des graphes, s’appuyant sur le concept de dégénérescence, à savoir des k-noyaux, en vue d’identifier les composants les plus cohésifs des graphes, autrement dit de trouver les constituants les plus collaboratifs. Cette métrique calcule les sous-graphes les plus robustes, représentant une connectivité dense et mutuelle, pour les graphes dirigés et pondérés aussi. La connectivité peut alors être interprétée de plusieurs manières : à savoir, comme la collaboration dans les graphes de citation ou de réseaux sociaux, comme l’affinité collective dans les graphes d’interactions entre protéines, etc. Nous utilisons aussi les meilleurs k-noyaux des graphes comme des graines pour optimiser la vitesse de l’algorithme de regroupement spectral. Nous avons conduit plusieurs expériences sur des ensembles de données réelles (DBLP, Wikipedia) et synthétiques. Ces résultats sont intéressants, particulièrement dans le cas du graphe de citation DBLP.

Nous étendons l’utilisation du k-noyau au traitement des graphes dirigés, introduisant le concept de D-noyau comme moyen d’évaluer la nature collaborative d’un graphe dirigé. À partir du D-graphe, nous développons toute une série de nouvelles mesures utilisées pour évaluer les aspects de collaboration d’un graphe. Nous avons appliqué ces approches à de grands graphes tirés du monde réel – Wikipedia et DBLP – et nous présentons des résultats intéressants.

Un prototype pertinent de démonstration peut être consulté sur : http://www.lix.polytechnique.fr/ giatsidis/cores/

JPEG - 55.2 ko

Biographie

Le Dr Vazirgiannis est professeur au LIX à l’École Polytechnique. Il possède un diplôme universitaire en physique et une maîtrise en robotique de l’université d’Athènes, ainsi qu’une maîtrise en systèmes à base de connaissances de Heriot Watt University (Edinburgh, Royaume-Uni). Il a obtenu un doctorat en 1994 (au département informatique de l’université d’Athènes). Depuis, il a mené des recherches au GMD-IPSI/Fraunhofer, Max Planck MPI (Allemagne), et à l’INRIA/FUTURS (Paris). Il a enseigné à l’université d’économie et de commerce d’Athènes (Grèce), à l’École Polytechnique, à l’école Télécom ParisTech (Paris, France) ainsi qu’à l’université Deusto (Espagne).

Ses intérêts de recherche actuels portent sur l’analyse et l’évolution des graphes Web, le contrôle du regroupement des graphes, les algorithmes pour les campagnes de publicité sur le Web et les mesures d’évaluation de la communauté. Il a participé à de nombreux projets industriels nationaux et financés par l’UE. Il a supervisé huit thèses de doctorat terminées. Il a contribué à des chapitres dans des livres et des encyclopédies, publié deux livres et plus de cent vingt articles dans des revues internationales à comité de lecture et pour des conférences. Il est aussi co-auteur de deux brevets déposés au bureau des brevets de Grèce.

Il est activement impliqué dans des projets nationaux et internationaux de recherche et développement. Il a reçu des bourses ERCIM et Marie Curie de l’UE. Il est actuellement titulaire d’une chaire scientifique Digiteo à l’École Polytechnique. Il participe au comité rédactionnel de la revue Intelligent Data Analysis et œuvre en tant que rédacteur invité pour les revues « Machine Learning » et « Data Mining & Knowledge Discovery ». Il a coprésidé le comité de programme de la conférence ECML/PKDD 2011, présidé le groupe sur l’exploration des données de la conférence IEEE - ICDE 2011 et participé à plus de cinquante conférences internationales en tant que membre du comité d’organisation, dans les domaines des bases de données, de l’exploration de données, de l’apprentissage des machines et du Web.

Pour plus d’informations, consulter : http://www.lix.polytechnique.fr/ mvazirg/index.php