thèse sur optimisation dans les graphes dynamiques au Havre - Normandie

Projet de thèse en informatique à l’Université Le Havre Normandie

Computer sciences thesis opportunity at Le Havre Normandy University

Titre : Problemes d'optimisation dans les reseaux temporels

Optimization problems in temporal networks

Encadrants : Yoann Pigné, Eric Sanlaville

Mots clés : graphes, algorithmes d'optimisation, réseaux temporels, graphes dynamiques

Keywords: graphs, optimization algorithms, temporal networks, dynamic graphs

Type de bourse : Financement d’établissement (Ministère Enseignement Supérieur et Recherche)

Funding source: Public funds (French Ministry of Education and Research)

Echéance : Vendredi 12 mai 2017

Deadline: Friday 12th of Mai, 2017

Description en Français :

Un réseau temporel, ou graphe dynamique, est un graphe défini sur un intervalle de temps, au sein duquel les arcs (resp. sommets) peuvent ne pas être présents à tout instant mais seulement de manière intermittente [1]. Les réseaux temporels permettent aussi bien de représenter la volatilité des sommets et des liens dans les réseaux mobiles ad hoc ou dans les réseaux sociaux, que les réseaux de transport soumis à des variations du trafic. Ils représentent donc un modèle très intéressant pour les probèmes de communication et de logistique [2], [3].

Notre objectif est d'étudier certains problèmes classiques d'optimisation dans les graphes dans ce nouveau cadre des réseaux temporels. à l'inverse, ces réseauxétant des objets assez récemment formalisés, il existe plusieurs facons de les définir, et une partie du travail consistera à proposer le formalisme le mieux adapté pour les problèmes que nous souhaitons traiter [4]. Les déterminations de flots, de structures (i.e. composantes connexes), valides dans le temps, seront abordées.

La démarche consistera à exploiter différentes approches de résolution (méta-heuristiques, programmation mathématique, algorithmes approchés, …) suivant la nature des problèmes abordés.

