FR 3068811 A1 20190111 FR 1756528 A 20170710 Fiabilité de cartographies de réseaux L'invention relève du domaine de la cartographie de réseaux physiques, en particulier de réseaux de distribution électrique. La gestion d'un réseau de distribution électrique nécessite d'assurer de nombreuses tâches, notamment d'intervenir rapidement pour réparer les installations en cas d'incident, de raccorder de nouveaux noeuds au réseau existant, d'assurer en temps réel un équilibrage des puissances sur le réseau afin de limiter les risques de surcharge locale, de planifier des interventions pour faire évoluer le réseau en prévision de besoins et contraintes futurs. Classiquement, les Systèmes d'Information Géographique (SIG) constituent un type d'outil à la disposition des gestionnaires de réseau pour assurer de telles tâches. De tels SIG contiennent notamment des cartographies du réseau de distribution électrique. Les cartographies contiennent des données organisées de manière à représenter, le plus fidèlement possible, le réseau physique et les installations qui le constituent. En pratique, les données du SIG doivent être entrées et mises à jour manuellement chaque fois que nécessaire ou qu'une intervention sur le réseau est mise en oeuvre. Des erreurs humaines entraînent des imprécisions et des incohérences dans les SIG par rapport à la réalité du réseau physique. Or, chaque différence entre le réseau physique de distribution et les informations s'y rapportant peut entraîner des incidents et des interventions inefficaces ou contre-productives. Souvent, la détection de telles erreurs relève du hasard. Par exemple, un opérateur sur le terrain constate une erreur dans une cartographie et la signale. Souvent, réparer une telle erreur nécessite le déplacement d'un second opérateur pour identifier précisément l'erreur, la caractériser et enfin pour la corriger. La tenue à jour des données du SIG est complexe, coûteuse et peu efficace. La vérification des données est rarement mise en oeuvre. Pour certains réseaux électriques, les données ne sont pas répertoriées et organisées informatiquement. Le SIG est inexistant et reste à créer. En outre, de nombreux SIG présentent une structure qui n'est pas normalisée et ne sont donc pas directement compatibles les uns avec les autres. Dans des situations où plusieurs acteurs du secteur doivent coopérer, l'échange d'information est complexe. L'invention vient améliorer la situation. 2 Il est proposé un procédé mis en oeuvre par ordinateur de construction d'une cartographie d'un réseau de distribution électrique comprenant au moins un noeud source incluant une pluralité de sorties, et une pluralité de noeuds consommateurs alimentés chacun par une unique sortie. À chaque couple de noeuds correspond un lien reliant les deux noeuds l'un à l'autre. Chacun des 5 noeuds consommateurs est apte à communiquer avec le noeud source par au moins une route de communication sur le réseau de distribution électrique. Chaque route est formée : - d'un unique lien reliant directement le noeud source au noeud consommateur, ou - d'une suite de liens reliant indirectement le noeud source au noeud consommateur par l'intermédiaire d'au moins un autre noeud consommateur formant un noeud relais. 10 Le procédé comprend : a) pendant au moins une période d'observation et pour chaque couple de noeuds consommateurs, compter le nombre de fois que le lien correspondant forme partie d'une route de communication entre le noeud source et un noeud consommateur, b) construire un graphe dans lequel chaque sommet correspond à un noeud consommateur et le 15 poids de chaque arc entre deux sommets est attribué en fonction du nombre de fois que le lien qui relie le couple de noeuds consommateurs correspondant forme partie d'une route de communication établie entre le noeud source et un noeud consommateur, c) partitionner les sommets du graphe en groupes par application d'algorithmes agencés de sorte que : 20 - deux sommets entre lesquels le poids de l'arc est élevé et/ou deux sommets partageant un nombre élevé de voisins communs tendent à être classés dans un même groupe, tandis que - deux sommets classés dans des groupes distincts tendent à présenter un poids de lien faible ou nul et/ou à posséder peu de voisins communs. 25 Un tel procédé permet d'automatiser la construction de cartographies, par création de nouvelles cartographies, ou encore par vérification et/ou correction de cartographies existantes. La plupart des erreurs peuvent être détectées préventivement, sans attendre une éventuelle détection par un opérateur envoyé sur le terrain. Détecter rapidement les erreurs permet de corriger rapidement les plus simples et de planifier à l'avance la correction des plus complexes. Les erreurs 30 identifiées peuvent être corrigées avant de nuire à la gestion du réseau. Dans la plupart des cas, la correction des erreurs elles-mêmes peut être automatisée, ou au moins être mise en oeuvre sans que l'intervention d'un opérateur sur le terrain ne soit nécessaire. Le procédé peut être mis en oeuvre, par exemple, au moyen de dispositifs communicants existants sur le réseau. Dans ce cas, l'installation d'équipements dédiés est superflue. Par exemple, des compteurs 35 communiquant, connus sous la référence commerciale « Linky » sont en cours de déploiement 3 en France. De tels compteurs comprennent un module de communication apte à la mise en oeuvre du procédé, chaque compteur correspondant à un noeud consommateur, parfois appelé « Point De Livraison » (PDL). 5 Selon un autre aspect, il est proposé un système comprenant au moins un concentrateur et une unité de traitement, l'unité de traitement incluant une mémoire apte à stocker au moins une cartographie d'un réseau de distribution électrique. Le réseau de distribution électrique comprend au moins un noeud source incluant une pluralité de sorties, et une pluralité de noeuds consommateurs alimentés chacun par une unique sortie. À chaque couple de noeuds correspond 10 un lien reliant les deux noeuds l'un à l'autre. Chacun des noeuds consommateurs est apte à communiquer avec le noeud source par au moins une route de communication sur le réseau de distribution électrique. Chaque route est formée : - d'un unique lien reliant directement le noeud source au noeud consommateur, ou - d'une suite de liens reliant indirectement le noeud source au noeud consommateur par 15 l'intermédiaire d'au moins un autre noeud consommateur formant un noeud relais. Le concentrateur est agencé pour a) pendant au moins une période d'observation et pour chaque couple de noeuds consommateurs, compter le nombre de fois que le lien correspondant forme partie d'une route de communication entre le noeud source et un noeud consommateur, 20 L'unité de traitement est agencée pour réceptionner les données de comptage et b) construire un graphe dans lequel chaque sommet correspond à un noeud consommateur et le poids de chaque arc entre deux sommets est attribué en fonction du nombre de fois que le lien qui relie le couple de noeuds consommateurs correspondant forme partie d'une route de communication établie entre le noeud source et un noeud consommateur, 25 c) partitionner les sommets du graphe en groupes par application d'algorithmes agencés de sorte que : - deux sommets entre lesquels le poids de l'arc est élevé et/ou deux sommets partageant un nombre élevé de voisins communs tendent à être classés dans un même groupe, tandis que - deux sommets classés dans des groupes distincts tendent à présenter un poids de lien faible ou 30 nul et/ou à posséder peu de voisins communs. Selon un autre aspect, il est proposé un programme d'ordinateur apte à être mis en oeuvre en un procédé de construction d'une cartographie tel que les procédés définis dans les présentes. Selon encore un autre aspect, il est proposé un support d'enregistrement non transitoire lisible par un 4 ordinateur sur lequel est enregistré un programme comprenant des instructions pour la mise en oeuvre d'un des procédés proposés dans les présentes. Les caractéristiques suivantes peuvent, optionnellement, être mises en oeuvre. Elles peuvent être 5 mises en oeuvre indépendamment les unes des autres ou en combinaison les unes avec les autres : - Les poids sont attribués en fonction du nombre de fois que le lien correspondant forme partie d'une route pour un nombre constant de routes entre chaque couple de noeud source et de noeud 10 consommateur. Ceci permet d'améliorer la représentativité de la période d'observation, y compris si certains des noeuds consommateurs sont plus actifs que d'autres en établissant plus de routes de communication durant la période d'observation que durant une période de fonctionnement usuelle. 15 - À l'issu du comptage, une opération intermédiaire d'échantillonnage aléatoire est mise en oeuvre et les opérations de partitionnement sont effectuées à partir des échantillons obtenus, la succession des opérations d'échantillonnage, de construction de graphe et de partitionnement font l'objet d'une boucle itérative. Les biais de mesure sont ainsi réduits. 20 - Les communications entre les noeuds s'établissent selon une architecture distribuée par Courant Porteur en Ligne sur le réseau de distribution électrique. La présence d'un réseau de communication dédié est alors superflue. Les réseaux de distribution électriques pourvus de modules communicants peuvent être rendus compatibles avec peu ou pas de modifications matérielles. 25 - Le procédé comprend en outre : d) comparer la composition des groupes obtenue au rattachement des noeuds consommateurs sur les sorties selon une cartographie préexistante, e) déduire de la comparaison l'exactitude de la cartographie ou l'existence d'au moins une 30 erreur, f) en cas de déduction d'au moins une erreur, corriger la cartographie en fonction de la composition des groupes obtenue. Ceci permet de vérifier, de corriger et/ou de mettre à jour des cartographies existantes. Le partitionnement en groupe peut être combiné et croisé avec d'autres données déjà contenues 35 dans les cartographies existantes. 5 - Le partitionnement inclut la mise en oeuvre d'un algorithme divisif, d'un algorithme agglomératif, d'un algorithme d'optimisation par vérification de densité ou d'une combinaison de tels algorithmes. De tels algorithmes peuvent être mis en oeuvre en grande partie de manière 5 automatisé tout en permettant d'atteindre une haute fiabilité des informations de cartographie. D'autres caractéristiques, détails et avantages de l'invention apparaîtront à la lecture de la description détaillée ci-après, et à l'analyse des dessins annexés, sur lesquels : - la figure 1 est une représentation partielle des données d'une cartographie à vérifier/corriger, 10 - les figures 2 et 3 montrent chacune un diagramme fonctionnel d'un mode de réalisation d'une partie au moins d'un procédé selon l'invention, - les figures 4 et 5 montrent chacune un graphe établi au cours d'un procédé selon l'invention, - les figures 6, 7 et 8 montrent des détails d'un procédé selon l'invention, - la figure 9 est une représentation d'une partition mise en oeuvre selon le procédé, 15 - les figures 10, 11 et 12 montrent chacune une partie d'un mode de réalisations selon l'invention, - la figure 13 montre une partie d'un mode de réalisations selon l'invention, et - les figures 14 et 15 montrent des graphes obtenus au cours d'un procédé selon l'invention. 20 Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. Dans la suite, le terme de cartographie désigne un ensemble de données représentatives de 25 l'organisation mutuelle des équipements d'un réseau telles que des données géographiques et/ou de raccordement. La carte, ou plan de quartier, de la figure 1 est un exemple de représentation visuelle d'une partie des données d'une cartographie. Une telle représentation vise essentiellement à faciliter la compréhension. Une cartographie d'un réseau peut comprendre d'autres données que celles représentées sur le plan de quartier, notamment des données non 30 strictement géographiques telles que des puissances nominales associées à chaque noeud, des caractéristiques relatives aux câblages présents, ou encore les caractéristiques techniques de chaque équipement. Dans l'exemple de la figure 1, la cartographie 100 comprend trois noeuds source 1 comprenant 35 chacun une pluralité de sorties 3, ou lignes, et des noeuds consommateurs 5. Dans l'exemple 6 décrit ici, un noeud source 1 correspond à un transformateur disposé entre le réseau de transport moyenne tension (ou haute tension type A HTA) et le réseau de distribution basse tension (BT) en aval. Par exemple, chacun des noeuds source 1 comprend entre une et dix lignes. En général, chaque ligne s'étend dans un quartier ou une rue pour alimenter les noeuds consommateurs 5 qui 5 s'y trouvent. Le réseau Basse Tension (BT) choisi en exemple présente une structure arborescente. Le sommet de la structure arborescente correspond à un noeud source 1, ici un poste de transformation HTA/BT, alimente un ensemble de sorties 3. Chaque sortie 3 se prolonge par une ligne constituée elle-même d'une succession de tronçons. Les noeuds consommateurs 5 forment des points de branchements distribués le long des tronçons. 10 Les noeuds consommateurs 5 correspondent sensiblement aux « Point De Livraison (PDL) ». Chaque noeud consommateur 5 forme une interface entre le réseau de distribution basse tension BT et un réseau électrique secondaire, généralement privé. En pratique, le noeud consommateur 5 est matérialisé par un ensemble d'équipements, dont un compteur propre à comptabiliser la 15 consommation électrique du réseau secondaire à des fins de facturation. Par abus de langage, les noeuds consommateurs 5 peuvent être appelés compteurs. La cartographie 100 associe chaque noeud source 1 et chaque noeud consommateur 5 à une position géographique, par exemple une adresse postale, et/ou à un identifiant usager/poste. 20 Plusieurs noeuds consommateurs 5 peuvent être associés à un identifiant d'usager commun et/ou à une position géographique commune. Plusieurs noeuds 1, 5 associés respectivement à un identifiant peuvent en outre être associés à une position géographique commune, par exemple pour les logements collectifs ou les zones denses. 25 Pour un usage domestique, tel qu'une habitation ou un commerce, un compteur alimenté en monophasé est généralement suffisant. Pour certains usages, notamment industriels, une alimentation en courant triphasé peut être nécessaire. Dans les exemples décrits ici, chaque sortie (ou ligne) est triphasée conformément à l'usage en France. La demanderesse a constaté que la transmission de données par Courant Porteur en Ligne (CPL) entre deux phases distinctes 30 d'une même sortie restait possible. En variante, les lignes peuvent être monophasées. La cartographie 100 comprend en outre des associations entre des noeuds consommateurs 5 et des sorties 3. Ce dernier type d'association est une information particulièrement utile pour gérer la répartition de la puissance sur le réseau. 35 7 Ainsi, selon la cartographie 100 représentée en figure 1, - les noeuds consommateurs 5 représentés par une croix sont associés à la sortie 3A, - les noeuds consommateurs 5 représentés par un carré sont associés à la sortie 3B, - les noeuds consommateurs 5 représentés par un rond vide sont associés à la sortie 3C, 5 - les noeuds consommateurs 5 représentés par un triangle sont associés à la sortie 3D, - le noeud représenté par un cône de signalisation est répertorié dans la cartographie 100 mais n'est associé à aucune sortie, et - le noeud représenté par un point d'exclamation n'est pas du tout répertorié dans la cartographie 100. 10 En théorie, les associations contenues dans la cartographie 100 devraient correspondre à la réalité physique sur le terrain. Chaque noeud consommateur 5 devrait être alimenté en énergie électrique par la sortie 3 du noeud d'alimentation 1 à laquelle il est associé dans la cartographie 100. Cependant, la cartographie 100 contient des erreurs et des informations sont manquantes. 15 Dans le présent contexte, volontairement simpliste par rapport aux situations réelles, les erreurs et informations manquantes sont connues et identifiées. En outre, la représentation visuelle des câblages sur une carte permet instinctivement de deviner certaines des erreurs et leurs corrections. En pratique, le nombre de données et leur complexité rend une telle détection 20 fastidieuse, voire impossible, sans recherche ciblée et sans l'assistance d'outils informatiques. Dans l'exemple de la figure 1 et d'après la cartographie 100, le noeud consommateur 51 est alimenté par la sortie 3A (représenté par une croix). Il s'agit d'une erreur : le noeud consommateur 51 est en réalité alimenté par la sortie 3E. Dans l'exemple de la figure 1 et d'après la cartographie 100, le noeud consommateur 52 (représenté par un cône de chantier) n'est pas alimenté, ce qui pourrait correspondre par exemple à un compteur installé mais non encore relié. Un opérateur doit donc a priori vérifier le raccordement sur place pour entrer les données pertinentes dans la cartographie 100. Dans l'exemple de la figure 1 et d'après la cartographie 100, le noeud consommateur 53 (représenté par un carré) est alimenté par la sortie 3B. Il s'agit d'une erreur : le noeud consommateur 53 est en réalité alimenté par la sortie 3C. 25 30 8 Dans l'exemple de la figure 1 et d'après la cartographie 100, le noeud consommateur 54 n'existe pas (car non répertorié ; représenté par un point d'exclamation). Il s'agit d'une erreur : le noeud consommateur 54 existe et est alimenté par l'une des sorties 3. 5 Une première méthode connue de détection/correction d'erreurs consiste à comparer la sortie 3 théorique d'un noeud consommateur 5 à la sortie 3 théorique des noeuds consommateurs 5 géographiquement voisins du premier. Ceci suppose que les données utilisées pour la comparaison soient disponibles, fiables, complètes et précises. Ces hypothèses sont rarement vérifiées. En particulier, une telle méthode ne donne pas de résultat probant dans les zones 10 denses ou ayant subi de nombreux changements non encore transcrits dans la cartographie 100. Pour les noeuds consommateurs 51, 52 et 54, le rattachement au noeud source 1 est erroné ou manquant. Pour le noeud consommateur 53, le rattachement au noeud source 1 est correct mais le rattachement à la sortie 3 est erroné. Ce dernier cas d'erreur peut être considéré comme le plus 15 difficile à détecter et à corriger. Par exemple, une analyse basée sur la position géographique du noeud ne permet pas de déterminer de manière fiable la sortie 3 par laquelle il est alimenté. Chacun des noeuds consommateurs 5 comprend un module de communication, ou interface de communication, apte à communiquer avec d'autres modules de communication via le réseau de 20 distribution électrique. Par exemple, les compteurs intelligents ou AMM pour « Automated Meter Management » sont aptes à échanger des données avec un concentrateur. Les concentrateurs sont généralement disposés à proximité des noeuds sources 1. Le concentrateur collecte les données de plusieurs AMM. 25 Dans l'exemple décrit ici, les concentrateurs transmettent à leur tour les informations à une unité de traitement commune et distante, par exemple via un réseau de téléphonie mobile. Ainsi, l'unité de traitement de données comprend un processeur couplé de manière opérationnelle avec une mémoire pour mettre en oeuvre au moins en partie le procédé défini dans les présentes. En variante, une partie au moins du traitement des données peut être mis en oeuvre par les 30 concentrateurs et/ou localement par des équipements voisins des concentrateurs. Par exemple, les opérations de comptage peuvent être effectuées par les concentrateurs, puis des données relatives aux comptages sont transmises à l'unité de traitement. Dans certains cas, analyser et comparer les variations de tension enregistrées par différents 35 noeuds consommateurs 5 permet d'identifier des correspondances et donc de déterminer quels 9 sont les noeuds consommateurs 5 reliés à une source 3 commune. Cependant, des changements de tension mesurés sur un noeud consommateur 5 peuvent résulter de l'activité sur le réseau privé correspondant et/ou sur d'autres réseaux privés alimentés par la même sortie 3. La fiabilité d'une telle analyse est donc faible. En outre, cela nécessite des mesures fréquentes et à des 5 instants coïncidents pour tous les noeuds consommateurs 5. Par ailleurs, cela implique d'enregistrer à long terme des mesures de consommations précises, datées et associées à chaque noeud consommateur. De tels stockages et traitements de données pourraient permettre de déduire des informations précises sur les usages de chaque consommateur. Faciliter par des moyens techniques un tel usage de données à caractère privé n'est généralement pas 10 souhaitable. Autrement dit, la collecte automatisée de telles données pourrait être aisément détournée de l'application prévue (la vérification du contenu des SIG) pour un usage qui nuirait à la confidentialité et à la préservation de la vie privée. Certaines normes et réglementations tendent à restreindre la mise en place de systèmes d'information pouvant être aisément détournés à de telles fins. 15 Parmi les AMM développés, certains comprennent des modules de communication fonctionnant par Courant Porteur en Ligne (CPL). Ainsi, les données sont échangées par le réseau électrique lui-même sans qu'il soit nécessaire de prévoir un réseau de communication dédié entre les noeuds source 1 et les noeuds consommateurs 5. Le réseau de communication utilise 20 physiquement le réseau câblé électrique. Dans certains cas, la technologie de communication mise en oeuvre est de type maillée : un noeud consommateur 5 est apte à communiquer avec un noeud consommateur 5 voisin. Par exemple, les compteurs « Linky » déployés en France sont équipés de module CPL fonctionnant 25 sous protocole «G3 ». Le protocole G3 est adapté spécifiquement aux caractéristiques des réseaux électriques et permet notamment de créer un réseau de communication décentralisé (ou distribué). Ainsi, les noeuds consommateurs 5 les plus éloignés du noeud source 1, ou noeuds terminaux, peuvent échanger efficacement des données avec certains autres noeuds consommateurs 5, ou noeuds commutateurs, faisant office de relais/routeurs. Autrement dit, 30 l'information est transmises de proche en proche d'un noeud consommateur 5 à un noeud consommateur 5 voisin jusqu'au noeud source 1. Ceci permet de pallier les atténuations inévitables du signal CPL sur de longues distances. Ceci permet en outre une adaptation automatique des routes de communication : deux noeuds peuvent communiquer l'un avec l'autre à plusieurs reprises via diverses routes en fonction des situations et notamment en fonction de la 35 disponibilité des équipements. 10 Les routes de communication entre les noeuds consommateurs 5 s'établissent de façon préférentielle entre les noeuds consommateurs 5 reliés à une sortie 3 commune. 5 Dans la suite, on appelle « route de communication » la route reliant un noeud source 1 à un noeud consommateur 5 terminal Les routes sont référencées 9 avec l'indice i identifiant le noeud source 1 et l'indice j identifiant le noeud consommateur 5. Pour un couple d'un noeud source 1 et d'un noeud consommateur 5 terminal, plusieurs routes 91 j différentes peuvent exister. Chaque route 9 est formée : 10 - d'un unique lien 7, j (ou relation) reliant directement le noeud source 1 au noeud consommateur 5, ou - d'une suite de liens 7 7 7 7 reliant indirectement le noeud source 1 au noeud consommateur 5 par l'intermédiaire d'au moins un noeud consommateur 5x, 5y, 5z formant noeud relais. Dans le présent contexte, deux routes 91 j reliant le même couple de noeud i, j par des liens 15 7 différents sont distinguées l'une de l'autre. Un lien 7,y est défini comme un sous ensemble d'une route 9 et un chemin reliant un premier noeud (noeud source 1 ou noeud consommateur 5) à un second noeud (noeud source 1 ou noeud consommateur 5). Dans un réseau, à chaque couple de noeuds x, y correspond un lien 7'y reliant 20 les deux noeuds x, y l'un à l'autre. Chaque lien 7'y est constitué d'une succession d'un ou plusieurs tronçons du réseau électrique. En pratique, deux liens 7'y constitués de différents tronçons du réseau électriques peuvent être utilisés pour transmettre des données entre le premier noeud x et le second noeud y. Dans le présent contexte, ces différences sont ignorées et il n'est pas fait de distinction entre deux liens 7'y établis via différents tronçons du réseau. 25 Autrement dit, il est considéré que, pour chaque couple x, y de noeuds, il existe un unique lien Un lien 7'y peut relier deux noeuds physiquement distants l'un de l'autre, y compris si d'autres noeuds sont présents entre les deux premiers. Par exemple, une route 91 j peut comprendre des liens 7'y qui se superposent au moins en partie sur le réseau physique de sorte que, sur un tronçon de câble, les données peuvent transiter dans deux sens opposés pour une 30 même route 9 Dans une première partie du procédé, un graphe est établi. Le graphe est représentatif des liens 7,y utilisés lors de l'établissement des routes de communications 91,j. 11 Dans une opération 201 de la première partie du procédé, on compte le nombre de fois que chaque lien 7, 7,z, 7y,z forme partie d'une route 9, de communication entre un noeud source 1, et un noeud consommateur 5, terminal. L'opération 201, le comptage, est mise en oeuvre pendant une durée d'observation et pour chaque couple de noeuds consommateurs x, y ; y, z ; x, z. 5 Dans une opération 202 de la première partie du procédé, on construit un graphe dans lequel chaque sommet correspond à un noeud consommateur 5,, 5, 5z et le poids px,y,PY'z' P 'y:7 de, chaque arc entre deux sommets est attribué en fonction du nombre de fois que le lien7', qui relie le couple de noeuds consommateurs 5,, 5y ; 5,, 5z ; 5, 5z forme partie d'une route 9 10 de communication établie entre un noeud source 1 et un noeud consommateur 5 terminal. Plus la durée d'observation et de comptage est longue, plus le graphe obtenu est représentatif de la variété des routes de communication établies, et plus les ressources informatiques nécessaires au traitement sont importantes. 15 Dans un premier mode de réalisation, l'opération 202 est mise en oeuvre en tenant compte de la totalité des résultats (des comptages) de l'opération 201 précédente. Le graphe obtenu est considéré comme « complet ». L'opération 202 est alors dépourvue d'échantillonnage. La suite du procédé peut être mise en oeuvre sur ce seul graphe complet. Dans ce cas, il convient de 20 sélectionner la durée et la période d'observation de manière à limiter le nombre de données à traiter en fonction des ressources informatiques disponibles tout en préservant une représentativité des observations. Dans un deuxième mode de réalisation, l'opération 202 est mise en oeuvre en tenant compte 25 d'une partie seulement des routes de communication surveillées à l'opération 201. Autrement dit, un ensemble de routes de communication est extrait et seules les comptages de liens 7y correspondants sont retenus à l'issu du comptage. Afin d'améliorer la représentativité du graphe, l'échantillonnage est de préférence aléatoire. Cela permet de sélectionner a posteriori le nombre de données à traiter pour construire les graphes. 30 L'échantillonnage peut aussi être temporel : plusieurs comptages sont effectués sur des plages temporelles distinctes. Les graphes obtenus sont considérés comme « échantillonnés ». La suite du procédé peut être mise en oeuvre sur plusieurs des graphes obtenus après échantillonnage. Afin d'améliorer la représentativité du graphe, et indépendamment des deux modes de 35 réalisation qui précèdent, le nombre de routes 9, j pour chaque noeud consommateur j terminal 12 pour lequel les liens 7y sont comptés est rendu le plus homogène possible, et de préférence égal, par exemple par échantillonnage. Autrement dit, le nombre de routes surveillées pendant l'opération 201 est de préférence identique pour chaque noeud consommateur 5, terminal 5 Dans le graphe obtenu, plus la fréquence d'utilisation du lien 7y entre deux noeuds x,y est élevée, plus la force de la relation unissant les deux noeuds x,y est importante. La figure 4 présente un exemple d'une représentation d'un graphe obtenu, ici à partir des routes de communication sous protocole CPL G3. Le noeud central correspond à l'unique noeud source 1 d'un réseau d'essai (sous forme d'un triangle sur la figure 1). Le noeud source 1 est fortement lié 10 à la plupart des noeuds consommateur 5. Cela s'explique par le positionnement particulier du noeud source 1 au centre du réseau en arborescence. Dans les exemples décrits ici, les noeuds source 1 sont ignorés lors de la construction du graphe. Le résultat de la suppression du noeud source 1 de la figure 4 est représenté en figure 5. Cela peut être effectué par suppression effective du sommet correspondant au noeud source 1 ou en ne comptant pas les liens 7y pour 15 lesquels x ou y correspond au noeud source 1 lors de l'opération 201. Dans certaines situations, des noeuds consommateurs 5 peuvent présenter des liens uniquement avec le noeud source 1. Cela correspond généralement au cas des noeuds géographiquement voisins du noeud source 1. Les routes de communication établies correspondantes sont toutes 20 constituées de l'unique lien 7j direct entre le noeud source 1, et ledit noeud consommateur 5, terminal, sans noeud consommateur 5 formant relais. Dans ce cas, les sommets de tels noeuds consommateurs 5 se trouvent isolés (non reliés aux autres sommets) après suppression du sommet du noeud source 1. De tels noeuds ne peuvent être localisés. Les sommets correspondants sont donc aussi supprimés du graphe. 25 Le graphe obtenu peut être représenté sous la forme de la matrice G suivante, pour laquelle l'indice 1 correspond au noeud source 1 et est donc absent et les indices 2 à N correspondent respectivement à chacun des N-1 noeuds consommateurs 5, noeuds isolés exclus : P2,2 - - - G= **. P2,N1 PN,2 - - - PN,N 30 Dans une deuxième partie du procédé, les noeuds consommateurs 5 sont répartis en groupes par partitionnement des sommets du graphe. Le partitionnement est mis en oeuvre par application 13 d'algorithmes de détection de groupes, agencés de manière à tendre vers les deux objectifs suivants : - deux sommets entre lesquels le poids Ny de l'arc est élevé et/ou deux sommets partageant un nombre élevé de voisins communs appartiennent au même groupe, tandis que 5 - deux sommets appartenant à deux groupes distincts ont un poids de lien faible ou nul et à posséder peu de voisins communs. Autrement dit, les algorithmes sont agencés pour définir des groupes, ou communautés, pour lesquels les noeuds 5 d'un même groupe sont fortement connectés entre eux et les connexions intergroupes sont faibles ou nulles. Chaque noeud 5 est affecté à un unique groupe. 10 Des exemples d'algorithmes sont décrits ci-après. Les algorithmes peuvent être classés en trois types : - les algorithmes divisifs détectent les liens intergroupes et les suppriment pour mettre en évidence les groupes ; 15 - les algorithmes agglomératifs rassemblent des noeuds ou des groupes de noeuds présentant des similarités dans un groupe commun ; - les algorithmes d'optimisation par vérification de densité : des fonctions objectives sont maximisées pour définir des groupes de noeuds sur la base de critères de densité. 20 Dans un premier exemple du procédé, la deuxième partie du procédé comprend la mise en oeuvre d'un algorithme agglomératif. Cette deuxième partie est, par exemple, appliquée sur une pluralité de graphes échantillonnés obtenus par la mise en oeuvre de la première partie du procédé selon le second mode de réalisation. L'algorithme agglomératif comprend par exemple l'algorithme de Louvain. Le premier exemple de procédé est représenté par le logigramme de la 25 figure 2. L'algorithme de détection de groupes est appliqué sur une pluralité de graphes échantillons. Chaque graphe échantillon est obtenu par tirage aléatoire de routes de communication 9 observées sur une durée d'un mois et pour les lesquels les liens 7 sont comptés. 30 Un nombre identique de routes 9 pour chaque noeud terminal 5, est retenu pour le comptage des liens 7. Ainsi, le traitement des noeuds terminaux 5, est équitable et la base d'observation reste aussi diversifiée que possible. Si des noeuds terminaux 5 sont plus actifs que d'autres, cela ne crée pas de biais de représentativité (une hétérogénéité des routes établies pour chaque noeud 35 terminal 5 est sans conséquence). Le respect d'un tel critère peut être assimilé à un 14 rééchantillonnage, ou « Bootstrap » en anglais, pour une inférence statistique. Le nombre de routes 9 que l'on choisit de surveiller pour compter les liens 7 est lui-même un hyperparamètre : en jouant sur ce nombre, il est possible de sélectionner la représentativité du graphe et les ressources (informatiques) de traitement qui sont nécessaires. 5 Le partitionnement par algorithme de Louvain est basé sur la maximisation d'une métrique estimant la qualité de la partition réalisée, appelée « modularité ». La modularité d'une partition mesure la différence entre la proportion de liens internes aux groupes et la même quantité dans un graphe équivalent mais défini de manière aléatoire dans lequel aucune structure de groupe 10 n'est attendue. La modularité Q d'une partition P.{ci,..., ck} est définie comme suit : 1,, ' Q=Pii- 2m (5ci' ci) avec Pi,/ étant le poids associé au lien entre les noeuds i et j, kt= -2Ejpi,j étant la somme des poids des liens du noeud i, 15 8(c, cj) =1 si et seulement si c=c. Le facteur -2m est ajouté afin de normaliser les valeurs possibles de Q dans l'intervalle 1-1,1], avec m = -2Eijpi,j. La modularité Q est positive pour un graphe et une partition pour lesquels il n'y a aucun lien (ou 20 un arc de poids nul) entre deux noeuds de groupes différents mais au moins un lien entre deux noeuds du même groupe. La modularité Q est négative pour un graphe et une partition pour lesquels il n'y a aucun lien entre deux noeuds du même groupe mais au moins un lien entre deux noeuds de groupes différents. La modularité Q tend vers zéro lorsque l'on partitionne aléatoirement un graphe dans lequel les arcs (ou arêtes) sont distribués aléatoirement. Dans 25 l'exemple décrit ici, il est considéré qu'une partition de graphe est significative (pertinente) si la modularité Q est supérieure ou égale à 0,3. La sélection d'un tel seuil est basée sur la littérature, et notamment sur le document suivant : M. E. J. Newman, Fast algorithm for detecting community structure in netvvorks, Phys. Rev. E 69, 066133 (2004). En variante, des seuils différents sont choisis. 30 Un exemple d'application de l'algorithme de Louvain sur un graphe est représenté en figure 6. L'application de l'algorithme de Louvain peut être décomposée de la manière suivante. 15 Dans un état initial (représenté en bas à gauche de la figure 6, tirée de M. E. J. Newman et M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004) dans Newman et Girvan (2004)), le nombre de groupe est égal au nombre de 5 noeuds/sommets du graphe. Chaque noeud est classé aléatoirement dans un groupe. Ensuite, dans une première sous-opération, pour chaque noeud i, on estime le gain de modularité Q obtenu en retirant ce noeud i de son groupe et en le plaçant dans le groupe du noeud j. Le noeud i est déplacé dans le groupe pour lequel le gain de modularité Q est maximum, si et 10 seulement si le gain est positif. Le noeud i est alors « réalloué ». La suite estimation-réallocation est réitérée tant que la modularité Q de la partition est améliorée. On obtient un graphe à modularité Q optimisée (représenté en haut de la figure 6). Ensuite, dans une deuxième sous-opération, le graphe de noeuds à modularité Q optimisée est 15 transformé en un graphe de groupes (représenté en bas au centre de la figure 6) : - les sommets représentant chacun un noeud d'un même groupe sont fusionnés en un unique sommet représentant ledit groupe de manière à obtenir un graphe dont chaque sommet représente désormais un groupe. - les arcs entre deux noeuds appartenant à deux groupes distincts sont fusionnés en un arc reliant 20 désormais les deux sommets correspondant aux deux dits groupes. Ainsi chaque arc/arête représente désormais les relations intergroupes. Lors de cette fusion, le poids de chaque arc entre deux sommets-groupes est obtenu en sommant le poids de chaque arc fusionné. - Les arcs internes des groupes (entre les noeuds d'un même groupe) sont transformés en une boucle de poids égal à la somme des poids des arcs internes. 25 L' application de l'algorithme de Louvain est réitérée depuis le classement aléatoire des noeuds dans les groupes tant que cela permet d'augmenter la modularité Q. Le résultat d'une seconde itération est représenté en bas à droite de la figure 6. 30 L' application de l'algorithme forme une heuristique au sens de l'optimisation combinatoire. La partition obtenue (représentée par le graphe obtenu) dépend de l'initialisation (aléatoire) de la partition. Ainsi la partition obtenue peut varier entre deux exécutions successives de l'algorithme. L'application de l'algorithme est donc de préférence réitérée plusieurs fois sur des graphes échantillons différents afin d'améliorer la stabilité du résultat. 35 16 La seconde partie du procédé peut comprendre la construction d'une matrice de similarité M. La matrice de similarité M est carrée et de dimension égale au nombre de sommets du graphe, c'est-à-dire le nombre de noeuds consommateurs 5 de la cartographie 100 auquel on a retranché 5 le nombre de noeuds non reliés au reste du graphe comme décrit ci-avant. Le graphe étant non orienté, la matrice de similarité M est symétrique. La matrice de similarité M est construite par boucles itératives, tel que cela est représenté en figure 2 et décrit en détail ci-après. Dans une opération 301, la matrice de similarité M est initialisée à zéro. Le compteur 10 d'itérations it est initialisé à un. Puis, un algorithme de détection de groupes sur un graphe construit aléatoirement est mis en oeuvre en une itération, par exemple selon la méthode de Louvain décrite ci-avant. 15 Les résultats de la détection de groupes effectuée à l'itération it courante sont sauvegardés dans la matrice M. Dans une opération 302, une matrice D, de détection de groupes est construite pour un graphe construit aléatoirement. La matrice D' est de dimension identique à celle de la matrice de similarité M. Par exemple, la matrice D' prend la forme d'une matrice carrée dont chaque ligne et chaque colonne correspond à un noeud. Chaque terme prend la valeur «1 » 20 lorsque les noeuds correspondant à l'intersection ligne-colonne appartiennent à un groupe commun et prend la valeur « 0 » dans le cas contraire. Dans une opération 303, la matrice D, est ajoutée à la matrice M. Autrement dit, à chaque itération de détection de groupe sur le graphe, la matrice des degrés D, correspondante est ajoutée à la matrice de similarité M. 25 Après construction, la matrice de similarité M permet d'estimer la probabilité que deux noeuds consommateurs 5 appartiennent à un groupe commun Après l'opération 303, il est vérifié si le critère d'arrêt des itérations est atteint. Ici, le critère d'arrêt prend la forme d'un nombre it_max d'itérations à mettre en oeuvre. Si ce n'est pas le cas, 30 le compteur d'itération est incrémenté de un, puis les opérations 302 et 303 sont réitérées sur un nouveau graphe construit aléatoirement. Dans une opération 305, à la fin de la boucle, la matrice M est normalisée. La normalisation de la matrice M comprend une division par le nombre d'itérations effectuées ci-avant (M/it_max). 35 17 La matrice de similarité M normalisée peut être vue comme la matrice d'adjacence d'un graphe dont le poids des liens correspond à la probabilité que deux noeuds appartiennent à un même groupe. 5 Dans le présent contexte, deux noeuds appartenant au même groupe peuvent être considérés comme étant électriquement reliés au même départ 3 d'un noeud source 1, et non seulement au même noeud source 1. Un partitionnement final peut optionnellement être obtenu par une opération supplémentaire 10 306 en appliquant un algorithme de détection de groupe, tel que l'algorithme de Louvain, sur la matrice de similarité normalisée M. Chaque noeud consommateur 5 est ainsi placé dans un groupe, qui représente une structure de noeuds fortement connectés par des liens communicants et par un même rattachement électrique au niveau d'un départ du poste de transformation. 15 Dans un deuxième exemple du procédé, la deuxième partie du procédé comprend la mise en oeuvre d'un algorithme divisif. Cette deuxième partie est, par exemple, appliquée sur un unique graphe complet obtenu par la première partie du procédé. L'algorithme divisif comprend par exemple un algorithme de calcul de centralités d'intermédiarité, par exemple celui de GirvanNewman (ou « edge betweenness » en anglais). Le deuxième exemple de procédé est représenté 20 par le logigramme de la figure 3. Dans une opération initiale 401, un graphe obtenu selon la première partie du procédé, ici un unique graphe complet, est établi. 25 Puis, dans une opération 402, un algorithme de détection de groupes sur le graphe complet est mis en oeuvre, par exemple l'algorithme de Girvan-Newman qui sera décrit plus loin, de manière à obtenir une partition des noeuds dans des groupes. Puis, une opération de correction 403 des partitions est mise en oeuvre : chaque partition du 30 graphe est corrigée par application sur chaque noeud d'un algorithme des plus proches voisins (décrit en détail ci-après) pour déterminer l'appartenance la plus probable à un groupe de noeuds consommateurs 5. Ensuite, la pertinence du regroupement des noeuds dans un groupe est mesurée par la conductance (opération 404). Dans une opération 405, les noeuds du groupe avec la meilleure connectivité sont détachés du graphe des routes. 35 18 La boucle est réitérée sur le graphe ainsi simplifié : les noeuds restants sont de nouveau découper en groupe par application de l'algorithme de détection de groupes (répétition de l'opération 402), et ainsi de suite. Les itérations sont stoppées lorsqu'un critère d'arrêt est atteint, ou lorsqu'il ne reste qu'un seul groupe. 5 L'exemple de l'algorithme de Girvan-Newmann (« Edge Betweenness ») va maintenant être décrit en détail. À la place de déterminer les liens centraux indispensables à la structure d'un groupe, 10 l'algorithme divisif « edge betweenness » est prévu pour détecter les liens connectant des groupes de noeuds les uns avec les autres. Ainsi, plutôt que de construire des groupes par addition de liens forts sur un ensemble de noeuds non connectés, les groupes sont mis en évidence par suppression successive de liens intergroupes. La figure 7 représente l'identification du lien B, ayant la plus forte mesure d' intermédiarité. 15 Pour identifier les liens intergroupes, c'est à dire ceux correspondant à une mesure de centralité d' intermédiarité forte, plusieurs moyens sont connus : - intermédiarité du plus court chemin (ou « shortest-path betweenness ») : déterminer les chemins les plus courts entre deux noeuds du graphe et compter le nombre de fois que chaque 20 lien est emprunté ; - intermédiarité de la marche aléatoire (ou « Random-walk betweenness ») : établir des chemins aléatoires entre deux noeuds, compter le nombre de fois que chaque lien est emprunté et additionner ce nombre pour chaque paire de noeuds du graphe ; - intermédiarité courant-débit « Current-flow betweenness »: calculer la valeur absolue du 25 courant entre deux noeuds, sommée sur toutes les paires de noeuds sources et puits du graphe. Dans «M. E. J. Newman et M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004) dans Newman et Girvan (2004) », les algorithmes divisifs (« edge betweenness ») peuvent être définis de la manière suivante : 30 i. calculer des scores de centralités d'intermédiarité de tous les liens dans le graphe, ii. trouver le lien avec le score le plus élevé et le supprimer du réseau, iii. recalculer les centralités d'intermédiarité pour tous les liens restants, iv. répéter l'étape ii tant que des liens de forte centralité peuvent être supprimés sans dégrader les groupes déterminés aux itérations précédentes ou que le critère de maximisation de la 35 fonction de modularité soit satisfait. 19 La figure 8 est un exemple de groupes identifiés par la suppression successive des liens en gras, ici quatre groupes. La figure 9 représente un dendrogramme (ou arbre de clusters) qui peut être obtenu après mise en oeuvre d'un algorithme divisif. Les extrémités des branches (en bas sur la 5 figure 9) représentent les noeuds du graphe. L'arbre représente un réseau connecté découpé en groupes de plus en plus petits, suivant un parcours descendant de l'arbre. La ligne en pointillé indique la répartition des noeuds dans quatre communautés et le nombre de groupes choisis. L'algorithme des plus proches voisins va maintenant être décrit. Avant simplification du graphe 10 par suppression du groupe de plus faible conductance, chaque noeud est réaffecté au groupe le plus probable suivant l'identification du groupe de ses plus proches voisins (ou noeuds les plus similaires). Cet algorithme comprend les opérations suivantes : 15 - Pour chaque noeud : i. Identifier les noeuds voisins (ceux avec lesquels au moins un lien est partagé), ii. Pour chaque noeud voisin, calculer le taux de voisins communs (voir ci-après), iii. Affecter au noeud le groupe des voisins les plus proches. 20 La similarité entre deux noeuds est mesurée par l'indice de Jaccard, tel que défini par exemple dans « Linyuan Lu et Tao Zhou, Link prediction in complex network : A survey, Phys. A 390 (2011) » : S(X, Y) = T(X) U F (Y) 25 avec /'(X) et F(Y) étant l'ensemble de voisins du noeud X, respectivement Y. Le numérateur représente la liste des voisins communs aux noeuds X et Y. Le dénominateur représente la liste complète de tous leurs voisins. L'indice S mesure le taux de voisins communs et est compris entre 0 et 1. Plus le taux est élevé, plus la probabilité d'appartenance à un même 30 groupe des deux noeuds X et Y est forte. F(x) n F(Y) La figure 10 représente un exemple de deux noeuds u et v ayant trois voisins communs. La figure 11 montre un graphe dans lequel l'affectation initiale de deux noeuds (identifiés par des 20 flèches) est erronée. La mise en oeuvre de l'algorithme des plus proches voisins permet de réaffecter à ces deux noeuds le groupe de leurs plus proches voisins. La figure 12 montre un graphe dans lequel l'affectation initiale d'un noeud (identifié par une flèche) semble erronée. Ici, il est choisi de réaffecter un noeud à un groupe si et seulement si plus de la moitié des noeuds 5 voisins appartiennent à un même groupe. La mise en oeuvre de l'algorithme des plus proches voisins conduit donc, ici, à laisser le noeud affecté au groupe initial même si plus de la moitié des noeuds voisins sont affectés à deux autres groupes. Le partitionnement issu des opérations précitées peut être amélioré en appliquant de manière 10 successive l'algorithme « edge betweenness » (opération 402) sur les noeuds appartenant aux groupes les moins denses. Autrement dit, l'opération 401 peut elle-même être une boucle itérative. Les noeuds appartenant au groupe le plus pertinent sont déterminés par la mesure de la conductance, c'est-à-dire la fraction de liens sortants de la communauté sur le volume total de liens des noeuds du groupe. Plus la conductance est faible, moins les noeuds du groupe partagent 15 de relations avec les noeuds des autres groupes. La formule de la conductance (I) par groupe i est la suivante : (1)- = 2ms + 20 avec C, étant le nombre de liens s'étendant au-delà du groupe (vers des noeuds d'autres groupes), et m, étant le nombre de liens dont l'une au moins des extrémités est un noeud du groupe i La figure 13 représente une succession d'itérations de détection de groupes. À la première 25 itération, le groupe référencé 3 présente la conductance la plus faible. Les noeuds et les liens du groupe 3 sont donc supprimés du graphe. À la deuxième itération, le groupe 2 présente la conductance la plus faible. Les noeuds et les liens du groupe 2 sont donc à leur tour supprimés du graphe. À l'issue de la dernière itération N, 10 groupes ont été successivement identifiés et éliminés Quatre noeuds restent non reliés au reste et sont donc considérés comme isolés. 30 La figure 14 montre les résultats d'un essai de la demanderesse sur des routes de communication créées selon le protocole CPL G3 avec 60 noeuds consommateurs 5. La partie gauche montre le graphe obtenu à l'issue de la première partie du procédé (phase d'observation cs 21 et construction du graphe). La partie droite montre le résultat obtenu après application de l'algorithme de détection de groupes : trois groupes ont été identifiés et présentent respectivement des conductances de 0,06, 0,13 et 0,13. 5 La figure 15 montre une comparaison d'un graphe établi pour des noeuds dont l'attribution initiale des groupes correspond aux données cartographique d'un SIG existant (à gauche de la figure) et du même graphe après correction et réaffectation des groupes selon le procédé. Dans cette exemple, le SIG comprend des données relatives au rattachement des noeuds (ou compteurs) aux divers départs 3 d'un noeud source 1, ici un poste de transformation basse 10 tension. En partie gauche, les trois différentes formes utilisées pour représenter les noeuds consommateurs 5 indiquent respectivement le départ 3 auquel est sensé être relié chaque noeud 5 d'après les informations du SIG. Dans l'essai mené par la demanderesse, des vérifications sur le terrain ont été menées pour 15 identifier avec certitude les erreurs éventuelles : - sept noeuds répertoriés par erreur dans le SIG comme reliés au départ 3 correspondant au signe « triangle » sont en réalité reliés au départ 3 correspondant au signe « carré » ; et - sept noeuds répertoriés par erreur dans le SIG comme reliés au départ 3 correspondant au signe « triangle » sont en réalité reliés au départ 3 correspondant au signe « rond ». 20 Comme le montre la partie gauche de la figure, le procédé permet d'identifier les noeuds 5 dont le rattachement est erroné à partir de l'observation des routes de communication établies sur le réseau de noeuds. Outre la détection des erreurs elle-même, le procédé permet de déterminer comment les corriger. Autrement dit, il est possible d'identifier le départ 3 de rattachement 25 correct de chaque noeud consommateur 5 mal référencé. Durant ses essais, la demanderesse a appliqué le procédé sur 81 noeuds source 1 et 7698 noeuds consommateurs 5. La répartition des cas étudiés ici est la suivante : - 39 noeuds source 1 reliés à moins de 50 noeuds consommateurs 5; 30 - 19 noeuds source 1 reliés à plus de 50 noeuds consommateurs 5 et moins de 100 noeuds consommateurs 5 ; - 23 noeuds source 1 reliés à plus de 100 noeuds consommateurs 5 ; et - 78% des noeuds sources 1 étudiés comprennent entre 2 et 6 départs 3. 22 Les erreurs ou absences de résultats semblent essentiellement dépendantes du nombre de noeuds consommateurs 5 par groupe et du nombre de départs par noeud source 1. En effet, plus le nombre de noeuds consommateurs 5 par départ est faible, plus les marges d'erreur des algorithmes de détection de groupes augmentent. 5 Pour les essais, des vérifications sur le terrain ont permis de levé tout doute et de détecter toute erreur à l'issue de l'application du procédé. Il a été obtenu un taux de confirmation ou de correction valide de 96%. Pour 4% des noeuds consommateurs 3 le procédé n'a pas permis d'identifier un départ de rattachement ou a identifié un départ de rattachement de manière 10 incorrecte. Dans les exemples précédents, les résultats des procédés, c'est-à-dire les partitionnement en groupes des noeuds, sont utilisés pour vérifier, et optionnellement corriger, des cartographies préexistantes. Dans des variantes, les cartographies existantes contiennent peu d'informations 15 fiables ou bien n'existent pas du tout. De tel procédé peuvent être mis en oeuvre pour créer une telle cartographie sans se baser sur une cartographie préexistante. Ainsi, par « construction » d'une cartographie, on entend ici créer une cartographie à partir de rien ou bien créer une cartographie par vérification et/ou correction d'une cartographie préexistante. 20 L'invention ne se limite pas aux exemples de procédé et de système décrits ci-avant, seulement à titre d'exemple, mais elle englobe toutes les variantes que pourra envisager l'homme de l'art REVENDICATIONS1. Procédé mis en oeuvre par ordinateur de construction d'une cartographie (100) d'un réseau de distribution électrique comprenant au moins un noeud source (1) incluant une pluralité 5 de sorties (3), et une pluralité de noeuds consommateurs (5) alimentés chacun par une unique sortie (3), à chaque couple de noeuds (5x, 5) correspondant un lien (7x,y) reliant les deux noeuds (5x, 5) l'un à l'autre, chacun des noeuds consommateurs (5,) étant apte à communiquer avec le noeud source (11) par au moins une route (91,J) de communication sur le réseau de distribution électrique, 10 chaque route (91,J) étant formée : - d'un unique lien (71,J) reliant directement le noeud source (11) au noeud consommateur (Si), ou - d'une suite de liens(7 , 7 7 7) reliant indirectement le noeud source (11) au noeud consommateur (Si) par l'intermédiaire d'au moins un autre noeud consommateur (5x, 5y, 5) formant un noeud relais, le procédé comprenant : 15 a) pendant au moins une période d'observation et pour chaque couple de noeuds consommateurs (5x, 5y ; 5, 5z ; 5, 5, ; 5y, 5z ; 5y, 5, ; 5, 5,), compter (201) le nombre de fois que le lien correspondant (7x 7x,z,7j,7y,z, 7y,j, 7) forme partie d'une route (91,J) de communication entre le noeud source (11) et un noeud consommateur (Si), b) construire (202) un graphe dans lequel chaque sommet correspond à un noeud consommateur 20 (5x, 5y, 5z, 5,) et le poids (ip x,y, PX,Z, PXJ, Py,z, Py,j, Pz,j) de chaque arc entre deux sommets est attribué en fonction du nombre de fois que le lien (7x 7x,z, 7j,7y,z, 7y,j, 7) qui relie le couple de noeuds consommateurs correspondant (5x, 5y ; 5x, 5z ; 5y, 5) forme partie d'une route (9) de communication établie entre le noeud source (1) et un noeud consommateur (5), c) partitionner les sommets du graphe en groupes par application d'algorithmes agencés de sorte 25 que : - deux sommets entre lesquels le poids (p) de l'arc est élevé et/ou deux sommets partageant un nombre élevé de voisins communs tendent à être classés dans un même groupe, tandis que - deux sommets classés dans des groupes distincts tendent à présenter un poids (p) de lien faible ou nul et/ou à posséder peu de voisins communs. 30 2. Procédé selon la revendication 1, dans lequel les poids (p) sont attribués en fonction du nombre de fois que le lien (7) correspondant forme partie d'une route (9) pour un nombre constant de routes (91,J) entre chaque couple de noeud source (11) et de noeud consommateur (Si). 24 3. Procédé selon l'une des revendications précédentes, dans lequel, à l'issu du comptage, une opération intermédiaire d'échantillonnage aléatoire est mise en oeuvre et les opérations de partitionnement sont effectuées à partir des échantillons obtenus, la succession des opérations d'échantillonnage, de construction de graphe et de partitionnement font l'objet d'une boucle 5 itérative. 4. Procédé selon l'une des revendications précédentes, dans lequel les communications entre les noeuds (1, 5) s'établissent selon une architecture distribuée par Courant Porteur en Ligne sur le réseau de distribution électrique. 10 5. Procédé selon l'une des revendications précédentes, comprenant en outre : d) comparer la composition des groupes obtenue au rattachement des noeuds consommateurs (5) sur les sorties (3) selon une cartographie (100) préexistante, e) déduire de la comparaison l'exactitude de la cartographie (100) ou l'existence d'au moins une 15 erreur, f) en cas de déduction d'au moins une erreur, corriger la cartographie (100) en fonction de la composition des groupes obtenue. 6. Procédé selon l'une des revendications précédentes, dans lequel le partitionnement inclut 20 la mise en oeuvre d'un algorithme divisif, d'un algorithme agglomératif, d'un algorithme d'optimisation par vérification de densité ou d'une combinaison de tels algorithmes. 7. Système comprenant au moins un concentrateur et une unité de traitement, l'unité de traitement incluant une mémoire apte à stocker au moins une cartographie (100) d'un réseau de 25 distribution électrique, le réseau de distribution électrique comprenant au moins un noeud source (1) incluant une pluralité de sorties (3), et une pluralité de noeuds consommateurs (5) alimentés chacun par une unique sortie (3), à chaque couple de noeuds (5x, 5y) correspondant un lien (7x,y) reliant les deux noeuds (5x, 5y) l'un à l'autre, chacun des noeuds consommateurs (Si) étant apte à communiquer avec le noeud source (1,) par 30 au moins une route (9,j) de communication sur le réseau de distribution électrique, chaque route (9,) étant formée : - d'un unique lien (7,) reliant directement le noeud source (1,) au noeud consommateur (Si), ou - d'une suite de liens ( .7.,x, 7x 7y,z, 7) reliant indirectement le noeud source (1,) au noeud consommateur (Si) par l'intermédiaire d'au moins un autre noeud consommateur (5x, 5y, 5z) 35 formant un noeud relais, 25 le concentrateur étant agencé pour a) collecter et transmettre à l'unité de traitement des données de comptage du nombre de fois que chaque lien 7j, 7) 7y,J, 7z,J) correspondant à chaque couple de noeuds consommateurs (5x, 5y ; 5, 5z ; 5, 5 ; 5, 5z ; 5, 5 ; 5, 5,) forme partie d'une route (9,,J) de 5 communication entre le noeud source (1,) et un noeud consommateur (5,) pendant au moins une période d'observation, l'unité de traitement étant agencée pour réceptionner les données de comptage et b) construire (202) un graphe dans lequel chaque sommet correspond à un noeud consommateur (5,,, 5, 5, 5,) et le poids (1D,,y, 1D,,z, 1D1Dy,z, 1Dy,j, 1Dz,j) de chaque arc entre deux sommets est 10 attribué en fonction du nombre de fois que le lien (7 7,, 7j, 7', 7y j, 74,) qui relie le couple de noeuds consommateurs correspondant (5x, 5y ; 5, 5z ; 5, 5) forme partie d'une route (9) de communication établie entre le noeud source (1) et un noeud consommateur (5), c) partitionner les sommets du graphe en groupes par application d'algorithmes agencés de sorte que : 15 - deux sommets entre lesquels le poids (p) de l'arc est élevé et/ou deux sommets partageant un nombre élevé de voisins commun tendent à être classés dans un même groupe, tandis que - deux sommets classés dans des groupes distincts tendent à présenter un poids (p) de lien faible ou nul et/ou à posséder peu de voisins communs. 20 8. Programme informatique comportant des instructions pour la mise en oeuvre du procédé selon l'une des revendications 1 à 6, lorsque ce programme est exécuté par un processeur. 9. Support d'enregistrement non transitoire lisible par un ordinateur sur lequel est enregistré un programme comprenant des instructions pour la mise en oeuvre du procédé selon l'une des 25 revendications 1 à 6.