Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Application de la théorie des graphes à l’analyse des réseau

No description
by

fadoua jouili

on 10 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Application de la théorie des graphes à l’analyse des réseau

Introduction
Problématique
Intérêt de l’analyse des réseaux sociaux
Pour la compréhension des phénomènes sociaux

Besoin de données adaptées à l’extraction des liens sociaux pertinents

Besoin de méthodes efficientes pour modéliser et analyser ces réseaux

Besoin de modèles efficaces

Application de la théorie des graphes à l’analyse des réseaux sociaux
Fadoua JOUILI
Faraha HAMROUNI
Wassila JERBI

Modélisation d'un réseau social
Analyse du réseau social
Datamining des réseaux
Un réseau social
=
(
Individus /organisations
)

I
nteractions sociales régulières
Pourquoi analyser un réseau social
Comment le faire avec la théorie des graphes
L'analyse des réseaux sociaux
: Étude basée sur plusieurs théories dont
la théorie des graphes
1930 [Moreno]
1956 [Cartwright et Harary]
Sociogramme
Graphe
un sociogramme
Un
schéma
: des
lignes
qui relient un ensemble de
points
.
Visualiser
graphiquement
un réseau social
un graphe
Outil de modélisation
:
Noeuds: les entités sociales
Arrêtes : les interactions sociales
Outil d'analyse
:
la théorie de graphe est un outil mathématique puissant.
le trou structural
Mesure l'
importance
d'un noeud dans un graphe
Les approches de centralité de:
Degré
Intermédiarité
Prestige
Proximité
Le trou structural
Centralité de degré
Centralité d'intermédiarité
La
capacité
d'un nœud à servir d'
intermédiaire
.

Le
nombre de fois
où un nœud se trouve
sur les chemins
de toutes les autres
paires de nœuds
.



Centralité de prestige
 PD(i) = DE(i)/ (n-1)
Centralité de proximité
La capacité d'un noeud à
se connecter rapidement
avec les autres.

la capacité d'un noeud à
atteindre
un autre ou à
être atteint
par un autre.


Étudier
des
relations
entre les
acteurs
et les
réseaux
constitués par l’
agrégation
de ces relations.
Deux
méthodes
:
Des
indicateurs
Datamining
des réseaux
S’intéresse aux taches du
Datamining
pour l'
extraction de connaissances
:

Classification
Recherche de motifs fréquents
Clustering

Classification
Recherche des motifs fréquents
CD(i) = D(i)/ (n-1)
D(i): le nombre d’arrêtes d’un nœud i .
n-1: le degré maximal d’un nœud.
Les centraux d’un graphe:

Les
degré
les
plus élevés
.

Un potentiel élevé à
faire circuler l'information .

Plus un nœud est intermédiaire, plus il a de pouvoir.
Exemple
'2' situé sur l'unique chemin reliant '1' et '3' Possède un fort contrôle sur la communication de ces noeuds.
DE(i): le nombre d’arrêtes entrantes d’un nœud i
n-1: le degré maximal d’un nœud.
Un noeud connecté aux noeuds à fort degré possède une centralité de prestige importante
Séparation entre deux contacts non redondants.

Accès rapide à des informations non redondantes.

canaux de circulation de ces informations.

Conclusion
Indicateurs
Indicateurs

Locales: Caractérisent localement un noeud ou un groupe de noeuds

Globales: Apportent une information sur l’ensemble de la structure
Densité


0 si tous les points sont isolés
D
1 si chaque sommet est connecté à tous les autres

v: le nombre de liens dans le graphe.
n: le nombre de nœuds.



{
D = v/ [n(n-1)/2]
Centralité
Décrire la connectivité à l’intérieur du graphe.

Définir la cohésion d'un réseau social.

Mesurer la performance de la communication dans ce réseau
le trou structural
Mesure l'importance d'un noeud dans un graphe
Les approches de centralité de:
degré
intermédiarité
prestige
proximité
le trou structural
Centralité de degré
Centralité d'intermédiarité
La
capacité
d'un nœud à servir d'
intermédiaire
.

Le
nombre de fois
où un nœud se trouve
sur les chemins
de toutes les autres
paires de nœuds
.



Centralité de prestige
 PD(i) = DE(i)/ (n-1)
Centralité de proximité
La capacité d'un noeud à
se connecter rapidement
avec les autres.

la capacité d'un noeud à
atteindre
un autre ou à
être atteint
par un autre.

CD(i) = D(i)/ (n-1)
D(i): le nombre d’arrêtes d’un nœud i .
n-1: le degré maximal d’un nœud.
Les centraux d’un graphe:

Les
degré
les
plus élevés
.

Un potentiel élevé à
faire circuler l'information .

Plus un nœud est intermédiaire, plus il a de pouvoir.
Exemple
'2' situé sur l'unique chemin reliant '1' et '3' Possède un fort contrôle sur la communication de ces noeuds.
DE(i): le nombre d’arrêtes entrantes d’un nœud i
n-1: le degré maximal d’un nœud.
Un noeud connecté aux noeuds à fort degré possède une centralité de prestige importante
Séparation entre deux contacts non redondants.

Accès rapide à des informations non redondantes.

canaux de circulation de ces informations.

Centralité
Densité
Global: Apporte une information sur l
la structure
Local: Caractérise
un noeud
ou
un groupe de noeuds
{
Clustering
Identifier les communautés:

Déterminer la répartition des acteurs et des activités

Coefficient du Clustering
Algorithmes
Evaluer le niveau de transitivité local ou global d’un graphe. 
 Ci = 3 Triades/ Triplets
Triades: le nombre de triade (cycle de 3 sommets)
Triplets: le nombre maximal de triade possible.
La probabilité pour un noeud v que ses deux voisins v1
et v2 soient également voisins entre eux.
Utilisés pour détecter les communautés
Algorithmes du Clustering héarchique
Algorithmes à base des heuristiques
Heuristiques liées à la structure en communauté
Affecte un poids par paire de sommets et leurs arêtes.

Construit un arbre dont les nœuds sont des groupes de sommets plus ou moins proches
Les algorithmes séparatifs
Construction de l'arbre: Manière inverse.

Le poids d'une arête = Son caractère séparatif entre ses extrémités.

Retrait itératif des arêtes par poids décroissant.

Exemple
: L’algorithme de
Girvan and Newman 2002:

Calcul des centralités d'intermédiarité couteux en temps

O(m².n): m = le nombre d'arêtes et n = le nombre de sommets.
Algorithmes agglomératifs
Affecte des
poids
aux arrêtes:

Nombre de chemins passant par ces noeuds.

Chemins : Pas des noeuds et des arrêtes en commun .

Sommets: triés par ordre décroissant du poids

Exemple
: L'algorithme
netwalk :Zhou et Lipowsky 2004

Basé sur
le temps moyen d'atteinte d'un sommet


O(n3)


Nœuds les plus profonds
=
Groupes de sommets les plus proches.

Remonter dans l'arbre Grandes communautés.
Des labels initiaux aux noeuds : les communautés
A chaque étape: le nœud change
son labe
l par le
plus réparti
dans
son voisinage
.
Un
label unique
pour chaque
communauté
.
Terminaison
non déterministe
Exemple
: algorithme
par propagation de label

(Raghvan et al 2007)
Affecter une
classe
à chaque noeud du réseau
Rechercher les
sous-graphes fréquents
dans les réseaux
La théorie des graphe en analyse des réseaux sociaux :



Grande contribution dans la modélisation, l'analyse et l'extraction des connaissances.

Full transcript