<div dir="ltr"><p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><b><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Candidate
Profile: </span></b></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Master
degree or Engineer in computer science, mathematics or physics with</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">strong
skills in graph algorithms/network science / Data Science/data mining and
programming in</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Python/C++/Java.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><b><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Financing
Institution: </span></b></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">ANR
Contract Coregraphie (ANR-20-CE23-0002)</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Application
Deadline: June 25, 2021</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Contract
starts: October 01, 2021</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><b><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Supervisors:
</span></b></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">H.
Cherifi (LIB, Dijon), H. Séba (LIRIS, Lyon), O. Togni (LIB, Dijon)</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><b><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Contacts:
</span></b></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""><a href="mailto:hocine.cherifi@u-bourgogne.fr">hocine.cherifi@u-bourgogne.fr</a>,
<a href="mailto:hamida.seba@univ-lyon1.fr">hamida.seba@univ-lyon1.fr</a>, olivier.togni@u-</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span style="font-size:11pt;font-family:"CMU Serif Roman""><a href="http://bourgogne.fr">bourgogne.fr</a></span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><b><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Subject:
</span></b></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">In this
Big Data world, we face the central issue of processing massive graphs. The
approach considered in the ANR project Coregraphie is to build a summary (or
compressed version) of the graph and to query this summary instead of the
original graph. </span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">One can distinguish
between lossless and lossy compression techniques. Lossless compression (or
compact coding) decreases the size of the graph representation without losing
any information while controlling the cost induced by coding on the operations,
like, for instance, in WebGraph [BV04].</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Lossy compression
allows a part of the information (nodes and edges) to be lost. If the
compression is by deleting edges, one speaks of sparsification. This subclass
of lossy compression allows more effective requests, such as estimating the
distance between two nodes [KB+21]. Lossy compression is mainly accomplished
using two approaches: Selecting a sample, i.e., a sub-graph using different
technics (random walks, propagation, filtering, etc.) [HL13] and grouping
nodes/edges (generalization) [CR15]. In most cases, lossy compression methods are
specialized for one type of request [FL+12].</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">One major issue
for lossy compression is determining to which extent the compression algorithms
damage the initial graph and how this damage can be measured and controlled. This
thesis aims to concentrate on lossy compression. We plan to investigate the
impact of compression methods on the graph topological properties and/or
requests performed. We propose approaching this issue starting with simple
requests such as testing neighborhoods or proximity between nodes. We will then
study more complex requests such as finding a given size clique, clustering
[QK15] or partitioning the graph into independent sets [T19]. </span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Among further
aspects that can be explored are:</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span style="font-size:11pt;font-family:Symbol">·</span><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> The links with lossless compression
and combined approaches;</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span style="font-size:11pt;font-family:Symbol">·</span><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> Links with structural properties,
in particular with some orders/hierarchies ((k-</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">shells,
k-trusses, modular decomposition, twin-width, etc.);</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span style="font-size:11pt;font-family:Symbol">·</span><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> Links with community structure and centrality
measures [GC+20];</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span style="font-size:11pt;font-family:Symbol">·</span><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> Compromises between preserving
properties and anonymizing [MRT20].</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">The main
application domain is social networks. Indeed, the LIB lab has the</span></p>
<p style="margin:0cm;text-align:justify;font-size:12pt;font-family:"Times New Roman",serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">scientific
environment to handle massive online social data. Data from Medicine, Biology,
Economics may also be considered. The final goal is to propose effective tailored
compression methods and generic compression schemes to deal with many
types of requests while controlling the bias induced by the compression.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">References</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[BV04]
P. Boldi and S. Vigna, The webgraph framework i: Compression techniques. In
Proceedings of the 13th International Conference on World Wide Web, WWW ’04,
pages 595–602, New York, NY, USA, 2004. ACM.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[CR15]
J. Casa-Roma, F. Rousseau, Community-preserving generalization of social
networks. In IEEE. 2015 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM). </span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[S.l.],
2015. p. 1465–1472.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[FL+12]
W. Fan, J. Li, X. Wang, and Y. Wu, Query preserving graph compression. In</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Proceedings
of the 2012 ACM SIGMOD International Conference on Management of</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Data
(SIGMOD '12), 2012. DOI:<a href="https://doi.org/10.1145/2213836.2213855">https://doi.org/10.1145/2213836.2213855</a></span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[GC+20]
Z. Ghalmane,C. Cherifi, H. Cherifi, M. El Hassouni. Extracting backbones in</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">weighted
modular complex networks. Sci Rep 10, 15539 (2020).</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""><a href="https://doi.org/10.1038/s41598-020-71876-">https://doi.org/10.1038/s41598-020-71876-</a></span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[HL13]
P. Hu and WC. Lau, A survey and taxonomy of graph sampling. 2013. CoRR
abs/1308.5865, <a href="http://arxiv.org/abs/1308.5865,1308.5865">http://arxiv.org/abs/1308.5865,1308.5865</a></span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[KB+21]
A. E. Kiouche, J. Baste, M. Haddad and H.Seba. A Neighborhood-preserving Graph
Summarization, 2021, coRR abs/ 2101.11559, <a href="https://arxiv.org/abs/2101.11559">https://arxiv.org/abs/2101.11559</a>.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[MRT20]
G. Minello, L. Rossi and A. Torsello, k-Anonymity on Graphs using the Szemerédi
Regularity Lemma, IEEE Transactions on Network Science and Engineering, 2020,</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""><a href="https://doi.org/10.1109/TNSE.2020.3020329">https://doi.org/10.1109/TNSE.2020.3020329</a>.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[QK15]
F. Queyroi and S. Kirgizov. Suppression distance computation for hierarchical
clusterings. Information Processing Letters, Volume 115, Issue 9, 2015.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[T19]
O. Togni. Coloring Large Real World Networks : the DSAT-ratio, In MARAMI 2019,
2019.</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">[YAA21]
M. I. Yousuf, I. Anwer and R.Anwar, Empirical Characterization of Graph</span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman"">Sampling
Algorithms, 2021, coRR abs/2102.07980 , <a href="https://arxiv.org/abs/2102.07980" style="color:rgb(5,99,193)">https://arxiv.org/abs/2102.07980</a></span></p>
<p class="MsoNormal" style="text-align:justify;margin:0cm;font-size:12pt;font-family:Calibri,sans-serif"><span lang="EN-US" style="font-size:11pt;font-family:"CMU Serif Roman""> </span></p><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><div><span style="font-size:x-small"><br>Join us at</span><b style="font-size:x-small"> </b><a href="https://www.complexnetworks.org/" style="font-size:x-small" target="_blank">COMPLEX NETWORKS 2021 Madrid Spain</a><font size="1"><b><br></b></font></div><div><font size="1"><b>-------------------------</b></font></div><div><font size="1" color="#666666">Hocine CHERIFI </font></div><div><font size="1" color="#666666">University of Burgundy Franche-Comté</font></div><div><font size="1" color="#666666">Deputy Director LIB EA N° 7534 <br></font></div><div><font size="1"><font color="#666666">Editor in Chief </font><a href="https://appliednetsci.springeropen.com/" target="_blank">Applied Network Science</a></font></div></div></div><div><p class="MsoNormal" style="margin:0cm 0cm 0.0001pt;font-size:12pt;font-family:Cambria"><span style="font-size:10pt;font-family:Arial"><font color="#666666">Editorial Board member </font><a href="https://journals.plos.org/plosone/" style="color:purple" target="_blank">PLOS One</a><font color="#000000">, </font><a href="https://ieeeaccess.ieee.org/?http%3A%2F%2Fieeeaccess_ieee_org%2F" style="color:purple" target="_blank">IEEE ACCESS</a><font color="#000000">, </font><a href="https://www.nature.com/srep/" style="color:purple" target="_blank">Scientific Reports</a><font color="#000000">,</font></span></p><p class="MsoNormal" style="margin:0cm 0cm 0.0001pt;font-size:12pt;font-family:Cambria;color:rgb(0,0,0)"><span style="font-size:10pt;font-family:Arial"><a href="https://www.mdpi.com/journal/jimaging" style="color:purple" target="_blank">Journal of Imaging</a>, <a href="https://www.springer.com/journal/11135/" style="color:purple" target="_blank">Quality and Quantity</a>, <a href="https://computationalsocialnetworks.springeropen.com/" style="color:purple" target="_blank">Computational Social Networks</a>,</span></p><span style="color:rgb(0,0,0);font-size:10pt;font-family:Arial"><a href="https://www.complex-systems.com/" style="color:purple" target="_blank">Complex Systems</a> <a href="https://www.hindawi.com/journals/complexity/" target="_blank">Complexity</a></span><span style="color:rgb(0,0,0);font-size:medium"></span><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>