Introduction générale

La détection de communautés dans l'analyse des réseaux sociaux suscite de plus en plus d'attention dans la communauté scientifique et de nombreuses recherches ont été menées dans ce domaine. De nos jours, les réseaux sociaux sur internet apparaissent comme un nouveau moyen important de communication. Tout d'abord, il faut savoir qu'un réseau social est un ensemble d'identités sociales où des individus sont reliés entre eux par des liens d’interactions sociales, il regroupe de nombreux individus, nommés des utilisateurs. Les réseaux sont souvent modélisés par des graphes, une structure permettant l'encodage de données relationnelles. Quel que soit le domaine applicatif.

Les sites de réseautage social font partie des centres dans le monde d'échange de connaissances, de langues et de gains tribaux qui distinguent l'individu du reste du groupe et lui font se développer et se rapporter à des événements que nous pouvons incorporer sous une forme mathématique en utilisant un des ( caractéristiques ) dites théories des graphes, , comme ce qui se passe sur Facebook, Twitter et Instagram à partir de l'échange de messages constitués d'un ensemble de mots-clés, de sémantiques et d'images qui expriment la forme et notre travail de mémoire fin d’étude a pour objectif de présenter et d’étudier quelques méthodes de détection de communautés , en plus l’évaluations avec modèle de données réal, ce rapport de mémoire est structuré comme suit dans

• Le premier et deuxième chapitre, nous traiterons d'identifier les différents modèles de la détection de communauté et les algorithmes choisie respectivement la méthodologie.
• Le troisième et quatrième chapitre, nous aborderons l’étape de la conception à l’aide le PXP concernant les diagrammes et identifications les acteurs externes et internes.
• Le cinquième chapitre l’implémentation de l’algorithme avec langage python.

Chapitre 1 Modèle des données et méthodologie

1.1 Introduction

Dans ce chapitre nous allons présenter le contexte des algorithmes de détection de communauté et la méthodologie de réaliser et choisie les modèles de données.

1.2 Contexte

Le monde qui nous entoure peut être vu comme un ensemble d’interactions entre éléments, qui peuvent être d’origine naturelle et concrète, par exemple des contacts entre êtres humains, ou bien basées sur des constructions plus abstraites comme les interactions économiques régissant les marchés financiers. Elles peuvent avoir lieu à l’échelle microscopique, telles les interactions entre protéines en permanence à l’œuvre dans notre corps, ou au contraire à une échelle macroscopique à l’instar des interactions gravitationnelles entre corps célestes, Ces interactions ou ensembles d’interactions, appelés systèmes complexes, dans de nombreux domaines scientifiques : sociologie, physique, économie, biologie etc. Si les plus simples ont pu être expliquées au fil du temps, une grande majorité d’entre elles échappe encore à une modélisation qui les rendrait prédictibles.

1.3 Problématique

La détection communautaire est devenue au cours de la dernière décennie l'un des problèmes les plus difficiles et les plus étudiés dans l'analyse de réseau complexe, en raison de sa pertinence pour un large éventail d'applications telles que l'étude de l'information et la propagation de l’analyse et benchmarks [1]. Nous avons identifié trois problèmes suivants :

• La taille des modèles.
• Temps de l’exécution.
• Les règles l’opération de benchmark non satisfiable.

1.4 Modèle de données

Un réseau complexe peut être modélisé à l'aide d'un graphe tel que les nœuds représentent des individus et les arêtes un certain type d'interaction entre ceux-ci. Les termes {nœud, sommet} sont utilisés de façon interchangeable pour désigner strictement le même concept ; de même pour [lien, arête] et [communauté, cluster, module]. Le terme {arc} est réservé aux arêtes orientées, c'est-à-dire aux relations non réciproques.

Figure 1 –  Représentations avec sommets et les arrêts une relation indirecte.

1.4.1 Graphe orienté

Un graphe avec p sommets et q arêtes sera nommée un (p, q) graphe, Un graphe orienté G = (V, E) est un digraphe tel que (u, v) ∈ E ⇒ (v, u) ∉ E

Figure 2 – Graphe orienté avec p=6 et q=8

1.4.2 Graphe non orienté

Un graphe non orienté G = (V, E) est un digraphe tel que (u, v) ∈ E ⇒ (v, u) ∈ E

