- Speaker: Pierluigi Crescenzi, GSSI, University of L’Aquila
- Title: On Computer Science Conferences and their Temporal Evolution — (watch the video)
- When: October 6, 2022 — 14:00
- Where: Campus SophiaTech, Forum F201, and online
-
Abstract: In this talk we will present the evolution of computer science conferences over the past 50 years, by analysing data from the DBLP database.
Our goal was to try and understand the evolution of each conference throughout its history, the ebb and flow in the popularity of its research areas, and the centrality of its authors, as measured by several metrics from network science, amongst other topics. In particular we tried to answer several different questions.
How did the conference evolve in terms of its number of authors, number of papers, and number of collaboration sizes? How much the conference was open to new entries? Did the percentage of female authors change over time? Were different topics more popular in different periods? If the conference covers a broad spectrum of research areas, did the percentage of each area change over time? Did the conference present the small-world phenomenon? What are the most influential authors of the conference?The tentative answer to these questions was given by either analysing only one conference at a time or by performing a comparative analysis between a specific set of conferences. We will also briefly present the web-based resources that accompany this talk. It goes without saying that our analysis has to be taken with a huge pinch of salt and is only meant to be food for thought for the community.
-
Short Bio: Pierluigi Crescenzi is a professor at the Gran Sasso Science Institute. Before joining GSSI, he has been researcher at the University of L’Aquila, and professor at the University of Rome, Florence, and Paris. He has taught in basically every field of computer science. He is the author of more than 130 scientific publications in the field of algorithm theory and its applications. He is co-author of 5 university textbooks, including 2 in English, and a popular Italian book. He is member of the editorial board of JCSS. He is co-author of the NP optimisation compendium, which is still widely cited. He is co-inventor of a US Patent on an IP address lookup algorithm and he has been a member of the steering committee of the COST 295 DYNAMO action. His current research is mostly focus on the analysis of complex networks and, more specifically, of temporal networks.
Author: David COUDERT
PhD defense of Foivos Fioravantes
- Title: “Edge-labellings, vertex-colourings and combinatorial games on graphs”
- When: September 26, 2022 — 14:00
- Where: Inria Sophia Antipolis, Euler violet
- Committee:
- Éric Sopena (referee), Professor, LaBRI, Université de Bordeaux
- Mariusz Woźniak (referee), Professor, AGH University of Science and Technology
- Julien Bensmail (supervisor), Associate professor, I3S, Université Côte d’Azur
- Nicolas Nisse (supervisor), Inria Research Officer, Inria Sophia Antipolis
- Théo Pierron, Associate professor, LIRIS, Université Claude Bernard Lyon 1
- Olivier Togni, Professor, LIB, Université de Bourgogne
-
Abstract: In this thesis, we consider two families of computational problems defined on graphs: proper edge-labellings and combinatorial games. We attack these problems in a similar (and classical) way: we show that they are computationally hard, and then find efficient algorithms for instances with specific structure.
First we focus on problems related to proper labellings of graphs. For some natural number k, a k-labelling is a weight function on the edges of a graph G, assigning weights, called labels in this context, from {1, . . . , k}. A k-labelling induces a vertex-colouring of G, where each vertex receives as colour the sum of the labels of its incident edges. A k-labelling is proper if the induced vertex-colouring is proper, i.e., such that any two adjacent vertices of G are assigned different colours. According to the so-called 1-2-3 Conjecture, any connected graph of order at least 3 should admit a proper 3-labelling. Weconsider three variations of this conjecture. We look into equitable proper k-labellings, for which the assigned labels appear an equal number of times. We then focus on proper labellings that also minimise the sum of labels being used, and finally, proper 3-labellings that also minimise the number of times that the label 3 is assigned.
The choice to study these variations is natural. Indeed, an equitable version of the 1-2-3 Conjecture claims that almost every graph G should admit an equitable proper 3-labelling. Also, the sum of labels of such a labelling would be at most 2|E(G)| and it would assign label 3 to at most one third of the edges of G. We prove that the introduced optimisation problems are NP-hard. Furthermore, through structural and algorithmical results, we propose new conjectures for the upper bounds of the parameters that we study, which we verify for specific graph classes (e.g. complete, bipartite, regular, 3-chromatic, etc.). Interestingly, our work gives further evidence that stronger variations of the 1-2-3 Conjecture could hold. We close our study of proper labellings by considering the problem of finding a largest induced subgraph of a given graph that admits a proper 1-labelling. This problem is proven to be computationally hard and not approximable within a ratio of O(|V(G)|^(1−c)) for every natural number c. Nevertheless, we provide efficient parameterised algorithms.In the second part of the thesis, we introduce and study the Maker-Breaker largest connected subgraph game. This game is played by two players, Alice and Bob, on a shared, initially uncoloured graph G. The two players take turns colouring the vertices of G, each one with their own colour, until there remains no uncoloured vertex. Alice is the winner of the game if, by the end, the largest connected subgraph of G induced by her colour is of order greater than k, where the natural number k is also given at the start of the game. Otherwise Bob wins the game. We also consider a Maker-Maker version of the same game, played in the same way, but in which the winner is the player whose colour induces the largest connected subgraph of G by the end of the game.
We first prove that deciding the outcome of both of these games is PSPACE-hard, and then proceed by providing efficient algorithms when the games are played on particular graph classes (e.g. paths, cycles, cographs, (q, q − 4)-graphs, etc.). Comparing the behaviour of these games, one of the main differences we observe is that Bob can never win the Maker-Maker version (if Alice plays optimally). Nevertheless, if Alice can win the Maker-Breaker version when playing on G for a value of k equal to half the order of G (the best outcome she can hope for), then she can build a connected subgraph of the same order for the Maker-Maker version; such graphs are called A-perfect. We then study regular graphs that are A-perfect and prove that any 3-regular A-perfect graph has order at most 16. We finish by providing sufficient conditions for a graph to be A-perfect. - Titre: “Étiquetages d’arêtes, colorations de sommets et jeux combinatoires sur les graphes”
-
Résumé: Cette thèse considère deux familles de problèmes définis sur des graphes : les étiquetages d’arêtes propres et les jeux combinatoires. Nous traitons ces problèmes de façon similaire (et classique) : nous montrons que les problèmes considérés sont difficiles à résoudre, puis nous trouvons des algorithmes efficaces sur des instances restreintes.
Nous nous concentrons d’abord sur des problèmes concernant des étiquetages propres de graphes. Pour un entier k fixé, un k-étiquetage d’un graphe G est une fonction associant à chaque arête de G une étiquette parmi {1, . . . , k}. Un k-étiquetage induit une coloration des sommets de G, où chaque sommet reçoit comme couleur la somme des étiquettes de ses arêtes incidentes. Un k-étiquetage est propre si, dans la coloration induite, deux sommets adjacents de G reçoivent des couleurs différentes. D’après la Conjecture 1-2-3, tout graphe connexe d’ordre au moins 3 admet un 3-étiquetage propre. Nous considérons trois variantes de cette conjecture. Nous étudions les k-étiquetages propres équilibrés, pour lesquels les étiquettes assignées apparaissent dans les mêmes proportions.
La deuxième variante concerne les étiquetages propres qui minimisent la somme des étiquettes utilisées. Enfin, nous nous intéressons aux 3-étiquetages propres qui minimisent le nombre de fois où l’étiquette 3 est attribuée. Le choix d’étudier ces variantes est naturel. En effet, une version équilibrée de la Conjecture 1-2-3 est que presque tous les graphes G admettent un 3-étiquetage propre équilibré. En outre, la somme des étiquettes d’un tel étiquetage est au plus égale à 2|E(G)| et associe l’étiquette 3 à au plus un tiers des arêtes de G. Nous prouvons que les problèmes d’optimisation introduits sont NP-difficiles. Grâce à des résultats structurels et algorithmiques, nous sommes amenés à proposer de nouvelles conjectures pour ces problèmes, que nous vérifions sur quelques classes de graphes (complets, bipartis, réguliers, 3-chromatiques, etc.).
Notre travail renforce l’idée que des variantes plus fortes de la Conjecture 1-2-3 pourraient être vraies. Nous terminons en considérant le problème consistant à trouver un plus grand sous-graphe induit d’un graphe donné qui admet un 1-étiquetage propre. Il est prouvé que ce problème est difficile à résoudre et qu’il n’est pas approximable à un facteur O(|V (G)|^(1−c)) près pour tout entier c. Néanmoins, nous fournissons des algorithmes paramétrés efficaces.La deuxième partie de la thèse introduit le jeu du plus grand sous-graphe connexe Maker-Breaker, joué par deux joueurs, Alice et Bob, sur un graphe G, initialement non coloré. Les joueurs colorent à tour de rôle les sommets de G, chacun avec sa couleur, jusqu’à ce que tous les sommets soient colorés. Alice est la gagnante si, à la fin, le plus grand sous-graphe connexe de G induit par sa couleur est d’ordre au moins k, un entier fixé. Sinon, Bob gagne le jeu. Nous considérons aussi une version Maker-Maker du même jeu, dans laquelle le gagnant est le joueur dont la couleur induit le plus grand sous-graphe connexe de G à la fin du jeu. Nous prouvons que décider de l’issue de ces deux jeux est PSPACE-difficile et nous fournissons des algorithmes efficaces pour le cas où le jeu se déroule dans certaines familles de graphes (chemins, cycles, cographes, (q,q−4)-graphes, etc.).
En comparant ces deux jeux, la principale différence que nous observons est que Bob ne peut jamais gagner la version Maker-Maker (si Alice joue de manière optimale). Pour une valeur de k égale à la moitié de l’ordre de G, remarquons que si Alice peut gagner la version Maker-Breaker alors elle peut aussi construire un sous-graphe connexe du même ordre dans la version Maker-Maker ; de tels graphes sont nommés A-parfaits. Nous étudions les graphes réguliers qui sont A-parfaits et prouvons que tout graphe 3-régulier A-parfait a au plus 16 sommets. Nous terminons en fournissant des conditions suffisantes pour qu’un graphe soit A-parfait.
GRASTA 2022
10th Workshop on GRAph Searching, Theory and Applications (GRASTA 2022)
- When: May 16-20, 2022
- Where: Porquerolles, France
- Contact: Nicolas Nisse (organizing chair)
- Link: conference website
Best paper award
The paper On Finding k Earliest Arrival Time Journeys in Public Transit Networks [1] won the best paper award at ICORES 2022.
Congratulation to the authors!
The source code used to conduct experiments for this paper is here.
- A. Al-Zoobi, D. Coudert, A. Finkelstein, and J. Régin, “On Finding k Earliest Arrival Time Journeys in Public Transit Networks,” in 11th International Conference on Operations Research and Enterprise Systems (ICORES), Virtual event, France, 2022, pp. 314-325.
[BibTeX] [Download PDF]@inproceedings{alzoobi:hal-03559992, TITLE = {{On Finding k Earliest Arrival Time Journeys in Public Transit Networks}}, AUTHOR = {Al-Zoobi, Ali and Coudert, David and Finkelstein, Arthur and R{\'e}gin, Jean-Charles}, URL = {https://hal.inria.fr/hal-03559992}, BOOKTITLE = {{11th International Conference on Operations Research and Enterprise Systems (ICORES)}}, ADDRESS = {Virtual event, France}, PAGES = {314-325}, YEAR = {2022}, MONTH = Feb, KEYWORDS = {Public Transit Routing ; shortest path ; dissimilar paths}, PDF = {https://hal.inria.fr/hal-03559992/file/ptkssp.pdf}, HAL_ID = {hal-03559992}, HAL_VERSION = {v1}, }
PhD defense of Thi Viet Ha Nguyen
- Title: “Graph problems motivated by (low and high) resolution models of large protein assemblies”
- When: December 13, 2021 — 14:00
- Where: Laboratoire I3S (Les Algorithmes – bât. Euclide B), room 007 and live on Zoom
- Committee:
- Etienne Birmelé (referee), Professor, IRMA, Strasbourg, France
- Guillaume Fertin (referee), Professor, LS2N, Nantes, France
- Christophe Paul, Senior Researcher (DR CNRS), LIRMM, Montpellier, France
- Blerina Sinaimeri, Senior researcher (CR Inria), Inria Lyon, France
- Stéphane Vialette, Senior researcher (DR CNRS), LIGM, Grenoble, France
- Frédéric Havet (supervisor), Senior researcher (DR CNRS), Université Côte d’Azur, CNRS, I3S, Inria, Sophia Antipolis, France
- Dorian Mazauric (supervisor), Senior Researcher (CR Inria), Inria, Sophia Antipolis, France
-
Abstract: To explain the biological function of a molecular assembly (MA), one has to know its structural description. It may be ascribed to two levels of resolution: low resolution (i.e. molecular interactions) and high resolution (i.e. relative position and orientation of each molecular subunit, called conformation). Our thesis aims to address the two problems from graph aspects.
The first part focuses on low resolution problem. Assume that the composition (complexes) of a MA is known, we want to determine all interactions of subunits in the MA which satisfies some property. It can be modeled as a graph problem by representing a subunit as a vertex, then a subunit-interaction is an edge, and a complex is an induced subgraph. In our work, we use the fact that a subunit has a bounded number of interactions. It leads to overlaying graph with bounded maximum degree. For a graph family F and a fixed integer k, given a hypergraph H = (V (H), E(H)) (whose edges are subsets of vertices) and an integer s,
MAX (∆ ≤ k)-F-OVERLAY consists in deciding whether there exists a graph with degree at most k such that there are at least s hyperedges in which the subgraph induced by each hyperedge (complex) contains an element of F. When s = |E(H)|, it is called (∆ ≤ k)-F-OVERLAY . We present complexity dichotomy results (P vs. NP-complete) for MAX (∆ ≤ k)-F-OVERLAY and (∆ ≤ k)-F-OVERLAY depending on pairs (F, k).
The second part presents our works motivated by high resolution problem. Assume that we are given a graph representing the interactions of subunits, a finite set of conformations for each subunit and a weight function assessing the quality of the contact between two subunits positioned in the assembly. Discrete Optimization of Multiple INteracting Objects (DOMINO ) aims to find conformations for the subunits maximizing a global utility function. We propose a new approach based on this problem in which the weight function is relaxed, CONFLICT COLORING . We present studies from both theoretical and experimental points of view. Regarding the theory, we provide a complexity dichotomy result and also algorithmic methods (approximation and fixed paramater tracktability). Regarding the experiments, we build instances of CONFLICT COLORING associated
with Voronoi diagrams in the plane. The obtained statistics provide information on the dependencies of the existences of a solution, to parameters used in our experimental setup. - Titre: “Problèmes de graphes motivés par des modèles basse et haute résolution de grands assemblages de protéines.”
-
Résumé: Pour comprendre les fonctions biologiques d’un assemblage moléculaire (AM), il est utile d’en avoir une représentation structurale. Celle-ci peut avoir deux niveaux de résolution : basse résolution (i.e. interactions moléculaires) et haute résolution (i.e. position relative et orientation de chaque sous-unité, appelée conformation). Cette thèse s’intéresse à trouver de telles représentations à l’aide de graphes.
Dans la première partie, nous cherchons des représentations basse résolution. Etant donné la composition des complexes d’un AM, notre but est de déterminer les interactions entre ses différentes sous-unités. Nous modélisons l’AM à l’aide d’un graphe : les sous-unités sont les sommets, les interactions entre elles sont les arêtes et un complexe est un sous-graphe induit. Utilisant le fait qu’une sous-unité n’a qu’un nombre limité d’interactions, nous arrivons au problème suivant. Pour un graphe F et un entier k fixés, étant donné un hypergraphe H et un entier s, MAX (∆ ≤ k)-F-OVERLAY consiste à décider s’il existe un graphe de degré au plus k tel qu’au moins s hyperarêtes de H induisent un sous-graphe contenant F (en tant que sous-graphe). La restriction au cas s = |E(H)| est appelée (∆ ≤ k)-F-OVERLAY . Nous donnons une dichotomie de complexité (P vs. NP-complet) pour MAX (∆ ≤ k)-F-OVERLAY et (∆ ≤ k)-F-OVERLAY en fonction du couple (F, k).
Dans la seconde partie, nous nous attaquons à la haute résolution. Nous sont donnés un graphe représentant les interactions entre sous-unités, un ensemble de conformations possibles pour chaque sous-unité et une fonction de poids représentant la qualité de contact entre les conformations de deux sous-unités interagissant dans l’assemblage. Le problème Discrete Optimization of Multiple INteracting Objects (DOMINO) consiste alors à trouver les conformations pour les sous-unités qui maximise une fonction d’utilité globale. Nous proposons une nouvelle approche à ce problème en relâchant la fonction de poids, ce qui mène au problème de graphe CONFLICT COLORING . Nous donnons tout d’abord des résultats de complexité et des algorithmes (d’approximation et à paramètre fixé). Nous menons ensuite des expérimentations sur des instances de CONFLICT COLORING associées à des diagrammes de Voronoi dans le plan. Les statistiques obtenues nous informent sur comment les paramètres de notre montage expérimental influe sur l’existence d’une solution.
PhD defense of Ali Al Zoobi
- Title: “Practical computation of simple paths with length and diversity constraints in complex and multimodal networks”
- When: November 25, 2021 — 10:30
- Where: Inria, Euler Violet and live on Youtube (https://youtu.be/M6ypcki8yF4)
- Committee:
- Mohammed Amine Ait Ouahmed, Research Engineer, Instant-System, Sophia Antipolis, France
- David Coudert (supervisor), Senior Researcher (DR Inria), Inria, Sophia Antipolis, France
- David Ilcinkas (referee), Senior Researcher (CR CNRS), LaBRI, Bordeaux, France
- Christian Laforest, Professor, ISIMA, LIMOS, Clermont-Ferrand, France
- Nicolas Nisse (supervisor), Senior researcher, Inria, Sophia Antipolis, France
- Jean-Charles Régin, Professor, I3S, Université Côte d’Azur, Sophia Antipolis, France
- Laurent Viennot (referee), Senior Researcher (DR Inria), IRIF, Paris, France
-
Abstract: The shortest path problem is one of the most studied problem in graph theory and operations research. A classic generalization of this problem is the problem of finding k shortest simple paths (kSSP for short). That is, the problem of finding a shortest, a second-shortest, etc. until a k-th shortest simple path from a source to a destination in a directed weighted graph. Yen (1971) proposed the state-of-the-art kSSP algorithm, with theoretical time complexity in \(O(kn(m+n\log{n}))\), where n is the number of vertices and m is the number of arcs of the input digraph. Since then, the problem has been widely studied from an algorithmic engineering perspective, that is designing exact algorithms offering better performances in practice.
In this thesis, we study the kSSP problem from an algorithm engineering perspective. More precisely, we design new kSSP algorithms allowing to outperform the state-of-the-art algorithms in terms of running time, memory consumption, or offering a better space-time trade-off. We also show how to apply our algorithms in graphs with arbitrary arc weights without negative cycles.
Then, we study the problem of finding paths respecting dissimilarity constraints. Precisely, we study the complexity of the problem according to four different similarity measures, and we show in which cases the problem is NP-Complete or polynomial time solvable.
Finally, we show how to adapt the kSSP problem to a multimodal public transportation network model, i.e., combining metro, tram, buses, and walk. Precisely, we design some kSSP algorithms to solve a related problem, which is, the problem of finding k earliest arrival journeys from a source station to a destination station in a public multimodal transportation network. - Titre: “Calcul pratique de chemins simples avec des contraintes de longueur et de diversité dans des réseaux complexes et multimodaux”
-
Résumé: Le problème du plus court chemin est l’un des problèmes les plus étudiés en théorie des graphes et en recherche opérationnelle. Une généralisation classique de ce problème est le problème de trouver k plus courts chemins simples (kSSP). C’est-à-dire, le problème de trouver le plus court, le deuxième plus court, etc. jusqu’au k-ième plus court chemin simple d’une source à une destination dans un graphe orienté pondéré. Yen (1971) a proposé l’algorithme avec la meilleure complexité théorique connue pour résoudre le kSSP dans un graphe orienté pondéré à n sommets et m arcs, avec une complexité en \(O(kn(m+n\log{n}))\). Depuis, le problème a été largement étudié du point de vue de l’ingénierie algorithmique.
Dans cette thèse, nous étudions également le problème kSSP sous cet angle, c’est-à-dire que nous proposons des algorithmes exacts offrant de meilleures performances en pratique que l’état de l’art, en termes de temps d’exécution, de consommation mémoire ou offrant de meilleurs compromis espace-temps. Nous montrons aussi comment étendre nos algorithmes au cas des graphes avec des poids arbitraires sans cycles négatifs.
De plus, nous étudions le problème de trouver k plus courts chemins simples qui sont mutuellement dissimilaires. Plus précisément, nous étudions la complexité du problème en fonction de quatre mesures de similarité différentes, et nous montrons dans quels cas le problème est NP-Complet ou peut être résolu en temps polynomial.
Enfin, nous montrons comment adapter le problème kSSP à un modèle de réseau de transport public multimodal. Nous adaptons certains de nos algorithmes pour le kSSP au problème de trouver, dans un réseau de transport public multimodal, les k itinéraires d’une station source et à une station destination arrivant au plus tôt.
PhD defense of Adrien Gausseran
- Title: “Optimization algorithms for network slicing for 5G”
- When: November 9, 2021 — 14:30
- Where: Auditorium E130 of Polytech, Templier 2 building
- Committee:
- Mathieu Bouet (referee), head of network software lab, Thales SIX GTS France, Gennevilliers, France
- Frédéric Giroire (supervisor), Senior Researcher, CNRS, Sophia Antipolis, France
- Brigitte Jaumard, Professor, Concordia University, Montréal, Québec, Canada
- Adlen Ksentini, Professor, EURECOM, Sophia Antipolis, France
- Joanna Moulierac (supervisor), Assistant Professor, Université Côte d’Azur, Sophia Antipolis, France
- Nicolas Nisse (supervisor), Senior researcher, Inria, Sophia Antipolis, France
- Géraldine Texier (referee), Professor, IMT Atlantique, Cesson-Sévigné, France
- Guillaume Urvoy-Keller, Professor, I3S, Sophia Antipolis, France
-
Abstract: Our decade is marked by an increase in the use of mobile networks for industrial and administration actors as well as for the general public thanks to their evolution. The introduction of the 5th generation of mobile networks, 5G, brings a diversity of use cases for mobile networks and a growing number of demands with very heterogeneous needs and with strong quality of service (QoS) constraints. The development of 5G relies on new techniques such as Software Defined Networking (SDN) and Network Function Virtualisation (NFV) technologies. SDN allows the separation of control and data planes by providing centralised network management. NFV decouples network functions from the hardware that performs them through virtualisation. The use of these two technologies automates the management of the network and makes it much more flexible and adaptable to changing traffic flows and requirements. The introduction of the network slicing paradigm leads to a division of the network into multiple independent virtual networks cohabiting on the same infrastructure. This paradigm allows to meet the very heterogeneous needs of future applications. In this thesis, we focus on optimising the resource utilisation of next generation networks in order to decrease operational costs and to accept more demands. We first study the allocation of service function chains, to quickly accept requests and to meet the diverse and high-volume demands of mobile networks. We then study the feasibility of Make-Before-Break reconfiguration of requests, which allows to reconfigure without degrading the QoS. We then scale up our reconfiguration and adapt it to network slicing to be used on future 5G networks. Finally, we optimise the reconfiguration periods by implementing a reinforcement learning algorithm, minimising the management costs.
- Titre: “Algorithmes d’optimisation pour le Network Slicing pour la 5G”
-
Résumé: Notre décennie voit l’accroissement de l’utilisation des réseaux mobiles pour les acteurs industriels et administratifs ainsi que pour le grand public grâce à l’introduction de la 5ème génération de réseaux mobiles : la 5G. La 5G apporte une diversité de cas d’utilisation des réseaux mobiles et un nombre croissant de demandes avec des besoins très hétérogènes mais toujours avec de fortes contraintes de qualité de service (QoS).
La 5G a été développée pour utiliser les technologies de réseaux définis par logiciel (SDN) et de virtualisation de fonctions réseaux (NFV). SDN sépare les plans de contrôle et de données et offre une gestion centralisée du réseau. NFV dissocie les fonctions réseaux du matériel qui les exécute grâce à la virtualisation. Ces technologies automatisent la gestion du réseau et le rendent plus flexible et adaptable à l’évolution du débit du trafic ainsi que de ses besoins. L’introduction du paradigme de découpage du réseau entraîne une division du réseau en des réseaux virtuels indépendants cohabitant sur la même infrastructure. Ce paradigme permettra de répondre aux besoins très hétérogènes des futures demandes.
Dans cette thèse nous nous intéressons à l’optimisation de l’utilisation des ressources des réseaux de nouvelle génération afin de diminuer les coûts opérationnels et d’accepter plus de demandes. Nous étudions d’abord l’allocation de chaînes de fonctions de services, pour accepter rapidement les requêtes et répondre aux demandes diverses et abondantes des réseaux mobiles. Nous étudions ensuite la faisabilité de la reconfiguration Make-Before-Break des requêtes, qui permet de reconfigurer sans dégrader la QoS. Nous adaptons ensuite notre reconfiguration au network slicing pour l’utiliser sur les futures réseaux 5G. Enfin nous optimisons les périodes de reconfiguration grâce à un algorithme d’apprentissage par renforcement, réduisant ainsi les coûts de gestion.
New team member: Chuan Xu
Welcome to our new team member: Chuan Xu.
Chuan Xu received her PhD in Computer Science, titled ‘Power-Aware Protocols for Wireless Sensor Networks’, from University of Paris Saclay in Dec. 2017. After three years of postdocs in project-team NEO, at Inria Sophia Antipolis Méditerranée and Nokia (2018-2021), she joined Université Côte d’Azur (UCA) as an associate professor (“maître de conférences”) in Sept. 2021 and became a member of the I3S laboratory and of project-team COATI. Her main research interests are distributed machine learning, federated learning, population protocols, self-stabilizing distributed algorithms, energy problems in mobile wireless sensor networks and chance constrained program (stochastic optimization).
C@fé-in par Nicolas Nisse: Jouons un peu sur un échiquier (sans jouer aux échecs)
- Quand: 8 juillet 2021 à 13h, en replay sur https://www.youtube.com/watch?v=uOW3HpsTuGY.
- Intrigue: Dans ce Café-in, vous allez apprendre deux jeux/énigmes amusant(e)s (j’espère) auxquels vous pourrez jouer avec vos familles et amis.
- Etant donné un échiquier, sauriez vous couvrir toutes ses cases à l’aide de dominos, exceptées celles de deux coins opposés ?
- Considérons un échiquier classique (8 cases par 8) dont chaque case peut être soit saine soit infectée. Supposez que, si au moins 2 des 4 voisins d’une case infectée sont saines, alors la case infectée devient saine. Quel est le nombre minimum de cases qui doivent être saines initialement pour éradiquer complètement l’infection de l’échiquier ? Vous pouvez tester ce jeu ici : https://scratch.mit.edu/projects/517390361/
A travers ces jeux, nous discuterons de questions importantes dans le travail des chercheurs comme « y a t-il une solution ? », « combien y a-t-il de solutions ? », « est-ce que cette solution est optimale ? » … Précisément, je répondrai à ces questions dans le cas des deux jeux proposés en présentant de très belles preuves de la littérature (oui, des preuves peuvent être « belles »: élégantes et simples). Pour finir, je présenterai une généralisation du second problème et montrerai brièvement ses relations avec le jeu de la vie de John Conway qui, malgré des règles très simples, permet de simuler n’importe quel ordinateur.
- Biographie: Nicolas Nisse est CR Inria dans l’équipe COATI. Ses sujets de recherche portent sur l’algorithmique des graphes avec des applications dans les réseaux de télécommunication, routiers, sociaux… En particulier, son travail s’appuie sur la théorie des jeux combinatoires dans les graphes. Nicolas Nisse est ingénieur Supélec, a effectué sa thèse à l’université Paris-Sud 11 puis un postdoc à l’université du Chili (Santiago, Chili) et un postdoc dans l’équipe Mascotte (devenue COATI). Il est également membre de Terra Numerica.
- En savoir plus sur MASTIC et C@fé-in.
PhD defense of Thibaud Trolliet
- 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.