VOILÀ POURQUOI CETTE PROMENADE A CHANGÉ LE MONDE… CMH#29

Cette vidéo est issue d’une rencontre avec le Centre de physique théorique (Aix-Marseille Université / CNRS / Université de Toulon), sur une idée originale de Play Azur Prod (https://playazur-prod.fr/), Aix-Marseille Université et le CNRS.

Pour découvrir d’autres projets de recherche, rendez-vous au Festival Explore du 27 mai au 2 juin 2024 à Marseille : https://explore.univ-amu.fr

Ces recherches et cette vidéo ont été financées en tout ou partie par l’Agence Nationale de la Recherche (ANR).

► POUR SOUTENIR LA CHAÎNE :
• Un petit pourboire?
https://fr.tipeee.com/mathador
• Partager cette vidéo à vos amis
• Mettre des pouces bleus, et poster des commentaires
► RÉSEAUX SOCIAUX
• facebook : https://www.facebook.com/Mathador-960047670809006
• twitter : https://twitter.com/mathador5
• Instagram : https://www.instagram.com/franckdunas

►SOURCES

LES PONTS DE KÖNIGSBERG

• La cathédrale : https://fr.wikipedia.org/wiki/Cathédrale_de_Königsberg
• super document de Paul Deguire Département de mathématiques et statistique Université de Moncton, Canada : https://www.umoncton.ca/umcm-sciences-mathstat/files/umcm-sciences-mathstat/wf/wf/pdf/les_ponts_de_konigsberg_1.pdf

LA THEORIE DES GRAPHES :
• Un super pdf de l’inévitable Yvan Monka : https://www.maths-et-tiques.fr/telech/GraphesTESL1.pdf

NOTION DE RESEAU :
• Super article qui résume parfaitement l’histoire des réseaux complexes: https://journals.openedition.org/communicationorganisation/4093

• l’article fondateur de Moreno à l’origine des sociogrammes. : « Who shall survive? A new approach to the problem of human interrelations” 
https://libarch.nmu.org.ua/bitstream/handle/GenofondUA/19122/ec864a8b154e504d3ca6f099b94331d8.pdf?sequence=1

ETUDE DU PETIT MONDE (MILGRAM)
• https://snap.stanford.edu/class/cs224w-readings/milgram67smallworld.pdf

SCIENCE DES RESEAUX ET EPIDEMIOLOGIE
• https://theconversation.com/que-sait-on-du-role-des-ecoles-dans-lepidemie-de-covid-19-cinq-experts-repondent-158259
• Ebola : (2014) https://www.cpt.univ-mrs.fr/~barrat/lefigaro_Oct2014.pdf
• https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0119678

LA COLLABORATION SOCIOPATTERNS

• https://www.cpt.univ-mrs.fr/~barrat/LaRecherche_mai2012_couleur.pdf
• https://www.cpt.univ-mrs.fr/~barrat/LesEchos_020179647561.pdf
Salathé M, Bengtsson L, Bodnar TJ, Brewer DD, Brownstein JS, et al., PLOS Comput. Biol. 8(7): e1002616 (2012) http://www.sociopatterns.org/publications/digital-epidemiology/
https://news.cnrs.fr/opinions/modeling-epidemics-back-to-school

LE PROJET DATAREDUX :
• https://dataredux.weebly.com
• Les spans-core : https://dl.acm.org/doi/10.1145/3418226
• Rich Club Coeficient : https://www.nature.com/articles/s41567-022-01634-8
• Rich Club Coeficient : https://en.wikipedia.org/wiki/Rich-club_coefficient

ARTICLE SUR LES HYPER GRAPHES
https://www.nature.com/articles/s41467-023-41887-2

RESSOURCES :

13:35 : Live Social Semantics with SocioPatterns : https://www.youtube.com/watch?v=wNGYqxRwXm4

13:35 : (SocioPatterns) high resolution close contact network data from a French lycée in 2013 — one week
: https://www.youtube.com/watch?v=Lwt9rdkjtfM

15:12 : https://cedric.cnam.fr/vertigo/Cours/RCP216/coursFouilleGraphesReseauxSociaux2.html
15-14 : https://cisco.goffinet.org/ccna/ethernet/principes-conception-lan-cisco/

To begin this video, I’d like to a riddle. See this picture? It represents an envelope. My challenge is simple. Take a sheet of paper, a pencil. And ask yourself if it’s possible to draw this picture without ever lifting a finger. your pencil once, and without ever returning the same side. The answer, at the end of the video… Sometimes, when my ramblings get the better of me the realities of everyday life, I like to wander all over the planet thanks to this incredible tool called google map. I love the feeling of visiting in secret like a little mouse, important places in the history of science. Imagine! You’re quietly in Cambridge University in the footsteps in the footsteps of Isaac Newton or Stephen Hawking, when suddenly, with a click, you’re headlong for Berne, the exact location of Einstein’s former patent office. And then you get the idea to go back to the origins. In an instant you’re in India, in front of the Temple of Chaturbhuj, said to contain the first first representation of the number zero. From here, the travel cravings follow one another and I leave the famous Leaning Tower of Pisa. Galileo did NOT perform his famous falling-body experiment contrary to legend, to spend some time in front of Maryam Mirzakhani’s high school in Teheran. But if there’s one place that particularly fascinates me a single place in front of which I can marvel at for hours on end from behind my screen, it’s this place. For one fine day in 1735, a man stood up from one of these benches for a walk. And at that moment, he had no idea that that his walk will result in nothing less than the choice of GPS routes, the management of overhead overhead lines and power grids, rail networks, genealogy, metro maps metro maps, epidemic management, the circulation of water in a or… the Internet. Generic Chapter 1: Knots and bridges… The man who begins this famous walk is Leonhard Euler. He’s a mathematician and physicist whose fame is already to prove. As for the city in Kaliningrad, the town in which he was still bears in 1735 the name that has remained in the history of mathematics: Königsberg. And contrary to popular belief, it was not physically, but mentally but mentally. Because, at the time, a question arose about Kneiphof Island, a remarkable place for several reasons: Firstly, because it’s home to one of the world’s largest the city’s most emblematic monuments, the Köniksberg Cathedral, destroyed during the the Second World War, then rebuilt since then. The tomb of philosopher Immanuel Kant, who lies in a mausoleum in a mausoleum to the north-east of the cathedral. And finally … bridges. 5 Bridges. Or, more precisely, 7 bridges at the time, which the island from one end to the other, as well as the extension of the Pregolia, the river bordering the island. And Euler’s challenge about of these bridges is the following: Is it possible to plan a walk in which each of the bridges once and only once, returning of the 7 bridges, returning to the starting point? This founding problem is now known as the called the “7 bridges problem”, or “the Königsberg bridges”, and is the basis the basis for a new branch of mathematics that will keep us very busy this trip: graph theory. As is often the case in the history of this subject, mathematicians have devoted themselves to the study of this new disciple before any real before any real applications emerged. And it’s starting with the 7-bridge problem that we begin to formalize these notions: Like the different areas of the island connected by bridges, graphs are a set of points we’ll call vertices called vertices, connected by links which we’ll call edges. From this point on, a new vocabulary enters the world of mathematics to describe the various components of graphs: Two vertices are directly connected by a edge? These vertices are adjacent. Does any vertex start with 3 edges? The vertex is said to be of degree 3. Are all vertices adjacent to each other adjacent? The graph is complete. Gradually, the mathematical formulation became and it soon became clear that the Königsberg bridge problem could be summarized as follows: In this graph representing the regions of the island connected by the bridges, is there a chain that traverses all edges once and only once to return to the starting vertex? Although he never formulated it in this way this way, Euler did have that this problem opened the way to a new a new way of looking at mathematics, in the sense that, for the first time, we weren’t objects themselves, but only in the way they were connected to each other. Chapter 2: From graph to network. “Connected to each other. A notion that resonated with other disciplines, and spread like a rumor through the world of world of ideas: Mathematics would have invented a tool that describes the properties of everything that can be networked… Se could it be that these theoretical properties apply to concrete networks? Even if the graph tool was initially developed the work of mathematics, the answer to this question quickly decades and decades. centuries that followed, and the tool of graphs was adopted in many disciplines. For example, in chemistry, where in this molecule, atoms can be seen as vertices, and its interactions as edges. In the social sciences, where people are linked by social social interactions. Or again, closer to home, in transportation, where airports airports are connected by airlines. From now on, the world of mathematics and that of other other scientific disciplines will work hand in hand, the former to demonstrate theoretical results theoretical results about graphs, the other to see how these results apply apply to their respective disciplines. For example, in response to the Königsberg bridge problem, the Euler-Hierholzer theorem teaches us that in a graph, such a walk is only possible if all the vertices of this graph are of even degree. Algebra also gets involved, when we understand that we can represent a graph a graph as a matrix, which we call an adjacent matrix. The principle is simple: each term of the matrix is equal to the number of edges connecting the other vertices. For example, in this graph, Vertex number 4 is adjacent to to vertices 2, 3 and 5, but not to itself, nor to vertex 1. The 4th row of this matrix is therefore “0 1 1 0 1”. In parallel with the theoretical advances and laws governing this new discipline, the other sciences took over the field. In 1874, when the word “graph” had not yet been yet official (Euler called this field geometry of positions"), Arthur Cayley publishes one of the first representations of molecular graphs. The development of electricity also brings the notion of complete graphs. Applied to this type of network, such structures to ensure network robustness. Indeed, since all vertices of a complete graph graph are connected in pairs, then even in failure at one point in the network, the information can still reach all the vertices of the graph via another path. Unfortunately, such such structures are extremely costly as the number of edges increases exponentially. exponentially. Engineers understand when it’s all a question of compromise in managing such networks… In 1934, Jacob Levy Moreno had the idea of studying the structure of various human communities, and, using graphs as a tool, he constructed what he he called a sociogram. Sociometry, a discipline that grew out of his work, will make it possible to quantitatively study interactions between human groups. In 1929, Hungarian writer Frigyes Karinthy introduced the notion of the degree of separation between human beings, and in a short story of his book “Minden másképpen van” that every person on Earth can be connected by a chain of knowledge comprising at least plus 6 links. This is what we call the 6 handshake theory, which the psychosociologist Stanley Milgram revisited 1967 article with the following protocol: Each person at the start of the experiment given a file containing the name of one of the participants. and clear instructions on how to reach instructions on how to reach them by mail: if the does not know the target personally, then he/she should forward the letter to one of acquaintance she thinks is more likely to know more likely to know her personally. This study, although it has its limitations limitations, confirms what we will call the “Milgram paradox”. Despite the immensity of a network, the degree of separation between vertices remains relatively small. But let’s go back to the previous matrix, in which the most observant and most observant may have noticed a symmetry. This symmetry can be explained by the fact that that the links connecting the vertices are equally equally symmetrical: If A and B are two airports and if A is connected to B, then B is also connected to A. to A. Or if A and B are two computers, in the same way, if A is connected to B on a then B is necessarily connected to A. But this is not always the case. Some networks imply a direction. A direction in the link. The web graph, for example, on which you are watching this video at this very moment. At A and B are two web pages, it’s perfectly possible for A to redirect to B without B redirecting to A. The link is then one-way. We call directed graphs. Finally, the previous matrix contains only 0’s and 1’s. As we’ve seen, the 0 stands for the absence of an edge between two vertices, and the 1 means a connection between the two. But this example doesn’t allow us to differentiate between the links. They appear to be equivalent. However, if we take example of the road network, it seems obvious that that the A6 linking Paris to Lyon is a link much busier than the départementale 301 between Saint Come en Vairais and Rouperoux le coquet. How do you account for this difference? between these edges in a graph? It’s to answer to this kind of imperative, the notion of weighted graph. The idea is simple, each vertex is assigned a weight, a number, which in a way defines the importance of this vertex in the graph. This number can be found in the matrix if if this representation mode is chosen, and we go from an adjacency matrix to a weighted matrix. This is how advances in this field this field took place, mixing dozens of seemingly unrelated disciplines seemingly unrelated. And it’s precisely these links that that will enable the emergence of a the 20th century: network science. century: network science. Chapter 3: A new era. The question is central, and far from trivial : Within the various networks studied so-called “emergent” properties, the networks studied have not been “constructed”. with these characteristics. They themselves from the evolution of the network. and uncontrolled interactions within the within the network. From here, Several questions arise: Firstly, is it possible to develop new interdisciplinary tools for understanding the understanding the mechanisms that lead to the emergence of these properties? And secondly In a kind of retroactive loop, how do these emerging properties of the network influence the network itself? Yet, particularly in the social sciences studies have long been limited by information bias. Unrepresentative samples, collected on personal networks, incomplete, or collected form systems, which do not allow which do not allow for tracking over time… limitations that prevented satisfactory quantitative studies. In order to provide the most accurate their questions, the researchers of the 20th century that the 21st century would provide in proportions they could never have imagined could never have imagined: data. Indeed, since the early 2000s, a veritable digitization of the world, generating a sheer volume of data that borders on a tidal wave of information, almost overnight on the scale of the history of science. Mobile telephony, alone, enables us to collect data on both communication between humans, but also on their mobility. A another scale, GPS data can also be used to collect data of millions of individuals, and thus suggest the best path through the immense graph represented by the millions of possible routes. Computerization also provides the progress of viruses, diseases. For in epidemiology, too, the notion network is central. Just that the degree of a vertex corresponds to the number of interactions an individual has with to understand the impact of network science of network science in this field… Here’s the thing: an abundance of data does not guarantee the absence of bias. And paradoxically, research in recent years recent years shows that a return to intermediate scales, often referred to as “meso scales” is desirable, if not inevitable. As a result, several research groups have set about have set out to build infrastructures that will enable to collect data and better understand and better understand this type of scale intermediate scales, such as a school school, museum or hospital. For example, the SocioPatterns collaboration collaboration collects in this kind of places and interdisciplinary way, data on the physical proximity physical proximity of individuals. Since 2008, this collaboration between Germany, Italy and France, has set up a infrastructure based on a radio-frequency radio-frequency identification badges, which measures the face-to-face proximity of individuals in these environments, thus enabling the creation of a kind of “catalog” of human interactions. These are proving extremely useful in useful in epidemiology, of which infectious disease propagation models of infectious diseases. Following in the footsteps of SocioPatterns, another project, called “dataredux”, will see the light of day in 2020. Funded by the ANR, dataredux is once again working to reduce complexity of networks in order to feed efficient and realistic models. Linking prestigious research structures, this project led by researcher Alain Barrat, research director at the Centre de Physique de Physique Théorique in Marseille, a laboratory of the CNRS, Aix-Marseille University and the University of Toulon. It has to transform gigantic quantities of data into of data into knowledge. The idea is still the same: Reduce complexity by controlling scale but without losing the richness of the data. of the raw data. With a central question that never leaves researchers in this field: In this immense flood of data, what is purely and what is pure chance? relevant information? What do I really need? The answer obviously depends on what I want to do what I want to do with the data…”. Particularly in so-called time networks, i.e. the networks that evolve over time, one of the main one of the main challenges facing is to identify structures (subsets of vertices and links, for a certain period of time) that have a particular role in the processes processes. For example, they identified two particularly interesting notions 1) dense structures, i.e. groups of nodes with a large number of connections between them 2) Their temporal range, i.e. the length of time these vertices summits retain their high density. To this end, in a 2020, researchers proposed an algorithm for efficiently finding in a temporal network what they call “span-cores”, i.e. groups of such nodes, characterized by two numbers, their density and their temporal extent. A second algorithm can even be used to directly find maximum “span-cores”, i.e. the maximum densest or longest-lasting, without having having to calculate all the span-cores. The various experiments associated with this show that this new notion of span-core is highly relevant, for example, to the analysis of social dynamics; for example, nodes participating in such structures can more easily propagate information. In another study, Nicola Pedreschi, Demian Battaglia & Alain Barrat propose to introduce a temporal version of the so-called “Rich-Club”: The “coefficient Rich Club” is a measurement designed to determine the extent to which different hubs in a network are equally connected to each other. In this example, the red vertices are hubs because they are each contain an important degree in the network network, and together they form a “Rich Club”. In a temporal network evolves over time), a question arises concerning these hubs if the degree of these vertices is large, we don’t know whether these links links were simultaneous or not… The “Rich Club” coefficient therefore meets this need for knowledge of link temporality, by representing the maximum value of the density of hubs that remain stable for a certain period of time. Properties such as span-cores or the “rich-club” coefficient characterize temporal networks at intermediate scales, and also to verify that models, which create fictitious time networks, can be used to generate realistic data with properties similar to those of real properties of real data, and can therefore be used, for example, in simulations of the spread disease or information. But however powerful network representation shows limits, which the most recent research that the most recent research is tending to overcome: In fact, the very structure of a graph defines interactions in pairs, from vertex to vertex. another. However, the reality is quite different, and many systems include interactions of order greater than two. For example, if a graph seems suitable for representing a discussion between two people, it is no longer to describe a group discussion. This gave rise to the notion of hypergraphs, which which allow the establishment of models to describe phenomena such as the contagion of an such as the contagion of an opinion, for example, which we will be different depending on whether it is held or by a group of people. These new studies have identified non-trivial non-trivial structures, which are invisible in standard analyses. It seems that hypergraphs have a lot to offer. to network science, and that knowledge in this field knowledge in this field is on the cusp of a new era. in the years to come. But that’s another story… The spread of viruses and rumors, how social networks work, trafficking of all kinds, are just some of the applications applications for this work, and if this video has reached your eyes and ears, this is yet another result of this network science. Finally, once again, the mathematical tool seems indispensable to model the world around us, and this graph theory, so young in the history of science, seems to be no exception to the rule. The resulting science of networks is unparalleled in terms of interdisciplinarity. It also puts an end to the dichotomy between the so-called “hard” sciences humanities and social sciences, because especially in network science, one constantly feeds the other. Epilogue And that’s it. Like Euler, it’s time for me to finish to finish my walk through the science of networks. And to bring this Eulerian cycle full circle cycle, it’s worth pointing out, for those who haven’t deduced it from this video from this video, that the famous Königsberg bridges would only have been possible if each node of the graph were of even degree, which is not the case with this one, for example, or this one (diagram). And the envelope enigma, you might ask? And Well, let’s rephrase the question. we can trace this envelope without lifting the pencil is the same as asking whether there’s such a thing as an Eulerian chain. One of the theorems of graph theory tells us that a graph has an Eulerian chain if and only if it has at most 2 odd-degree nodes. In the case of our envelope, the graph has exactly graph has exactly 2. Here, and here. Mathematics tells us tells us: it’s possible to this feat. And here’s how. Let me know in the comments if you succeeded in tracing it. Until then, don’t take any chances: calculate it!