%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{A. Castillon : Compression de graphes en utilisant les quasi-cliques}
%

% Pour le sommaire
\addcontentsline{toc}{section}{A. Castillon : Compression de graphe en utilisant les quasi-cliques}
%

% Pour la liste des auteurs
\index{Castillon, A.}
%

% Citer un par un les auteurs et leur affiliation
Julien Baste, CRIStAL, Lille, {\tt julien.baste@univ-lille.fr}\\
\indent \underline{Antoine Castillon}, ENS de Lyon, Lyon, {\tt antoine.castillon@ens-lyon.fr}\\
\indent Mohammed Haddad, LIRIS, Lyon, {\tt mohammed.haddad@univ-lyon1.fr}\\
\indent Hamida Seba, LIRIS, Lyon, {\tt hamida.seba@univ-lyon1.fr} \\
%souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

En 2020, Wang et al. \cite{nk1}, ont introduit une nouvelle méthode de compression sans perte d'information en utilisant les quasi-cliques. La compression d'un graphe se fait pour chaque quasi-clique de la façon suivante: on garde en mémoire tous les sommets qui la composent ainsi que les paires de sommets non adjacents. Pour des quasi-cliques de densité supérieure à $0.5$ il est clair que cette représentation est moins coûteuse que de stocker toutes les arêtes.

\smallskip

Nous avons étudié cette méthode de compression en nous concentrant surtout sur la phase de détection des quasi-cliques. Nous nous sommes d'abord intéressés au Quasi-Clique Enumeration Problem (QCE), qui est le problème d'énumération de toutes les quasi-cliques d'un graphe. En nous basant sur l'algorithme Quick \cite{nk2}, nous avons proposé une nouvelle technique de pré-calcul permettant d'accélérer significativement la résolution de ce problème. L'énumération de toutes les quasi-cliques d'un graphe pouvant conduire à des redondances lors de la compression, nous avons ensuite étudié comment mieux adapter la phase de détection des quasi-cliques à la compression du graphe. Nous nous sommes donc intéressé à d'autres problèmes de détection de quasi-cliques où l'on impose une certaine diversité des résultats \cite{nk3} ainsi qu'à leur application à la compression.


%Cette méthode de compression repose sur la détection des quasi-cliques. Ce problème appelé Quasi-Clique Enumeration Problem (QCE) est le problème d'énumération de toutes les quasi-cliques d'un graphe.

\begin{thebibliography}{99}

\bibitem{nk1}
Wang et al, \emph{Dense Subgraphs Summarization: An Efficient Way to Summarize Large Scale Graphs
by Super Nodes}, Intelligent Computing Methodologies (2020), 520-530.

\bibitem{nk2}
Liu and Wong, \emph{Effective Pruning Techniques for Mining Quasi-Cliques}, (2008), DOI: $10.1007/978-3-540-87481-2\_3$

\bibitem{nk3}
Wang et al, \emph{Redundancy-Aware Maximal Cliques}, Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2013), 122-130.

\end{thebibliography}


\vfill
\end{document}
