Analyse de graphes et de réseaux sur Databricks
Cet article présente les capacités de Databricks pour l'analyse de graphes et une introduction aux concepts de base des graphes. Les graphes sont également couramment appelés réseaux, en particulier dans le contexte d'un domaine d'étude spécifique, tel que les réseaux sociaux ou les réseaux de communication.
Un Graphe est un ensemble de sommets connectés par des arêtes. Les sommets sont souvent aussi appelés nœuds, et les arêtes sont parfois appelées links, relations ou arcs. Par exemple, les réseaux sociaux représentent les liens entre les personnes. D'autres exemples incluent les réseaux de transport, tels que les liaisons aériennes, ferroviaires ou par autobus entre les villes, et les réseaux de télécommunications, tels que les câbles qui transportent le trafic Internet entre les serveurs. Le traitement graphique est également couramment utilisé dans des domaines tels que la détection des fraudes ou des menaces et la recommandation de produits. De nombreux problèmes commerciaux bénéficient d'une compréhension et d'une analyse des réseaux via le traitement graphique, et c'est particulièrement puissant lorsqu'il est combiné avec d'autres techniques analytiques, y compris le Machine Learning.
Le diagramme montre un exemple simple. Les nœuds de ce réseau sont 6 pays d'Europe occidentale et centrale. Les lignes, ou arêtes, dans le diagramme indiquent que deux pays partagent une frontière.
Databricks Runtime ML comprend des packages d'analyse réseau pour les problèmes à toute échelle. Pour les réseaux relativement petits pouvant être traités sur un seul nœud de compute, utilisez NetworkX. Pour les grands réseaux qui nécessitent un traitement distribué, utilisez GraphFrames. Vous pouvez également installer des packages open source supplémentaires si nécessaire, ou vous connecter à des partenaires et outils externes pour le traitement graphique et la visualisation.
Le reste de cet article décrit les concepts de base de l'analyse réseau et inclut un Notebook qui utilise le package NetworkX pour illustrer certains de ces concepts.
Concepts d'analyse de graphe et de réseau
Cette section décrit certains des concepts de base de l'analyse réseau.
Nœuds et arêtes
En analyse de réseau, un réseau, ou graphe, se compose d'un ensemble de nœuds et d'un ensemble d'arêtes, ou Link, qui connectent les nœuds. Les nœuds représentent les éléments connectés, tels que des personnes ou des villes. Les arêtes représentent les connexions ou les relations entre eux, tels que les personnes qui ont travaillé ensemble, ou les gares qui ont un direct Link entre elles.
Les nœuds sont aussi appelés sommets, points ou entités. Les arêtes sont aussi appelées lignes, relations ou Link.
Réseaux dirigés et non dirigés
Une arête dans un réseau peut représenter une relation unidirectionnelle, comme un fan suivant une célébrité sur un réseau social, ou une relation bidirectionnelle, comme des collègues. Si les arêtes peuvent être unidirectionnelles, le réseau est dit orienté. Si les arêtes n'ont pas de direction associée, le réseau est dit non dirigé.
Arêtes pondérées
Les arêtes peuvent avoir des poids. Les exemples de poids dans un réseau peuvent être la capacité de charge d'une autoroute ou d'un câble.
Degré
Le degré d'un nœud est le nombre d'arêtes qui Link à celui-ci. Par exemple, dans le diagramme précédent, le nœud « France » a un degré de 4.
Pour les graphes orientés, le degré entrant est le nombre d'arêtes arrivant au nœud, et le degré sortant est le nombre d'arêtes s'éloignant du nœud.
Propriétés du réseau et des nœuds
Chemin d'accès le plus court
Le chemin le plus court est la distance minimale entre deux nœuds, en tenant compte des Link directionnels et, facultativement, des poids des arêtes. Par exemple, dans le diagramme précédent, le chemin le plus court entre les nœuds Allemagne et Espagne passe par la France, pour une distance de chemin de 2.
Centralité
La centralité est un moyen de mesurer l'importance d'un nœud dans un réseau. Il existe plusieurs mesures de centralité. La centralité de degré d'un nœud est basée sur la fraction de nœuds dans un réseau auxquels le nœud est directement connecté. La centralité d'intermédiarité d'un nœud est la fraction des chemins les plus courts dans un réseau qui passent par le nœud.
Distribution des degrés
La distribution des degrés d'un réseau est le nombre de nœuds de chaque degré. Il fournit des informations sur la structure et l'organisation du réseau.
Diamètre
Le diamètre d’un réseau est le maximum des chemins les plus courts entre deux nœuds. Le diamètre est équivalent à l’excentricité maximale des nœuds dans un réseau.
Densité
La densité d'un graphe est le nombre d'arêtes dans le graphe divisé par le nombre total d'arêtes possibles. Pour un graphe non orienté, le nombre total d'arêtes possibles est n(n-1)/2, où n est le nombre de nœuds. Pour un graphe orienté, chaque arête a deux directions possibles, donc le nombre total d'arêtes possibles est n(n-1).
Réseaux du petit monde
La plupart des réseaux réels ne sont pas connectés de manière aléatoire, et présentent plutôt des motifs et des sous-structures. Un exemple d'un tel modèle dans les réseaux impliquant des personnes est le « phénomène du petit monde », par lequel nous observons des sous-groupes étroitement liés et une courte longueur de chemin moyenne entre deux nœuds quelconques. Ces modèles sont très courants dans la pratique et entraînent des problèmes fréquents de traitement graphique à Monter en charge, tels que les occurrences naturelles de distorsion des données à gérer lors du traitement de Graphes volumineux.
Exemple de Notebook
Le notebook d'exemple suivant utilise le package NetworkX, intégré à Databricks Runtime pour le ML, pour illustrer certains concepts d'analyse de réseau de base.