Figure 3 – Graphe non orienté avec p=6 ,q=8

1.5 Traduction numérique

Les graphes possédant une structure en communautés plus ou moins naturelles sont engendrés par le protocole de Newman

1.5.1 Matrice adjacent graphe orienté

Un graphe peut être représenté à l’aide matrice dite d’adjacence () qui indique les connexions entre les nœuds, dans l’exemple suivant on a une matrice avec 6 sommets et 8 les arêtes.

Tableau 01 – Matrice adjacente d’un graphe orienté de figure n°1.

1.5.2 Matrice adjacent graphe non orienté

Tableau 01 – Matrice adjacente d’un graphe non orienté de figure n°3

1.6 Notion les graphes statiques et propriétés

Nous allons vous expliquer certains des principes à prendre en compte pour comprendre les algorithmes de détection de communauté, Soit

1. (m, v) une arête reliant les sommets u et v. Si l'arête est non orientée, alors (m, v) = (v, m)
2. G = G (V, E, W) un graphe simple (sans boucles ni liens multiples), pondéré et non orienté (sauf indication contraire) représentant un réseau où V est l'ensemble des nœuds et E celui des arêtes. , et où W est une matrice, telle que W (u, v) = est le poids de l'arête (m, v) de E. Dans le cas des graphes non-pondérés, w, v = 1, pour chaque lien (m, v) de E. Dans ce cas particulier, le graphe sera noté simplement G = G (V, E)
3. N = |y| le cardinal de l'ensemble V, c'est-à-dire le nombre de sommets du graphe.
4. M = \E\ le cardinal de l'ensemble E, c'est-à-dire le nombre de liens du graphe
5. d(u) =  le degré du sommet u de V, c'est-à-dire la somme des poids des arêtes non orientées dont une extrémité pointe le sommet u.
6. (u) =le degré entrant du sommet u de V, c'est-à-dire la somme des poids des arcs vers le sommet u.
7. =le degré sortant du sommet u de V, c'est-à-dire la somme des poids des arcs depuis le sommet u
8. la matrice d'adjacence telle que

A (u, v) =                                                                (1.5)

• Dans le cas d'un graphe non pondéré, W ≡ A.

1.7 Notion les communautés statique

Soit

• M = {}  une collection de sous-graphes de V telle que est une communauté de G. Dans le cas de communautés disjointes,  pour tout, alors que dans le cas de communautés avec recouvrement l'ensemble  peut-être non vide pour . Dans les deux cas, un sommet peut être non-affilié, c'est-à-dire m u G mais.
• =  le cardinal de l'ensemble c'est-à-dire le nombre de communautés du graphe.
• =  le cardinal de l’ensemble, c'est-à-dire le nombre des sommets du sous-graphe.
• L’ensemble des voisins du sommet   dans, c'est-à-dire l'ensemble des nœuds v €  tels que (u, v).
• Com(u) un vecteur d'étiquettes du sommet u, c'est-à-dire l'affiliation de u à une ou plusieurs communautés.
• Le degré interne du nœud u dans la communauté, c'est-à-dire la somme des poids des arêtes (u, v) de E telles que u, v

• Le degré externe du nœud u dans la communauté, c'est-à-dire la somme des poids des arêtes (u, v) de E telles que u, v

1.8 Méthodologie

Le problème de l'identification des données fait partie des étapes les plus complexes auxquelles la plupart des chercheurs sont confrontés en raison de la difficulté et de la taille, Le secteur privé majeur dans l'étude détection de communauté, qui est une question qui doit choisir les aspects des réseaux dynamiques présents dans les réseaux évolutifs, des solutions proposées sont tout aussi diverses qu'il existe de variantes au problème, nous n'aspirons aucunement à généraliser l'étude des communautés dynamiques, mais bien à confronter un jeu de données réelles à l'état de l'art.

• La première section décrit les caractéristiques d'un réseau traité
• La seconde section propose des modélisations d'un jeu de données réelles satisfaisante les contraintes et les caractéristiques imposées selon les multiples stratégies de détection de communautés (statique ou dynamique) et réseau évolutifs.
• Troisième sections propose les méthodes évolutives et benchmarks pour comparer les algorithmes choisie (Louvain et Girvan Newman).

