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

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