Admin CliCours
Application des algorithmes de fouille de graphe aux forums d’entraide
Les algorithmes de fouille de graphe utilisés et leurs familles Les algorithmes existent dans l’un des trois niveaux de maturité : • Qualité de production : Indique que l’algorithme a été testé en termes de stabilité et d’évolutivité. Les algorithmes de ce niveau sont préfixés par gds.. • Bêta : Indique que l’algorithme est candidat au niveau de qualité de production. Les algorithmes de ce niveau sont préfixés par gds.beta.. • Alpha : Indique que l’algorithme est expérimental et peut être modifié ou supprimé à tout moment. Les algorithmes de ce niveau sont préfixés par gds.alpha..
Détection de communauté
Une communauté est un groupe de personnes, d’objets ou de concepts qui entretiennent des liens privilégiés parce qu’ils ont des affinités particulières, ou présentent des caractéristiques similaires, ou encore partagent des centres d’intérêts, etc. Au sens du graphe, une communauté est un cluster de nœuds qui sont fortement liés entre eux, et faiblement liés avec les nœuds situés en dehors de la communauté La bibliothèque Neo4j Graph Data Science (GDS) comprend plusieurs algorithmes de détection de communauté, mais selon l’utilité de chacun et notre objectif ainsi que le niveau de maturité, nous avons utilisé les algorithmes suivants
Louvain
C’est un algorithme qui appartient au niveau -Qualité de production-, sa méthode est basée sur la maximisation de modularité , où la modularité 1 quantifie la qualité d’une affectation de nœuds aux communautés. Louvain se caractérise par limite de résolution et une scalabilité bien meilleure. L’algorithme de Louvain est un algorithme de clustering hiérarchique, qui fusionne récursivement les communautés en un seul nœud et exécute le clustering de modularité sur les graphes condensés, mais peut également s’exécuter sur des graphes pondérés, prenant en compte les poids de relation donnés lors du calcul de la modularité .
L’algorithme
Etape 1 : 1- chaque nœud du graphe est affecté à sa propre communauté. 2- pour chaque nœud « i », on calcule le changement de modularité occasionné par la suppression de « i » de sa propre communauté et son déplacement dans la communauté de chacun des voisins « j » de « i » ( « i » est placé dans la communauté qui entraine la plus grande augmentation de la modularité. Si aucune augmentation n’est possible, « i » reste dans sa communauté d’origine). Ce processus est appliqué de manière répétée et séquentielle sur tous les nœuds jusqu’à ce qu’aucune augmentation de la modularité ne se produise. Etape 2 : Tous les nœuds d’une même communauté sont regroupés, et un nouveau graphe est construit où les nœuds sont les communautés de la phase précédente
B- Syntaxe d’exécution
Call gds.louvain.stream (configuration : Map) YIELD nodeId : Integer, communityId : Integer, intermediateCommunityIds : Integer []
Composants fortement connectés
Un ensemble est considéré comme un composant fortement connecté s’il existe un chemin dirigé entre chaque couple de nœuds au sein de l’ensemble. L’algorithme permet de calculer la décomposition d’un graphe à un ensemble des composantes fortement connexes. Cet algorithme appartient au niveau -Alpha-. [48] A- L’algorithme Une application classique de l’algorithme de recherche en profondeur d’abord, un parcours de graphe qui commence à un nœud donné et explore autant que possible le long de chaque branche avant de revenir en arrière. 1- Marquer v comme sommet déjà visité. 2- Pour toutes les arêtes dirigées de v à un sommet w, si le sommet w n’est pas marqué comme déjà visité, alors ajouter w au composant de v et aller à 1 pour w. 3- commençant une nouvelle recherche en profondeur chaque fois que la boucle atteint un sommet qui n’a pas déjà été ajouté à un composant trouvé trouvé précédemment
Télécharger le cours complet
