Français Anglais
Accueil Annuaire Plan du site
Accueil > News du laboratoire > Séminaire DIGITEO, séance du 20/10
Séminaire DIGITEO, séance du 20/10
Séminaire DIGITEO, séance du 20/10 Séminaire DIGITEO, séance du 20/10
20 octobre 2011

Degeneracy Based Community Evaluation
Michalis Vazirgiannis, chaire Digiteo
Supélec, amphi F3.05, 14h30
Abstract
--------------
Graphs constitute the dominant data structure in the WWW, and appear essentially in all forms of
information. Examples are the web graph, social networks, protein interaction networks, terms
dependency graphs etc. Important knowledge is hidden in the macroscopic topology and features of these
graphs. The dominant knowledge artifacts extracted from graphs are either individual node based scores
(such as authority/hubness/centrality) or unsupervised grouping of nodes in to clusters or global statistics
computations (such as degree distributions etc). What is missing is metrics, structures and measures that
represent the deeper knowledge hidden in the macroscopic structure of potentially directed/weighted
graphs. We propose new metrics and evaluation schemes for the macroscopic structure of graphs
capitalizing on the degeneracy concept, i.e. k-cores, towards identifying the most cohesive components
of graphs – finding thus the most collaborative constituents. These metrics compute the most robust subgraphs
representing dense and mutual connectivity in the case of directed and weighted graphs as well.
Connectivity can be then interpreted in several ways: i.e. as collaboration in citation or social networking
graphs, collective affinity in protein interaction graphs etc. We also use the best k-cores of graphs as
seeds for optimizing the speed of spectral graph clustering. We conducted several experiments on real
(DBLP, Wikipedia) and synthetic data sets. The results are interesting especially in the case in the DBLP
citation graph. 

We further extend k-core to deal with directed graphs, introducing  the D-core concept, 
as means of evaluating  a digraph’s collaborative nature. Based on the D-core we devise a 
wealth of novel metrics used to evaluate the graphs collaboration features. 
We applied the above approaches on large real world graphs - Wikipedia and DBLP - 
and report interesting results. 

A relevant prototype demo is available at:
http://www.lix.polytechnique.fr/~giatsidis/cores/


Pour en savoir plus: http://www.digiteo.fr/Digiteo_NewsSeminaire_Michalis
News
George Manoussakis, lauréat 2018, prix de thèse (accessit) Charles Delorme
18 septembre 2018
George Manoussakis, est lauréat de prix de thèse (accessit) Ch. Delorme 2018. Il a soutenu sa thèse au LRI/Galac en Novembre 2017 sous la direction de J. Cohen et A. Deza. Depuis Septembre 2018 il est MdeC à l'Université de Versailles/Li-PaRAD.

TrackML dans Nature
21 janvier 2018
L'apprentissage automatique peut-il aider la physique des hautes énergies à découvrir et à caractériser de nouvelles particules ? TAO participe à l'organisation du challenge TrackML avec le CERN. La seconde phase de la compétition utilisera Codalab.

Un article de Isabelle Guyon sur la démocratisation de l'IA
19 mars 2018
Lien vers l'article paru dans le journal le monde :
http://www.lemonde.fr/acces-restreint/sciences/article/2018/04/08/a4544bd07cad09fe52980c0f82c08b34_5282548_1650684.html