Aller au contenu

Utilisateur:Manel411195/Modélisation des Réseaux (M1, 2018)/Activité E

Une page de Wikiversité, la communauté pédagogique libre.

Pour le graphe de la slide 25 du diapo 3 :

1)     Calculer la centralité de vecteur propre des noeuds

Matrice d’adjacence du graphe :

A =

a b c d e f g h
a 0 1 1 1 0 0 0 0
b 0 0 1 0 1 0 0 0
c 0 0 0 0 0 0 1 1
d 0 0 1 0 0 1 0 0
e 1 0 0 0 0 0 0 0
f 1 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 1
h 0 0 0 0 0 0 1 0

Matrice représentant le système linéaire :

M =

a b c d e f g h
a 0 1/3 1/3 1/3 0 0 0 0
b 0 0 1/2 0 1/2 0 0 0
c 0 0 0 0 0 0 1/2 1/2
d 0 0 1/2 0 0 1/2 0 0
e 1 0 0 0 0 0 0 0
f 1 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 1
h 0 0 0 0 0 0 1 0

Matrice transposée :

MT =

a b c d e f g h
a 0 0 0 0 1 1 0 0
b 1/3 0 0 0 0 0 0 0
c 1/3 1/2 0 1/2 0 0 0 0
d 1/3 0 0 0 0 0 0 0
e 0 1/2 0 0 0 0 0 0
f 0 0 0 1/2 0 0 0 0
g 0 0 1/2 0 0 0 0 1
h 0 0 1/2 0 0 0 1 0

On ne connait pas l'état initial donc on suppose que :

p(a) = p(b) = … = p(h) = 1/8

-> d’où la matrice P =

a
p(a) 1/8
p(b) 1/8
p(c) 1/8
p(d) 1/8
p(e) 1/8
p(f) 1/8
p(g) 1/8
p(h) 1/8

=> Matrice MT X P =

a b c d e f g h
a 0 0 0 0 1/8 1/8 0 0
b 1/24 0 0 0 0 0 0 0
c 1/24 1/16 0 1/16 0 0 0 0
d 1/24 0 0 0 0 0 0 0
e 0 1/16 0 0 0 0 0 0
f 0 0 0 1/16 0 0 0 0
g 0 0 1/16 0 0 0 0 1/8
h 0 0 1/16 0 0 0 1/8 0

Pour trouver la centralité, on résout l'équation pour trouver les p(n*) tels que P = MT X P

p(a)=1/8p(e)+1/8p(f)

p(b)=1/24p(a)

p(c)=1/24p(a)+1/16p(b)+1/16p(d)

p(d)=1/24p(a)

p(e)=1/16p(b)

p(f)=1/16p(d)

p(g)=1/16p(c)+1/8p(h)

p(h)=1/16p(c)+1/8p(g)

Et p(a)+p(b)+p(c)+p(d)+p(e)+p(f)+p(g)+p(h)=1, donc :

p(a)= 0.9

p(b)= 0.03

p(c)= 0.04

p(d)= 0.03

p(e)= 0.002

p(f)= 0.002

p(g)= 0.003

p(h)= 0.003

2)     Expliquer le résultat en fonction des rapports entre les composantes fortement connexes du graphe.

Il y a 2 groupes de composantes fortement connexes : (e, b, a, d, f), et (g, h).

3)     Comment pourrait-on procéder pour éviter ce problème ?

Pour le graphe de la slide 18 du diapo 3 :

1)     Calculer la proximité des nœuds

Nœud i 1 2 3 4 Somme cp(i) = Somme^(-1)
1 0 2 1 1 4 1/4
2 1 0 2 1 4 1/4
3 2 1 0 1 4 1/4
4 2 1 3 0 6 1/6

2)     Calculer l'intermédiarité des nœuds

Nœud i Paires des autres nœuds j,k Nombre des chemins les plus courts entre j et k Nombre de ces chemins qui passent par i Fraction g(i)
1 2,3

2,4

3,2

3,4

4,2

4,3

1

1

1

1

1

1

1

0

0

0

0

1

1/1

1/1

1+1 = 2
2 1,3

1,4

3,1

3,4

4,1

4,3

1

1

1

1

1

1

0

0

1

0

1

1

1/1

1/1

1/1

1+1+1=3
3 1,2

1,4

2,1

2,4

4,1

4,2

1

1

1

1

1

1

0

0

0

0

0

0

0
4 1,2

1,3

2,1

2,3

3,1

3,2

1

1

1

1

1

1

1

0

0

0

0

0

1/1 1

3)     Faire le tableau de corrélation combiné mettant en relation ces deux mesures

Nœud i Proximité Intermédiarité
1 1/4 2
2 1/4 3
3 1/4 0
4 1/6 1

4)     Dessiner le graphique pour la corrélation combiné de ces deux mesures

Cf feuille