C'est l'hiver. Et comme tout voyageur fréquent le sait, l'hiver peut entraîner des retards météorologiques dans les aéroports. Un blizzard à Minneapolis, une plaque tournante aéroportuaire majeure, peut rapidement entraîner des retards dans la douceur de Miami ou le brouillard de Londres.

Pour minimiser les perturbations, les analystes du contrôle du trafic aérien s'efforcent de prioriser les efforts de rétablissement. Mais avec tant de variables, il leur est difficile de faire des recommandations confiantes. Mais c'est exactement le genre de problème piloté par les données qu'un ordinateur peut être programmé pour résoudre. Le problème est le temps. Les méthodes actuelles ne sont pas assez rapides pour fournir des solutions en temps réel.

Maintenant, une équipe de recherche dirigée par des informaticiens du PNNL a développé un nouvel outil Graph, appelé Ripples, qui peut résoudre un problème d'analyse graphique complexe comme l'analyse des perturbations aéroportuaires en moins d'une minute sur un superordinateur. Le meilleur outil comparable peut prendre une journée entière sur un ordinateur ordinaire pour résoudre le même problème. Un jour, le jalon informatique peut rendre l'analyse des effets de réseau, comme les perturbations du trafic aérien, accessible aux décideurs en temps réel.

"Notre approche s'appuie sur une méthodologie rigoureuse d'analyse des réseaux sociaux, formellement connu sous le nom de problème de maximisation de l'influence, et le fait évoluer pour qu'il s'exécute sur des plates-formes de calcul parallèle hautement efficaces, " dit Arun Sathanur, un informaticien du PNNL qui a dirigé les travaux de modélisation de l'aéroport. "Ces modèles excellent à trouver des entités influentes, analyser l'impact de la connectivité, et en soulignant où les perturbations ont le plus grand effet d'entraînement en cascade."

L'équipe de recherche, qui comprend également des chercheurs de la Northeastern University et du Volpe National Transportation Systems Center du ministère des Transports, ont présenté leur analyse du réseau aéroportuaire au Symposium international de l'IEEE sur les technologies pour la sécurité intérieure en novembre 2019.

À l'aide de données accessibles au public fournies par la Federal Aviation Administration du ministère des Transports, ils ont regroupé les aéroports en clusters d'influence et ont montré quels aéroports sont les plus influents, ainsi que l'évolution de la liste des "influenceurs" les plus importants au cours de l'année civile.

Les résultats fournissent une preuve de principe, qui pourrait à terme être utilisé pour gérer les perturbations du réseau aéroportuaire, Ajouta Sathanur.

"Ripples fournit un outil puissant pour une planification stratégique et des opérations proactives, et a une large applicabilité à travers les systèmes d'infrastructure de transport en réseau, " a déclaré Sam Chatterjee, chercheur opérationnel au PNNL et chercheur principal pour les travaux de modélisation aéroportuaire menés par Sathanur.

La logistique ultime

Dans un monde de plus en plus congestionné, pouvoir restaurer rapidement le service après des dysfonctionnements accidentels des systèmes ou des violations de la cybersécurité serait un énorme avantage. C'est le domaine de l'analyse de réseau, qui a d'abord été développé pour comprendre comment les gens dans les réseaux sociaux sont connectés les uns aux autres. De plus en plus, l'analyse de réseau et l'analyse visuelle sont utilisées pour faire des choses comme repérer les accès non autorisés aux réseaux informatiques, détecter les relations entre les protéines dans les tumeurs cancéreuses, et résoudre les dilemmes de la congestion des transports comme le problème de la congestion du réseau aéroportuaire.

Cependant, pour que les résultats de l'analyse soient fiables, une séquence de calculs pour calculer la propagation de l'influence doit être effectuée. Cela s'avère être un problème de calcul difficile, dit Mahantesh Halappanavar, scientifique senior au PNNL et chercheur principal d'ExaGraph, un centre de co-conception d'applications financé par le projet Exascale Computing du Department of Energy (DOE).

"Pour de nombreux scénarios du monde réel, il n'est pas toujours clair comment attribuer un poids précis à la force des connexions entre les entités individuelles du réseau, " dit-il. " Nous, donc, répéter les simulations avec plusieurs paramètres pour augmenter la confiance des solutions calculées." Même lorsque les poids sont bien connus, la méthode repose encore sur la réalisation d'un grand nombre de simulations pour identifier les entités influentes.

Ils estiment les influenceurs les plus importants dans n'importe quel groupe en exécutant ces simulations répétées d'un modèle de cascade d'influences jusqu'à ce qu'ils arrivent à une estimation précise. Cette approche est ce qui rend intimidant de trouver même un petit groupe d'influenceurs importants dans un réseau de taille moyenne, prendre des jours pour terminer.

C'est pourquoi l'amélioration spectaculaire de Ripples en termes de vitesse de résolution est si importante.

« Se concentrer sur les entités les plus influentes des grands réseaux peut vite devenir chronophage, " dit Ananth Kalyanaraman, co-développeur de Ripples et de la chaire du centenaire Boeing en informatique à la School of Electrical Engineering and Computer Science, Université d'État de Washington, chez Pullman. "Ondulations, et sa nouvelle variante cuRipples, utilise une stratégie d'exploitation de quantités massives de puissance de calcul, y compris ceux des unités de traitement graphique modernes pour rechercher la « prochaine entité la plus influente » lors de sa recherche. »

Des réponses fiables

Plus loin, Ripples est basé sur la solution fournie avec ce qu'on appelle une "garantie d'approximation, " qui permet à l'utilisateur de troquer la qualité de la solution avec le temps de calculer une solution, tout en ayant la capacité de juger de la qualité de la solution calculée. Les équipes basées sur PNNL et WSU ont travaillé en étroite collaboration pour faire évoluer efficacement l'outil Ripples sur les supercalculateurs les plus rapides gérés par le DOE.

Cette stratégie permet à Ripples de converger efficacement vers une solution de meilleure qualité, jusqu'à 790 fois plus rapide que les méthodes précédentes non conçues pour les systèmes parallèles.

"Si nous pouvions converger vers une solution en moins d'une minute, nous pouvons commencer à l'utiliser comme un outil interactif, " dit Marco Minutoli au PNNL, le développeur principal de Ripples. "Nous pouvons poser et répondre à de nouvelles questions presque en temps réel."

Les scientifiques du PNNL font déjà exactement cela. Ils ont commencé à utiliser Ripples pour analyser des quantités massives de données et trouver les influenceurs les plus importants dans :

• Identifier les espèces les plus importantes au sein d'une communauté de micro-organismes du sol en réponse aux changements d'humidité ;
• Suivre la propagation des maladies infectieuses et proposer des stratégies de confinement pour contrôler la propagation d'une épidémie ; et
• Identifier les composants les plus importants dans les échantillons d'air à inclure dans des modèles climatiques détaillés pour étudier leur influence sur la pollution de l'air.

"Au meilleur de nos connaissances, c'est le premier effort de parallélisation de l'opération de maximisation d'influence à grande échelle, " dit Minutoli.

L'équipe de recherche a mis la méthode à la disposition de la communauté des chercheurs sur Github. Ils planifient la prochaine avancée majeure (cuRipples), qui sera d'optimiser la méthode sur Summit, le supercalculateur le plus rapide du monde.