Search

L'analyse et la prévision du comportement des réseaux de transport sont aujourd'hui des éléments cruciaux pour la mise en place de politiques de gestion territoriale. La simulation informatique du trafic routier est un outil puissant permettant de tester des stratégies de gestion avant de les déployer dans un contexte opérationnel. La simulation du trafic à l'échelle d'une ville requiert cependant une puissance de calcul très importante, dépassant les capacités d'un seul ordinateur. Dans cette thèse, nous étudions des méthodes permettant d'effectuer des simulations de trafic multi-agent à large échelle. Nous proposons des solutions permettant de distribuer l'exécution de telles simulations sur un grand nombre de coeurs de calcul. L'une d'elle distribue directement les agents sur les coeurs disponibles, tandis que la seconde découpe l'environnement sur lequel les agents évoluent. Les méthodes de partitionnement de graphes sont étudiées à cet effet, et nous proposons une procédure de partitionnement spécialement adaptée à la simulation de trafic multi-agent. Un algorithme d'équilibrage de charge dynamique est également développé, afin d'optimiser les performances de la distribution de la simulation microscopique. Les solutions proposées ont été éprouvées sur un réseau réel représentant la zone de Paris-Saclay. Ces solutions sont génériques et peuvent être appliquées sur la plupart des simulateurs existants. Les résultats montrent que la distribution des agents améliore grandement les performances de la simulation macroscopique, tandis que le découpage de l'environnement est plus adapté à la simulation microscopique. Notre algorithme d'équilibrage de charge améliore en outre significativement l'efficacité de la distribution de l'environnement. Nowadays, analysis and prediction of transport network behavior are crucial elements for the implementation of territorial management policies. Computer simulation of road traffic is a powerful tool for testing management strategies before deploying them in an operational context. Simulation of city-wide traffic requires significant computing power exceeding the capacity of a single computer. This thesis studies the methods to perform large-scale multi-agent traffic simulations. We propose solutions allowing the distribution of such simulations on a large amount of computing cores. One of them distributes the agents directly on the available cores, while the second splits the environment on which the agents evolve. Graph partitioning methods are studied for this purpose, and we propose a partitioning procedure specially adapted to the multi-agent traffic simulation. A dynamic load balancing algorithm is also developed to optimize the performance of the microscopic simulation distribution. The proposed solutions have been tested on a real network representing the Paris-Saclay area. These solutions are generic and can be applied to most existing simulators. The results show that the distribution of the agents greatly improves the performance of the macroscopic simulation, whereas the environment distribution is more suited to micro- scopic simulation. Our load balancing algorithm also significantly improves the efficiency of the environment based distribution.

In this paper, we want to study the informative value of negative links in signed complex networks. For this purpose, we extract and study a collection of signed networks representing voting sessions of the European Parliament (EP). We first process some data collected by the VoteWatch Europe Website for the whole 7 th term (2009-2014), by considering voting similarities between Members of the EP to define weighted signed links. We then apply a selection of community detection algorithms, designed to process only positive links, to these data. We also apply Parallel Iterative Local Search (Parallel ILS), an algorithm recently proposed to identify balanced partitions in signed networks. Our results show that, contrary to the conclusions of a previous study focusing on other data, the partitions detected by ignoring or considering the negative links are indeed remarkably different for these networks. The relevance of negative links for graph partitioning therefore is an open question which should be further explored., Dans cet article, nous étudions la valeur informative des liens négatifs propres aux réseaux complexes signés. Pour ce faire, nous extrayons et analysons une collection de réseaux signés représentant des sessions de vote au Parlement Européen (PE). Nous traitons d'abord les données recueillies par le site VoteWatch pour la 7 me législature (2009-2014), en utilisant la similarité des votes entre députés pour déterminer les signes et poids des liens. Nous appliquons ensuite à ces données une sélection d'algorithmes de détection de communautés, conçus pour traiter seulement des liens positifs. Nous faisons de même avec Parallel ILS, un algorithme récemment proposé pour identifier des partitions équilibrées dans des réseaux signés. Nos ré-sultats montrent que, contrairement aux conclusions d'une étude précédente traitant d'autres données, les partitions détectées dans nos réseaux varient remarquablement suivant qu'on con-sidère ou ignore les liens négatifs. La pertinence des liens négatifs dans le contexte du parti-tionnement de graphe est donc une question ouverte, qui mérite d'être explorée plus avant.

National audience

