Responsible digital developments in research and education: where do we start?
Daphné Tuncer (Laboratoire Ville Mobilité Transport, Ecole Nationale des Ponts et Chaussées, IPP)
Jeudi 10 Juillet 2025 à 14h00 en salle 26-00/428
Several recent initiatives have been proposing new directions for research practices and their operations in the computer science community, from updated codes of conduct that clarify the use of AI-assisted tools to the inclusion of ethical statements and the organisation of working groups on the environmental footprint of digitalisation. In this talk, we will discuss what frameworks are needed to help describe the sense of engagement and accountability with which the practitioner of a computing-related area may be confronted, and guide one to think about the incidence of technical realisations beyond techno-centric contributions. We will share examples from current research projects, including the recent organisation of a session at the 2025 Internet Governance Forum, and teaching practices to illustrate some concrete scenarios.
Inference of multi-dimensional political positions of online users and web
Antoine Vendeville, Post-doctorant (Médialab, Sciences-Po)
Jeudi, 12 Juin 2025 à 11h en salle 24-25/405
Several recent initiatives have been proposing new directions for research practices and their operations in the computer science community, from updated codes of conduct that clarify the use of AI-assisted tools to the inclusion of ethical statements and the organisation of working groups on the environmental footprint of digitalisation. In this talk, we will discuss what frameworks are needed to help describe the sense of engagement and accountability with which the practitioner of a computing-related area may be confronted, and guide one to think about the incidence of technical realisations beyond techno-centric contributions. We will share examples from current research projects, including the recent organisation of a session at the 2025 Internet Governance Forum, and teaching practices to illustrate some concrete scenarios.
On the role of diffusion dynamics on community-aware centrality measures
Stephany Rajeh , Hocine Cherifi
Rajeh S, Cherifi H (2024) On the role of diffusion dynamics on community-aware centrality measures. PLoS ONE 19(7): e0306561. https://doi.org/10.1371/journal.pone.0306561
Theoretical and empirical studies on diffusion models have revealed their versatile applicability across different fields, spanning from sociology and finance to biology and ecology. The presence of a community structure within real-world networks has a substantial impact on how diffusion processes unfold. Key nodes located both within and between these communities play a crucial role in initiating diffusion, and community-aware centrality measures effectively identify these nodes. While numerous diffusion models have been proposed in literature, very few studies investigate the relationship between the diffusive ability of key nodes selected by community-aware centrality measures, the distinct dynamical conditions of various models, and the diverse network topologies. By conducting a comparative evaluation across four diffusion models, utilizing both synthetic and real-world networks, along with employing two different community detection techniques, our study aims to gain deeper insights into the effectiveness and applicability of the community-aware centrality measures. Results suggest that the diffusive power of the selected nodes is affected by three main factors: the strength of the network’s community structure, the internal dynamics of each diffusion model, and the budget availability. Specifically, within the category of simple contagion models, such as SI, SIR, and IC, we observe similar diffusion patterns when the network’s community structure strength and budget remain constant. In contrast, the LT model, which falls under the category of complex contagion dynamics, exhibits divergent behavior under the same conditions.
Fast and Robust Flocking of Protesters on Street Networks
Guillaume Moinard, Matthieu Latapy
In: Luca Maria Aiello, Tanmoy Chakraborty, Sabrina Gaito (eds) 16th International Conference, ASONAM 2024, Rende, Italy, September 2–5, 2024, Proceedings, Part IV
doi : TBA
We propose a simple model of protesters scattered throughout a city who want to gather into large and mobile groups. This model relies on random walkers on a street network that follow tactics built from a set of basic rules. Our goal is to identify the most important rules for fast and robust flocking of walkers. We explore a wide set of tactics and show the central importance of a specific rule based on alignment. Other rules alone perform poorly, but our experiments show that combining alignment with them enhances flocking, and that obtained groups are then remarkably robust.
La vérité sur la blockchain
Pablo Rauzy, Professeur associé à up8
Mardi, 21 Janvier 2025 à 11h en salle 24-25-405
On entend de plus en plus parler de nouvelles technologies telles que les « cryptomonnaies », le « métavers », les « NFT », ou encore le « web3 », et celles-ci sont invariablement présentées comme des innovations incontournables du monde de demain, sans que ne soit jamais vraiment expliqué ni pourquoi ni comment… sauf une chose : c’est grâce à « la blockchain » ! En plus de ces nouvelles technologies, « la blockchain » est censée également révolutionner certaines pratiques existantes : par exemple la certification de documents (notariat, diplômes) ou la traçabilité (supply chain, agro-industrie), et parfois même, la démocratie (vote électronique)…
Mais, en vrai, ça sert à quoi, une blockchain ?
Après avoir rapidement expliqué les bases du fonctionnement d’une blockchain, nous partirons de cet état de fait technique pour se poser plusieurs questions (et y répondre !) : concrètement, ça fait quoi, une blockchain ? dans quelles hypothèses ? et du coup, quelles sont les limites de cette technologie ? mais alors, est-ce que ça résout un problème qui existe dans la vraie vie ?
En conclusion, nous reviendrons sur le caractère d’« innovation de rupture » systématiquement associé à cette technologie, et nous nous questionnerons sur son rôle en pratique, non plus techniquement, mais socialement et politiquement.
Planetary Limits, Anti-Limits in Computer Systems And The Missing Scenarios
Florence Maraninchi, Professeure à l’INP Grenoble
Jeudi, 9 Janvier 2025 à 11h en salle 25-26-105
Research in computer science and computer engineering includes several branches dedicated to the environmental impacts of ICT. Green-ICT consists in improving the performances of ICT itself (software, hardware, communication infrastruture) in order to reduce its impacts; Green-by-ICT promises to reduce the impacts of other sectors thanks to ICT. In this talk we will argue that this is not sufficient. Green-ICT optimizations are often (if not always) synonymous of massive rebound effects. Green-by-ICT is nothing more than a promise, at least until now. Moreover there are intrinsic anti-limits in the design principles that make it difficult, if not impossible, to stay within planetary limits. We should start studying other, less techno-optimistic, scenarios. A somewhat extreme hypothesis is that manufacturing new hardware will stop at some point in the future. We should therefore study the “fading-ICT” scenario, using the abundant ICT resources of today to prepare a future of scarcity.
Décarboner les mobilités urbaines : premiers résultats pour comprendre et favoriser le cyclisme en ville
Hervé Rivano, professeur à l’INSA de Lyon et chef de l’équipe Agora
mercredi 06 Novembre 2024 à 14h en salle 24-25/509
La transition des mobilités urbaines vers des modes décarbonés est un levier majeur face aux enjeux du dérèglement climatique. En particulier, développer le cyclisme urbain fait partie des stratégies déployées par les métropoles. Pour autant, la compréhension du comportement des cyclistes est encore parcellaire et les modes de partage de l’espace public cantonné à une répartition spatiale des voiries. Dans cet exposé, nous présenterons des contributions, issues de la thèse de Lucas Magnana, à l’analyse des comportements et une piste de partage dynamique de la voirie qui s’appuient sur l’analyse de données de mobilité et des techniques d’apprentissage machine. Des perspectives de recherche, dont une part se fera dans le cadre du PEPR Mobidec, conclueront l’exposé.
Network Analysis Applied to Financial Stocks
Ixandra Achitouv
Mardi 05 Novembre 2024 à 11h en salle 24-25/405
Financial markets exhibit properties of complex systems. By applying network analysis to stock return correlations, I will present the dynamical properties of the network and their correlation with overall market returns. This approach identifies key variables that provide insight into the complex dynamics of stock interactions and the underlying market structure.
Community detection in directed graphs using stationary distribution and hitting times methods
PHAN Thi Ha Duong
jeudi 24 Octobre 2024 à 14h en salle 26-00/534
Community detection has been extensively developed using various algorithms. One of the most powerful algorithms for undirected graphs is Walktrap, which determines the distance between vertices by employing random walk and evaluates clusters using modularity based on vertex degrees. Although several directions have been explored to extend this method to directed graphs, none of them have been effective. In this paper, we investigate the Walktrap algorithm (Pons and Latapy in J Graph Algorithms Appl 10:191–218, 2006) and the spectral method (Newman in Phys Rev E 88:042822, 2013) and extend them to directed graphs. We propose a novel approach in which the distance between vertices is defined using hitting time, and modularity is computed based on the stationary distribution of a random walk. These definitions are highly effective, as algorithms for hitting time and stationary distribution have been developed, allowing for good computational complexity. Our proposed method is particularly useful for directed graphs, with the well-known results for undirected graphs being special cases. Additionally, we utilize the spectral method for these problems, and we have implemented our algorithms to demonstrate their plausibility and effectiveness.
Géopolitique et réseaux maritimes : l’impact de la guerre Ukraine-Russie sur les connections maritimes de l’Ukraine
Marc-Antoine Faure et Barbara Polo
jeudi 04 juillet de 10h à 12h en salle 24-25/509
Les conflits, qu’ils soient politiques, commerciaux ou militaires, affectent les réseaux de transport. Les opérateurs cherchent à éviter les zones les plus tendues en reconsidérant certaines routes. Des liens peuvent être mis à mal dans le cas des tensions géopolitiques locales, qui peuvent avoir un impact global significatif. Cette présentation propose une analyse du réseau maritime de l’Ukraine et identifie les changements dans sa structure en raison du conflit ayant débuté en 2014, avec l’annexion de la Crimée. Le principal objectif est de mesurer et visualiser les principaux changements survenus dans ce réseau depuis 2010 jusqu’à fin 2023, grâce aux données les plus récentes. L’analyse inclut la modélisation du réseau, la représentation du commerce bilatéral et des routes maritimes. Les principaux résultats confirment l’impact majeur du conflit militaire sur la connectivité portuaire, contribuant ainsi à la littérature sur la vulnérabilité des réseaux maritimes.
Chocs et réseaux maritimes : étude comparée de New York, Kobé et New Orleans
César Ducruet
jeudi 04 juillet de 10h à 12h en salle 24-25/509
Cette présentation s’ouvre sur une brève revue de la littérature sur les chocs dans les réseaux (spatiaux), et plus particulièrement dans le cas des réseaux maritimes. L’absence d’études comparatives a motivé l’analyse conjointe de l’impact de l’attaque des Twin Towers à New York (2001), du tremblement de terre à Kobé (1995), et de l’ouragan Katrina à la Nouvelle-Orléans (2004). L’hypothèse majeure est que des mécanismes identiques sont repérables d’un cas à un autre malgré les différences de nature entre ces chocs. Dans les trois cas et comme attendu, une baisse de trafic significative est observée durant le choc, avec des différences en fonction de la spécialisation commerciale des ports (conteneurs, céréales). Au niveau géographique, on constate une hausse de trafic le long de chaque façade maritime à mesure que la distance à l’épicentre augmente, par effet de diversion. Kobé se distingue par une crise plus longue, son trafic de transit ayant été récupéré par le port proche et concurrent de Busan en Corée du Sud, alors en plein essor. En termes de connectivité, les trois ego-networks se caractérisent par une hausse de leur densité suite au choc, soit une perte d’optimalité dans les circulations maritimes régionales.
Evaluating Network Embedding Through the Lens of Community Structure
Barbour, J., Rajeh, S., Najem, S., & Cherifi, H
In: Cherifi, H., Rocha, L.M., Cherifi, C., Donduran, M. (eds) Complex Networks & Their Applications XII. COMPLEX NETWORKS 2023. Studies in Computational Intelligence, vol 1141. Springer, Cham.
https://doi.org/10.1007/978-3-031-53468-3_37
Network embedding, a technique that transforms the nodes and edges of a network into low-dimensional vector representations while preserving relevant structural and semantic information, has gained prominence in recent years. Community structure is one of the most prevalent features of networks, and ensuring its preservation is crucial to represent the network in a lower-dimensional space accurately. While the core objective of network embedding is to bring related nodes in the original network close together in a lower-dimensional space, common classification metrics overlook community structure preservation. This work addresses the need for a comprehensive analysis of network embedding algorithms at the community level. On a set of synthetic networks that span strong to weak community structure strengths, we showcase the variability in the performance of network embedding techniques across mesoscopic metrics. Additionally, we highlight that the mesoscopic metrics are not highly correlated with the classification metrics. The community structure can further diminish the correlation as its strength weakens.
Modeling both pairwise interactions and group effects in polarization on interaction networks
Duncan Cassells, Lionel Tabourier, Pedro Ramaciotti
In: Botta, F., Macedo, M., Barbosa, H., Menezes, R. (eds) Complex Networks XV. CompleNet-Live 2024. Springer Proceedings in Complexity. Springer, Cham.
https://doi.org/10.1007/978-3-031-57515-0_4
The study of polarization has gained increasing attraction in the past decades. Since observing both opinions and interactions is challenging, epistemic programs such as agent-based models have been proposed as a means to assessing the systemic consequences of social psychology mechanisms. Most results in agent-based models for opinion dynamics have focused on individual opinion constructs and pairwise interactions, with a few works treating group effects as constraints. Meanwhile, a tradition in social sciences has been putting emphasis on how group configuration affects individual behavior. In this work, we introduce a new model for accounting for both pairwise interactions in which actors observe and update opinions, and individual perception of the evolving configuration of groups that make up the population in which they are embedded. Through experiments, we show that pairwise interactions which are different depending on whether they are in-group or out-group, has quantifiable impact on the resulting polarization of a population. In particular, the tolerance toward out-group opinions is shown to have a strong impact on the resulting polarization. Our model produces and accounts for polarized states resulting from group consolidation and fragmentation.
Mapping low-resolution edges to high-resolution paths: the case of traffic measurements in cities
Bastien Legay, Matthieu Latapy
In: Botta, F., Macedo, M., Barbosa, H., Menezes, R. (eds) Complex Networks XV. CompleNet-Live 2024. Springer Proceedings in Complexity. Springer, Cham.
https://doi.org/10.1007/978-3-031-57515-0_1
We consider the following problem: we have a high-resolution street network of a given city, and low-resolution measurements of traffic within this city. We want to associate to each measurement the set of streets corresponding to the observed traffic. To do so, we take benefit of specific properties of these data to match measured links to links in the street network. We propose several success criteria for the obtained matching. They show that the matching algorithm generally performs very well, and they give complementary ways to detect data discrepancies that makes any matching highly dubious.
Visite guidée de la distillerie de Scotch
François Pellegrini (LaBRI, Bordeaux)
jeudi 20 juin à 11h en salle 24-25/405, LIP6, Sorbonne Université
Le partitionnement de graphes est un problème très courant qui a de nombreuses applications dans le domaine de l’informatique scientifique. Du fait de la taille croissante des problèmes à résoudre, de nombreuses mises en œuvre parallèles d’algorithmes de partitionnement de graphes ont été proposées dans la littérature, que ce soit pour des multiprocesseurs à mémoire partagée ou des multi-ordinateurs à mémoire distribuée. Cet exposé présentera les principales structures de données et les algorithmes mis en œuvre au sein des bibliothèques libScotch et libPTScotch. Il se concentrera principalement sur les types d’algorithmes disponibles, plutôt que sur leurs détails d’implémentation. Il abordera néanmoins quelques questions opérationnelles importantes, concernant la reproductibilité et le multi-tâches.
BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
Alexis Baudin, Clémence Magnien, Lionel Tabourier
preprint arXiv:2405.04428
Bipartite graphs are a prevalent modeling tool for real-world networks, capturing interactions between vertices of two different types. Within this framework, bicliques emerge as crucial structures when studying dense subgraphs: they are sets of vertices such that all vertices of the first type interact with all vertices of the second type. Therefore, they allow identifying groups of closely related vertices of the network, such as individuals with similar interests or webpages with similar contents. This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. This algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm, which enumerates the maximal cliques in standard (non-bipartite) graphs. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations. We analyze it theoretically to establish two complexity formulas: one as a function of the input and one as a function of the output characteristics of the algorithm. We also provide an open-access implementation of BBK in C++, which we use to experiment and validate its efficiency on massive real-world datasets and show that its execution time is shorter in practice than state-of-the art algorithms. These experiments also show that the order in which the vertices are processed, as well as the choice of one of the two types of vertices on which to initiate the enumeration have an impact on the computation time.
Faster maximal clique enumeration in large real-world link streams
Alexis Baudin, Clémence Magnien, Lionel Tabourier
Journal of Graph Algorithms and Applications, Vol. 28 No. 1 (2024), p. 149-178
Link streams offer a good model for representing interactions over time. They consist of links (b,e,u,v), where u and v are vertices interacting during the whole time interval [b,e]. In this paper, we deal with the problem of enumerating maximal cliques in link streams. A clique is a pair (C,[t0,t1]), where C is a set of vertices that all interact pairwise during the full interval [t0,t1]. It is maximal when neither its set of vertices nor its time interval can be increased. Some of the main works solving this problem are based on the famous Bron-Kerbosch algorithm for enumerating maximal cliques in graphs. We take this idea as a starting point to propose a new algorithm which matches the cliques of the instantaneous graphs formed by links existing at a given time t to the maximal cliques of the link stream. We prove its validity and compute its complexity, which is better than the state-of-the art ones in many cases of interest. We also study the output-sensitive complexity, which is close to the output size, thereby showing that our algorithm is efficient. To confirm this, we perform experiments on link streams used in the state of the art, and on massive link streams, up to 100 million links. In all cases our algorithm is faster, mostly by a factor of at least 10 and up to a factor of 10**4. Moreover, it scales to massive link streams for which the existing algorithms are not able to provide the solution.
De l’écosystème au graphe dynamique ou comment représenter la nature dans sa complexité.
Jacques Gignoux (iEES-Paris)
mardi 30 avril 2024 à 10h30 en salle 25-26/105, LIP6, Sorbonne Université
L’écologie prétend étudier toutes les formes d’organisation du monde vivant, de la bactérie à la biosphère. Elle utilise pour cela le concept d’écosystème qui malgré sa simplicité autorise des représentations (graphiques, mathématiques, informatiques) efficaces très variées du monde qui nous entoure. Comme beaucoup de systèmes vivants, les écosystèmes sont qualifiés de systèmes complexes, susceptibles de présenter des propriétés émergentes comme la stabilité ou la résilience aux perturbations. Malheureusement, les définitions précise de l’émergence font défaut… ou sont beaucoup trop nombreuses pour être utilisables. Je montre qu’en se donnant une définition formelle d’un système possiblement complexe sous la forme d’un graphe dynamique, on peut arriver à la définition précise de 4 types d’émergence et des conditions dans lesquelles elles se manifestent. Sur cette base, on peut construire un simulateur généraliste applicable à l’écosystème et analysable en tant que système complexe avec des outils algorithmiques encore à définir, dont je proposerai un exemple. L’enjeu de ce travail est de fournir un cadre conceptuel permettant la comparaison des représentations/modèles d’écosystème et l’analyse de leurs propriétés émergentes.
Modèle de graphe hiérarchique pour la représentation et
l’analyse de la mobilité et du réseau maritime
Cyril Ray (École Navale / Arts et Métiers)
jeudi 28 mars 2024 à 14h en salle 25-26/105, LIP6, Sorbonne Université
La crise sanitaire et plus récemment la situation géopolitique internationale que nous traversons nous ont rappelé à quel point nos économies modernes étaient tributaires du transport international de marchandises en général et de la maritimisation des échanges internationaux en particulier (puisque 90% de ce transport s’effectuent par voie maritime). Le transport maritime est donc au coeur de nos économies globalisées. Désormais, à l’aide de nombreux capteurs, un large panel de données maritimes est collecté en continu, archivé, et exploité pour la réalisation de nombreuses applications (suivi des pêches, sécurisation de la navigation, planification de routes optimales, contrôle du respect des règles internationales, protection de la biodiversité…). Les bénéfices de cette numérisation de l’espace et de l’information maritime sont multiples. Elle offre de nombreuses opportunités pour appréhender, analyser, prédire les échanges maritimes par l’analyse des données. Durant cette présentation nous aborderons la conception d’un modèle de graphe de hiérarchique pour représenter les mobilités et le réseau de transport maritime. Le modèle est construit par agrégation de trajectoires sémantiques, elles-mêmes émergentes des données de localisation de navires. Le modèle de graphe se concentre sur les origines, destinations et points saillants des mobilités. Un lien entre les données géographiques et les nœuds du graphe est réalisé par indexation hexagonale hiérarchique. La présentation abordera également l’algorithme d’agrégation hiérarchique et les opérateurs de centralité et mesure d’évolution de la dynamique du graphe.