Cette thèse s'insère dans les thématiques de recherche de l'équipe RIIC (Réseau d'Interaction et Intelligence Collective) du LITIS (Laboratoire d'Informatique, de traitement de l'Information et des systèmes). Les graphes dynamiques constituent l'épine dorsale des travaux de l'équipe. L'analyse en profondeur des méthodes d'optimisation dans les réseaux temporels trouvera des applications imme?diates dans les projets de recherche applique?e de l’équipe (logistique [3],[6], réseaux mobiles [7], équilibrage de charge [8]). Les réseaux temporels permettent en effet de modéliser et piloter l'évolution dans le temps de ces types de réseaux.

L’e?quipe RI2C développe une plate-forme logicielle de manipulation de graphes dynamiques, GraphStream [9], [10], que ce travail de thèse viendra enrichir avec l’apport d’un nouveau modèle de représentation et d'analyse des graphes dynamiques.

Le plan de travail pourra suivre les étapes suivantes :

• Analyse des différents modèles de réseaux temporels dans la littérature.

• Extensions des problèmes d'optimisation pour les réseaux temporels

• Conception, analyse d'algorithmes de résolution pour ces problèmes

• Implémentation des algorithmes et modèles dans la plateforme GraphStream

• Valorisation scientifique

• Rédaction du manuscrit

La/Le candidat(e) sélectionné(e) fera preuve de compétences fortes en théorie des graphes et en optimisation. Un excellent niveau technique en terme de développement logiciel est également attendu (en particulier en Java). Les techniques de bases de génie logiciels doivent être maitrisées et utilisées (développement orienté tests, gestion de version, etc.) Elle/Il sera en mesure d’organiser son travail, de fournir un plan de travail cohérent, des états d’avancement régulier et sera capable de respecter les échéances décidées avec l’encadrement. Des compétences en analyse statistique et la maitrise du langage R seront un plus.

Les candidat(e)s intéressé(e)s sont prié(e)s d’envoyer par mail leur CV, lettre de motivation, ainsi que toute preuve concernant les compétences précitées (relevés de notes (mêmes partiels), rapports de stage, lettres de recommandation, profile GitHub, etc.) à Eric Sanlaville (eric.sanlaville@univ-lehavre.fr) et Yoann Pigné (yoann.pigne@univ-lehavre.fr).

English Version:

A temporal network, also called dynamic graph, is a graph defined on a time interval, where arcs (resp. vertices) might not be present at any time, but only occasionally [1]. Temporal networks allow to represent nodes and arcs presence variability in ad hoc mobile networks or social networks, as well as transportation networks submitted to traffic congestion. Hence they are a very interesting model for communication and logistic problems. [2], [3].

Our goal is to study some classical optimization problems on graphs within this new framework. Moreover, as the formalism for these networks is not completely fixed in the literature, a part of the work will consist in proposing the best adapted one for the tackled problems [4]. Determining for instance flows, particular structures like connected components valid during the considered time interval, will be considered. Several solving approaches like meta-heuristics, mathematical programming, approximation algorithms, will be exploited according to the treated problem natures.

The thesis subject fits well the research themes of the RIIC team (Interaction Networks and Collective Intelligence) of the computer science research department LITIS. Indeed, dynamic graphs are the backbone of the team work. The in-depth analysis of optimization methods in temporal networks will find immediate applications in the applied research funded projects of the team (logistics [3],[6], mobile networks [7], load balancing [8]). Indeed, temporal networks allow to model and control the evolution with time of this kind of physical networks.

The RI2C team develops a software platform to manipulate dynamic graphs, GraphStream [9], [10], this work will enrich the software by the way of a new model to represent and analyse dynamic graphs.

Work plan:

• Analysis of the temporal networks models from the literature.

• Extension of optimization problems to temporal networks

• Design, analysis of solving algorithms for these problems

• Implementation of the algorithms and models within GraphStream

• Scientific valorization

• Thesis writing

The chosen candidate shall display strong skills in graph theory and optimization. An excellent technical level in software development is expected (particularly in Java). The Software engineering basis techniques must be mastered and used (test oriented development, version management). He/She will organize his/her work and be able to respect the fixed due dates. Skills in statistic analysis and the knowledge of R language would be appreciated.

Interested candidates should send by email CV, motivation letter and any additional material (master marks, training reports, recommendation letters, GitHub profile,...) to Eric Sanlaville (eric.sanlaville@univ-lehavre.fr) and Yoann Pigné (yoann.pigne@univ-lehavre.fr).

[1] P. Holme et J. Sarama?ki, « Temporal networks », Physics Reports, vol. 519, no 3, p. 97-125, oct. 2012.

[2] B. B. Xuan, A. Ferreira, et A. Jarry, « Evolving graphs and least cost journeys in dynamic networks », pre?sente? a? WiOpt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003, 10 pages.

[3] F. Guinand et Y. Pigne?, « Time considerations for the study of complex maritime networks », in Maritime Networks Spatial structures and time dynamics, Ce?sar Ducruet, Routledge, 2015, p. 163-189.

[4] D. Kempe, J. Kleinberg, et A. Kumar, « Connectivity and Inference Problems for Temporal Networks », in Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, New York, NY, USA, 2000, p. 504–513.

[5] O. Michail, « An Introduction to Temporal Graphs: An Algorithmic Perspective », Internet Mathematics, vol. 12, no 4, p. 239-280, juill. 2016.

[6] S. Balev, S. Michel, E. Sanlaville, et X. Schepler, « Global planning in a multi-terminal and multi-modal maritime container port », Transportation Research Part E, accepte?, de?c. 2016.

[7] A. Casteigts, S. Chaumette, F. Guinand, et Y. Pigne?, « Distributed maintenance of anytime available spanning trees in dynamic networks », in International Conference on Ad-Hoc Networks and Wireless, 2013, p. 99–110.

[8] J. L. J. Laredo, F. Guinand, D. Olivier, et P. Bouvry, « Load Balancing at the Edge of Chaos: How Self-Organized

Criticality Can Lead to Energy-Efficient Computing », IEEE Transactions on Parallel and Distributed Systems, 2016.

[9] A. Dutot, F. Guinand, D. Olivier, et Y. Pigne?, « Graphstream: A tool for bridging the gap between complex systems and dynamic graphs », in Emergent Properties in Natural and Artificial Complex Systems. Satellite Conference within the 4th European Conference on Complex Systems (ECCS’2007), 2007.

[10] « GraphStream - A Dynamic Graph Library ». [En ligne]. Disponible sur: http://graphstream-project.org/. [Consulte? le: 06-fe?vr-2017].