La section algorithmes contient deux parties distinctes expliquant les propriétés et les conditions qui doivent exister pour les appliquer à un graphe (non orientée).

1.9 Propriétés du réseau évolutif

Dans la partie, nous aborderons les caractéristiques des types de données auxquels nous pouvons appliquer des algorithmes qui dépendent fortement du réseau ou un ensemble des individus et les problèmes auxquels nous pouvons faire face lors de l'application pratique.

1.9.1 Réseau social

Les graphes sont à la fois une structure de donnée informatique et un outil mathématique abstrait avec de nombreuses applications par exemple chimie ( chemoinformatique ) et biochimie ( génomique ), génie électrique et théorie des codes, réseaux informatiques, urbains, sociaux ( Internet, Google, Facebook ), Chaque type de réseau, qu'il soit biologique, neural, social, d'information, etc., présente une structure propre, que ce soit en rapport à la distribution des degrés des nœuds de son graphe.

1.9.2 Réseau temporel

C'est un réseau qui contient et se caractérise par son changement temporel qui est évolutif en termes de composants d'individus dans le temps car il change simultanément par rapport à la base de données utilisée qui est destructible.

1.9.3 Réseau hors-ligne

Un jeu de données hors-ligne suppose que toute l'information est disponible avant de modéliser le réseau, c'est-à-dire qu'il s'agit de valeurs historiques connues (Modèle de données karateclub, Barbell ).

1.9.4 Interactions pondérées

Qu’entretiennent des individus ne sont pas toujours de nature unique. Ainsi, modéliser les liens de façon binaire entre les sommets d'un graphe pourrait masquer une part de l'information sur la force de la relation entre ces individus. Il est alors raisonnable de penser qu'un poids pour chacun des liens peut exprimer la nature de la liaison. Par exemple, ce poids peut représenter la durée ou la répétition de l'interaction [2]

1.10 Modélisations d’un réseau social hors ligne sous forme un document TXT ou YML

Figure 4 – l’opération de capturer et traduire sous forme YML ou TXT

Nous proposons deux modèles sous forme ( TXT ou YML ) à l’aide les modèle hors ligne de networks X bibliothèque suivant

1. Karate club modèle le club de karaté se compose de méthodes de pointe pour faire un apprentissage non supervisé sur des données structurées en graphes, il d´écrite les relations d’amitiés entre 34 membres d’un club de Karaté observées lors de la gestion d’un conflit durable entre l’entraîneur et l’administrateur du club , on a 34 sommets.
2. Barbell modèle le plus couramment utilisé est un graphe à n haltères qui est un graphe simple obtenu en connectant deux copies d'un graphe complet avec n nœuds, dans notre application nous avons choisie n=5.

1.11 L’étude de l’existence

L'analyse de la société à travers des applications et des algorithmes spécifiques est quelque chose qui doit être exploité pour extraire des résultats efficaces et valorisants car Internet contient beaucoup de code source, mais il souffre de nombreux inconvénients et lacunes qui le rendent incompréhensible par les utilisateurs car la plupart des applications ne contiennent pas d'outils de protection.

• L'absence d'une fonctionnalité qui contribue à organiser les algorithmes en termes d'efficacité.
• L'absence de la fonctionnalité de saisie des informations de manière fluide qui contribue à gagner du temps et à obtenir un résultat précis.
• L’absence benchmarks avec F1 score (MIN, MAX, MOYENNE).
• L’absence de fonctionnalité de l’impression pour mieux comprendre les informations et les détails dans le system (nombre inter communauté)
• L’absence l’organisation les utilisateurs principales de l’application pour organisée les acteurs dans le système.
• L’absence la politique de la sécurité par exemple le chiffrement et droit accès dans le système.
• L’absence l’outil pour créer les modèles des données ou modifiée les paramètres respectivement le type des modèles choisie.

1.12 Conclusion

Dans ce chapitre nous avons conclure que la détection de communautés dans les réseaux sociaux s’appuie sur des algorithmes ou des méthodes issus de domaines de recherche ayant évolué de manière relativement indépendante : la classification automatique à l’aide les modèles de données et la théorie des graphes.

Télécharger fichier complete