- Title: “Study of properties and modeling of complex social graphs”
- When: June 25, 2021 — 14:00
- Where: online on YouTube
- Committee:
- Augustin Chaintreau, Assistant Professor, Columbia University, New York, USA
- Christophe Crespelle (referee), Associate Professor, UCBL, Lyon, France
- Frédéric Giroire (supervisor), Senior Researcher, CNRS, Sophia Antipolis, France
- Jean-Loup Guillaume (referee), Professeur, L3i, La Rochelle, France
- Clémence Magnien, Senior Researcher, CNRS, LIP6, Paris, France
- Giovanni Neglia, Researcher, Inria, Sophia Antipolis, France
- Pawel Pralat, Professor, Ryerson University, Canada
-
Abstract: The rapid emergence of social networks, their major impact on today’s society, and the recent access to large amounts of data about them has led to a strong interest in the study of complex networks in last decades. Many random graph models have been proposed to reproduce these networks and their properties – small diameter, power-law degree distribution, presence of communities, … However, due to the complexity of their theoretical study, the proposed models are often designed for undirected graphs and focus on the emergence of one or two properties at a time. This thesis aims at developing models of random graphs that are general enough to reproduce many complex properties observed in real-world networks. In particular, we present models for constructing graphs with arbitrary degree distributions, directed graphs with a high clustering coefficient, and hypergraphs with power-law degree distributions and a strong presence of communities. We study analytically and experimentally the properties of the presented models. We develop a tool using Markov chains to compute the degree distribution of preferential attachment models.
In order to help in the construction of these models, we study in this thesis two large complex networks: a directed network with all followings on Twitter, with 505 million accounts and 23 billion followings; and a hypergraph of scientific co-publications extracted from the Scopus database, containing 2.2 million authors and 3.9 million publications. Atypical properties emerge from the study of these two graphs, coming in particular from their directed and hypergraph character, that no model of the literature could reproduce until now. - Titre: “Etude des propriétés et modélisation de graphes sociaux complexes”
-
Résumé: L’émergence rapide des réseaux sociaux lors des deux dernières décennies, leur impact majeur sur la société actuelle, ainsi que l’accès récent à de grandes quantités de données les concernant, a amené un fort attrait pour l’étude des réseaux complexes.
De nombreux modèles de graphes aléatoires ont été proposés afin de reproduire ces réseaux et leurs propriétés – faible diamètre, distribution des degrés en loi de puissance, présence de communautés, …
Cependant, du fait de la complexité de l’étude théorique de leurs propriétés, les modèles proposés sont souvent conçus pour des graphes non orientés et se concentrent sur l’émergence d’une ou deux propriétés à la fois.Cette thèse a pour but de développer des modèles de graphes aléatoires suffisamment généraux pour reproduire de nombreuses propriétés complexes observées dans les réseaux du monde réel. En particulier, nous présentons des modèles permettant de construire des graphes avec des distributions de degrés quelconques, des graphes dirigés avec un haut coefficient de clustering, et des hypergraphes avec distribution de degrés en loi de puissance et une forte présence de communautés. Nous étudions analytiquement et expérimentalement les propriétés des modèles présentés. Nous développons enfin un outil utilisant les chaînes de Markov pour calculer la distribution des degrés de modèles d’attachement préférentiel.
Afin de s’aider dans la construction de ces modèles, nous étudions dans cette thèse deux réseaux complexes de grande taille : un graphe dirigé de l’ensemble des liens d’abonnements sur le réseau social Twitter, avec 505 millions de comptes et 23 milliards d’abonnements ; et un hypergraphe de co-publications scientifiques extraites de la base de données Scopus, contenant 2.2 millions d’auteurs distincts et 3.9 millions de publications.
Des propriétés atypiques émergent de l’étude de ces deux graphes, provenant en particulier de leur caractère dirigé et d’hypergraphe, et qu’aucun modèle de la littérature ne permettait jusqu’alors de reproduire.
SEA 2021
19th Symposium on Experimental Algorithms (SEA 2021)
- When: June 6-9, 2021
- Where: Nice, France
- Chairs: David Coudert and Emanuele Natale
- Link: conference website
- Submission deadline: January 24, 2021
Ali Al Zoobi participated the MT180 final at Université Côte d’Azur
Ali Al Zoobi, PhD student of COATI, participated the 2021 edition of the Ma thèse en 180 secondes contest organized at Université Côte d’Azur.
Watch the video (in French).
PhD defense of Giuseppe Di Lena
-
- Title: “Distributed and Trustable SDN-NFV-enabled Network Emulation on Testbeds and Cloud infrastructures”
- When: March 22, 2021 — 10:00
- Where: online – (recorded and uploaded here)
- Committee:
- Guillaume Urvoy-Keller (President), Professor, Université Côte d’Azur, France
- Marcelo Dias de Amorim (Referee), Senior Researcher, LIP6 CNRS, Paris, France
- Stefano Secci (Referee), Professeur, CNAM, Paris, France
- Mathieu Bouet, Engineer, Thales, France
- Luigi Iannone, Professor, Telecom ParisTech, Paris, France
- Thierry Turletti (co-supervisor), Senior Researcher, Inria, Sophia Antipolis, France
- Frédéric Giroire (co-supervisor), Senior Researcher, CNRS, Sophia Antipolis, France
- Chidung Lac (co-supervisor), Engineer, Orange Labs, France
-
Abstract: In recent years, there have been multiple enhancements in virtualization tech-nologies, cloud computing, and network programmability. The emergence of concepts likeSoftware Defined Networking (SDN)andNetwork Function Vir-tualization (NFV) are changing the way the Internet Service Providers manage their services. In parallel, the last decade witnessed the rise of secure pub-lic cloud platforms like Amazon AWS and Microsoft Azure. These new con-cepts lead to cost reductions and fast innovation, driving the adoption of these paradigms by the industry. All these changes also bring new challenges. Net-works have become huge and complex while providing different kinds of services.Testing them is increasingly complicated and resource-intensive. To tackle this issue, we propose a new tool that combines emulation technologies and opti-mization techniques to distribute SDN/NFV experiments in private test-beds and public cloud platforms. Cloud providers, in general, deliver specific metrics to the users in terms of CPU and memory resources for the services they propose, but they tend to give a high-level overview for the network delay, without any specific value. This is a problem when deploying a delay-sensitive applica-tion in the cloud, since the users do not have any precise data about the delay. We propose a testing framework to monitor the network delay between multiple datacenters in the cloud infrastructures. Finally, in the context of SDN/NFVnetworks, we exploit the SDN centralized logic to implement an optimal routingstrategy in case of multiple link failures in the network. We also created a test-bed environment to validate our proposition in different network topologies.
- Titre: “Emulation fiable et distribuée de réseaux virtualisés et programmables sur bancs de test et infrastructures Cloud”
-
Résumé: De nombreux progrès ont eu lieu ces dernières années dans les domaines de la virtualisation, l’informatique en nuage et la programmation des fonctions réseau. L’essor des concepts tels que Software Defined Networking (SDN) et Network Function Virtualization (NFV) a largement modifié la manière dont les fournisseurs de services Internet gèrent leurs offres. Parallèlement, au cours de la dernière décennie, les plateformes sécurisées de Cloud publiques telles que Amazon AWS ou Microsoft Azure sont devenues des acteurs incontournables de la scène. Ces nouveaux concepts permettent des réductions de coûts et une plus grande rapidité d’innovation, ce qui a conduit à l’adoption de ces paradigmes par l’industrie. Tous ces changements apportent également leur lot de nouveaux défis. Tout en étant devenus tentaculaires et complexes, ces réseaux offrent une plus grande diversité de services: les tester devient ainsi de plus en plus compliqué, tout en nécessitant
beaucoup de ressources. Pour résoudre ce problème, nous proposons un nouvel outil qui combine les technologies d’émulation et les techniques d’optimisation afin de distribuer les simulations SDN/NFV dans des bancs de test privés et des plateformes de Cloud publiques. Par ailleurs, les fournisseurs de Cloud proposent en général aux utilisateurs des métriques spécifiques en termes de CPU et de ressources mémoire afin de caractériser leurs services, mais ont tendance à présenter une vue d’ensemble de haut niveau du délai maximum engendré par le réseau, sans aucune valeur spécifique. Ceci peut constituer un problème lorsqu’il s’agit de déployer des applications sensibles au délai dans le Cloud, car les utilisateurs n’ont pas de données précises sur ce sujet. Nous proposons un cadre de test pour surveiller le délai engendré par le réseau entre plusieurs centres de données des infrastructures Cloud. Enfin, dans le contexte des réseaux SDN/NFV, nous ex
ploitons la logique centralisée SDN pour implémenter une stratégie optimale de routage en cas de défaillances multiples des liens dans le réseau. Un environnement de banc de test a également été créé afin de valider nos propositions pour différentes topologies de réseau.
François Pirot recipient of the PhD prize Graphes “Charles Delorme” 2020
François Pirot, post-doc at COATI since November 1st 2020 and former PhD student of the G-SCOP laboratory (Grenoble), is the recipient of the PhD prize Graphes “Charles Delorme” 2020, for his PhD thesis entitled Colouring sparse graphs. Congratulations !
The prize has been announced during Journées Graphes et Algorithmes — online, November 16-18, 2020.
HDR defense of Julien Bensmail
- Title: A contribution to distinguishing labellings of graphs
- When: December 15, 2020 — 09:00
- Where: online with live streaming on Youtube
- Committee:
- Cristina Bazgan, PR, Université Paris-Dauphine, Paris
- Frédéric Cazals, DR, Inria Sophia Antipolis – Méditerranée
- Louis Esperet CR HDR, CNRS, G-SCOP, Grenoble
- Mickaël Montassier (referee), PR, Université de Montpellier
- Éric Sopena PR, Université de Bordeaux
- Stéphan Thomassé, PR, ENS de Lyon
- Olivier Togni (referee), PR, Université de Bourgogne, Dijon
- Xuding Zhu (referee), PR, National Sun Yat-sen University (Taïwan)
- Manuscript: http://jbensmai.fr/hdr/
-
Abstract: During the talk, I will present some of my contribution to distinguishing labellings of graphs, and the so-called 1-2-3 Conjecture that occupies an important place in this field. The general objective in this kind of problems is, given a (connected undirected) graph, to weight its edges in such a way that the adjacent vertices get distinguishable accordingly to some parameter computed from the edge-weighting. For instance, in the 1-2-3 Conjecture, raised by Karonski, Łuczak and Thomason in 2004, the aim is to weight the edges with 1,2,3 so that adjacent vertices get distinguished accordingly to their sums of incident weights.
Although the 1-2-3 Conjecture was raised as nothing but a toy problem when it was introduced, several results in the recent years have established its deeper nature. The conjecture, by its very definition, has undoubtedly an algebraic nature. Some results have also established that it has some decompositional flavour. Although the conjecture is rather artificial, it is also related to other classical notions of graph theory, such as proper vertex-colourings of graphs.
Through the results I will focus on during the talk, my main goal is to point out how deep this field is, and the many aspects of interest that are worth considering.
JGA 2020
22e Journées Graphes et Algorithmes (JGA 2020)
- When: November 16-18, 2020
- Where: Online
- Link: conference website
New team member: Małgorzata Sulkowska
Welcome to our new team member: Małgorzata Sulkowska.
Małgorzata Sulkowska got her M.Sc. in Computer Science in 2007 from Wrocław University of Science and Technology (Poland). The thesis, written jointly with Michał Przykucki, won second award in the Polish Mathematical Society contest for the best M.Sc. thesis in probability theory and applied mathematics. Małgorzata got her Ph.D. in Mathematics in 2013 from Wrocław University of Science and Technology under the supervision of prof. Michał Morayne. She got the assistant position at the same university already in 2012 and since 2014 she is an assistant professor in the Department of Fundamentals of Computer Science. In years 2015-2016 she spent 5-months as a postdoc at Federal University of Ceara (Fortaleza, Brazil) under the supervision of prof. Fabricio Siqueira Benevides. In years 2016-2020 she conducted a series of shorter research visits, among others, at University of London (Great Britain), Vienna University of Technology (Austria), University of Louisville (USA) and Inria Sophia-Antipolis (France). Since 2018 she has been a mentor of the Student Research Group Solvro at Wrocław University of Science and Technology. In 2019 Małgorzata was awarded a Miniatura3 grant from Polish National Science Center for research on stopping algorithms for graphs. In September 2020 she started a one-year postdoc position at Universite Cote d’Azur as a member of COATI team at INRIA Sophia-Antipolis. Her main research interests are optimal stopping problems, lying on the crossroads of graph theory, combinatorics and probability theory.
New team member: Ramon Aparicio-Pardo
Welcome to our new team member: Ramon Aparicio-Pardo.
Ramon Aparicio-Pardo received a MEng in Telecom. and a Ph.D. from Universidad Politécnica de Cartagena (UPCT), Spain, in 2006 and 2011, respectively. His Ph.D. thesis, titled ‘Optimization and Planning of WDM Transparent Optical Networks,’ was distinguished with TELEFÓNICA Award for Best Thesis in Networking.
After two postdocs, at Orange Labs on optical switching networks (2012-2013) and at IRISA, in former IMT-Telecom Bretagne, on adaptive streaming (2013-2015), he joined Université Côte d’Azur (UCA) as an associate professor (“maître de conférences”) in Sept. 2015 and became a member of the SigNet group of the I3S laboratory. His main research interest is the optimal design and management of communication networks.
In September 2020, he joined obtained a “délégation Inria” to work with COATI on the design of AI-based methods for network optimization.
Adrien Gausseran, 1st prize of the jury for the MT180 final at Université Côte d’Azur
Adrien Gausseran, PhD student of COATI, has been awarded the 1st prize of the jury during the 2020 edition of the Ma thèse en 180 secondes contest organized at Université Côte d’Azur. Congratulation !