Laboratoire d'informatique de l'École polytechnique

The laboratory LIX

The abbreviation LIX stands for Laboratoire d'Informatique de l'Ecole polytechnique (Laboratory of Informatics of the École polytechnique), where the letter X represents the Polytechnique per French tradition. LIX is a mixed research unit (UMR 7161) consisting of two tutelles: the École polytechnique and the National Center for Scientific Research (CNRS). LIX falls under the jurisdiction of the INS2I division (which stands for the National Institute of Sciences of Information and their Interactions) of CNRS.

Sémin'Ouvert : « Graph degeneracy for citation networks exploration », par Michalis Vazirgiannis

Community subgraphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In our research, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results. We further extend introduce novel metrics for evaluating the collaborative nature of /directed graphs/ and define a novel /D-core/ framework, extending the classic graph-theoretic notion of k-cores for undirected graphs to directed ones. Based on the D-core, which essentially can be seen as a measure of the robustness of a community under degeneracy, we devise a wealth of novel metrics used to evaluate graph collaboration features of directed graphs. We applied the D-core approach on large real-world graphs such as Wikipedia and aminer.org citation data and report interesting results. The D-core metric has been adopted by aminer as part of its reported metrics - see an example here.