Title: *Optimization problems in temporal networks*
Supervisors: Yoann Pigne, Eric Sanlaville
Keywords: graphs, optimization algorithms, temporal networks, dynamic graphs
Funding source: Public funds (French Ministry of Education and Research)
Deadline: *Friday 12th of Mai, 2017 *
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
techniquesmust 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 mail CV, motivation letter and any
additional material (master marks, training reports, recommendation
letters,GitHub profile,...)
toEric Sanlaville (eric.sanlaville@univ-lehavre.fr
<mailto:eric.sanlaville@univ-lehavre.fr>) andYoann Pigné
(yoann.pigne@univ-lehavre.fr <mailto:yoann.pigne@univ-lehavre.fr>).
[1] P. Holme et J. Saramä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 », présenté à /WiOpt'03: Modeling
and Optimization in Mobile, Ad Hoc and Wireless Networks/, 2003, 10 pages.
[3] F. Guinand et Y. Pigné, « Time considerations for the study of
complex maritime networks », in /Maritime Networks Spatial structures
and time dynamics/, Cé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/, accepté, déc. 2016.
[7] A. Casteigts, S. Chaumette, F. Guinand, et Y. Pigné, « 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. Pigné, « 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/. [Consulté le: 06-févr-2017].
--
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Eric Sanlaville
Full professor, Le Havre University
Research department LITIS-EA 41-08
Team RI2C : Interaction Networks, Collective Intelligence
Tel : +33 232 744 548
Fax : +33 232 744 314
http://litis.univ-lehavre.fr/~sanlaville
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
