Informations

Date limite Pas de date limite
Limite de soumission Pas de limite

Se connecter

EXAMEN_Facile_Modularite

La matrice de modularité Q, que vous allez devoir calculer, est une matrice symétrique très utilisée dans l’analyse de réseaux ou graphes, par exemple les réseaux sociaux. Elle se calcule à partir de la matrice n x n d’adjacence du réseau, A, qui contient les interactions / relations entre paires d’individus pris deux à deux (n individus au total). Par exemple, pour le réseau Facebook, l’élément \([A]_{ij} = a_{ij}\) de la matrice d’adjacence A contient +1 si l’individu numéro i est ami avec j et 0 sinon (ils sont en relation d’amitié ou pas).

Dans d’autres réseaux sociaux, cette matrice d’adjacence pourrait, par exemple, contenir le nombre de fois (fréquence) que la personne i est allée au cinéma en compagnie de le personne j durant l’année, ou toute autre forme d’interaction / relation entre paires d’individus. Donc, dans ce cas, plus la valeur \(a_{ij}\) est élevée, plus les deux personnes sont considérées comme « proches », socialement parlant, car elles interagissent beaucoup. Pour cette question d’examen, nous supposerons que la matrice d’adjacence, qui est connue, est carrée, symétrique, à diagonale nulle (pas d’auto-interaction), et contient uniquement des valeurs entières non-négatives.

La matrice de modularité Q se calcule à partir de la matrice d’adjacence et contient la fréquence d’interaction entre deux individus moins la fréquence attendue si les interactions se faisaient « au hasard » (elle ressemble donc au Chi-carré). Mais ce qui nous importe ici, c’est la forme de cette matrice : l’élément \([Q]_{ij} = q_{ij}\) de la matrice de modularité s’obtient à partir de la matrice d’adjacence à l’aide de la formule

\(q_{ij}=a_{ij}-\frac{d_id_j}{a_{**}}\)

où les \(d_i\) sont les « degrés » des individus, à savoir \(d_i\) est la fréquence totale d’interactions de l’individu i avec tous les autres individus. Celui-ci se calcule par \(d_i=a_{i*}=\sum^{n}_{j=1}a_{ij}\) et \(d_j=a_{*j}=\sum^{n}_{i=1}a_{ij}\) où le point (*) signifie donc la sommation sur l'indice correspondant. Par ailleurs, \(a_{**}=\sum^{n}_{i=1}\sum^{n}_{j=1}a_{ij}\). Dans le code, vous devez donc calculer le vecteur de degrés d et ensuite la matrice de modularité Q par la formule ci-dessus.

Exemple : Prenons un petit exemple. Voici une matrice d’adjacence d’un mini-réseau comprenant seulement trois personnes, et sa matrice de modularité correspondante. On a par exemple observé 2 interactions entre les individus 1 et 3.

Septembre_2020_Modularite/modularite.PNG

et le vecteur de degrés est \(d = [3, 4, 5]^T\).

Nous vous demandons donc de calculer cette matrice de modularité Q à partir de la matrice d’adjacence A en python dans la fonction calculModularite. Ce code doit pouvoir gérer toute matrice d’adjacence carrée de taille n x n, symétrique, et contenant uniquement des valeurs non-négatives. Vous ne devez pas vérifier ces propriétés ; elle sont supposées avoir été vérifiées auparavant.

N’hésitez pas à écrire une fonction intermédiaire qui calcule les degrés des individus d et que vous utiliserez dans calculModularite.

Signature de la fonction : def calculModularite(A)


Implémentation

Implémentez la fonction def calculModularite(A) en Python et les fonctions intermédiaires si vous en utilisez.