In the present Ph.D. dissertation I present results concerning disordered and frustrated models of relevance in statistical mechanics and in combinatorial optimization. As an application of spin glass theory I study the disordered and frustrated Blume-Emery-Griffiths model. The model is treated in its mean-field approximation using replicas. Within the Ansatz of replica-symmetry, I present a complete numerical solution; I also discuss effects of replica symmetry breaking. The stability of the RS solution is studied and the regions of instability inferred. The phase diagram exhibits first and second order transitions. The tricritical point is still present in the frustrated model, in agreement with former work. A version of the BEG model with disordered chemical potential is also studied. The calculations confirm that the disorder decreases the tricritical temperature. Next, I consider the graph partitioning problem, a combinatorial optimization problem, which, from the point of view of statistical mechanics is a spin glass model with the constraint of zero magnetisation. I focus on the statistical properties of low energy solutions generated by "heuristic" algorithms designed to solve such hard combinatorial optimization problems. Several heuristics proposed to solve this problem were implemented. Scaling laws are obtained; in particular, the average cost and its variance grow linearly with the number of vertices of the graphs. As a consequence the cost found by the heuristics is self-averaging. I suggest that this property is quite general, valid for random solutions, quasi-optimal solutions, and probably for the optimum solutions, too. Furthermore a ranking method is proposed and illustrated on an ensemble of graph partitioning problems. This ranking procedure takes into account the quality of the solution as well as the time necessary to find that solution. In the third part of this dissertation I study in detail the zero-temperatures properties of spin glasses on sparse random graphs with fixed connectivity. Spin glasses on these graphs may be considered as a more realistic approximation to real spin glasses as represented by the model of Sherrington and Kirkpatrick. I have designed a new algorithm for finding low energy states. Second, I present a method for deriving the ground state energy from heuristic algorithms, even though they are not guaranteed to find the optimum. Third, I present a numerical test of a conjecture due to Banavar, Sherrington and Sourlas, giving the large volume energy density of the ground states as function of the connectivity. The distribution of the order parameter is found to be non-trivial, and I give evidence for the presence of ultrametricity for all values of the connectivity. These results confirm the expectation that the remarquable properties of the infinite range Sherrington-Kirkpatrick model carry over to more realistic models, as for example the spin glass model on random graphs with finite connectivity studied in the present work., Dans la présente thèse de doctorat je présente des résultats concernant des modèles désordonnés et frustrés venant de la physique statistique et de l'optimisation combinatoire. Comme application de la théorie des verres de spins, j'étudie le modèle de Blume, Emery et Griffiths désordonné et frustré. Ce modèle est traité dans l'approximation de champ moyen dans le cadre de la méthode des répliques A l'aide de l'Ansatz symétrique dans les répliques je présente une solution numérique complète puis je discute des effets de brisure de cette symétrie La stabilité de la solution symétrique a été Rudik et les régions instables identifiées Le diagramme de phase exhibe des transitions de premier et de second ordre. Le point tricritique persiste dans le modèle frustré, Ce qui est en accord avec des travaux antérieurs une version du modèle BEG avec un potentiel chimique désordonné a également été étudiée. les calculs confirment que le point tricritique apparaît à plus basse température quand il y a du désordre. Ensuite je considère le problème de la bipartition d'un graphe. Ce problème correspond du point de vue de la physique statistique h un verre de spins soumis h une contrainte d'aimantation totale nulle. je considère les propriétés statistiques des solutions de faible énergie engendrées par des algorithmes heuristiques. de tels algorithme sont en général conçus pour résoudre des problèmes d'optimisation combinatoire qui sont NP- difficiles. Plusieurs heuristiques ont 60 implémentées pour le problème de la bipartition de graphe. des lois d'échelle ont été obtenues : en particulier la moyenne et la variance du coût obéissent A une loi linéaire en N. Par conséquent le coût obtenu par des heuristiques est une quantité auto-moyennante. je suggère que cette propriété est générale valable aussi pour les solutions aléatoires pour les solutions quasi-optimales et pour les solutions optimales. En outre je propose une procédure pour comparer des algorithmes heuristiques. Cette procédure tient compte de la qualité de la solution aussi bien que du temps de calcul utilisé. Dans la troisième partie de ma thèse j'ai étudié en détail les propriétés h température nulle des verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe. les verres de spins sur de tels graphes peuvent être considérés comme une approximation aux vrais verres de spins qui est plus réaliste que le modèle de Sherrington et Kirkpatrick. J'ai conçu un nouvel algorithme pour trouver les états fondamentaux. Aussi je teste numériquement une conjecture de Banavar, Sherrington et Sourlas qui donne la densité d'énergie du fondamental dans la limite de grande taille en fonction de la coordination. La distribution du paramètre d'ordre se révèle être non triviale et les données présentent une forte indication de la présence d'ultramétricité pour toutes les valeur de la coordination. Ces résultats confirment que les propriétés particulières des verres de spin, déduites an niveau de l'approximation de champ moyen dans le cadre du modèle de Sherrington et Kirkpatrick, sont aussi présentes pour des modèles plus réalistes comme les verres de spins sur des graphes aléatoires lacunaires avec une coordination fixe.