Postdoctoral position in dynamic graphs

Available from september 2018 up to September 2019

(this announcement is republished after the chosen candidate finally declined)

Context

LITIS laboratory seeks to hire a postdoctoral researcher to join the ASTREOS project (Flows in sociotechnical systems - structure, reliability and control) funded by Normandy region.

Sociotechnical systems are, by their nature, complex systems. Networks are the fundamental model of such systems. Graph theory supported by statistical physics provides tools to characterize and analyze them. But the networks we are interested in are not immutable. They are traversed by flows (of goods, vehicles, money, energy, information and so on) which modify and restructure them all the time. Dynamic graphs (also called time-varying graphs or temporal networks) are therefore the appropriate tool to study the sociotechnical systems.

The postdoctoral researcher will join the RI2C team of LITIS and will work in Le Havre. Most of the team’s research activity is structured around dynamic graphs. In particular, the team develops and maintains GraphStream, a software library for modeling and analyzing dynamic graphs.

Job description

Dynamic graphs are relatively new research area and that is why there are many ways to define them. We will retain a description of the dynamics as a stream of discrete elementary events: addition or deletion of a vertex or an edge; change of a value associated to a vertex or an edge. The result of this event stream is a graph that evolves over time.

The research will be guided by the following general question: how to maintain a structure in such a graph? Depending on the problem, this structure could be a spanning tree, a path between two nodes, a community structure, a load distribution between nodes, network flows and so on.

To answer this question, two approaches are considered:

• reoptimization algorithms trying to adapt the structure to the changes in the graph without recomputing from scratch

• distributed heuristic approaches based on agents and swarm intelligence.

The theoretical results of this work will complete the GraphStream library and in particular its dynamic algorithms. They will also feed the applied research within ASTREOS project, particularly in logistics, territorial intelligence and sensor networks.

Desired skills and experience

• PhD in computer science or related field

• Strong background in graph algorithms

• Experience in complex systems and networks

• Background in optimization and/or swarm intelligence

• Good programming skills, especially in Java

• Team spirit and communication skills

• French language is convenient but not required

Contact: stefan.balev@univ-lehavre.fr, yoann.pigne@univ-lehavre.fr, eric.sanlaville@univ-lehavre.fr

____________________________________________________

Poste CDD de postdoc / ingénieur de recherche sur les graphes dynamiques

Début : au plus tôt  (septembre 2018)

(cette annonce est republiée le 7 septembre 2018 après que le candidat choisi a finalement décliné l'offre)

Fin : septembre 2019

Contexte

Ce poste est à pourvoir dans le cadre du projet ASTREOS (Maîtrise des flux dans les systèmes socio-techniques - structure, fiabilité et contrôle) financé par la région Normandie.

Les systèmes socio-techniques sont par nature des systèmes complexes. Le modèle fondamental d'étude de tels systèmes est le réseau. La théorie des graphes épaulée par la physique statistique fournit beaucoup d'outils pour leur caractérisation et analyse. Mais les réseaux qui nous intéressent ne sont pas immuables. Ils sont traversés par des flux (de marchandises, de véhicules, d'argent, d'énergie, d'information, etc. selon la nature du système) qui les modifient et restructurent constamment. Les graphes dynamiques (ou encore graphes évolutifs, réseaux temporels) sont donc l'outil adapté pour l'étude des systèmes socio-techniques.

L'ingénieur(e) intégrera l'équipe RI2C du LITIS. La grande majorité des activités de recherche de cette équipe est structurée autour des graphes dynamiques. L'équipe développe et maintient en particulier GraphStream, une bibliothèque logicielle de modélisation et d’analyse de graphes dynamiques.

Mission

Les graphes dynamiques étant un domaine de recherche assez récent, il existe plusieurs façons de les définir. Nous retiendrons une description de la dynamique sous forme d'un flux d'événements élémentaires discrets : ajout ou suppression d'un sommet ou d'une arête ; changement d'une valeur associée à un sommet ou à une arête. Le résultat de ce flux d'événements est un graphe qui évolue dans le temps.

La question centrale à laquelle ce travail essayera d'apporter des éléments de réponse est : Comment maintenir une structure dans un tel graphe ? Selon le problème étudié, la structure qui nous intéresse pourrait être un arbre couvrant, un chemin entre deux sommets, des communautés, une distribution de charge entre les sommets ou encore des flots.

Pour répondre à cette question, deux pistes sont envisagées :

• algorithmes de ré-optimisation essayant d'adapter la structure aux changements que subit le graphe sans tout recalculer ;

• approches heuristiques décentralisées à base d'agents sur le principe de l'intelligence en essaim.

Les résultats théoriques de ce travail viendront enrichir la bibliothèque GraphStream et notamment ses algorithmes dynamiques. Ils trouveront également leur place dans les travaux de recherche appliquée dans le cadre du projet ASTREOS, notamment en logistique, intelligence territoriale et réseaux de capteurs.

Compétences et aptitudes souhaitées

• Doctorat en informatique ou une discipline proche ;

• Maîtrise de l'algorithmique des graphes ;

• Expérience en systèmes complexes et réseaux complexes ;

• Maîtrise des techniques d'optimisation et/ou d'intelligence en essaim ;

• Bon niveau en programmation, notamment en Java ;

• Bon relationnel et aptitudes de communication ;

• Bon niveau d’anglais.

Contact: stefan.balev@univ-lehavre.fr, yoann.pigne@univ-lehavre.fr, eric.sanlaville@univ-lehavre.fr